Total unimodularity and integrality

A matrix is totally unimodular, abbreviated TU, when every square submatrix has determinant zero, one, or minus one. The one-by-one minors force all entries to lie in $\{0,1,-1\}$. A square integer matrix with determinant one or minus one is unimodular, but need not be totally unimodular: an entry of two already violates the one-by-one condition. Conversely, a rectangular TU matrix may have no determinant of its own. The definition controls every possible nonsingular basis that can arise, which is why it is useful for an optimization algorithm that changes bases.

Several operations preserve TU: transposing, multiplying a row or column by minus one, deleting rows or columns, and appending an identity matrix or its negative. These facts follow by reducing the relevant determinant using signs and expansion along unit columns or rows. Adding an arbitrary valid inequality is not on this list and can destroy TU. A modeler must inspect the actual augmented matrix after adding resource limits, side constraints, or variable transformations. Integrality is a theorem about the specified representation with an integral right-hand side, not a decorative label attached permanently to an application.

Consider $P=\{x:Ax\le b,\ x\ge0\}$ with TU $A$ and integral $b$. At a vertex, choose a full-rank square system of active constraints from $A$ and the nonnegativity rows. Its coefficient matrix is a nonsingular minor of the TU augmentation with negative identity, so its determinant is one or minus one. Its inverse is integral by the adjugate formula. Multiplying that inverse by the integral active right-hand side gives an integral vertex. This proof establishes the key implication directly and shows exactly where the integrality of $b$ is needed.

Because nonnegativity makes this polyhedron pointed, a feasible LP with finite optimal value has an optimal vertex, hence an integer optimum. The objective coefficients do not need to be integral. The theorem does not say that every feasible point is integral: convex combinations of distinct integer vertices are usually fractional. Nor does it guarantee feasibility, boundedness, or uniqueness. If an interior-point method returns the midpoint of an optimal edge, it may return a fractional optimum even though an integral optimal vertex exists. A vertex extraction or combinatorial algorithm can then supply an integral representative.

A directed node-arc incidence matrix has one minus one and one plus one in each non-loop arc column. It is TU: for any square submatrix, a column with at most one nonzero entry permits induction by determinant expansion; if every column has two entries, their opposite signs make the row sum zero and the determinant vanishes. Bipartite graph node-edge incidence matrices are also TU after changing signs on one vertex partition. This links matching and flow integrality to a concrete determinant argument rather than to an assumption that networks are automatically easy.

A triangle's unsigned node-edge incidence matrix has determinant two in absolute value, so it is not TU. With unit capacities at vertices, assigning one-half to each of its three edges satisfies the degree inequalities and can be a fractional vertex. Odd-set inequalities repair the matching description, but the original degree matrix alone lacks the bipartite guarantee. A separate failure is a nonintegral right-hand side: even the TU one-by-one matrix $(1)$ gives the fractional endpoint one-half when its bound is one-half. Check structure and data together before dropping integer declarations.