Unimodular matrix

From Wikipedia, the free encyclopedia

In mathematics, a unimodular matrix is a square matrix with determinant +1 or −1.

A totally unimodular matrix is a matrix for which every square non-singular submatrix is also unimodular. From the definition it follows that any totally unimodular matrix has only 0, +1 or −1 entries.

The zero matrix shows that a totally unimodular matrix need not be unimodular.

An integer program whose constraint matrix is totally unimodular and whose right hand side is integral, can be solved efficiently since its LP relaxation gives rise to integer basic solutions.

1 Examples of unimodular matrices
2 Example of totally unimodular matrix
3 Abstract Linear Algebra
4 References
5 External reference
6 See also

[edit] Examples of unimodular matrices

Identity matrix
Symplectic matrices
Pascal matrices
The product of two unimodular matrices is also unimodular.
The Kronecker product of two two unimodular matrices is also unimodular. This follows since

$\det(A \otimes B) = (\det A)^p (\det B)^q,$

where p and q are the dimensions of A and B, respectively.

[edit] Example of totally unimodular matrix

The following matrix is totally unimodular:

$A=\begin{bmatrix} -1 & -1 & 0 & 0 & 0 & +1\\ +1 & 0 & -1 & -1 & 0 & 0\\ 0 & +1 & +1 & 0 & -1 & 0\\ 0 & 0 & 0 & +1 & +1 & -1\\ \end{bmatrix}.$

This matrix arises as the constraint matrix of the linear programming formulation (without the capacity constraint) of the maximum flow problem on the following network:

This matrix $A$ has the following properties:

all of its entries are either 0, −1 or +1;
any column has at most two nonzero entries; and
the columns with two nonzero entries have entries with opposite sign.

Those properties are sufficient for a matrix to be totally unimodular (but they are not necessary). Any network flow problem will yield a constraint matrix with the above structure (so that's why any network flow problem with bounded integer capacities has an integer optimal value).

[edit] Abstract Linear Algebra

In abstract linear algebra, matrices are considered which have entries from any ring, and not specifically the integers. In this context, a unimodular matrix is one whose determinant is a unit.

[edit] References

Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Section 13.2, Dover Publications, Mineola NY, 1998. ISBN