Unimodular matrix

From Glossary

Jump to: navigation, search

A nonsingular matrix whose determinate has magnitude 1. A square matrix is totally unimodular if every nonsingular submatrix from it is unimodular. This arises in (linear) integer programming because it implies a basic solution to the LP relaxation is integer-valued (given integer-valued right-hand sides), thus obtaining a solution simply by a simplex method. An example of a totally unimodular matrix is the node-arc incidence matrix of a network, so basic solutions of network flows are integer-valued (given integer-valued supplies and demands).

Personal tools