Combinatoria y Matrices

Question

Encuentre el número de $4\times4$ matrices tales que $|a_{ij}| = 1 \forall i,j\in[1,4]$ y la suma de cada fila y columna es cero.

He probado a "contar" el número de matrices que cumplen las condiciones anteriores, es decir, los elementos son $1$ o $-1$ y la suma de cada fila y columna es cero.

En el intento de generar una recursión empecé con un $2\times2$ matriz, para cuyo caso la respuesta es $2$ . (El primer elemento es 1 o -1, los demás elementos se deciden en consecuencia) Sin embargo, este método se vuelve engorroso y matemáticamente decepcionante para $3x3$ y matrices más grandes.

¿Podría alguien explicar el método o publicar una solución al problema? ¿Es posible generalizar el resultado a una matriz nxn?

Answer 1

La primera fila tiene dos $1$ s y dos $-1$ s. Hay $\binom{4}{2} = 6$ formas en que se pueden organizar en la primera fila. Contaremos el número de matrices con primera fila $(1,1,-1,-1)$ y multiplicar por $6$ para dar cuenta de todos los demás arreglos de la primera fila.

La segunda fila puede ser una de las tres cosas siguientes: $(1,1,-1,-1)$ o $(-1,-1,1,1)$ o $(1,-1,1,-1)$ . En el tercer caso esto cuenta para $4$ posibilidades: las dos primeras columnas pueden estar cambiadas, o las dos últimas pueden estar cambiadas. Contaremos el número de matrices en cada uno de estos tres casos (multiplicando la cuenta del tercer caso por $4$ para tener en cuenta los interruptores).

Caso 1: La matriz tiene el siguiente aspecto $$ \begin{pmatrix} 1 & 1 & -1 & -1 \\ 1 & 1 & -1 & -1 \\ * & * & * & * \\ * & * & * & * \end{pmatrix} $$ Sólo hay una matriz posible: $$ \begin{pmatrix} 1 & 1 & -1 & -1 \\ 1 & 1 & -1 & -1 \\ -1 & -1 & 1 & 1 \\ -1 & -1 & 1 & 1 \\ \end{pmatrix} $$

Caso 2: La matriz tiene el siguiente aspecto $$ \begin{pmatrix} 1 & 1 & -1 & -1 \\ -1 & -1 & 1 & 1 \\ * & * & * & * \\ * & * & * & * \end{pmatrix} $$ En las dos últimas filas, hay precisamente una $-1$ en cada columna y dos $-1$ s en cada fila. Hay $\binom{4}{2}=6$ formas de elegir las ubicaciones de dos $-1$ s en la tercera fila; luego se determina la cuarta fila (tiene $-1$ s en las posiciones complementarias).

Caso 3: La matriz tiene el siguiente aspecto $$ \begin{pmatrix} 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ * & * & * & * \\ * & * & * & * \end{pmatrix} $$ Se determinan la primera y la última columna: $$ \begin{pmatrix} 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ -1 & * & * & 1 \\ -1 & * & * & 1 \end{pmatrix} $$ Hay dos soluciones: el bloque restante puede ser $\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}$ o lo contrario. Eso da dos soluciones cuando la segunda fila es como se muestra, pero debido a la posibilidad de cambiar las dos primeras o las dos últimas columnas, contamos $8$ soluciones.

Subtotal: Con esta primera fila, tenemos $1+6+8=15$ matrices.

Total: Hay $6$ arreglos equivalentes de la primera fila, por lo que tenemos $6 \cdot 15 = 90$ matrices en total.

Parece poco probable que este tipo de enfoque pueda generalizarse a matrices más grandes.

Answer 2

Esto es bastante difícil de generalizar a un $n \times n$ matriz. Yo sugeriría generalizar a tener dos $1$ en cada fila y columna de un $n \times n$ matriz, como se hace es problema $8$ de la combinatoria en Febrero 2012 HMMT . La recursión desarrollada en la solución oficial resuelve su problema para $n=4$ .

También hay una forma algo más sencilla de contarlo constructivamente para el $4 \times 4$ problema. Primero dividimos los tipos en dos casos.

La primera es cuando tenemos dos pares de columnas coincidentes, como $$\begin{bmatrix} 1 & -1 & 1 & -1 \\ 1 & -1 & 1 & -1 \\ -1 & 1 & -1 & 1 \\ -1 & 1 & -1 & 1 \end{bmatrix}$$ Podemos contar cuántas hay eligiendo primero dos $1$ de $4$ espacios para la primera columna, y luego $1$ del siguiente $3$ para replicar la primera columna. $$\binom{4}{2} \binom{3}{1} = 18$$

El segundo caso es cuando no tenemos columnas repetidas, ya que $$\begin{bmatrix} 1 & -1 & \color{red}1 & -1 \\ 1 & \color{red}1 & -1 & -1\\ -1 & \color{red}1 & -1 & 1\\ -1 & -1 & \color{red}1 & 1 \end{bmatrix}$$ De nuevo podemos empezar a contarlas eligiendo dos $1$ de $4$ espacios para la primera columna. Entonces tenemos dos opciones para emparejar el $1$ en las columnas que comparten un $1$ fila con la primera columna, que se representa en rojo para facilitar su visualización. Finalmente tenemos $3!$ formas de organizar las tres segundas columnas. Al multiplicarlas, tenemos $$\binom{4}{2} \cdot 2 \cdot 3! = 72$$ Y finalmente sumamos los dos casos para obtener $18+72 = \color{red}{90}$ .

