Unimodular matrix

In mathematics, a unimodular matrix M is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N that is its inverse (these are equivalent under Cramer's rule). Thus every equation Mx = b, where M and b both have integer components and M is unimodular, has an integer solution. The n × n unimodular matrices form a group called the n × n general linear group over , which is denoted . Unimodular matrices form a subgroup of the general linear group under matrix multiplication, i.e. the following matrices are unimodular: Identity matrix The inverse of a unimodular matrix The product of two unimodular matrices Other examples include: Pascal matrices Permutation matrices the three transformation matrices in the ternary tree of primitive Pythagorean triples Certain transformation matrices for rotation, shearing (both with determinant 1) and reflection (determinant −1). The unimodular matrix used (possibly implicitly) in lattice reduction and in the Hermite normal form of matrices. The Kronecker product of two unimodular matrices is also unimodular. This follows since where p and q are the dimensions of A and B, respectively. A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. Equivalently, every square submatrix has determinant 0, +1 or −1. A totally unimodular matrix need not be square itself. From the definition it follows that any submatrix of a totally unimodular matrix is itself totally unimodular (TU). Furthermore it follows that any TU matrix has only 0, +1 or −1 entries. The converse is not true, i.e., a matrix with only 0, +1 or −1 entries is not necessarily unimodular. A matrix is TU if and only if its transpose is TU. Totally unimodular matrices are extremely important in polyhedral combinatorics and combinatorial optimization since they give a quick way to verify that a linear program is integral (has an integral optimum, when any optimum exists).