- Unimodular matrix
In
mathematics , a unimodular matrix "M" is a squareinteger matrix withdeterminant +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 underCramer'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 .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:
* TheKronecker product of two unimodular matrices is also unimodular. This follows since :: where "p" and "q" are the dimensions of "A" and "B", respectively.Concrete examples include:
* Symplectic matrices
* Pascal matricesTotally 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 by an m by n matrix whose rows can be partitioned into two disjoint sets and , with the following properties:
* Every column of contains at most two non-zero entries;
* Every entry in is 0, +1, or −1;
* If two non-zero entries in a column of have the same sign, then the row of one is in , and the other in ;
* If two non-zero entries in a column of have opposite signs, then the rows of both are in , or both in .Then every minor determinant of 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 or 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 is an oriented graph, is some set of directed paths in , and is the incidence matrix of versus . Then for to have the unimodular property it is sufficient that be alternating. If consists of the set of all directed paths of , then for to have the unimodular property it is necessary and sufficient that 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 .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 itExternal reference
See a [http://glossary.computing.society.informs.org/index.php?page=U.html Mathematical Programming Glossary] by Harvey J. Greenberg.
Wikimedia Foundation. 2010.