Answer 3

Y aquí está un recorrido por la solución HMMT para la versión generalizada, para la posteridad y para la comprensión.

El planteamiento del problema es ahora el siguiente: "Encontrar la cantidad de $n \times n$ existen matrices para las que todas las columnas y filas contienen exactamente dos $1$ y el resto de números son $-1$ 's"

En el primer párrafo se explica un concepto importante, vital para la solución del problema, que tiene que ver con los ciclos. Un ciclo de longitud $n$ es una permutación de objetos $a_i$ donde $a_{k_1}$ mapas a $a_{k_2}$ , $a_{k_2}$ mapas a $a_{k_3}$ y así sucesivamente hasta que tengamos $a_{k_n}$ volver a asignar a $a_{k_1}$ donde todos $n$ $k_i$ son distintos.

Ahora, cuando miramos el $n \times n$ matriz coloreada teniendo en cuenta los ciclos. Podemos ver que existen partes de la matriz que trazan un camino que corresponde a un ciclo. Como ejemplo, esta $5 \times 5$ contiene dos ciclos. Uno de longitud $2$ y uno de longitud $3$ . $$\begin{bmatrix} \color{blue}1 & \color{blue}1 & -1 & -1 & -1 \\ -1 & \color{blue}1 & -1 & \color{blue}1 & -1 \\ -1 & -1 & \color{red}1 & -1 & \color{red}1 \\ \color{blue}1 & -1 & -1 & \color{blue}1 & -1 \\ -1 & -1 & \color{red}1 & -1 & \color{red}1 \end{bmatrix}$$ Para un $n \times n$ matriz, podemos contar el número de formas de crear la matriz creando un $k$ ciclo de tamaño y luego rellenar el resto con un $(n-k) \times (n-k)$ matriz. Si denotamos el número de matrices de tamaño $n \times n$ como $f(n)$ como se hace en la solución HMMT, podemos sumar sobre todos los ciclos de longitudes diferentes (de longitudes al menos $2$ ) para obtener $$f(n) = \sum_{k=2}^n a_kf(n-k) \tag{1}$$ Dónde $a_k$ es el número de formas de crear un $k$ ciclo en un $n \times n $ matriz. Así que ahora debemos encontrar $a_n$ . La forma más fácil de hacerlo es como se hace en la solución HMMT. Mirando la primera columna, tenemos $\binom{n}{2}$ formas de elegir las dos primeras casillas. Ahora elegimos la segunda columna. Hay $n-1$ formas de elegir la segunda columna, y $n-2$ formas de elegir el segundo $1$ en esa columna (si $n>2$ ). Entonces $n-2$ formas de elegir la tercera columna y $n-3$ formas de elegir el segundo $1$ en esa columna (si $n>3$ ). Obsérvese que partimos de una sola de las dos casillas de la primera columna para evitar un recuento excesivo.

Podemos ver que este patrón continúa hasta que elegimos la última columna de $n-k+1$ columnas restantes, y el segundo cuadrado debe alinearse con el otro de los dos primeros cuadrados. Así tenemos la fórmula $$a_k = \frac{n(n-1)}{2} \times (n-1)(n-2) \times ... \times (n-k+1) = \frac{n!(n-1)!}{2(n-k)!(n-k)!} \tag{2}$$ Combinando $(1)$ y $(2)$ obtenemos la fórmula de la solución oficial $$f(n) = \sum_{k=2}^{n}\frac{1}{2} f(n-k) \frac{n!(n-1)!}{(n-k)!(n-k)!}$$ A continuación, un poco de reordenación para obtener $$\frac{2nf(n)}{n!n!} = \sum_{k=2}^{n} \frac{f(n-k)}{(n-k)!(n-k)!}$$ Y, por último, un truco para deshacerse de la suma $$\frac{2nf(n)}{n!n!} - \frac{2(n-1)f(n-1)}{(n-1)!(n-1)!} = \sum_{k=2}^{n} \frac{f(n-k)}{(n-k)!(n-k)!} - \sum_{k=2}^{n-1} \frac{f(n-k)}{(n-k)!(n-k)!} \\ \frac{2nf(n)}{n!n!} - \frac{2(n-1)f(n-1)}{(n-1)!(n-1)!}=\frac{f(n-2)}{(n-2)!(n-2)!}$$ Finalmente, multiplicando cada lado por $n!n!/2n$ obtenemos nuestra recursión para la solución del problema generalizado. $$f(n) = (n)(n-1)f(n-1) + \frac{n(n-1)^2}{2}f(n-2)$$ Y aplicando esto, con $f(1) = 0$ y $f(2) = 1$ obtenemos los siguientes resultados, entre ellos $90$ para $n=4$ como era de esperar. $$f(3) = 6$$ $$\color{red}{f(4) = 90}$$ $$f(5) = 2040$$ $$f(6) = 67950$$ Y aquí está la secuencia de la OEIS https://oeis.org/A001499