Matriz de densidad con inverso completo

Question

¿Cuál es la sparsest matriz en $\mathbb R^{n,n}$ tal que el inverso es completo?

I. e. Estoy buscando una matriz de $A\in \mathbb R^{n,n}$ con tan pocos no-cero entradas como sea posible, de tal manera que $A^{-1}$ no tiene ceros.

La mejor que pude encontrar fue $$ A = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 & 1 \\ 0 & 1 & 1 & 0 & \cdots & 0 \\ \vdots & & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1 & 1 \end{pmatrix}\in \mathbb R^{n,n}, $$ que ha $2n$ cero entradas. Su inversa es $$ A^{-1} =\frac12 \begin{pmatrix} 1 & 1 & -1 & \cdots & -1 & 1 \\ -1 & 1 & 1 & -1 & \cdots & -1 \\ \vdots & & \ddots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & \ddots & \ddots & \vdots \\ & \cdots & 1 & -1 & 1 & 1 \end{pmatrix}\in \mathbb R^{n,n}. $$ Ambas matrices son matrices de Toeplitz, yo no soy de los que en gran tex-ing matrices grandes.

Hay una matriz de con estas propiedades que tiene menos de $2n$ cero entradas. Si no ¿cómo se podría demostrar que $2n$ es la mejor posible?

Answer 1

$2n$ elementos de distinto de cero es el mínimo.

Supongamos que $A\in \mathbb R^{n,n}$ tiene menos de $2n$ elementos de distinto de cero. Entonces hay un % de fila $i$que contiene a más de un elemento. $A$ Es invertible, debe haber exactamente un elemento de esa fila (en la columna $j$) es distinto de cero. Podemos así encontrar matrices de permutación $P,Q$ tal que PAQ $$ = \left(\begin{array}{c|c} * & * \\ \hline 0& a_{ij} \end{array}\right). $$ Ahora, $PAQ$ es bloque triangular, por lo tanto es bloque triangular $(PAQ)^{-1}$ y $A^{-1} = Q (PAQ)^{-1}P$ contiene al menos $n-1$ ceros.