¿La inversa de una matriz invertible totalmente unimodular es también totalmente unimodular?

Question

Mi pregunta se aprende de aquí . Permítanme reafirmarlo de la siguiente manera:

A matriz unimodular $M$ es una matriz entera cuadrada que tiene el determinante $+1$ o $1$ . A matriz totalmente unimodular (matriz TU) es una matriz para la que cada submatriz cuadrada no singular es unimodular.

Ahora supongamos que un $n\times n$ matriz no sinular $A$ es totalmente unimodular. ¿Podemos demostrar que $A^{1}$ ¿también es totalmente unimodular? O si no es correcto, ¿podemos tener un contraejemplo? Cualquier ayuda es muy apreciada.

Editar : Lo que ya sé es que la afirmación es verdadera cuando $n=2$ y $3$ . Se deduce de la definición de matriz unimodular y del hecho de que si $A$ es unimodular, entonces $$A^{-1}=\det A\cdot \mathrm{adj}(A)=\pm \mathrm{adj}(A).$$

Answer 1

Tal y como comenta Jyrki Lahtonen, la afirmación es cierta y se desprende inmediatamente de la siguiente relación entre los menores de $A^{-1}$ y los menores de $A$ .

Propuesta : Si $A$ es un invertible $n\times n$ matriz, y si $i_1,\dots,i_n$ y $j_1,\dots,j_n$ sean dos permutaciones de $1,\dots,n$ entonces el menor de $A$ correspondiente a las filas $i_1,\dots,i_k$ y columnas $j_1,\dots,j_k$ , denotado por $d$ y el menor de $A^{-1}$ correspondiente a las filas $j_{k+1},\dots,j_n$ y columnas $i_{k+1},\dots,i_n$ , denotado por $d'$ , satisfacen que $$d=\pm d'\det A.$$

Prueba : Dejemos que $e_1,\dots,e_n$ sea una base de $\mathbb{R}^n$ y que $f_i= A e_i$ , $i=1,\dots,n$ . Entonces, por un lado, $$\omega:=Ae_{j_1}\wedge\cdots\wedge Ae_{j_k}\wedge e_{i_{k+1}}\wedge \cdots\wedge e_{i_n}=\pm d\cdot e_1\wedge\cdots\wedge e_n,$$ por otro lado, $$\omega=f_{j_1}\wedge\cdots\wedge f_{j_k}\wedge A^{-1}f_{i_{k+1}}\wedge \cdots\wedge A^{-1}f_{i_n}=\pm d'\cdot f_1\wedge\cdots\wedge f_n.$$ Desde $$f_1\wedge\cdots\wedge f_n=\det A\cdot e_1\wedge\cdots\wedge e_n,$$ la conclusión es la siguiente.

Answer 2

He aquí una prueba más elemental.

Teorema: La inversa de una matriz (no singular) totalmente unimodular es totalmente unimodular.

En la demostración se utilizarán los siguientes lemas.

Lema 1: La permutación de filas y columnas preserva la unimodularidad total.

Lema 2: Matriz $A$ es totalmente unimodular si y sólo si la matriz $$\begin{bmatrix} A & I \\ \end{bmatrix}$$ es totalmente unimodular (donde $I$ es la matriz de identidad del tamaño adecuado).

Lema 3: El operación de pivote preserva la unimodularidad total.

(Operación de pivote: elegir un elemento no nulo $a_{i,j}$ , llamado pivote. Multiplica el $i$ -ésima fila por un escalar para que el pivote se convierta en 1. A continuación, añada los múltiplos de la $i$ -a todas las demás filas para que todos los elementos de la columna $j$ excepto el pivote se convierten en 0.)

Prueba del teorema:

Dejemos que $A$ sea una matriz no singular totalmente unimodular. Por el lema 2, $\begin{bmatrix} A & I \end{bmatrix}$ es totalmente unimodular. Aplicando repetidamente las operaciones de pivote obtenemos $\begin{bmatrix} I & A^{-1} \end{bmatrix}$ (básicamente haciendo una eliminación gaussiana en $A$ ). Por el lema 3, esta matriz es totalmente unimodular, y por los lemas 1 y 2, $A^{-1}$ es totalmente unimodular. $\blacksquare$

---

Prueba del lema 1: Dejemos que $A$ sea totalmente unimodular, y que $\tilde A$ obtenido de $A$ permutando filas y columnas y que $\tilde B$ sea una submatriz cuadrada de $\tilde A$ . Entonces $\tilde B$ también se obtiene permutando alguna submatriz $B$ de $A$ . La permutación de filas y columnas cambia como mucho el signo del determinante. Así, $\det(\tilde B) = \pm\det(B) \in \{-1,0,1\}$ $\blacksquare$

Prueba del lema 2: Dejemos que $A$ sea totalmente unimodular. Cualquier submatriz cuadrada $B$ de $\begin{bmatrix} A & I\end{bmatrix}$ puede permutarse a la forma $$\tilde B = \begin{bmatrix} A_1 & 0 \\ A_2 & I_k \\ \end{bmatrix}.$$ donde $A_1$ es una sub-matriz cuadrada de $A$ y así $\det(A_1) \in \{-1,0,1\}$ .

Tenemos

$$\det(B) = \pm\det(\tilde B) = \det(A_1) \in \{-1,0,1\}.$$

Por otro lado, si $\begin{bmatrix} A & I\end{bmatrix}$ es totalmente unimodular, entonces como la eliminación de columnas preserva la unimodularidad total, $A$ también es totalmente unimodular. $\blacksquare$

Prueba del lema 3: Dejemos que $A$ sea totalmente unimodular y que $\tilde A$ se obtenga de $A$ mediante la operación de pivote con pivote $a_{i,j}$ . Sea $\tilde B$ sea una submatriz cuadrada de $\tilde A$ . Distinguimos tres casos:

1. $\tilde B$ contiene la fila pivote $i$ .
   Entonces $\tilde B$ se obtuvo de algunos $B$ una submatriz cuadrada de $A$ (i) multiplicando una fila por $\pm1$ y (ii) añadiendo múltiplos de esa fila a otras filas. Las operaciones (i) y (ii) preservan el determinante hasta el signo, por lo que tenemos $\det(\tilde B) = \pm\det(B) \in \{-1, 0, 1\}$ .
2. $\tilde B$ no contiene la fila pivote $i$ pero contiene la columna pivote $j$ . Dado que la columna de $\tilde B$ correspondiente al pivote es todo cero, tenemos $\det(\tilde B) = 0$ .
3. $\tilde B$ no contiene ni la fila ni la columna pivote. Sea $\tilde B_1$ sea la matriz obtenida de $\tilde B$ añadiendo la fila y la columna de $\tilde A$ correspondiente al pivote. Dado que la columna de $\tilde B_1$ correspondiente al pivote tiene exactamente un 1 y todo lo demás 0, tenemos $\det(\tilde B) = \pm\det(\tilde B_1)$ . Pero $\tilde B_1$ se obtuvo de alguna submatriz $B_1$ de $A$ mediante operaciones (como en 1.) que preservan el determinante hasta el signo. Así que tenemos $\det(\tilde B) = \pm\det(\tilde B_1) = \pm\det(B_1) \in \{-1,0,1\}$ . $\blacksquare$