Zero-diagonal doubly stochastic minimum

← Minc’s list

Minc’s list · Conjecture 44

Zero-diagonal doubly stochastic minimum

Open

Posed by
Folklore
First posed
1987

Statement

A folklore conjecture, recorded by Minc in 1987 as the last conjecture of his list: “It must have occurred to every researcher in the field.”

Conjecture 44. The permanent on the set of \(n\times n\) doubly stochastic matrices with zero trace attains its minimum uniquely at \(U_n=(J-I)/(n-1)\), the matrix all of whose off-diagonal entries are \(1/(n-1)\).

For nonnegative matrices zero trace means zero diagonal. The conjectured minimum is \(\operatorname{per}U_n=D_n/(n-1)^n\), where \(D_n\) is the number of derangements of \(n\) objects; for example \(11/256\) when \(n=5\).

Prior progress

  • The cases \(n=2,3\) are elementary, and London and Minc (1989) proved the conjecture, with uniqueness, for \(n\le4\).
  • Burghduff (1995) proved that \(U_n\) is a strict local minimum in every order.
  • Minc (1994) studied faces with zeros prescribed on part of the diagonal; Cheon and Wanless (2005) reported no progress on the conjecture itself.

Our progress so far

  • Counterexamples lie near \(U_n\), in every order. For every \(n\ge3\) and \(1\le k<n\) we proved an explicit lower bound for \(\operatorname{per}A\) on zero-diagonal doubly stochastic matrices that grows with \(\lVert A-U_n\rVert_F\). It shows that every counterexample satisfies \(\lVert A-U_n\rVert_F^2\le\sqrt{2/n}+O(1/n)\).
  • Order five, a thin shell. Writing \(s=\lVert A-U_5\rVert_F\), the conjecture holds, with a quadratic margin, when \(s\le 9/80\), and whenever \(s^2\ge5/14\). So a counterexample at \(n=5\) would have \(81/6400<s^2<5/14\).
  • Excluded patterns in every order. The conjecture holds when the bipartite graph of the nonzero pattern of \(A\) is disconnected, and when each component’s face of the Birkhoff polytope is a simplex.
  • Exhaustive checks in order five. All \(25{,}834{,}874\) zero-diagonal doubly stochastic \(5\times5\) matrices with entries in \(\frac1q\mathbb Z\) for some \(q\le8\) satisfy the conjecture, with equality only at \(U_5\). This is finite evidence, not a proof of the case \(n=5\).

References

  1. H. Minc, Theory of permanents 1982–1985, Linear and Multilinear Algebra 21 (1987), 109–148. doi:10.1080/03081088708817786
  2. D. London and H. Minc, On the permanent of doubly stochastic matrices with zero diagonal, Linear and Multilinear Algebra 24 (1989), 289–300. doi:10.1080/03081088908817922
  3. H. Minc, Minimum permanents of doubly stochastic matrices with prescribed zero entries on the main diagonal, Linear Algebra Appl. 201 (1994), 135–154. doi:10.1016/0024-3795(94)90111-2
  4. J. B. Burghduff, Minimum permanents of doubly stochastic matrices with zero main diagonal, Linear and Multilinear Algebra 40 (1995), 125–140. doi:10.1080/03081089508818428