Maximum permanent conjecture for stochastic matrices of bounded rank

About 8 years old · traced to

Let Mn+\mathcal{M}_n^+ denote the set of n×nn\times n nonnegative real matrices. Let Rnk‾R_n^{\overline{k}} and Lnk‾L_n^{\overline{k}} be the sets of row-stochastic and column-stochastic n×nn\times n matrices, respectively, of rank at most kk. For k,n∈Nk,n\in\mathbb{N} with 1≤k≤n1\leq k\leq n, write n=rk+sn=rk+s with r,s∈Nr,s\in\mathbb{N} and 0≤s<k0\leq s<k. Let JmJ_m be the m×mm\times m doubly stochastic matrix with every entry equal to 1/m1/m, let Jr⃗=Jr⊕⋯⊕Jr⊕Jr+1⊕⋯⊕Jr+1J_{\vec r}=J_r\oplus\cdots\oplus J_r\oplus J_{r+1}\oplus\cdots\oplus J_{r+1} for 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}}), and let Sn\mathfrak{S}_n be the set of permutation matrices. Maximum permanent conjecture. If A∈Rnk‾∪Lnk‾A\in R_n^{\overline{k}}\cup L_n^{\overline{k}}, then

per⁡(A)≤(r!rr)k−s((r+1)!(r+1)r+1)s.\operatorname{per}(A)\leq \left(\frac{r!}{r^r}\right)^{k-s}\left(\frac{(r+1)!}{(r+1)^{r+1}}\right)^s.

Equality should hold if and only if A=PJr⃗QA=PJ_{\vec r}Q for some P,Q∈SnP,Q\in\mathfrak{S}_n; in particular, every maximizing matrix should be doubly stochastic of rank kk. This is formulated as equivalent to the corresponding conjecture for nonnegative matrices with prescribed row and column sums. The conjecture concerns the extremal permanent among stochastic matrices subject to a rank bound.

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.