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

Yair Lavi

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

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Yair Lavi ↗

Version 1 / Nov 12, 2026/ arXiv: 2608.08933 / CC BY 4.0

Abstract

Let

Ω_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Ω_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}

. They proposed the block construction

A_\star=\frac12(J_3-I_3)\oplus P_2^{\oplus(k-1)}

, where

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

.

Tools used

OpenAI: GPT-5.6-sol
Anthropic: Claude FableVersion 5

References

K. H. Kim and F. W. Roush, Expressions for Certain Minors and Permanents, Linear Algebra and its Applications 41 (1981), 93--97. doi:10.1016/0024-3795(81)90090-2 (https://doi.org/10.1016/0024-3795(81)90090-2).DOI
H. Minc, Theory of Permanents 1982--1985, Linear and Multilinear Algebra 21 (1987), 109--148. doi:10.1080/03081088708817786 (https://doi.org/10.1080/03081088708817786).DOI
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
L. I. Troanca, Permanents of Doubly Stochastic Matrices , M.Sc. thesis, University of Manitoba, 2008. University repository PDF (https://mspace.lib.umanitoba.ca/bitstreams/5f1b99a6-487f-4308-91e8-0ff0c3b4e7b1/download).link
Z. Chen and L. Cao, On the Maximum of the Permanent of $(I-A)$ , Linear Algebra and its Applications 555 (2018), 412--431. doi:10.1016/j.laa.2018.06.031 (https://doi.org/10.1016/j.laa.2018.06.031); arXiv:1801.00225 (https://arxiv.org/abs/1801.00225).arXiv DOI

Version history

v1 · 11 pagesSubmitted by Yair LaviInitial depositCurrentNov 11, 2026