Para un $n\times n$ matriz $A$ con entradas de $\{0,1\}$ . ¿Cuál es el número máximo de 1's tal que $A$ ¿es invertible?
Si $n=2$ la respuesta es $3$ .
Si $n=3$ la respuesta es $7$ . ¿Existe una fórmula para el $n$ ?
Respuesta
¿Demasiados anuncios?
Evidentemente, la respuesta no puede ser superior a $n^2 - n + 1$ ya que de lo contrario habrá al menos dos filas que contengan sólo 1's y por lo tanto el determinante se convertirá en 0.
Este límite se puede obtener, de la siguiente manera: Sea $a_{ij}$ sea cero si i=j > 1 para los elementos $a_{ij}$ de A.
Está claro que esto sólo ha $n-1$ ceros.
Número de permutaciones en este cuyo producto es distinto de cero = número de derivaciones en $n-1$ elementos, que es impar. (considere la fórmula para el número de derivaciones, $n!/k!$ es incluso ser divisible por $(n-k)!$ para todos los términos, excepto cuando $k=n$ ). Así que el determinante no puede ser cero ya que es la suma de un número de términos impar cuyo valor es $+/-1$ .
Por lo tanto, tiene un determinante distinto de cero y, por lo tanto, es invertible.
EDIT: El número de permutaciones no es directamente igual al número de derivaciones para n-1, pero utilizando la misma lógica que en la derivación de la fórmula para el número de derivaciones, podemos obtener la siguiente fórmula:
$\sum_{k=1}^{n-1} (-1)^k (n-1)!(n-k)/k!$ . Para k hasta n-3, $(n-1)!/k!$ está en paz. Para $k=n-2$ , $n-k$ está en paz. Esto deja sólo el último término con k=n-1, que es 1 y por lo tanto impar.
