Totally unimodular matrix

Remarks

Example: $\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$ is totally unimodular. Its $1 \times 1$ minors are entries in $\{0, 1\}$, and its $2 \times 2$ minors are $1$, $1$ and $1$. Non-example: $\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$ is not totally unimodular, because its determinant is $2$. A totally unimodular matrix has all entries in $\{0, 1, -1\}$, since the entries are its $1 \times 1$ minors. A square totally unimodular matrix need not be unimodular, because its determinant may be $0$. The incidence matrix of a bipartite graph and the incidence matrix of a directed graph are totally unimodular. By a theorem of Hoffman and Kruskal, an integer matrix $A$ is totally unimodular exactly when the polyhedron $\set{x \in \R^n : Ax \le b,\ x \ge 0}$ has integral vertices for every integral vector $b$.