Probability of zero in a random matrix - MathOverflow

Probability of zero in a random matrix

2012-06-03T10:52:33Z

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.

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.

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:

Prove that $P(n,k)$ is a non-decreasing function of $k$ for fixed $n$.

COMMENT: By a result of Stanley (see David Speyer's answer for refs) there are non-negative integers $\{h_i\}$ 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.]

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 real $k$ until $k$ is larger.

Answer by Vidit Nanda for Probability of zero in a random matrix

2012-06-03T21:10:48Z

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:

It is clear that $P(2,k) = \frac{k-1}{k+1}~$ which is certainly non-decreasing in $k$.

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

For $i = 1$ or $2~$, $\sum_j a_{ij} \leq k$
For $j = 1$ or $2~$, $\sum_i a_{ij} \leq k$
And finally, $\sum_{ij} a_{ij} \geq k$.

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.

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...

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.

Answer by David Speyer for Probability of zero in a random matrix

2012-06-04T18:24:40Z

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.

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 $$h(x) := \sum_k |M(n,k)| x^k$$ By the Erhart theorem, $|M(n,k)|$ is a polynomial in $k$, so we can write $$h(x) = \frac{\delta(x)}{(1-x)^{(n-1)^2+1}}$$ 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.

It might be worth pausing for an example: According to this webpage, $$|M(3,k)| = 1 + \frac{9 k}{4} + \frac{15 k^2}{8} + \frac{3 k^3}{4} + \frac{k^4}{8}$$ and we can compute $$h(x) = \frac{1+x+x^2}{(1-x)^5}.$$ The polynomial $\delta$ is $1+x+x^2$.

Now, we have the following implications:
(1) $\delta(x)$ has all real roots $\implies$
(2) Writing $\delta(x) = \sum \delta_k x^k$, we have $\delta_k^2 \geq \delta_{k-1} \delta_{k+1}$ $\implies$
(3) We have $M(n,k)^2 \geq M(n,k-1) M(n,k+1)$ $\implies$
(4) $M(n,k) M(n,k+n-1) \geq M(n,k-1) M(n,k+n)$, which is the relation you want.

The implication $(3) \implies (4)$ is elementary; the others are discussed in Stanley's superb survey "Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry".

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 "Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry: an update" by Brenti (scroll down), a counter example can be found in Niesi and Robbiano; 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.

I went over to Dennis Pixton's webpage 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).

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 $(-170629.9 \pm 70111.4 i)^{\pm 1}$ . (This all assumes you trust Mathematica's numerical algorithms.)

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".

Answer by Pietro Majer for Probability of zero in a random matrix

2012-06-05T08:42:53Z

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}$. A discrete convolution of log-concave discrete functions $\mathbb{N}^p\to [0,\infty)$ is log-concave [edit: this has to be checked!].
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}\ .$

Answer by Gjergji Zaimi for Probability of zero in a random matrix

2012-06-06T02:18:56Z

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 "Brunn-Minkowski inequalities for contingency tables and integer flows", 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.

Another way of stating the problem is through RSK, and turn it into an inequality in terms of Kostka numbers. 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 Schur positivity results.

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)}.$$

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 "Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley", 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.