Maximum permanent conjecture for stochastic matrices of bounded rank

Let Mn+\mathcal{M}_n^+ denote the set of n×nn\times n nonnegative real matrices. Let RnkR_n^{\overline{k}} and LnkL_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,nNk,n\in\mathbb{N} with 1kn1\leq k\leq n, write n=rk+sn=rk+s with r,sNr,s\in\mathbb{N} and 0s<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=JrJrJr+1Jr+1J_{\vec r}=J_r\oplus\cdots\oplus J_r\oplus J_{r+1}\oplus\cdots\oplus J_{r+1} for r=(r,,rks times,r+1,,r+1s 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 ARnkLnkA\in R_n^{\overline{k}}\cup L_n^{\overline{k}}, then

per(A)(r!rr)ks((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=PJrQA=PJ_{\vec r}Q for some P,QSnP,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.

Sources & referencesView supporting material

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.