PreprintCC BY 4.0arXiv
The Maximum Permanent of a Stochastic Matrix of Bounded Rank
Abstract
Let A be a stochastic n× n matrix with rankA≤ k, where 1≤ k≤ n. Write n=qk+s, where 0≤ s<k. The author conjectured in 2018 that perA≤ (q!/qq)k−s((q+1)!/(q+1)q+1)s, with equality if and only if A=P(Jq⊕(k−s)⊕ Jq+1⊕ s)Q, where P,Q are permutation matrices and Jt is the t× t matrix with every entry 1/t. We prove this conjecture in full.
Related
- The Maximum Diagonal Product of a Stochastic Matrix of Bounded Rank
- Equality cases for matrix spaces with bounded-rank commutators
- A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix
- An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix
- Maximum principle for quasilinear SPDE’s on a bounded domain without regularity assumptions
BibTeX
@misc{lavi2026maximum,
title = {{The Maximum Permanent of a Stochastic Matrix of Bounded Rank}},
author = {Yair Lavi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27911},
eprint = {2609.27911},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27911},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Maximum Permanent of a Stochastic Matrix of Bounded Rank
AU - Yair Lavi
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.27911
UR - https://arxiv.org/abs/2609.27911
AB - Let A be a stochastic n× n matrix with rankA≤ k, where 1≤ k≤ n. Write n=qk+s, where 0≤ s<k. The author conjectured in 2018 that perA≤ (q!/q^q)^k−s((q+1)!/(q+1)^q+1)^s, with equality if and only if A=P(J_q^⊕(k−s)⊕ J_q+1^⊕ s)Q, where P,Q are permutation matrices and J_t is the t× t matrix with every entry 1/t. We prove this conjecture in full.
ER -