Gyires’s ratio inequality

← Minc’s list

Minc’s list · Conjecture 20

Gyires’s ratio inequality

Open

Posed by
Gyires
First posed
1978

Statement

Posed by B. Gyires in the proceedings of the 1976 Keszthely colloquium on combinatorics, published in 1978; it is Conjecture 20 in Minc’s 1978 book.

Conjecture 20. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices. For every \(A\in\Omega_n\),

\[ \frac{4\,(\operatorname{per}A)^2}{\operatorname{per}(AA^*)+\operatorname{per}(A^*A)+2\operatorname{per}(A^2)}\ \ge\ \frac{n!}{n^n}, \]

with equality if and only if \(A=J_n\), the matrix with every entry \(1/n\).

At \(J_n\) all four permanents equal \(n!/n^n\). For real \(A\), \(A^*\) is the transpose.

Prior progress

  • Chang (1990) proved the inequality for all \(A\in\Omega_3\), and in every order for matrices whose entries are all at least \((n-2)/(n-1)^2\); this covers \(\Omega_2\). His results do not include the equality clause.
  • Minc (1983, 1987) and Cheon and Wanless (2005) record no other progress, and we found no later publication that advances the conjecture.

Our progress so far

  • The whole boundary of \(\Omega_4\). Every \(A\in\Omega_4\) with a zero entry satisfies the inequality strictly.
  • An explicit ball around \(J_n\). For \(n\ge5\), the inequality holds, strictly unless \(A=J_n\), whenever \(\lVert A-J_n\rVert_F\le 3/(4(n-1))\). In every order it holds strictly on some punctured neighbourhood of \(J_n\).
  • A symmetric one-parameter family, all orders. Every symmetric \(A\in\Omega_n\) that is invariant under permutations of the indices \(2,\dots,n\) satisfies the inequality; for \(n\ge6\) equality holds only at \(J_n\). This includes the whole segment from \((nJ_n-I)/(n-1)\) through \(J_n\) to \(I\).
  • Mixtures of few permutation matrices. The inequality holds for every convex combination of two permutation matrices in every order, and for every combination of at most three \(5\times5\) permutation matrices.

References

  1. B. Gyires, On permanent inequalities, in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. János Bolyai 18, North-Holland, 1978, 471–484.
  2. D. K. Chang, On two permanental conjectures, Linear and Multilinear Algebra 26 (1990), 207–213. doi:10.1080/03081089008817977
  3. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488