Unimodular Matrix - Total Unimodularity

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:

    I only know that a rook
    Ordering its black feathers can so shine
    As to seize me senses, haul
    My eyelids up, and grant

    A brief respite from fear
    Of total neutrality.
    Sylvia Plath (1932–1963)