5
$\begingroup$

[I posted this question on math.stackexchange a few weeks back, but no luck there so far: https://math.stackexchange.com/questions/1095659/an-inequality-concerning-non-negative-integer-matrices-with-constant-row-and-col]

I'd appreciate any suggestions for how to prove (or disprove) the inequality described below. Some notation first: for positive integers $k$ and $M$, let ${\mathcal D}_{k,M}$ denote the set of all $k \times k$ non-negative integer matrices with row and column sums all equal to $M$. For $k \times k$ matrices $A = [a_{i,j}]$ and $B = [b_{i,j}]$, we write $A \le B$ if $a_{i,j} \le b_{i,j}$ for all $i,j$.

Now, let $M, N$ be fixed positive integers with $M < N$. I'd like to prove that for any $B \in \mathcal{D}_{k,N}$, we have $\displaystyle \sum_{A \in \mathcal{D}_{k,M}: A \le B} \prod_{i,j} \frac{\binom{b_{i,j}}{a_{i,j}}}{\binom{N-b_{i,j}}{M-a_{i,j}}} \ge {\binom{N}{M}}^{2k-k^2}$.

It is easy to check that the inequality holds with equality when $B$ is $N$ times a permutation matrix. It is also straightforward to show that the inequality holds when $B$ has at most two non-zero entries in each row. In particular, the inequality holds when $B$ is a convex combination of $B_1$ and $B_2$, where each of $B_1$ and $B_2$ is $N$ times a permutation matrix. How to proceed when $B$ is a convex combination of three or more such matrices is not clear.

$\endgroup$
  • 2
    $\begingroup$ Where does this question arise? $\endgroup$ – Stefan Kohl Feb 25 '15 at 10:21
  • $\begingroup$ Related to the enumeration of pairings between multisets, this answer to the question mathoverflow.net/q/67359/41291 contains a reference $\endgroup$ – მამუკა ჯიბლაძე Feb 25 '15 at 10:35
  • 2
    $\begingroup$ @StefanKohl This is not so easy for me to answer in comment form. It arises in the context of a certain approximation, called the Bethe approximation, to the permanent of a non-negative square matrix. See arxiv.org/abs/1107.4196 for details on the so-called "Bethe permanent" and its relationship to the permanent. The ArXiv reference shows that the Bethe permanent can be expressed as the limsup of a certain sequence of "degree-$M$ permanents". Gurvits [arxiv.org/abs/1106.2844] has shown that the Bethe permanent is a lower bound on the permanent. (cont'd below) $\endgroup$ – Navin K. Feb 25 '15 at 12:30
  • 4
    $\begingroup$ @StefanKohl The inequality I wish to show would prove that the sequence of "degree-$M$ permanents" is sub-multiplicative, which would imply Gurvits's result and also strengthen Vontobel's result by showing that the Bethe permanent is in fact the limit of the sequence of degree-$M$ permanents. $\endgroup$ – Navin K. Feb 25 '15 at 12:34
  • $\begingroup$ Just to help me understand: each matrix in $D_{k,M}$ is $M$ times a doubly stochastic matrix, so that in the case mentioned above, if we write $B=N\sum_i \alpha_i P_i$, we have the case of a convex combination of permutation matrices that you allude to in the question, and you are wondering whether for such a $B$, the inequality holds... $\endgroup$ – Suvrit Feb 25 '15 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.