Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality \begin{equation} \label{le} per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n \end{equation} We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\ For all pairs of $n \times n$ matrices $(P,Q)$, where $P$ is nonnegative and $Q$ is doubly-stochastic \begin{equation} \label{st} \log(per(P)) \geq \sum_{1 \leq i,j \leq n} \log(1- Q(i,j)) (1- Q(i,j)) - \sum_{1 \leq i,j \leq n} Q(i,j) \log(\frac{Q(i,j)}{P(i,j)}) \end{equation} The main corrollary of (\ref{st}) is the following inequality for doubly-stochastic matrices: $$ \frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} \left(1- A(i,j)\right)^{1- A(i,j)}. $$ We present explicit doubly-stochastic $n \times n$ matrices $A$ with the ratio $\frac{per(A)}{F(A)} = \sqrt{2}^{n}$ and conjecture that $$ \max_{A \in \Omega_n}\frac{per(A)}{F(A)} \approx \left(\sqrt{2} \right)^{n}. $$ If true, it would imply a deterministic poly-time algorithm to approximate the permanent of $n \times n$ nonnegative matrices within the relative factor $\left(\sqrt{2} \right)^{n}$.
Article
View Unharnessing the power of Schrijver's permanental inequality