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 under 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(\mathbb{Z})$ .

1 Examples of unimodular matrices
2 Totally unimodular
- 2.1 Example of a totally unimodular matrix
- 2.2 Sufficient conditions for a matrix to be totally unimodular
3 Abstract linear algebra
4 References
5 External reference
6 See also

[edit] Examples of unimodular matrices

Unimodular matrices form a group under matrix multiplication, 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 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 need not be square itself. 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 integer can be solved by linear programming (LP) since all its basic feasible solutions are integer.

[edit] Example of a 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:

[edit] Sufficient conditions for a matrix to be totally unimodular

In the appendix of a paper by Heller and Tompkins^[1], A.J. Hofmann proves the following theorem, which shows sufficient but not necessary conditions for a matrix to be totally unimodular:

Let $A$ by an m by n matrix whose rows can be partitioned into two disjoint sets $B$ and $C$ , with the following properties:

Every column of $A$ contains at most two non-zero entries;
Every entry in $A$ is 0, +1, or −1;
If two non-zero entries in a column of $A$ have the same sign, then the row of one is in $B$ , and the other in $C$ ;
If two non-zero entries in a column of $A$ have opposite signs, then the rows of both are in $B$ , or both in $C$ .

Then every minor determinant of $A$ is 0, +1, or −1.

Most network flow problems, including the example shown above, will yield a constraint matrix with these properties and one of the sets $B$ or $C$ being empty. Thus, most network flow problem with bounded integer capacities have an integral optimal value. The exception being the network flow problem that computes the minimum cost network coded multicast flow. In this case, it is possible to have fractional optimal value even with bounded integer capacities.

Hoffman and Kruskal^[2] prove the following theorem:

Suppose $G$ is an oriented graph, $P$ is some set of directed paths in $G$ , and $A$ is the incidence matrix of $G$ versus $P$ . Then for $A$ to have the unimodular property it is sufficient that $G$ be alternating. If $P$ consists of the set of all directed paths of $G$ , then for $A$ to have the unimodular property it is necessary and sufficient that $G$ be alternating.

[edit] Abstract linear algebra

Abstract linear algebra considers matrices with entries from any commutative ring, not limited to 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 $GL_n R\,$ .

Over a field, unimodular has the same meaning as 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

^ Heller, I. & Tompkins, C.B. (1956), “An Extension of a Theorem of Dantzig's”, in Kuhn, H.W. & Tucker, A.W., Linear Inequalities and Related Systems, vol. 38, Annals of Mathematics Studies, Princeton (NJ): Princeton University Press, pp. 247-254
^ Hoffman, A.J. & Kruskal, J.B. (1956), “Integral Boundary Points of Convex Polyhedra”, in Kuhn, H.W. & Tucker, A.W., Linear Inequalities and Related Systems, vol. 38, Annals of Mathematics Studies, Princeton (NJ): Princeton University Press, pp. 223-246

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