Characterizing barycentric matrices

← Minc’s list

Minc’s list · Problem 15

Characterizing barycentric matrices

Open

Posed by
Brualdi
First posed
1985

Statement

Posed by R. A. Brualdi in 1985, in the same paper as Problem 14; it is Problem 15 in Minc’s 1987 survey.

Problem 15. Characterize barycentric matrices.

For an \(n\times n\) \((0,1)\)-matrix \(A\) with \(\operatorname{per}A>0\), let \(\Omega(A)\) be the face of the doubly stochastic matrices that vanish wherever \(A\) does. Its barycenter is the average \(b(A)=\frac1{\operatorname{per}A}\sum_{P\le A}P\) of the permutation matrices \(P\) below \(A\), and \(A\) is barycentric if \(b(A)\) minimizes the permanent on \(\Omega(A)\). Barycentric matrices are cohesive (Problem 14), but not conversely.

Prior progress

  • Hwang (1985) proved that staircase supports are barycentric, and Hwang and Shin (1997) that barycentricity is preserved by certain expansions; Hwang and Pyo (1999) added the Ferrers supports.
  • Do and Hwang (1991) showed that a barycentric face has a rational minimum permanent, so faces with irrational minima are not barycentric. Minc (1994) proved that faces with two or three prescribed zeros on the diagonal are not barycentric.
  • Song (1995) proved that \(C_n=J_n-I_n+E_{11}\) is not barycentric, and Fischer and Hwang (1996) found cohesive, non-barycentric families. Pula, Song and Wanless (2011) and Cheon and Song (2024) studied the families \(\bigl[\begin{smallmatrix}I_n&J\\J&0\end{smallmatrix}\bigr]\) and \(\bigl[\begin{smallmatrix}I_n&J\\J&J_m\end{smallmatrix}\bigr]\).

Our progress so far

  • Simplex faces, completely. When \(\Omega(A)\) is a simplex, which happens exactly when every perfect matching of \(A\) uses a position no other one uses, \(A\) is barycentric if and only if the products of the matching counts \(\operatorname{per}A(i\mid j)\) along its perfect matchings are all equal. On such faces the minimizers form a convex set.
  • New infinite non-barycentric families. For all \(m,n\ge2\), the matrix \(V_{m,n}=\bigl[\begin{smallmatrix}I_n&J\\J&J_m\end{smallmatrix}\bigr]\) is not barycentric; with Pula, Song and Wanless’s cohesiveness theorem this proves the “cohesive but not barycentric” half of their conjecture. For every \(n\ge5\), the cyclic support \(I_n+P_n+P_n^2\) is not barycentric.
  • An exact finite test. For fully indecomposable \(A\), the barycenter is a critical point of the permanent, a necessary condition, if and only if the matching counts \(\operatorname{per}A(i\mid j)\) factor as \(a_ic_j\). This condition can be decided with finitely many exact comparisons.
  • Positive classes. Every fully indecomposable support of real rank at most \(2\) is barycentric, and so is every support whose bipartite graph has maximum degree at most \(2\).
  • Unique minimizer, not barycentric. The support \(D_8\) from our counterexample to Conjecture 41 has a unique interior minimizer, but its barycenter has larger permanent, so cohesive does not imply barycentric even with a unique minimizer.

References

  1. R. A. Brualdi, An interesting face of the polytope of doubly stochastic matrices, Linear and Multilinear Algebra 17 (1985), 5–18. doi:10.1080/03081088508817637
  2. S.-G. Hwang, Minimum permanent on faces of staircase type of the polytope of doubly stochastic matrices, Linear and Multilinear Algebra 18 (1985), 271–306. doi:10.1080/03081088508817694
  3. S.-S. Do and S.-G. Hwang, Some rationally looking faces of Ωₙ having irrational minimum permanents, Linear and Multilinear Algebra 30 (1991), 145–154. doi:10.1080/03081089108818097
  4. 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
  5. S.-Z. Song, A conjecture on permanents, Linear Algebra Appl. 222 (1995), 91–95. doi:10.1016/0024-3795(93)00286-9
  6. I. Fischer and S.-G. Hwang, Certain nonbarycentric cohesive matrices, Linear Algebra Appl. 239 (1996), 185–200. doi:10.1016/S0024-3795(96)90011-7
  7. S.-G. Hwang and S.-J. Shin, A face of the polytope of doubly stochastic matrices associated with certain matrix expansions, Linear Algebra Appl. 253 (1997), 125–140. doi:10.1016/0024-3795(95)00780-6
  8. K. Pula, S.-Z. Song and I. M. Wanless, Minimum permanents on two faces of the polytope of doubly stochastic matrices, Linear Algebra Appl. 434 (2011), 232–238. doi:10.1016/j.laa.2010.08.015
  9. G.-S. Cheon and S.-Z. Song, A conjecture on minimum permanents, Czechoslovak Math. J. 74 (2024), 273–282. doi:10.21136/CMJ.2023.0186-23