Combinaciones de $(0,1)$-Matrices con igual suma de filas y columnas

Question

Considere un $(2n\times2n)$ - Matriz con elementos de $\{0,1\}$. Las sumas de filas y columnas deben ser iguales a$n$para cada fila y suma respectivamente. Aquí hay un ejemplo para$n=2$:

$$ \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} $$ Cómo encontrar el número de todas estas matrices que dependen de $n$?

Answer 1

Lo que sigue son mis propios intentos (A), y una referencia (B) que encontré después dando de hecho la respuesta.

A) Mis propios intentos:

Consideremos el caso $n=2$ (presentación extensible al caso general):

Empezar con

$$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)$$ y considerar las multiplicaciones de izquierda y derecha $JAK$ de $A$ por matrices de permutación $J$ y $K$.

Usando este principio, he podido construir un programa que produce lo siguiente $18$ matrices para el caso $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) $$ Pero el problema es que, debido a$\det(A)=0$, todas las matrices que hemos generado de esta manera tienen también un determinante cero ... Y peor que eso, algunas matrices con determinante cero, como: $$ \Bigl(\begin{smallmatrix} 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1 \end{smallmatrix} \Bigr)$$

no están en la lista anterior.

De hecho, hay un total de $90$ $4 \times 4$ (0-1) matrices con dos $1$s en cada fila y / o columna.

Y hay tantos como $297200$ $6 \times 6$ (0-1) matrices con tres $1$s en cada fila y / o columna.

Estos valores se han encontrado en las siguientes referencias:

http://oeis.org/A008300y http://oeis.org/A001499, http://oeis.org/A001501, http://oeis.org/A058528, http://oeis.org/A075754, y más en general http://oeis.org/wiki/Index_to_OEIS:_Section_Mat#binmat

B) Unas horas más tarde, encontré un documento escrito por Odama, Yumi y Musiker, Gregg: "Enumeración de (0,1) y matrices enteras doblemente estocásticas" (diciembre de 2001), en Science Direct dando una fórmula general basada en particiones de entero$N=2n$. Uno encuentra (página 2) casos particulares comprensibles mientras que la fórmula general es muy difícil de entender.

Más tarde, descubrí aquí la agradable propiedad de que tales matrices son la suma de$n$ matrices de permutaciones, con una conexión natural con grafos bipartitos regulares.

Para una interesante "Clasificación de matrices pequeñas (0-1)", vea aquí un documento con este título de Miodrag Zivkovic; vea también el documento muy denso aquí