The Maximum Diagonal Product 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 11, 2026/ arXiv: 2611.01763 / CC BY 4.0

Abstract

Let

A=(a_{ij})

be a nonnegative row-stochastic or column-stochastic

n\times n

matrix of rank at most

k

, where

1\le k\le n

. Write

n=qk+s

, where

0\le s<k

. The author conjectured in 2018 that, for every permutation

σ

of

\{1,\ldots,n\}

,

\prod_{i=1}^n a_{i,σ(i)}\le q^{-q(k-s)}(q+1)^{-(q+1)s}

. We prove this bound and classify all equality cases.

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
A. Ostrowski, Über die Determinanten mit überwiegender Hauptdiagonale , Comment. Math. Helv. 10 (1937), 69--96. doi:10.1007/BF01214284 (https://doi.org/10.1007/BF01214284).DOI
A. Brauer, Limits for the characteristic roots of a matrix. II , Duke Math. J. 14 (1947), 21--26. doi:10.1215/S0012-7094-47-01403-8 (https://doi.org/10.1215/S0012-7094-47-01403-8).DOI
K. Fan and A. J. Hoffman, Lower bounds for the rank and location of the eigenvalues of a matrix , National Bureau of Standards Report 2246 (1953). doi:10.6028/NBS.RPT.2246 (https://doi.org/10.6028/NBS.RPT.2246).DOI
Y. Lavi, The Maximum Permanent of a Stochastic Matrix of Bounded Rank , arXiv:2609.27911v1 (2026). doi:10.48550/arXiv.2609.27911 (https://doi.org/10.48550/arXiv.2609.27911).arXiv DOI
P. Flor, On groups of non-negative matrices , Compositio Math. 21 (1969), 376--382. https://archive.numdam.org/item/CM_1969__21_4_376_0/.link