Total Unimodularity
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A totally unimodular matrix need not be square itself. From the definition it follows that any totally unimodular matrix has only 0, +1 or −1 entries.
Totally unimodular matrices are extremely important in polyhedral combinatorics and combinatorial optimization since they give a quick way to verify that a linear program is integral (has an integral optimum, when any optimum exists). Specifically, if A is TU and b is integral, then linear programs of forms like or have integral optima, for any c. Hence if A is totally unimodular and b is integral, every extreme point of the feasible region (e.g. ) is integral and thus the feasible region is an integral polyhedron.
Read more about this topic: Unimodular Matrix
Famous quotes containing the word total:
“The total collapse of the public opinion polls shows that this country is in good health. A country that developed an airtight system of finding out in advance what was in people’s minds would be uninhabitable.”
—E.B. (Elwyn Brooks)