HEXAGONbeta

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 1 / 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}.

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 15 referencesShow fewer references
  1. L. Lov á sz and M. D. Plummer, Matching Theory , Annals of Discrete Mathematics 29 , North-Holland, Amsterdam, 1986.
  2. 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
  3. 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
  4. 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
  5. 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 depositCurrentNov 06, 2026