Characterizing cohesive matrices

← Minc’s list

Minc’s list · Problem 14

Characterizing cohesive matrices

Open

Posed by
Brualdi
First posed
1985

Statement

Posed by R. A. Brualdi in 1985, in a paper on a face of the polytope of doubly stochastic matrices; it is Problem 14 in Minc’s 1987 survey, alongside Problems 15 and 16.

Problem 14. Characterize cohesive 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. Brualdi called \(A\) cohesive if the minimum of the permanent on \(\Omega(A)\) is attained at a matrix in the interior of the face, that is, one that is positive wherever \(A\) is. Every barycentric matrix, one for which the average of the permutation matrices below \(A\) is a minimizer (Problem 15), is cohesive, but not conversely.

Prior progress

  • Hwang (1985) showed that staircase supports are barycentric, hence cohesive. Song (1988) gave cohesive examples, some barycentric and some not, and a family of noncohesive ones.
  • Brualdi suggested \(C_n=J_n-I_n+E_{11}\), the all-ones matrix with its diagonal removed except the first entry, as a cohesive matrix that is not barycentric. Song (1995) proved \(C_n\) is never barycentric, and Hong, Jun, Kim and Song (1996) proved that \(C_4\) is cohesive; the question is open for \(n\ge5\).
  • Fischer and Hwang (1996) found infinite families of cohesive, non-barycentric matrices. Pula, Song and Wanless (2011), Song (2013) and Cheon and Song (2024) decided cohesiveness for large parts of the families \(\bigl[\begin{smallmatrix}I_n&J\\J&J_m\end{smallmatrix}\bigr]\).

Our progress so far

  • Reduction to irreducible cores. A matrix is cohesive exactly when each fully indecomposable block of its active support is, and cohesiveness is unchanged by the “expansions” of Hwang and Shin. So the problem reduces to fully indecomposable supports that are not expansions of smaller ones.
  • Order three, completely. Among the \(3\times3\) supports, every fully indecomposable one is cohesive except \(C_3\), whose unique minimizer \(\tfrac12(J_3-I_3)\) lies on the boundary. So Brualdi’s family starts noncohesive at \(n=3\) and becomes cohesive at \(n=4\).
  • Cohesiveness is fragile. The \(8\times8\) support \(D_8\) from our counterexample to Conjecture 41 is cohesive but not barycentric: its unique minimizer is interior and irrational. Adding the single position \((1,5)\) gives a support that is not cohesive, since the minimizer stays the same and vanishes there.
  • Interior minimizers are rarely positive semidefinite. If a fully indecomposable support \(D\ne J_n\) has ones on the diagonal, no minimizer in the interior of \(\Omega(D)\) is a positive semidefinite matrix.
  • Towards \(C_5\). We found an exact interior critical point of the permanent on \(\Omega(C_5)\) with permanent \(11^4/588^2\), below the permanent of the barycenter.

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. H. Minc, Theory of permanents 1982–1985, Linear and Multilinear Algebra 21 (1987), 109–148. doi:10.1080/03081088708817786
  3. S.-Z. Song, Minimum permanents on certain faces of matrices containing an identity submatrix, Linear Algebra Appl. 108 (1988), 263–280. doi:10.1016/0024-3795(88)90192-9
  4. S.-Z. Song, A conjecture on permanents, Linear Algebra Appl. 222 (1995), 91–95. doi:10.1016/0024-3795(93)00286-9
  5. S.-M. Hong, Y.-B. Jun, S.-J. Kim and S.-Z. Song, A cohesive matrix in a conjecture on permanents, Bull. Korean Math. Soc. 33 (1996), 127–133.
  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