The Maximum of per(I − A) in Odd Order
2026-08-09
Research publication
The Maximum of per(I − A) in Odd Order
arXiv preprint
- Original date
- Authors
- Yair Lavi
- Combinatorics
- Matrix theory
- Permanents
- Doubly stochastic matrices
Abstract
Let \(\Omega_n\) denote the set of \(n\times n\) doubly stochastic matrices. Kim and Roush conjectured in 1981 that, for \(n=2k+1>1\),
\[ \max_{A\in\Omega_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}. \]
They proposed the following block construction as an extremizer:
\[ A_\star=\frac12(J_3-I_3)\oplus P_2^{\oplus(k-1)}, \qquad P_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}. \]
Here \(J_3\) is the \(3\times3\) all-ones matrix. They did not claim uniqueness. We fully prove their conjecture and classify equality: the maximizers are exactly the simultaneous-permutation conjugates of \(A_\star\).