Combinaisons de $(0,1)$-Matrices à somme égale en ligne et en colonne
Considérez un $(2n\times2n)$ - Matrice avec des éléments de $\{0,1\}$. Les sommes des lignes et des colonnes doivent être égales à$n$pour chaque ligne et somme respectivement. Voici un exemple de$n=2$:
$$ \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} $$ Comment trouver le nombre de toutes ces matrices dépendant de $n$?
Réponses
Ce qui suit est mes propres tentatives (A), et une référence (B) que j'ai trouvée par la suite donnant en fait la réponse.
A) Mes propres tentatives:
Considérons le cas $n=2$ (présentation extensible au cas général):
Commencer avec
$$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)$$ et considérez les multiplications à gauche et à droite $JAK$ de $A$ par matrices de permutation $J$ et $K$.
En utilisant ce principe, j'ai pu construire un programme criant ce qui suit $18$ matrices pour le cas $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) $$ Mais le problème est que, en raison de$\det(A)=0$, toutes les matrices que nous avons générées de cette manière ont aussi un déterminant nul ... Et pire que cela, certaines matrices avec un déterminant nul, comme: $$ \Bigl(\begin{smallmatrix} 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1 \end{smallmatrix} \Bigr)$$
ne figurent pas dans la liste ci-dessus.
En fait, il y a un total de $90$ $4 \times 4$ (0-1) matrices avec deux $1$s sur chaque ligne et / ou colonne.
Et il y en a autant que $297200$ $6 \times 6$ (0-1) matrices avec trois $1$s sur chaque ligne et / ou colonne.
Ces valeurs ont été trouvées dans les références suivantes:
http://oeis.org/A008300, et http://oeis.org/A001499, http://oeis.org/A001501, http://oeis.org/A058528, http://oeis.org/A075754, et plus généralement http://oeis.org/wiki/Index_to_OEIS:_Section_Mat#binmat
B) Quelques heures plus tard, j'ai trouvé un document rédigé par Odama, Yumi et Musiker, Gregg: "Enumeration of (0,1) and Integer Doubly Stochastic Matrices" (décembre 2001), sur Science Direct donnant une formule générale basée sur des partitions de entier$N=2n$. On trouve (page 2) des cas particuliers compréhensibles alors que la formule générale est très difficile à comprendre.
Plus tard, j'ai découvert ici la belle propriété que de telles matrices sont la somme de$n$ matrices de permutations, avec une connexion naturelle avec des graphes bipartis réguliers.
Pour une intéressante "Classification des petites matrices (0-1)", voir ici un document avec ce titre de Miodrag Zivkovic; voir aussi le document très dense ici