Maximum permanent conjecture for nonnegative matrices of bounded rank

At least 7 years old · documented by

Let A=(aij)A=(a_{ij}) be an n×nn\times n nonnegative matrix of rank at most kk, with row sums r1,…,rnr_1,\ldots,r_n and column sums c1,…,cnc_1,\ldots,c_n. For k,n∈Nk,n\in\mathbb{N} with 1≤k≤n1\leq k\leq n, write n=rk+sn=rk+s with 0≤s<k0\leq s<k, and set r⃗=(r,…,r⏟k−s times,r+1,…,r+1⏟s times)\vec r=(\underbrace{r,\ldots,r}_{k-s\text{ times}},\underbrace{r+1,\ldots,r+1}_{s\text{ times}}). When all row sums are positive, let A‾r\overline A^r be obtained by dividing each row of AA by its row sum; when all column sums are positive, define A‾c\overline A^c analogously. Let Jr⃗J_{\vec r} be the associated block-diagonal composition matrix and let Sn\mathfrak{S}_n denote the permutation matrices. Nonnegative permanent conjecture. One should have

per⁡(A)≤min⁡(∏i=1nri,∏i=1nci)(r!rr)k−s((r+1)!(r+1)r+1)s.\operatorname{per}(A)\leq \min\left(\prod_{i=1}^n r_i,\prod_{i=1}^n c_i\right)\left(\frac{r!}{r^r}\right)^{k-s}\left(\frac{(r+1)!}{(r+1)^{r+1}}\right)^s.

Equality should hold exactly in the four cases stated in the source: a zero row or column; the row-normalized matrix is a permutation of Jr⃗J_{\vec r} when the positive row-sum product is smaller; the analogous column-normalized condition when the positive column-sum product is smaller; or both normalized conditions when the two products are equal. This is the row-sum and column-sum form equivalent to the stochastic-matrix conjecture.

References

Primary source

Yair Lavi, “The permanent and diagonal products on the set of nonnegative matrices with bounded rank”, arXiv:1808.00016 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.