Foregger's Conjecture on Minimum Permanents of Nearly Decomposable Doubly Stochastic Matrices

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.RA — Rings and Algebras

Contributed by Yair Lavi

Version 2 / Nov 07, 2026 / CC BY 4.0

Abstract

We prove Foregger's conjecture: every nearly decomposable doubly stochastic matrix AA of order n≥2n\ge2 satisfies per⁡A≥21−n\operatorname{per}A\ge 2^{1-n}. Equality holds exactly for matrices obtained from 12(In+Pn)\tfrac12(I_n+P_n) by independent row and column permutations, where PnP_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 21−n2^{1-n}.

Author comments: Version 2 adds citations to T. Maciejewski, "Foregger's Permanent Conjecture, Part IV" (Zenodo preprint, 2 June 2026, doi:10.5281/zenodo.20510494), in the introduction, after (3.7) and after Lemma 5.1. The results and proofs are unchanged.

Tools used

OpenAI
GPT (Sol)
OpenAI
GPT (Astra)
Anthropic
Claude Fable

References

  1. R. A. Brualdi and M. B. Hedrick, ``A unified treatment of nearly reducible and nearly decomposable matrices,'' Linear Algebra and its Applications 24 (1979), 51--73. doi:10.1016/0024-3795(79)90146-0 (https://doi.org/10.1016/0024-3795(79)90146-0).DOI
  2. R. A. Brualdi and B. L. Shader, ``Minimum permanents on special faces of the polytope of doubly stochastic matrices,'' Linear Algebra and its Applications 201 (1994), 103--111. doi:10.1016/0024-3795(94)90109-0 (https://doi.org/10.1016/0024-3795(94)90109-0).DOI
  3. G.-S. Cheon and I. M. Wanless, ``An update on Minc's survey of open problems involving permanents,'' Linear Algebra and its Applications 403 (2005), 314--342. doi:10.1016/j.laa.2005.02.030 (https://doi.org/10.1016/j.laa.2005.02.030).DOI
  4. J. Edmonds, L. Lov á sz, and W. R. Pulleyblank, ``Brick decompositions and the matching rank of graphs,'' Combinatorica 2 (1982), 247--274. doi:10.1007/BF02579233 (https://doi.org/10.1007/BF02579233).DOI
  5. T. H. Foregger, ``On the minimum value of the permanent of a nearly decomposable doubly stochastic matrix,'' Linear Algebra and its Applications 32 (1980), 75--85. doi:10.1016/0024-3795(80)90008-7 (https://doi.org/10.1016/0024-3795(80)90008-7).DOI
  6. T. H. Foregger, ``Minimum permanents of multiplexes,'' Linear Algebra and its Applications 87 (1987), 197--211. doi:10.1016/0024-3795(87)90167-4 (https://doi.org/10.1016/0024-3795(87)90167-4).DOI
  7. L. Gurvits, ``Van der Waerden/Schrijver--Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all,'' Electronic Journal of Combinatorics 15 (2008), Research Paper 66. doi:10.37236/790 (https://doi.org/10.37236/790); arXiv:0711.3496 (https://arxiv.org/abs/0711.3496).arXivDOI
  8. D. J. Hartfiel, ``On constructing nearly decomposable matrices,'' Proceedings of the American Mathematical Society 27 (1971), 222--228. doi:10.1090/S0002-9939-1971-0268062-4 (https://doi.org/10.1090/S0002-9939-1971-0268062-4).DOI
  9. M. B. Hedrick, ``The permanent at a minimum on certain classes of doubly stochastic matrices,'' Bulletin of the American Mathematical Society 80 (1974), 836--838. doi:10.1090/S0002-9904-1974-13532-9 (https://doi.org/10.1090/S0002-9904-1974-13532-9).DOI
  10. L. Lov á sz and M. D. Plummer, ``On minimal elementary bipartite graphs,'' Journal of Combinatorial Theory, Series B 23 (1977), 127--138. doi:10.1016/0095-8956(77)90062-4 (https://doi.org/10.1016/0095-8956(77)90062-4).DOI
Show all 16 referencesShow fewer references
  1. L. Lov á sz and M. D. Plummer, Matching Theory , Annals of Discrete Mathematics 29 , North-Holland, Amsterdam, 1986.
  2. T. Maciejewski, ``Foregger's Permanent Conjecture, Part IV: A Trivalent Entropic Base Case and Verification Package,'' Zenodo preprint, 2 June 2026. doi:10.5281/zenodo.20510494 (https://doi.org/10.5281/zenodo.20510494).DOI
  3. H. Minc, ``Nearly decomposable matrices,'' Linear Algebra and its Applications 5 (1972), 181--187. doi:10.1016/0024-3795(72)90027-4 (https://doi.org/10.1016/0024-3795(72)90027-4).DOI
  4. H. Minc, ``Theory of permanents 1978--1981,'' Linear and Multilinear Algebra 12 (1983), 227--263. doi:10.1080/03081088308817488 (https://doi.org/10.1080/03081088308817488).DOI
  5. R. Sinkhorn and P. Knopp, ``Concerning nonnegative matrices and doubly stochastic matrices,'' Pacific Journal of Mathematics 21 (1967), 343--348. doi:10.2140/pjm.1967.21.343 (https://doi.org/10.2140/pjm.1967.21.343).DOI
  6. R. Sinkhorn and P. Knopp, ``Problems involving diagonal products in nonnegative matrices,'' Transactions of the American Mathematical Society 136 (1969), 67--75. doi:10.1090/S0002-9947-1969-0233830-7 (https://doi.org/10.1090/S0002-9947-1969-0233830-7).DOI

Version history

  1. v1 · 16 pagesSubmitted by Yair LaviInitial depositSupersededNov 06, 2026
  2. v2 · 17 pagesSubmitted by Yair LaviVersion 2 adds citations to T. Maciejewski, "Foregger's Permanent Conjecture, Part IV" (Zenodo preprint, 2 June 2026, doi:10.5281/zenodo.20510494), in the introduction, after (3.7) and after Lemma 5.1. The results and proofs are unchanged.CurrentNov 13, 2026