Unimodular matrix

From Wikipedia, the free encyclopedia

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

Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N which is its inverse (these are equivalent via Cramer's rule). Thus every equation Mx = b, where b is an integral matrix, has an integer solution.

These form a group, which is denoted $GL_n(\mathbf{Z})$ .

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

[edit] Examples of unimodular matrices

Unimodular matrices form a group, hence the following are unimodular:

Identity matrix
The inverse of a unimodular matrix
The product of two unimodular matrices

Further:

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.

Concrete examples include:

[edit] Totally unimodular

A totally unimodular matrix is a matrix for which every square non-singular submatrix is unimodular. A totally unimodular matrix needs not be square, which means that a totally unimodular matrix need not be unimodular (another example is the zero matrix). From the definition it follows that any totally unimodular matrix has only 0, +1 or −1 entries.

The point of a totally unimodular matrix is that every linear combination of columns of M and of the identity matrix I that is an integral matrix can be written as a linear combination with integer coefficients. Thus, an integer program whose constraint matrix is totally unimodular and whose right hand side is integral can be solved by linear programming (LP) since all its basic feasible solutions are integer.

[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 that is invertible over the ring; equivalently, whose determinant is a unit. This group is denoted $G L n R$ .

Over a field, unimodular is identical to non-singular; "unimodular" here refers to matrices with coefficients in some ring (often the integers) which are invertible over that ring, and one uses "non-singular" to mean matrices that are invertible over the field.

[edit] References

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