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 chief lesson of the Depression should never be forgotten. Even our liberty-loving American people will sacrifice their freedom and their democratic principles if their security and their very lives are threatened by another breakdown of our free enterprise system. We can no more afford another general depression than we can afford another total war, if democracy is to survive.”
—Agnes E. Meyer (1887–1970)