Foregger’s Conjecture on Minimum Permanents of Nearly Decomposable Doubly Stochastic Matrices
2026-11-04
Research publication
Foregger’s Conjecture on Minimum Permanents of Nearly Decomposable Doubly Stochastic Matrices
Preprint
- Original date
- Authors
- Yair Lavi
- Combinatorics
- Matrix theory
- Permanents
- Doubly stochastic matrices
Abstract
We prove Foregger’s conjecture: every nearly decomposable doubly stochastic matrix \(A\) of order \(n\ge2\) satisfies
\[ \operatorname{per}A\ge 2^{1-n}. \]
Equality holds exactly for matrices obtained from \(\tfrac12(I_n+P_n)\) by independent row and column permutations, where \(P_n\) is a single-cycle permutation matrix. In fact, for every fixed nearly decomposable support whose bipartite graph is not a single cycle, the minimum permanent on its closed doubly stochastic face is strictly larger than \(2^{1-n}\).