Combinations of $(0,1)$-Matrices with equal row and colum sum

Question

Consider a $(2n\times2n)$ - Matrix with elements from $\{0,1\}$. Row and colum sums have to be equal to $n$ for each row and sum respectively. Here is an exampel for $n=2$:

$$ \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} $$ How to find the number of all these matrices dependent on $n$?

Answer 1

Such matrices have the nice property to be the sum of $n$ permutation matrices see here. This result being in connection with results on bipartite graphs.

Using this principle, I have built a Matlab program that computes the number of such matrices in the cases $n=2$ and $n=3$ ($6 \times 6$ matrices). See at the bottom.

• for $n=1$: 2 matrices.

• for $n=2: 90 $ matrices (computation time with my program: a millisecond), a value that can be found here: http://oeis.org/A001499.

• for $n=3: 297200 $ matrices! (computing time with my program: about an hour on my slow PC). This value can be found here: http://oeis.org/A001501.

The general case is evidently out of reach with this kind of methods. One finds in the "litterature":

• for $n=4$: $116963796250$ matrices (see http://oeis.org/A058528).

• for $n=5$: $6736218287430460752$ matrices (see http://oeis.org/A075754).

The following references on OEIS site are connected to this issue:

http://oeis.org/A008300, and http://oeis.org/wiki/Index_to_OEIS:_Section_Mat#binmat

Later on, I found this document authored by Odama, Yumi and Musiker, Gregg: "Enumeration of (0,1) and Integer Doubly Stochastic Matrices" (December 2001), on Science Direct giving a general formula based on partitions of integer $N=2n$. One finds (page 2) understandable particular cases whereas the interpretation of the general formula is pretty hard.

For further reading, in particular a classification of (0-1) matrices up to row and column permutations: see here and here ; see as well the very dense document here.

Matlab program:

clear all;
n=3;m=2*n;% 
p=m^2-1;
f=factorial(m);
I=eye(m);
Pe=perms(1:m);% all permutations of 1...2n.
for P=1:f
    M=I(:,Pe(P,:));% The P-th permutation matrix, stored
    T(:,P)=M(:); % vertically as the P-th column of T
end;
S=[];
V=2.^(0:p);% V*M yields a (binary) coding (see below)
for P=1:f;
  for Q=P+1:f;
    U=T(:,P)+T(:,Q);
    if all(U<2)
       for R=Q+1:f
          M=U+T(:,R);
          if all(M<2);
              S=[S,V*M];
          end;
       end;
    end;
end;
S=unique(S);
end;
L=length(S)