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)$?

  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Mar 16 '18 at 14:22
  • $\begingroup$ @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. $\endgroup$ – Brendan McKay Mar 16 '18 at 22:03
  • $\begingroup$ 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 $\endgroup$ – 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*}

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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