¿Cuál es el mayor número posible de términos distinto de cero en un determinante de una matriz con exactamente $N$ ceros?

Question

Supongamos que tenemos una $n \times n$ matriz y sabemos que hay exactamente $N$ cero entradas. El factor determinante es la suma de $n!$ términos, cada uno formado por la selección de exactamente una entrada de cada fila y columna y la multiplicación de ellos. Si un determinado término proviene de la selección de uno o más ceros entonces que el término se convierte en cero. Esto plantea la cuestión de cómo muchos de los términos puede ser distinto de cero.

Intuitivamente me imagino que el número máximo se logra si tomamos una matriz de todos los $1$s y empezar a poner en ceros, comenzando con las entradas de $(1,2), (1,3), \ldots, (1,n)$ por lo que el único distinto de cero de entrada en esa línea es en $(1,1)$, y, a continuación, pasar a la siguiente fila y poner ceros en $(2,1), (2,3), \ldots, (2,n)$ por lo que el único distinto de cero de entrada en esa línea es en $(2,2)$, y así sucesivamente hasta que se nos está llenando de ceros en la última fila de a $(n,1), (n,2), \ldots, (n,n-1)$. En esta etapa tenemos la matriz de identidad y no es exactamente un término distinto de cero.

Me imagino que esto ya se ha probado en alguna parte, pero no puede encontrar una buena referencia. Podría alguien por favor provea una prueba, o mejor aún, un libro donde esto está demostrado, como parte de un más amplio de la teoría? Lo ideal es algo más elegante que la inducción?

Answer 1

Sí, el número máximo de ceros que pueden ocurrir sin que el determinante es cero $N=n(n-1)$. Si hay más de $n(n-1)$ ceros, entonces hay menos de $n$ cero entradas y así hay al menos una columna que contiene sólo el cero de entradas, y por lo que el determinante es cero.

Una pregunta relacionada es la forma de maximizar el número de no-cero términos del determinante cuando se $N=n$ es decir $n \times n$ matriz contiene exactamente $n$ cero términos.

El valor de cada término en el factor determinante de la suma es el producto de las entradas a lo largo de la diagonal principal en una de las $n!$ matrices que son el resultado de una permutación de las columnas (o filas) de la matriz original. Esto pasa por alto un factor de $\pm 1$, pero para los propósitos de la cuenta no sea cero, esto es irrelevante.

Si tenemos un cero en cada fila y en cada columna (por ejemplo, el $n$ ceros se encuentran a lo largo de una diagonal), a continuación, un cero a plazo se producirá si la permutación de las columnas pone cualquier columna en la posición donde su cero en la diagonal principal. Por otro lado, un no-cero término ocurrirá si cada columna está en uno de los otros $n-1$ posiciones donde su es cero fuera de la diagonal principal.

De la $n!$ permutaciones de columnas hay $!n$ (sub-factorial de $n$) en los que no cero se encuentra en la diagonal principal donde

$!n = n! \sum_{i=0}^{i=n} \frac{(-1)^i}{i!}$

debido a que este es el mismo que el recuento de los trastornos de $n$.

Creo que este es el que maximiza el número de no-cero términos y minimiza el número de cero términos. Si dos ceros se encuentran en la misma fila o columna, a continuación, creo que el número de cero términos aumenta.