Foregger’s nearly decomposable minimum

← Minc’s list

Minc’s list · Conjecture 15

Foregger’s nearly decomposable minimum

Open

Posed by
Foregger
First posed
1978

Statement

Posed by T. H. Foregger; it appears as Conjecture 15 in Minc’s 1978 book, and Foregger’s 1980 paper proved the bound in small orders.

Conjecture 15. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices. If \(A\in\Omega_n\) is nearly decomposable, then

\[ \operatorname{per}A\ \ge\ \frac{1}{2^{\,n-1}}, \]

with equality if and only if \(A=\tfrac12(I_n+P_n)\) up to permutations of rows and columns, where \(P_n\) is the permutation matrix of the cycle \((1\,2\,\cdots\,n)\).

A matrix is partly decomposable if it has an \(s\times(n-s)\) zero submatrix for some \(1\le s\le n-1\), and fully indecomposable otherwise. It is nearly decomposable if it is fully indecomposable but replacing any one positive entry by \(0\) makes it partly decomposable. The bound is attained: \(\tfrac12(I_n+P_n)\) has exactly two nonzero diagonals, so its permanent is \(2\cdot 2^{-n}\).

Prior progress

  • Foregger (1980) proved the bound \(\operatorname{per}A\ge 2^{1-n}\) for all \(2\le n\le 9\), by contracting a row or column with exactly two nonzero entries. His method does not start on certain patterns, such as the one obtained from \(K_{3,3}\) by replacing every edge with a path of length three. The equality clause was not proved.
  • Foregger (1987) found the exact minimum on faces of the Birkhoff polytope given by odd complexes, two vertices joined by internally disjoint paths of odd length, which satisfy the bound.
  • Cheon and Wanless (2005) reported no further progress.

Our progress so far

  • Foregger’s obstruction family, in every order. Take any bipartite graph with all degrees at least \(3\) and replace every edge by a path of length three. Every doubly stochastic matrix whose nonzero pattern is the resulting graph satisfies \(\operatorname{per}A>2^{1-n}\). This covers exactly the patterns on which Foregger’s induction cannot start, including the subdivided \(K_{3,3}\) of order \(12\).
  • The equality clause on a large class. If the pattern of a nearly decomposable \(A\in\Omega_n\) can be reduced to a single entry by repeatedly contracting rows or columns with two nonzero entries, then \(\operatorname{per}A\ge2^{1-n}\), with equality only when \(A\) is permutation-equivalent to \(\tfrac12(I_n+P_n)\). This proves the full statement, equality clause included, on an infinite family of patterns well beyond cycles.
  • The shape of a smallest counterexample. A counterexample of least order \(n\) must have \(n\ge10\) and at least \(2n+5\) nonzero entries.
  • Few dense lines. The bound holds whenever at most two columns, or at most two rows, of \(A\) have three or more nonzero entries.

References

  1. T. H. Foregger, On the minimum value of the permanent of a nearly decomposable doubly stochastic matrix, Linear Algebra Appl. 32 (1980), 75–85. doi:10.1016/0024-3795(80)90008-7
  2. T. H. Foregger, Minimum permanents of multiplexes, Linear Algebra Appl. 87 (1987), 197–211. doi:10.1016/0024-3795(87)90167-4
  3. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  4. R. A. Brualdi and B. L. Shader, Minimum permanents on special faces of the polytope of doubly stochastic matrices, Linear Algebra Appl. 201 (1994), 103–111. doi:10.1016/0024-3795(94)90109-0