¿Cómo demostrar que esta matriz es totalmente unimodular?

Question

Esta matriz es total unimodular (probado por un programa de computadora).

1 1 1 1 -1 -1 -1 -1
0 1 1 1  0 -1 -1 -1
0 0 1 1  0  0 -1 -1
0 0 0 1  0  0  0 -1
1 0 0 0 -1  0  0  0
1 1 0 0 -1 -1  0  0
1 1 1 0 -1 -1 -1  0
1 1 1 1 -1 -1 -1 -1

¿Existe alguna forma de demostrar teóricamente que esta matriz es total unimodular?

Ya he intentado algunas cosas del artículo de Wikipedia, pero un criterio falla, porque tiene más de a lo sumo dos entradas no nulas por columna.

Answer 1

Puedes ignorar las cuatro columnas a la derecha porque son negativas de las cuatro columnas a la izquierda. También puedes ignorar la última fila porque es idéntica a la primera. Por lo tanto, tu matriz es totalmente unimodular si y solo si la matriz $7\times5$ $$ B=\pmatrix{1&1&1&1\\ 0&1&1&1\\ 0&0&1&1\\ 0&0&0&1\\ 1&0&0&0\\ 1&1&0&0\\ 1&1&1&0} $$ es totalmente unimodular. Sin embargo, $B$ es totalmente unimodular si y solo si $C=DB$ es totalmente unimodular donde $D=\operatorname{diag}(-1,-1,-1,-1,+1,+1,+1)$. Ahora, en cada columna de $C$, sus entradas están ordenadas de forma ascendente. Según un resultado de Fujishige (1984; ver el séptimo resultado en la subsección "Common totally unimodular matrices" en Wikipedia), dicha matriz $C$ es totalmente unimodular si y solo si cada submatriz $2\times2$ tiene determinante 0, -1 o 1. Puedes continuar desde aquí.

Answer 2

Como señaló el usuario1551, solo necesitas demostrar que la matriz $ 7 \times 5 $ $B$ formada por las primeras 5 columnas, donde intercambiamos el signo de la quinta columna, es totalmente unimodular. Esto es inmediato, porque $B$ tiene las propiedades de unos consecutivos en las filas (es decir, en cada fila las entradas 1 aparecen consecutivamente).

Consulte la entrada de Wikipedia para "Matriz unimodular", en el punto 3 de la sección "Matrices completamente unimodulares comunes".