Kim–Roush odd-order maximum
Minc’s list · Conjecture 35
Kim–Roush odd-order maximum
Proved by us arXiv preprint, August 2026
- Posed by
- Kim and Roush
- First posed
- 1981
Statement
Posed by K. H. Kim and F. W. Roush in 1981; it is Conjecture 35 in Minc’s 1987 survey.
Conjecture 35. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices. For every \(k\ge 1\),
\[ \max_{A\in\Omega_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}, \]
and the maximum is attained at the direct sum of \(\tfrac12(J_3-I_3)\) and \(k-1\) copies of \(\begin{pmatrix}0&1\\1&0\end{pmatrix}\), where \(J_3\) is the \(3\times 3\) all-ones matrix.
Resolution
We proved the conjecture in every odd order, and showed that the maximizers are exactly the matrices \(PA_\star P^{\mathsf T}\), where \(A_\star\) is the proposed block matrix and \(P\) is a permutation matrix. The key step is a new inequality for the weights of the maps behind the Kim–Roush expansion of \(\operatorname{per}(I-A)\).
Before our proof only the smallest case was known: Kim and Roush proved \(n=3\), together with the analogous maximum \(2^{n/2}\) in even order. Chen and Cao (2018) later found the exact maximum over doubly substochastic matrices with total entry sum \(s\), except in odd order with \(n-1<s\le n\); the case \(s=n\) is the conjecture itself.
References
- K. H. Kim and F. W. Roush, Expressions for certain minors and permanents, Linear Algebra Appl. 41 (1981), 93–97. doi:10.1016/0024-3795(81)90090-2
- H. Minc, Theory of permanents 1982–1985, Linear and Multilinear Algebra 21 (1987), 109–148. doi:10.1080/03081088708817786
- Z. Chen and L. Cao, On the maximum of the permanent of (I − A), Linear Algebra Appl. 555 (2018), 412–431. doi:10.1016/j.laa.2018.06.031
- Y. Lavi, The maximum of per(I − A) in odd order, preprint (2026). arXiv:2608.08933