4
$\begingroup$

(asked by Shanzhen Gao, shanzhengao at yahoo.com, on the Q&A board at JMM)

Is there a closed formula for the number of n×n (0,1)-matrices with column sum 4, row sum 4, and trace 0?

$\endgroup$
1
  • $\begingroup$ Did you leave out the word "symmetric" on purpose? $\endgroup$ Feb 23, 2014 at 23:38

2 Answers 2

9
$\begingroup$

A formula (due to Musiker and Odama) for the number of $n\times n$ (0,1)-matrices with line sum 4 appears on page 5 of the first link at http://www.mtholyoke.edu/courses/gcobb/REU_MCMC/papers.html. The technique can easily be modified to give a formula for the trace 0 case.

$\endgroup$
2
$\begingroup$

This is somewhat of an ill-posed question, since "closed" is a very vague term. See: H. S. Wilf, `What is an answer?', Amer. Math. Monthly 89 (1982), 289-292.

A $k \times n$ Latin rectangle is an $k \times n$ matrix with symbols from $\mathbb{Z}_n$ in which each symbol occurs exactly once in each row and at most once in each column. A Latin rectangle is called normalised if its first row is $(0,1,\ldots,n-1)$. Given a $5 \times n$ normalised Latin rectangle $L=(l_{ij})$ we can construct a $n \times n$ $(0,1)$-matrix $T=(t_{ij})$ by setting $t_{ij}=1$ if symbol $j$ appears in column $i$ of $L$ (and $t_{ij}=0$ otherwise). We see that every row and every column of $T$ contains exactly $5$ copies of the symbol $1$. Moreover, since $L$ is normalised, $t_{ii}=1$ for all $i \in \mathbb{Z}_n$. Let $T'$ be formed from $T$ by setting main diagonal of $T$ to $(0,0,\ldots,0)$. Then $T'$ contains row sum $4$ and column sum $4$ and trace $0$.

Let $X_{4,n}$ be the number of $n \times n$ $(0,1)$-matrices with column sum 4 and row sum 4 and trace $0$. It is a well-known result that each $(0,1)$-matrix counted by $X_{4,n}$ can be formed as $T'$ for some normalised $5 \times n$ Latin rectangle (from Hall's Marriage Theorem). We conclude that $X_{4,n} \leq K_{5,n}$, where $K_{5,n}$ is the number of normalised $5 \times n$ Latin rectangles. Erdos and Kaplansky showed that $K_{5,n} \sim n!^4 e^{-10}$ (although you can expect $X_{4,n}$ to be much less than this).

There are several published formulae for the number of Latin rectangles (in fact, I have a paper on this topic). There's a good chance that modifying one of these formulae would yield a formula for $X_{4,n}$. One good example is by Doyle: http://arxiv.org/abs/math/0703896.

In addition, there is a easy graph theoretic interpretation of $X_{4,n}$. Let $G$ be the complete bipartite graph with bipartition $\{v_1,v_2,\ldots,v_n\} \cup \{u_1,u_2,\ldots,u_n\}$. Then $X_{4,n}$ is the number of $4$-regular subgraphs $H$ of $G$ minus the one-factor $\{v_i u_i\}_{1 \leq i \leq n}$ (on the same vertex set as $G$). Given such a subgraph $H$, let $X=(x_{ij})$ be defined by $x_{ij}=1$ if $v_i$ is adjacent to $u_j$ in $H$.

$\endgroup$
1
  • $\begingroup$ Interesting. I would've said that X_{4,n} is the number of labeled directed graphs such that each vertex has indegree and outdegree 4 (is this what "regular" means for directed graphs?) and with no multiple edges or self-loops. $\endgroup$ Jan 18, 2010 at 13:35

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.