Matrices totalmente unimodulares

Una matriz cuadrada o rectangular $ M $ se denomina totalmente unimodular si toda submatriz cuadrada no singular (es decir, con determinante distinto de cero) es una matriz unimodular.

Una submatriz cuadrada es unimodular si su determinante es exactamente igual a +1 o −1.

La definición incluye también las entradas individuales no nulas de $ M $, ya que pueden interpretarse como submatrices $ 1 \times 1 $ cuyo determinante coincide con el valor del elemento correspondiente.

Nota: Las entradas iguales a cero no se consideran, ya que como submatrices $ 1 \times 1 $ son singulares: $$ \det(0) = 0 $$

Ejemplo práctico
Propiedades fundamentales

Ejemplo práctico

Consideremos la siguiente matriz rectangular:

$$ \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \end{pmatrix} $$

Esta matriz es totalmente unimodular, ya que todas sus submatrices cuadradas no singulares tienen determinante igual a ±1:

$$ \det \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix} = 1 $$

$$ \det \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} = -1 $$

$$ \det \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = 1 $$

También se consideran como submatrices $ 1 \times 1 $ las entradas no nulas:

$$ \det(1) = 1 \qquad \det(-1) = -1 $$

Nota: Las entradas nulas se omiten porque su determinante es cero y, por tanto, no cumplen la condición de no singularidad.

Propiedades fundamentales

Las matrices totalmente unimodulares poseen una serie de propiedades estructurales de gran interés:

Una condición necesaria (aunque no suficiente) para que una matriz sea totalmente unimodular es que todas sus entradas no nulas sean iguales a 1 o −1.
Nota: Si una matriz contiene elementos distintos de ±1, estos conforman submatrices $ 1 \times 1 $ cuyo determinante no cumple la condición requerida. Sin embargo, la recíproca no es válida: una matriz compuesta exclusivamente por 0, 1 y −1 no es necesariamente totalmente unimodular. Por ejemplo, la matriz $$ \begin{pmatrix} 1 & -1 & 0 \\ 1 & 1 & 0 \end{pmatrix} $$ no es totalmente unimodular, ya que posee al menos una submatriz cuadrada cuyo determinante no pertenece al conjunto $ \{+1, -1\} $: $$ \det \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} = 2 $$
No toda matriz unimodular es totalmente unimodular.
Ejemplo: La matriz $$ \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} $$ es unimodular, ya que $$ \det \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} = 3 - 2 = 1 $$ Sin embargo, no es totalmente unimodular, pues algunas de sus submatrices $ 1 \times 1 $ no satisfacen la condición: $$ \det(3) = 3 \qquad \det(2) = 2 $$
Si una matriz $ M_{m,n} $ es totalmente unimodular, entonces al añadirle columnas o filas correspondientes a la matriz identidad $ I $ (o su opuesto), se conserva la total unimodularidad.
Ejemplo: Sea $$ M_{2,3} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \end{pmatrix} $$ una matriz totalmente unimodular. Si se le añade horizontalmente $ I_2 $ o $ -I_2 $: $$ [ M_{2,3} \ I_2 ] = \begin{pmatrix} 1 & -1 & 0 & \color{red}1 & \color{red}0 \\ 1 & 0 & 1 & \color{red}0 & \color{red}1 \end{pmatrix} $$ $$ [ M_{2,3} \ -I_2 ] = \begin{pmatrix} 1 & -1 & 0 & \color{red}-1 & \color{red}0 \\ 1 & 0 & 1 & \color{red}0 & \color{red}-1 \end{pmatrix} $$ Análogamente, si se añaden verticalmente $ I_3 $ o $ -I_3 $: $$ \begin{bmatrix} M_{2,3} \\ I_3 \end{bmatrix} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \\ \color{red}1 & \color{red}0 & \color{red}0 \\ \color{red}0 & \color{red}1 & \color{red}0 \\ \color{red}0 & \color{red}0 & \color{red}1 \end{pmatrix} $$ $$ \begin{bmatrix} M_{2,3} \\ -I_3 \end{bmatrix} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 0 & 1 \\ \color{red}-1 & \color{red}0 & \color{red}0 \\ \color{red}0 & \color{red}-1 & \color{red}0 \\ \color{red}0 & \color{red}0 & \color{red}-1 \end{pmatrix} $$

Estas propiedades hacen de las matrices totalmente unimodulares una herramienta clave en áreas como la programación entera, las redes de flujo y la teoría de matroides.