31
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ I can prove it for $n=1$. $\endgroup$
    – cardinal
    Jun 3, 2012 at 15:23
  • 1
    $\begingroup$ Can't you use something like an element of M(n,k) is the sum of k permutation matrices to get your desired result for k>n? Gerhard "Ask Me About System Design" Paseman, 2012.06.03 $\endgroup$ Jun 3, 2012 at 16:29
  • 1
    $\begingroup$ @Gerhard: That's one of the reasons I think the result is surely true, but can you turn it into a quantitative argument? The number of ways to write a matrix that way varies a great deal between matrices so you don't get a random matrix by adding together random permutation matrices. It is plausible that the relationship between $M(n,k)$ and $M(n,k+1)$ defined by having a difference which is a permutation matrix can be analyzed enough to give it. $\endgroup$ Jun 3, 2012 at 23:24
  • 2
    $\begingroup$ What is known about $|M(n,k)|$ for fixed $n$? It looks like log-concavity would imply the inequality you want. $\endgroup$ Jun 4, 2012 at 10:50
  • 2
    $\begingroup$ @Douglas: For fixed $n$, $|M(n,k)|$ is a polynomial in $k$ of degree $(n-1)^2$. It's called the Ehrhart polynomial of the Birkhoff polytope. See math.binghamton.edu/dennis/Birkhoff for a paper on it and the explicit polynomial for $n\le 9$. $\endgroup$ Jun 4, 2012 at 15:41

4 Answers 4

17
$\begingroup$

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 Ehrhart 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 (i.e. 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 might be worth pausing for an example: According to this paper, $$|M(3,k)| = 1 + \frac{9 k}{4} + \frac{15 k^2}{8} + \frac{3 k^3}{4} + \frac{k^4}{8}=\frac{(k + 1) (k + 2) (k^2 + 3 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, claiming 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, about the tenth reference from the bottom of the page), a counterexample 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 article which tabulates the Ehrhart 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 its roots, $52$ are real and clearly isolated. The four remaining roots are $(-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".

$\endgroup$
1
  • 2
    $\begingroup$ @Brendan Looking at your research interests, I suspect you already know the more standard parts of this, but I may as well record them for others. $\endgroup$ Jun 4, 2012 at 18:26
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}\, .$

$\endgroup$
10
  • 2
    $\begingroup$ Re: discrete convolution: For the 1D case (which may or may not be helpful here): J. Keilson and H. Gerber, Some Results for Discrete Unimodality, J. Amer. Stat. Assoc., vol. 66, no. 334, 386-389. $\endgroup$
    – cardinal
    Jun 5, 2012 at 10:31
  • 1
    $\begingroup$ What definition of log-concavity are you using for $\mathbb Z^2$ for example? If it's $f_{i,j}^4\geq \prod f_{neighbours}$ then a restriction doesn't have to be log-concave... $\endgroup$ Jun 5, 2012 at 10:37
  • 1
    $\begingroup$ Consider $\prod_{1\le i\lt j\le n} (1-x_ix_j)^{-1}$ for some odd $n$. The sequence $t_k$ which is the coefficient of $\prod_i x_i^k$ is not log-concave, since it is 0 for odd $k$. So some additional conditions are required. $\endgroup$ Jun 5, 2012 at 13:04
  • 1
    $\begingroup$ A simple counterexample: Let $f$ take the values $\begin{matrix} 1 & \epsilon \\ \epsilon & 1 \end{matrix}$ on $(0,0)$, $(0,1)$, $(1,0)$ and $(1,1)$, and be $0$ elsewhere. Let $g$ be $\begin{matrix} \epsilon & 1 \\ 1 & \epsilon \end{matrix}$. Then $f \ast g$ is $\begin{matrix} \epsilon & 1+\epsilon^2 & \epsilon \\ 1+\epsilon^2 & 4 \epsilon & 1+\epsilon^2 \\ \epsilon & 1+\epsilon^2 & \epsilon \end{matrix}$. If $\epsilon$ is small enough that $4 \epsilon < 1+ \epsilon^2$, then this is not log-concave by the above definition. $\endgroup$ Jun 5, 2012 at 13:16
  • 2
    $\begingroup$ Please don't delete this answer though! There are a lot of definitions of discrete convexity, and I am hopeful that one of them will make this solution work. $\endgroup$ Jun 5, 2012 at 13:17
2
$\begingroup$

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

  1. For $i = 1$ or $2~$, $\sum_j a_{ij} \leq k$
  2. For $j = 1$ or $2~$, $\sum_i a_{ij} \leq k$
  3. 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.

$\endgroup$
1
  • $\begingroup$ Please see my answer to Douglas above. $\endgroup$ Jun 4, 2012 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.