The permanent and diagonal products on the set of nonnegative matrices with bounded rank
2018-07-31
Research publication
The permanent and diagonal products on the set of nonnegative matrices with bounded rank
arXiv preprint
- Original date
- Authors
- Yair Lavi
- Combinatorics
- Matrix theory
- Permanents
- Stochastic matrices
About this work
Two conjectures of mine about stochastic matrices. The first one was proven by AI and published by me in a 2026 paper.
To state them, let \(R_n^{\leq k}\) and \(L_n^{\leq k}\) be the sets of \(n \times n\) row-stochastic and column-stochastic matrices, respectively, with rank at most \(k\). Write
\[ n=rk+s, \qquad 0\leq s<k, \]
and define
\[ J_m=\frac{1}{m}\mathbf{1}_m\mathbf{1}_m^{\mathsf T}, \qquad J_{\boldsymbol{\rho}} =J_r^{\oplus(k-s)}\oplus J_{r+1}^{\oplus s}. \]
Here \(J_{\boldsymbol{\rho}}\) is the block-diagonal doubly stochastic matrix whose block sizes are \(r\) repeated \(k-s\) times and \(r+1\) repeated \(s\) times.
1. The permanent conjecture
The first one is about permanents. It states that every \(A\in R_n^{\leq k}\cup L_n^{\leq k}\) satisfies
\[ \operatorname{per}(A) \leq \left(\frac{r!}{r^r}\right)^{k-s} \left(\frac{(r+1)!}{(r+1)^{r+1}}\right)^s. \]
Equality holds exactly for matrices of the form
\[ A=PJ_{\boldsymbol{\rho}}Q, \]
where \(P\) and \(Q\) are permutation matrices. In particular, for a singular row-stochastic or column-stochastic matrix,
\[ \operatorname{per}(A)\leq \frac12. \]
2. The diagonal-product conjecture
The second one, about products of diagonal entries, has no proof or disproof yet. For any permutation \(\sigma\in S_n\), it states that every \(A\in R_n^{\leq k}\cup L_n^{\leq k}\) satisfies
\[ \prod_{i=1}^n a_{i,\sigma(i)} \leq \left(\frac{1}{r^r}\right)^{k-s} \left(\frac{1}{(r+1)^{r+1}}\right)^s. \]
For the ordinary main diagonal, take \(\sigma\) to be the identity permutation. Equality holds exactly for matrices of the form
\[ A=P^{\mathsf T}J_{\boldsymbol{\rho}}P\,\pi(\sigma), \]
where \(P\) is a permutation matrix and \(\pi(\sigma)\) is the permutation matrix of \(\sigma\). In particular, for a singular row-stochastic or column-stochastic matrix,
\[ \prod_{i=1}^n a_{i,\sigma(i)}\leq \frac14. \]
Abstract
We formulate conjectures regarding the maximum value and maximizing matrices of the permanent and of diagonal products on the set of stochastic matrices with bounded rank. We formulate equivalent conjectures on upper bounds for these functions for nonnegative matrices based on their rank, row sums and column sums. In particular we conjecture that the permanent of a singular nonnegative matrix is bounded by \(\frac12\) times the minimum of the product of its row sums and the product of its column sums, and that the product of the elements of any diagonal of a singular nonnegative matrix is bounded by \(\frac14\) times the minimum of the product of its row sums and the product of its column sums.