Lih–Wang convexity inequality

← Minc’s list

Minc’s list · Conjecture 34

Lih–Wang convexity inequality

Open

Posed by
Lih and Wang
First posed
1982

Statement

Posed by K.-W. Lih and E. T. H. Wang in 1982; it is Conjecture 34 in Minc’s 1987 survey.

Conjecture 34. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices and \(J_n\) the matrix with every entry \(1/n\). If \(A\in\Omega_n\) and \(\tfrac12\le\alpha\le1\), then

\[ \operatorname{per}\bigl(\alpha J_n+(1-\alpha)A\bigr)\ \le\ \alpha\operatorname{per}J_n+(1-\alpha)\operatorname{per}A. \]

On the half of the segment from \(A\) to \(J_n\) nearer \(J_n\), the permanent lies on or below its chord. The restriction \(\alpha\ge\tfrac12\) cannot be dropped: for \(n=3\) and \(A=\tfrac12(I_3+C_3)\), with \(C_3\) a cyclic permutation matrix, the inequality fails for every \(0<\alpha<\tfrac12\).

Prior progress

  • Lih and Wang (1982) proved the case \(n=3\).
  • Foregger (1988) proved the case \(n=4\) for \(0.6217\ldots\le\alpha\le1\).
  • Kopotun (1996) proved the inequality, for all \(\alpha\in[0,1]\), for normal \(A\in\Omega_n\) whose eigenvalues lie in the sector \(\lvert\arg z\rvert\le\pi/(2n)\).
  • Udayan and Somasundaram (2024) proved an order-six result under root-free hypotheses on certain subpermanent polynomials.

Our progress so far

  • Order four, completely. For every \(A\in\Omega_4\) and every \(\alpha\in[\tfrac12,1]\) the inequality holds. At the midpoint \(\alpha=\tfrac12\) we proved the stronger bound \[ \operatorname{per}\Bigl(\frac{J_4+A}{2}\Bigr)\le\frac{\operatorname{per}J_4+\operatorname{per}A}{2}-\frac{\lVert A-J_4\rVert_F^2}{512}. \]
  • Order five, sparse mixtures. Every convex combination of at most four \(5\times5\) permutation matrices satisfies the inequality for all \(\alpha\in[\tfrac12,1]\).
  • Where a counterexample could live. For \(n\ge5\) and fixed \(\alpha\), if the inequality fails anywhere, then a worst violation occurs at a matrix with at least three zero entries; there is no violation with all entries positive.
  • Large blow-ups. For every fixed \(B\in\Omega_n\), the blow-up \(B\otimes J_q\) satisfies the inequality for all sufficiently large \(q\).

References

  1. K.-W. Lih and E. T. H. Wang, A convexity inequality on the permanent of doubly stochastic matrices, Congr. Numer. 36 (1982), 189–198.
  2. H. Minc, Theory of permanents 1982–1985, Linear and Multilinear Algebra 21 (1987), 109–148. doi:10.1080/03081088708817786
  3. T. H. Foregger, Permanents of convex combinations of doubly stochastic matrices, Linear and Multilinear Algebra 23 (1988), 79–90. doi:10.1080/03081088808817858
  4. K. A. Kopotun, A note on the convexity of the sum of subpermanents, Linear Algebra Appl. 245 (1996), 157–169. doi:10.1016/0024-3795(94)00228-2
  5. D. K. Udayan and K. Somasundaram, Lih Wang’s and Dittert’s conjectures on permanents, Spec. Matrices 12 (2024), 20240006. doi:10.1515/spma-2024-0006