Return to Question

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? If so, the result will generalise a lot since every lattice polytope has such an enumerator. Careful: some of the binomial coefficients are 0 when $k\lt d$.

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.

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

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? If so, the result will generalise a lot since every lattice polytope has such an enumerator. Careful: some of the binomial coefficients are 0 when $k\lt d$.

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

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

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