The Maximum Diagonal Product of a Stochastic Matrix of Bounded Rank
math.CO
Submitted: 2026-11-01
Updated: 2026-11-01
License: http://creativecommons.org/licenses/by/4.0/
The gist: Let A=(a ij) be a nonnegative row-stochastic or column-stochastic n times n matrix of rank at most k, where 1 at most k at most n.
Terminology
Abstract
Let A=(a ij) be a nonnegative row-stochastic or column-stochastic n times n matrix of rank at most k, where 1 at most k at most n. Write n=qk+s, where 0 at most s<k. The author conjectured in 2018 that, for every permutation σ of 1,,n, product from i=1 to n a i,σ(i) at most q-q(k-s)(q+1)-(q+1)s. We prove this bound and classify all equality cases.
Sources
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality