The Maximum Permanent of a Stochastic Matrix of Bounded Rank

Abstract

Let $A$ be a stochastic $n\times n$ matrix with $\operatorname{rank}A\leq k$, where $1\leq k\leq n$. Write $n=qk+s$, where $0\leq s<k$. The author conjectured in 2018 that $\operatorname{per}A\leq (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.