Skip to main content

Foregger’s nearly decomposable minimum

← Minc’s list

Minc’s list · Conjecture 15

Foregger’s nearly decomposable minimum

Proved by us Preprint, November 2026

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}\).

Resolution

We proved the conjecture in every order, equality clause included: every nearly decomposable \(A\in\Omega_n\) satisfies \(\operatorname{per}A\ge 2^{1-n}\), with equality only when \(A\) is \(\tfrac12(I_n+P_n)\) up to permutations of rows and columns. Moreover, on the face of \(\Omega_n\) given by any nearly decomposable pattern other than a single cycle, the minimum permanent is strictly larger than \(2^{1-n}\).

The proof is by induction on \(n\). Whenever a row or column with exactly two nonzero entries can be contracted so that the pattern stays nearly decomposable, Foregger’s contraction identity reduces the order. The patterns with no such contraction are expansions of fully indecomposable cores in which every row and column has at least three occurrences. For these, a normalized matching-entropy gap is positive, and since minimizers on nearly decomposable faces are interior, this gives a strict bound. A core without a nontrivial tight cut is handled with Gurvits’s degree-sensitive capacity inequality on a shortened star. Otherwise a minimum tight cut splits off a leaf, which supplies the gap, and a smaller remainder, which is covered by induction.

Read our paper →

Earlier 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.

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