Unimodular matrix

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. The unimodular matrices of order "n" form a group, which is denoted $GL\_n(mathbb\{Z\})$.

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 matricesFurther:
* 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:
* Symplectic matrices
* Pascal matrices

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.

Example of a totally unimodular matrix

The following matrix is totally unimodular:

:

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:

ufficient conditions for a matrix to be totally unimodular

In the appendix of a paper by Heller and Tompkins [Citation
last = Heller
first = I.
last2 = Tompkins
first2 = C.B.
contribution = An Extension of a Theorem of Dantzig's
editor-last = Kuhn
editor-first = H.W.
editor2-last = Tucker
editor2-first = A.W.
title = Linear Inequalities and Related Systems
series = Annals of Mathematics Studies
publisher = Princeton University Press
location = Princeton (NJ)
pages = 247-254
volume = 38
year = 1956 ] ,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 [Citation
last = Hoffman
first = A.J.
last2 = Kruskal
first2 = J.B.
contribution = Integral Boundary Points of Convex Polyhedra
editor-last = Kuhn
editor-first = H.W.
editor2-last = Tucker
editor2-first = A.W.
title = Linear Inequalities and Related Systems
series = Annals of Mathematics Studies
publisher = Princeton University Press
location = Princeton (NJ)
pages = 223-246
volume = 38
year = 1956 ] 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.

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.

ee also

*Special linear group

References

Citation
last = Papadimitriou
first = Christos H.
last2 = Steiglitz
first2 = Kenneth
year = 1998
title = Combinatorial Optimization: Algorithms and Complexity
publisher = Dover Publications (Section 13.2)
location = Mineola (NY)
Note = The 'section 13.2' is on the wrong place, but I don't know how to fix it

External reference

See a [http://glossary.computing.society.informs.org/index.php?page=U.html Mathematical Programming Glossary] by Harvey J. Greenberg.