Kombinationen von $(0,1)$-Matrizen mit gleicher Zeilen- und Säulensumme

Question

Betrachten Sie a $(2n\times2n)$ - Matrix mit Elementen aus $\{0,1\}$. Zeilen- und Spaltensummen müssen gleich sein$n$für jede Zeile bzw. Summe. Hier ist ein Beispiel für$n=2$::

$$ \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} $$ Wie man die Anzahl all dieser Matrizen findet, hängt davon ab $n$?

Answer 1

Was folgt, sind meine eigenen Versuche (A) und eine Referenz (B), die ich später gefunden habe und die tatsächlich die Antwort gibt.

A) Meine eigenen Versuche:

Betrachten wir den Fall $n=2$ (Präsentation erweiterbar auf den allgemeinen Fall):

Beginnen mit

$$A=\left(\begin{array}{cc|cc} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ \end{array}\right)$$ und betrachte Links- und Rechtsmultiplikationen $JAK$ von $A$ durch Permutationsmatrizen $J$ und $K$.

Nach diesem Prinzip konnte ich ein Programm erstellen, das Folgendes enthält $18$ Matrizen für den Fall $n=2$.

$$ \Bigl(\begin{smallmatrix} 1& 1& 0& 0\\ 1& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& 1 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 1& 0& 1\\ 0& 1& 0& 1\\ 1& 0& 1& 0\\ 1& 0& 1& 0 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 1& 1& 0\\ 0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 0& 1& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1\\ 1& 1& 0& 0 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 1& 0& 0& 1 \end{smallmatrix} \Bigr)$$ $$ \Bigl(\begin{smallmatrix} 0& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 1& 0& 0\\ 0& 0& 1& 1 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 1& 0& 1\\ 1& 0& 1& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 0& 1& 1& 0 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 1& 1& 0\\ 1& 0& 0& 1 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 1& 0& 1\\ 1& 0& 1& 0 \end{smallmatrix} \Bigr) \Bigl(\begin{smallmatrix} 1& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& 1\\ 1& 1& 0& 0 \end{smallmatrix} \Bigr)$$

$$ \bigl(\begin{smallmatrix} & 1& 0& 0& 1\\ & 0& 1& 1& 0\\ & 1& 0& 0& 1\\ & 0& 1& 1& 0 \end{smallmatrix} \bigr) \bigl(\begin{smallmatrix} & 1& 0& 1& 0\\ & 0& 1& 0& 1\\ & 1& 0& 1& 0\\ & 0& 1& 0& 1 \end{smallmatrix} \bigr) \bigl(\begin{smallmatrix} & 1& 1& 0& 0\\ & 0& 0& 1& 1\\ & 1& 1& 0& 0\\ & 0& 0& 1& 1 \end{smallmatrix} \bigr) \bigl(\begin{smallmatrix} & 1& 0& 0& 1\\ & 1& 0& 0& 1\\ & 0& 1& 1& 0\\ & 0& 1& 1& 0 \end{smallmatrix} \bigr) \bigl(\begin{smallmatrix} & 1& 0& 1& 0\\ & 1& 0& 1& 0\\ & 0& 1& 0& 1\\ & 0& 1& 0& 1 \end{smallmatrix} \bigr) \bigl(\begin{smallmatrix} & 0& 0& 1& 1\\ & 0& 0& 1& 1\\ & 1& 1& 0& 0\\ &1& 1& 0& 0 \end{smallmatrix} \bigr) $$ Aber das Problem ist, dass aufgrund$\det(A)=0$Alle Matrizen, die wir auf diese Weise erzeugt haben, haben auch eine Null-Determinante ... Und das Schlimmste ist, dass einige Matrizen mit einer Null-Determinante wie: $$ \Bigl(\begin{smallmatrix} 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1 \end{smallmatrix} \Bigr)$$

sind nicht in der Liste oben.

In der Tat gibt es insgesamt $90$ $4 \times 4$ (0-1) Matrizen mit zwei $1$s in jeder Zeile und / oder Spalte.

Und es gibt so viele wie $297200$ $6 \times 6$ (0-1) Matrizen mit drei $1$s in jeder Zeile und / oder Spalte.

Diese Werte wurden in den folgenden Referenzen gefunden:

http://oeis.org/A008300, und http://oeis.org/A001499, http://oeis.org/A001501, http://oeis.org/A058528, http://oeis.org/A075754und allgemeiner http://oeis.org/wiki/Index_to_OEIS:_Section_Mat#binmat

B) Einige Stunden später fand ich ein Dokument von Odama, Yumi und Musiker, Gregg: "Aufzählung von (0,1) und ganzzahligen doppelt stochastischen Matrizen" (Dezember 2001) auf Science Direct, das eine allgemeine Formel basierend auf Partitionen von ganze Zahl$N=2n$. Man findet (Seite 2) verständliche Sonderfälle, während die allgemeine Formel sehr schwer zu verstehen ist.

Später entdeckte ich hier die schöne Eigenschaft, dass solche Matrizen die Summe sind$n$ Permutationsmatrizen mit einer natürlichen Verbindung zu regulären zweigeteilten Graphen.

Für eine interessante "Klassifikation kleiner (0-1) Matrizen" siehe hier ein Dokument mit diesem Titel von Miodrag Zivkovic; siehe auch das sehr dichte Dokument hier