Determinante de la matriz booleana de $5 \times 5$

Question

Considerar el conjunto de matrices de #% de #% de % de $5 \times 5$ entradas iguales a $10$ y el otro $1$ las entradas igual a $15$. Me gustaría saber cuántos tales matrices con determinante distinto de cero. ¿Hay una manera de caracterizarlos?

Había experimentado un poco con algunos ejemplos, pero no podía hacer mucho progreso.

Answer 1

Esto no escala bien, pero debe correr rápidamente en nada a a $8\times 8$ matrices en hardware moderno.

Deje $D([k_1,k_2,\ldots,k_n])$ de rendimiento de un histograma de los factores determinantes de una $n\times n$ matriz que contiene $k_1$ $1$'s en su primera columna, $k_2$ $1$'s en su segunda columna, ..., y $k_n$ $1$'s en su $n$ésima columna. Naturalmente, hay ${n \choose k_1} {n \choose k_2} \cdots {n \choose k_m}$ tales matrices.

Para $n = 2$, $$D([0,0]) = \left\{ 0: 1 \right\}$$ $$D([0,1]) = \left\{ 0: 2 \right\}$$ $$D([0,2]) = \left\{ 0: 1 \right\}$$ $$D([1,0]) = \left\{ 0: 2 \right\}$$ $$D([1,1]) = \left\{ -1: 1, 0: 2, 1: 1 \right\}$$ $$D([1,2]) = \left\{ -1: 1, 1: 1 \right\}$$ $$D([2,0]) = \left\{ 0: 1 \right\}$$ $$D([2,1]) = \left\{ -1: 1, 1: 1 \right\}$$ $$D([2,2]) = \left\{ 0: 1 \right\}$$

Para cada una de las $n$ $3$ $n_{\max}$donde $n_{\max}$ es el tamaño de la matriz completa (5, en su caso):

1. generar todos los pares $(k_1,k_2)$ con $0 \leq k_1 \leq n$, $0 \leq k_2 \leq n\left(n-1\right)$ tal que $k_1 + k_2 \leq n_1$ donde $n_1$ es el número de 1's en la matriz (10 en su caso).
2. para cada una de las $k_1$, producir $R(n,k_1)$, el conjunto de todos los $n$-elemento vectores fila que contenga $k_1$ 1 $n-k_1$ 0.
3. para cada una de las $k_2$, producir $B(n,k_2)$, el conjunto de todos los $n$-elemento vectores fila cuyos elementos son enteros no negativos que se suma a $k_2$.

4. para cada una de las $(k_1,k_2)$ par

   yo. para cada una de las $r \in R(n,k_1)$ y cada una de las $b \in B(n,k_2)$

   1. Deje $r$ ser la fila superior de una matriz y deje $b$ el número de $1$'s en las columnas de la $\left( n-1\right) \times n$ submatriz debajo de la primera fila. Por ejemplo, $r = [1,1,0]$, $b = [2,0,1]$ habría una fila superior de $[1\; 0\; 1]$ dos $1$'s en la primera columna en la primera fila, cero $1$'s en la segunda columna en la primera fila, y uno de los $1$ en la tercera columna en la primera fila.

   2. Suponga que tiene la matriz $$\left(\begin{array}[c] & 1 & 1 & 0 \\ \times & \times & \times \\ \times & \times & \times \end{array}\right)$$ with $b = [2,0,1]$. The histogram of all determinants for matrices of this type is given by $$H = 1\cdot D([0,1]) - 1\cdot D([2,1]) + 0\cdot D([2,0])$$ Since these are histograms, scalar multiplication by $0$ means moving all counts into the $0$ bin, scalar multiplication by $-1$ significa la negación de las papeleras, y además se logra a través de la convolución. (Si alguien sabe cómo esta palabra mejor, por favor editar).

   3. Agregar el histograma $H$ (2) para una lista asociada con el vector $r+b$. Por ejemplo, la anterior $H$ se añadirá a la lista de asociados con $[3,1,1]$.

   ii. Calcular $D(x)$ todos los $n$-elemento de los vectores $x$ dejando $D(x)$ ser la suma (convolución) de todos los histogramas de la lista asociada con $x$.

La suma de $D(x)$ $n_{\max}$- elemento de los vectores $x$ se obtiene el determinante de histograma para una $n_{\max}\times n_{\max}$ matriz. El número de matrices con determinante cero será el recuento en el $0$ de reciclaje; el número de matrices con determinante distinto de cero será la suma de la cuenta en el resto de la basura. Obviamente, los dos deben sumar a $n_{\max}^2 \choose n_1$.

Answer 2

He examinado la matrices de #% de $2^9=512$% #%. Toda posible distribución de $3\times 3$s y $0$s. Los resultados se resumen en esta matriz $$ \left (\begin{array}{c|ccccc} 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 9 & 0 & 0 \\ 2 & 0 & 0 & 36 & 0 & 0 \\ 3 & 0 & 3 & 78 & 3 & 0 \\ 4 & 0 & 18 & 90 & 18 & 0 \\ 5 & 0 & 36 & 54 & 36 & 0 \\ 6 & 3 & 18 & 42 & 18 & 3 \\ 7 & 0 & 9 & 18 & 9 & 0 \\ 8 & 0 & 0 & 9 & 0 & 0 \\ 9 & 0 & 0 & 1 & 0 & 0 \\ \end{matriz} \right)$$ en la primera columna el número de $1$s; en las otras columnas de $1$ el número de matriz tiene determinante $5$

Por ejemplo matrices con $-2;\;-1;0;\;+1;\;+2$ $5$s y $1$ $4$s % determinante $0$son $0$ mientras que los determinantes $54$o $1$ $-1$.

¿Ves alguna regularidad?

Espero que esto ayude