Kombinacje $(0,1)$-Matryce z równą sumą wierszy i kolumn

Question

Rozważ a $(2n\times2n)$ - Macierz z elementami z $\{0,1\}$. Sumy wierszy i kolumn muszą być równe$n$odpowiednio dla każdego wiersza i sumy. Oto przykład$n=2$:

$$ \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} $$ Jak znaleźć liczbę wszystkich tych macierzy zależnych od $n$?

Answer 1

Poniżej znajdują się moje własne próby (A) i odniesienie (B), które znalazłem później, faktycznie udzielając odpowiedzi.

A) Moje własne próby:

Rozważmy przypadek $n=2$ (prezentacja rozszerzalna na przypadek ogólny):

Zacząć od

$$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)$$ i rozważ mnożenie z lewej i prawej strony $JAK$ z $A$ przez macierze permutacji $J$ i $K$.

Korzystając z tej zasady, udało mi się zbudować program składający się z następujących elementów $18$ matryce do sprawy $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) $$ Ale problem polega na tym, że z powodu$\det(A)=0$, wszystkie wygenerowane w ten sposób macierze mają również wyznacznik zerowy ... A co gorsza, niektóre macierze z wyznacznikiem zerowym, takie jak: $$ \Bigl(\begin{smallmatrix} 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1 \end{smallmatrix} \Bigr)$$

nie ma na powyższej liście.

W rzeczywistości jest ich w sumie $90$ $4 \times 4$ (0-1) macierze z dwoma $1$s w każdym wierszu i / lub kolumnie.

A jest ich aż $297200$ $6 \times 6$ (0-1) macierze z trzema $1$s w każdym wierszu i / lub kolumnie.

Wartości te zostały znalezione w następujących odniesieniach:

http://oeis.org/A008300, i http://oeis.org/A001499, http://oeis.org/A001501, http://oeis.org/A058528, http://oeis.org/A075754i bardziej ogólnie http://oeis.org/wiki/Index_to_OEIS:_Section_Mat#binmat

B) Kilka godzin później znalazłem dokument autorstwa Odamy, Yumi and Musiker, Gregg: „Enumeration of (0,1) and Integer Doubly Stochastic Matrices” (grudzień 2001), w Science Direct podający ogólny wzór oparty na partycjach liczba całkowita$N=2n$. Znaleziono (strona 2) zrozumiałe szczególne przypadki, podczas gdy ogólny wzór jest bardzo trudny do zrozumienia.

Później odkryłem tutaj ładną właściwość, której sumą są takie macierze$n$ macierze permutacji, z naturalnym połączeniem z regularnymi grafami dwudzielnymi.

Za ciekawą „Klasyfikacji małych (0-1) macierzy”, patrz tutaj dokument z tego tytułu przez Miodrag Zivkovic; zobacz również bardzo obszerny dokument tutaj