Probability of zero in a random matrix 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. 
 A: 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.
A: 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}\, .$ 
A: 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.
A: 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".
