The Maximum Permanent of a Stochastic Matrix of Bounded Rank
2026-08-21
Research publication
The Maximum Permanent of a Stochastic Matrix of Bounded Rank
arXiv preprint
- Original date
- Authors
- Yair Lavi
- Combinatorics
- Matrix theory
- Permanents
- Stochastic matrices
About this work
Very happy about this one - a proof of a conjecture of mine from 2018.
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\). I conjectured in 2018 that
\[ \operatorname{per}A\leq \left(\frac{q!}{q^q}\right)^{k-s} \left(\frac{(q+1)!}{(q+1)^{q+1}}\right)^s, \]
with equality if and only if
\[ A=P\left(J_q^{\oplus(k-s)}\oplus J_{q+1}^{\oplus s}\right)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.