# Sum-regular $\{0,1\}$-matrices

Let $n\in\mathbb{N}$ be a positive integer. We say that an $n\times n$-matrix $A$ with all entries in $\{0,1\}$ is $k$-regular for some $k\in \{0,\ldots,n\}$ if the sum of every row and the sum of every column of $A$ equals $k$. Let $M(n, k)$ be the number of $k$-regular $n\times n$-matrices with all entries in $\{0,1\}$.

It's easy to see that $M(n,1)=n!$. Moreover, a symmetry argument shows that $M(n,k) = M(n, n-k)$ for all $k\in \{0,\ldots,n\}$.

Question. Given $n>1$, is it true that for all $k\in\{0,\ldots, n\}$ we have $M(n,k)\leq M(n, \lfloor\frac{n}{2}\rfloor)$?

• Worth pointing out: relevant articles are: A.Barvinok, On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries. Adv. Math. 224, No. 1, 316-339 (2010) and A. Barvinok, Matrices with prescribed row and column sums. Linear Algebra Appl. 436, No. 4, 820-844 (2012). Sadly, it seems (and I have looked at them very closely), while very interesting, the estimates proved in there are not precise enough to answer the question. – Peter Heinig Mar 16 '18 at 17:12

I'm pretty sure this is unknown, though it would be great if I'm wrong.

Asymptotically there is a function $A(n)$ such that $M(n,n/2+t)\sim e^{-2t^2}A(n)$ for $t=o(n^{1/2})$, which follows from this paper of Canfield and McKay.

It is also known to be true for $n\le 20$.

To spell out the asymptotics a bit more, the paper cited above shows that $$M(n,k) = (e^{-1/2}+o(1)) \binom {n}{k}^{\!2n} \bigl( \lambda^\lambda(1-\lambda)^{1-\lambda}\bigr)^{n^2}, \qquad(*)$$ as $n\to\infty$, where $\lambda=k/n$ and $cn/\log n\le k\le n-cn/\log n$ for a particular constant $c$. The value $c=1/3$ will do. This expression without the error term is unimodal for $0\le k\le n$ and even with the error term it is unimodal if $n$ is large enough. The same formula holds for $k=o(n^{1/2})$ (McKay and Wang, 2003). A new method of Liebenau and Wormald will (I'm 100% confident) show that $(*)$ is also true for the intermediate ranges of $k$, but it is not published yet. Then we will know that $M(n,k)$ is unimodal in $k$ provided $n$ is large enough.

If we just want to know whether $M(n,k)\le M(n,\lfloor n/2\rfloor)$, as asked, and don't care about unimodality, then what remains asymptotically is to show that $M(n,k)\lt M(n,\lfloor n/2\rfloor)$ for $k\le \frac13 n/\log n$. This follows from the pairing (configuration) model for random $k$-regular bipartite graphs; namely $$M(n,k) \le \frac{ (nk)! }{ (k!)^{2n} }.\qquad(\#)$$ For large $k$, $(\#)$ is a pretty terrible bound, but if I didn't miscalculate it is sufficient to prove that $M(n,k)\lt M(n,\lfloor n/2\rfloor)$ for $k\le \frac13 n/\log n$.

That completes the proof that $M(n,\lfloor n/2\rfloor)$ is the largest value if $n$ is large enough.

• What if we count ways of summing disjoint permutations? Can we estimate the numbers that way, at least towards determining unimodality? Gerhard "The Sum Of All Gears" Paseman, 2018.03.16. – Gerhard Paseman Mar 16 '18 at 14:22
• @GerhardPaseman : The unimodality would follow if a precise estimate could be found for the expected number of permutation matrices covered by a random matrix in this class. The accuracy would need to be within a small constant. So far it has only been done asymptotically as far as I am aware. – Brendan McKay Mar 16 '18 at 22:03
• Excellent progress, thanks for putting so much effort into this! I think I am going to accept this answer, because it answers the question for $n\in\mathbb{N}$ large enough – Dominic van der Zypen Mar 17 '18 at 15:07

I can prove a related result. Perhaps someone can modify the proof to solve Dominic's problem.

I use multivariate notation such as $x^\alpha=x_1^{\alpha_1}\cdots x_m^{\alpha_m}$, where $\alpha=(\alpha_1,\dots,\alpha_m)$. Let $\alpha\in \{0,1,2,\dots\}^m$ and $\beta\in\{0,1,2,\dots\}^n$. Let $f(\alpha,\beta)$ be the number of $m\times n$ matrices with entries $0,1,2$, and with each entry equal to 1 colored either red or blue, with row sum vector $\alpha$ and column sum vector $\beta$.

Theorem. $$f(\alpha,\beta) \leq f((n,n,\dots,n),(m,m,\dots,m)).$$

Proof. Let $g(\alpha,\beta)$ be the number of $m\times n$ matrices with entries $-2,0,2$, and with each entry equal to 0 colored either red or blue, with row sum vector $\alpha$ and column sum vector $\beta$. By dividing each entry of such a matrix by 2 and then adding 1, it is clear that $$f(\alpha,\beta)=g\left(2\alpha-2(n,\dots,n), 2\beta-2(m,\dots,m)\right).$$ Hence we want to show that $$g(\alpha,\beta) \leq g((0,0,\dots,0),(0,0,\dots,0)).$$

We have for fixed $m,n$ that $$\sum_{\alpha,\beta} g(\alpha,\beta)x^\alpha y^\beta = \prod_{r=1}^m\prod_{s=1}^n (x_r^{-1}y_s^{-1}+x_ry_s)^2.$$ Since for any integer $k$ we have $\int_0^{2\pi}e^{ikx}dx = 1$ if $k= 0$ and otherwise is $0$, it follows that $$g(\alpha,\beta) = \frac{1}{(2\pi)^{m+n}} \int_0^{2\pi}\cdots \int_0^{2\pi} e^{-i(\alpha_1 \theta_1+\cdots+ \alpha_m\theta_m+\beta_1\psi_1+\cdots+\beta_n\psi_n)}\\ \prod_{r=1}^m\prod_{s=1}^n (e^{-i(\theta_r+\psi_s)} +e^{i(\theta_r+\psi_s)})^2\,d\theta\,d\psi.$$ Now $(e^{-i(\theta_r+\psi_s)}+e^{i(\theta_r+\psi_s)})^2$ is a nonnegative real number. Hence by the triangle inequality, \begin{eqnarray*} g(\alpha,\beta) & \leq & \frac{1}{(2\pi)^{m+n}} \int_0^{2\pi}\cdots \int_0^{2\pi} \prod_{r,s=1}^n (e^{-i(\theta_r+\psi_s)} +e^{i(\theta_r+\psi_s)})^2\,d\theta\,d\psi\\ & = & g((0,\dots,0),(0,\dots,0)).\ \Box \end{eqnarray*}