La siguiente matriz es totalmente unimodular (TUM):

${\displaystyle A={\begin{bmatrix}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\end{bmatrix}}}$ 

Esta matriz surge como la matriz restrictiva de la formulación del problema lineal (sin la restricción ) del problema del flujo máximo en la siguiente red:

Esta matriz ${\displaystyle A}$  tiene las siguientes propiedades:

• todos sus elementos ${\displaystyle \in \ \{{-1,0,1}\}}$ ;
• cualquier columna tiene como máximo dos elementos distintos de cero;
• las columnas con dos elementos distintos de cero tienen elementos de distinto signo.

Estas propiedades son suficientes para que la matriz sea totalmente unimodular (TUM) (pero no son necesarias). Cualquier problema de red de flujo produciría una matriz restrictiva con la susodicha estructura (por esto es que cualquier problema de redes de flujo con capacidades acotadas enteras tiene un valor óptimo entero).

Sea A una matriz totalmente unimodular y b entero, entonces el poliedro ${\displaystyle P=\{x\geq {\big |}Ax=b\}}$  tiene vértices enteros.

Sea A una matriz con ${\displaystyle a_{i,j}\in \ \,}$ ${\displaystyle \{{-1},0,1\}\,}$  ${\displaystyle \forall _{i,j}\,}$  A es totalmente unimodular si:

1)Cada columna de A tiene como mucho dos elementos no nulos

Demostración:

2)Existe una partición ${\displaystyle (I_{1},I_{2})\,}$  de las filas de A tal que cada columna con dos elementos no nulos tiene estos dos elementos pertenecientes a un conjunto ${\displaystyle I_{1}\,}$  y ${\displaystyle I_{2}\,}$  distintos sí y solo sí los dos elementos tienen el mismo signo.

${\displaystyle A\,}$  es TUM ${\displaystyle \Longleftrightarrow A^{T}}$  es TUM

En álgebra abstracta, las matrices son consideradas con elementos de cualquier anillo, y no exactamente enteros. En este contexto, una matriz de dimensiones ${\displaystyle m\times n\ (m\leq n)}$  es unimodular si el determinante de cada submatriz cuadrada no singular B es un anillo.

Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Section 13.2, Dover Publications, Mineola NY, 1998. ISBN 0-486-40258-4

• Mathematical Programming Glossary by Harvey J. Greenberg.