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 word infant derives from Latin words meaning “not yet speaking.” It emphasizes what the child cannot do and reflects the baby’s total dependence on adults. The word toddler, however, demonstrates our change in perspective, for it focuses on the child’s increased mobility and burgeoning independence.”
—Lawrence Kutner (20th century)