Hoffman-Kruskal theorem
From Egres Open
The theorem of Hoffman and Kruskal [1] is a characterization of totally unimodular matrices in terms of integrality of polyhedra defined by the matrices.
Theorem. An integer matrix [math]A \in {\mathbb Z}^{m \times n}[/math] is totally unimodular if and only if for every [math]b \in {\mathbb Z}^m[/math], the polyhedron [math]\{x \in {\mathbb R}^n: Ax \leq b, x \geq 0\}[/math] is integral, i.e. all of its vertices are integral.
