The Maximum Permanent of a Stochastic Matrix of Bounded Rank

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

Contributed by Yair Lavi ↗

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

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.

Y. Lavi, The permanent and diagonal products on the set of nonnegative matrices with bounded rank, arXiv:1808.00016v1 (2018). doi:10.48550/arXiv.1808.00016 (https://doi.org/10.48550/arXiv.1808.00016).arXiv DOI
M. Marcus and H. Minc, Generalized matrix functions, Trans. Amer. Math. Soc. 116 (1965), 316--329. doi:10.1090/S0002-9947-1965-0194445-9 (https://doi.org/10.1090/S0002-9947-1965-0194445-9).DOI
R. Sinkhorn and P. Knopp, Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math. 21 (1967), no. 2, 343--348. doi:10.2140/pjm.1967.21.343 (https://doi.org/10.2140/pjm.1967.21.343).DOI
H. Tverberg, A generalization of Radon's theorem, J. London Math. Soc. 41 (1966), 123--128. doi:10.1112/jlms/s1-41.1.123 (https://doi.org/10.1112/jlms/s1-41.1.123).DOI
A. Schrijver, Theory of Linear and Integer Programming , John Wiley & Sons, Chichester, 1986.