The Maximum of $\mathrm{per}(I-A)$ in Odd Order

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}}\mathrm{per}(I-A)=3\cdot 2^{k-2}$. They proposed the block construction $A_{\star }=\frac{1}{2}(J_3-I_3)\oplus P_2^{\oplus (k-1)}$, where $P_2=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. Here $J_3$ is the $3\times 3$ 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 }$.