The Maximum Permanent of a Stochastic Matrix of Bounded Rank

Abstract

Let $A$ be a stochastic $n\times n$ matrix with $\mathrm{rank}A\le k$, where $1\le k\le n$. Write $n=qk+s$, where $0\le s<k$. The author conjectured in 2018 that $\mathrm{per}A\le (q!/q^q{)}^{k-s}((q+1)!/(q+1{)}^{q+1}{)}^s$, with equality if and only if $A=P(J_q^{\oplus (k-s)}\oplus J_{q+1}^{\oplus s})Q$, where $P,Q$ are permutation matrices and $J_t$ is the $t\times t$ matrix with every entry $1/t$. We prove this conjecture in full.