Probability of zero in a random matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T05:13:07Z http://mathoverflow.net/feeds/question/98710 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98710/probability-of-zero-in-a-random-matrix Probability of zero in a random matrix Brendan McKay 2012-06-03T10:52:33Z 2012-06-06T10:22:17Z <p>Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, equivalently the probability that a random matrix from the uniform distribution on $M(n,k)$ has no zero entries.</p> <p>One thing to note is that $$P(n,k)=\frac{|M(n,k-n)|}{|M(n,k)|}$$ (think about subtracting 1 from every entry). Also note that $P(n,k)$ is the fraction of integer points in the $k$-dilated Birkhoff polytope that lie in the interior.</p> <p>It seems "obvious" that $P(n,k)$ is a non-decreasing function of $k$. For large enough $k$ it is strictly increasing by Ehrhart theory, but I'd like to see a proof for all $k$. So the problem is: </p> <p><strong>Prove that $P(n,k)$ is a non-decreasing function of $k$ for fixed $n$</strong>.</p> <p>COMMENT: By a result of Stanley (see David Speyer's answer for refs) there are non-negative integers <code>$\{h_i\}$</code> such that $$|M(n,k)| = \sum_{i=0}^d h_i \binom{k+i}{d}$$ where $d=(n-1)^2$. I'm wondering if this is enough. Does every polynomial of that form have the desired properties? [Gjergji showed not.]</p> <p>COMMENT2: The reciprocity theorem for Ehrhart series provides a formula for the number of points in the interior in terms of the number in the whole (closed) polytope. Making use of the above, we find that if the $H_n(k)$ is the polynomial equal to $|M(n,k)|$ for positive integers $k$, then the number of interior points (already identified as $H_n(k-n)$) equals $(-1)^{n+1}H_n(-k)$. So what we have to prove is that $$(-1)^{n+1}\frac{H_n(-k)}{H_n(k)}$$ is non-decreasing for integer $k\ge n$. Experimentally, it is not increasing for <em>real</em> $k$ until $k$ is larger. </p> http://mathoverflow.net/questions/98710/probability-of-zero-in-a-random-matrix/98740#98740 Answer by Vidit Nanda for Probability of zero in a random matrix Vidit Nanda 2012-06-03T21:10:48Z 2012-06-04T13:21:56Z <p>Okay, so this is nowhere near a complete solution, but this is as far as I got and hopefully someone else sees it from here:</p> <p>It is clear that $P(2,k) = \frac{k-1}{k+1}~$ which is certainly non-decreasing in $k$. </p> <p>When $n=3$, the matrices in $M(3,k)$ correspond to four integers $a_{11},a_{12},a_{21},a_{22}~$ from $0,\ldots,k~$ such that </p> <ol> <li>For $i = 1$ or $2~$, $\sum_j a_{ij} \leq k$</li> <li>For $j = 1$ or $2~$, $\sum_i a_{ij} \leq k$</li> <li>And finally, $\sum_{ij} a_{ij} \geq k$.</li> </ol> <p>These hyperplane inequalities carve out a convex region $C \subset \mathbb{R}^4$ from the cube $[0,k]^4$ and the "zero entry" cases of $M(3,k)$ are precisely the bounding faces of this region.</p> <p>So, if a theorem establishes that the ratio $$\frac{\text{integral points on the boundary of } C}{\text{ total number of integral points in }C}$$ decreases as one increases $k$, then we obtain your desired result. I don't know enough about convex polytopes to cite something here but it sounds reasonable just from dimension considerations...</p> <p>Ideally, this process would generalize to higher dimensions. An element of $M(n,k)$ has zero entries if and only if the vector of entries in the first $(n-1) \times (n-1)$ block lies in the boundary of convex polytope carved from the cube $[0,1]^{(n-1)^2}$ by $2n-1$ hyperplanes.</p> http://mathoverflow.net/questions/98710/probability-of-zero-in-a-random-matrix/98797#98797 Answer by David Speyer for Probability of zero in a random matrix David Speyer 2012-06-04T18:24:40Z 2012-06-04T18:24:40Z <p>This is frustrating because there is a lot of study of this sort of question in the combinatorial commutative algebra literature, and the exact example you discuss is a favorite example in this field, but I can't find an answer to your question. So, here are some pointers to the relevant background.</p> <p>Fix $n$. Let $R$ be the semigroup ring corresponding to the semigroup of $n \times n$ nonnegative integer matrices all of whose row and column sums are equal. So the Hilbert series of $R$ is <code>$$h(x) := \sum_k |M(n,k)| x^k$$</code> By the Erhart theorem, $|M(n,k)|$ is a polynomial in $k$, so we can write <code>$$h(x) = \frac{\delta(x)}{(1-x)^{(n-1)^2+1}}$$</code> for some polynomial $\delta(x)$ of degree $\leq (n-1)^2$. Richard Stanley pioneered the study of the relation between commutative algebra properties of $R$ and combinatorial properties of $\delta$. In particular, the ring $R$ is Gorenstein (the canonical module is generated by the all ones matrix) and this implies that $\delta$ is palindromic with positive coefficients. The standard reference for this material is Stanley's book "Combinatorics and Commutative Algebra"; it does not appear to be legally available online.</p> <p>It might be worth pausing for an example: According to <a href="http://www.math.binghamton.edu/dennis/Birkhoff/polynomials.html" rel="nofollow">this webpage</a>, <code>$$|M(3,k)| = 1 + \frac{9 k}{4} + \frac{15 k^2}{8} + \frac{3 k^3}{4} + \frac{k^4}{8}$$</code> and we can compute <code>$$h(x) = \frac{1+x+x^2}{(1-x)^5}.$$</code> The polynomial $\delta$ is $1+x+x^2$.</p> <p>Now, we have the following implications:<br> (1) $\delta(x)$ has all real roots $\implies$<br> (2) Writing $\delta(x) = \sum \delta_k x^k$, we have $\delta_k^2 \geq \delta_{k-1} \delta_{k+1}$ $\implies$<br> (3) We have $M(n,k)^2 \geq M(n,k-1) M(n,k+1)$ $\implies$<br> (4) $M(n,k) M(n,k+n-1) \geq M(n,k-1) M(n,k+n)$, which is the relation you want.</p> <p>The implication $(3) \implies (4)$ is elementary; the others are discussed in Stanley's superb survey <a href="http://math.mit.edu/~rstan/pubs/pubfiles/72.pdf" rel="nofollow">"Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry"</a>. </p> <p>In that Survey, Stanley made Conjecture 4, that the Hilbert series of any Cohen-Macaulay domain should obey (2). $R$ is a Cohen-Macualay domain (any normal semi-group ring is, by a result of Hochster), but Conjecture 4 turned out to be false. According to <a href="http://www.mat.uniroma2.it/~brenti/papers.htm" rel="nofollow">"Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry: an update"</a> by Brenti (scroll down), a counter example can be found in <a href="http://www.ams.org/mathscinet-getitem?mr=1230867" rel="nofollow">Niesi and Robbiano</a>; I haven't checked this reference. Stanley and Brenti both suggest that the conjecture is more plausible for Gorenstein rings, and a quick skim through the Mathscinet papers which cite them suggest that no Gorenstein counterexample is known.</p> <p>I went over to <a href="http://www.math.binghamton.edu/dennis/Birkhoff/polynomials.html" rel="nofollow">Dennis Pixton's webpage</a> which tabulates the Erhart polynomials for this exact problem. The largest value he lists is $n=9$. I computed the corresponding $\delta$ (coefficients available on request) and found that it violated (1) but obeyed (2).</p> <p>Specifically, for $n=9$, the polynomial $\delta$ has degree $56$. Of the roots, $52$ were real and clearly isolated. There are also four roots at <code>$(-170629.9 \pm 70111.4 i)^{\pm 1}$</code>. (This all assumes you trust <i>Mathematica</i>'s numerical algorithms.)</p> <p>Finally, you should probably know a few keywords: The polytope of $n \times n$ matrices with nonnegative entries and row and column sums equal to $1$ is the "Birkhoff polytope". The more general case where you just fix $(a_1, a_2, \ldots, a_n)$ and $(b_1, b_2, \ldots, b_n)$ with $\sum a_i = \sum b_i$ and ask for row sums $a_i$ and column sums $b_i$ is the "transportation polytope".</p> http://mathoverflow.net/questions/98710/probability-of-zero-in-a-random-matrix/98853#98853 Answer by Pietro Majer for Probability of zero in a random matrix Pietro Majer 2012-06-05T08:42:53Z 2012-06-05T10:26:06Z <p>Let's enlarge the set of variables and consider more generally, for $a\in\mathbb{N}^n$ and $b\in\mathbb{N}^m$, the number of $n\times m$ matrices with non-negative integer coefficients whose $i$-th row sums to $a_i$ and whose $j$-th column sums to $b_j$, for $1\le i\le n$ and $1\le j\le m$: $$\mu(a,b):= \Big| \big\{v\in\mathbb{N}^{n\times m}\ :\ \sum_{1\le j\le m}v_{ij}=a_i\ , \sum_{1\le i\le n}v_{ij}=b_j\big\}\Big|\ .$$ Then, for $x:=(x_1,\dots,x_n)$ and $y:=(y_1,\dots,y_m)$ $$\sum_{a\in\mathbb{N}^n\atop b\in\mathbb{N}^m}\mu(a,b)x^ay^b=\sum_{v\in\mathbb{N}^{n\times m} } \prod_{1\le i\le n \atop 1\le j\le m} x_i ^{\sum_jv_{ij}} y_j ^{\sum_iv_{ij}}=\prod_{1\le i\le n \atop 1\le j\le m}(1-x_iy_j)^{-1}\ .$$ Thus $\mu$ is the discrete convolution of certain $nm$ log-concave functions $\delta _{ij}:\mathbb{N}^{n+m}\to[0,\infty)$ , namely the coefficients sequences of $(1-x_iy_j)^{-1}$. <em>A discrete convolution of log-concave discrete functions $\mathbb{N}^p\to [0,\infty)$ is log-concave</em> [<strong>edit</strong>: this has to be checked!].<br> In particular, for $n=m$ and $u=(1,\dots,1)$ the sequence $|M(n,k)|=\mu(ku,ku)$ is log-concave w.r.to $k\in\mathbb{N}\ .$ </p> http://mathoverflow.net/questions/98710/probability-of-zero-in-a-random-matrix/98926#98926 Answer by Gjergji Zaimi for Probability of zero in a random matrix Gjergji Zaimi 2012-06-06T02:18:56Z 2012-06-06T02:18:56Z <p>Here are a few more ways to rephrase the problem. Let $A_k$ denote a $kn\times kn$ matrix, composed of $k\times k$ blocks, where the $ij$ block is filled with copies of a standard exponential random variable $\gamma_{ij}$. The $\gamma_{ij}$'s are taken to be independent. A. Barvinok showed that $$M(n,k)=\frac{\mathbb{E}(\operatorname{per}(A_k))}{(k!)^{2n}}$$ and used this to prove that $M(n,k)$ is almost log-concave in $k$. More specifically, he showed in <a href="http://www.math.lsa.umich.edu/~barvinok/brunn.pdf" rel="nofollow">"Brunn-Minkowski inequalities for contingency tables and integer flows"</a>, Adv. in Math., 211 (2007), 105-122, that the following inequality holds $$\alpha(k)M(n,k)^2\geq M(n,k-1)M(n,k+1)$$ with $\alpha(k)=O(k^n)$. He conjectures that this inequality holds for $\alpha=1$, but as far as I know, this remains open. I'm not sure what's the best upper bound for $$\frac{M(n,k)M(n,n+k+1)}{M(n,k+1)M(n,k+n)}$$ that one gets using this analytic approach.</p> <hr> <p>Another way of stating the problem is through RSK, and turn it into an inequality in terms of <a href="http://en.wikipedia.org/wiki/Kostka_number" rel="nofollow">Kostka numbers</a>. If $\tau(k)$ stands for the partition $(k,k,\dots,k)$, with $k$ parts. Then log-concavity is equivalent to $$\left(\sum_{\lambda} K_{\lambda \tau(k)}\right)^2\geq \left(\sum_{\lambda} K_{\lambda \tau(k-1)}\right)\left(\sum_{\lambda} K_{\tau(k+1)}\right)$$ and your inequality can be written similarly. One might hope that there is a proof making use of known inequalities between Kostka numbers or known <a href="http://arxiv.org/abs/math/0502446" rel="nofollow">Schur positivity</a> results.</p> <p>Yet another equivalent formulation comes from Pietro's answer. We need to prove that the coefficient of $(x_1y_1\cdots x_ny_n)^k(z_1t_1\cdots z_nt_n)^{k+1}$ is non-negative in $$\frac{\left(z_1t_1\cdots z_nt_n-x_1y_1\cdots x_ny_n\right)}{\prod_{i,j=1}^n(1-x_iy_j)(1-t_iz_j)}.$$</p> <hr> <p>In a different direction, we have $$M(n,k)=\sum_{i=0}^d h_i\binom{k+i}{d}$$ where $d=(n-1)^2$. In <a href="http://arxiv.org/abs/math/0312031" rel="nofollow">"Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley"</a>, C.A. Athanasiadis proved that $(h_0,h_1-h_0,\dots,h_{\lfloor d/2\rfloor}-h_{\lfloor d/2\rfloor-1})$ is a g-vector, so it satisfies the inequalities of Mcmullen's g-theorem. In particular $h$ is a symmetric unimodal sequence. I doubt that this is enough to conclude log-concavity of $M(n,k)$, or your property for that matter, but perhaps it gives some insight on how hard the problem is.</p>