Inmathematics, aunimodular matrixM is asquareinteger matrix havingdeterminant +1 or −1. Equivalently, it is an integer matrix that isinvertible over theintegers: there is an integer matrixN that is its inverse (these are equivalent underCramer's rule). Thus every equationMx =b, whereM andb both have integer components andM is unimodular, has an integer solution. Then ×n unimodular matrices form agroup called then ×ngeneral linear group over${\displaystyle \mathbb{Z}}$, which is denoted${\displaystyle {\mathrm{GL}}_n(\mathbb{Z})}$.

Unimodular matrices form asubgroup of thegeneral linear group undermatrix multiplication, i.e. the following matrices are unimodular:

• Identity matrix
• Theinverse of a unimodular matrix
• Theproduct of two unimodular matrices

Other examples include:

• Pascal matrices
• Permutation matrices
• the three transformation matrices in the ternarytree of primitive Pythagorean triples
• Certain transformation matrices forrotation,shearing (both with determinant 1) andreflection (determinant −1).
• The unimodular matrix used (possibly implicitly) inlattice reduction and in theHermite normal form of matrices.
• TheKronecker product of two unimodular matrices is also unimodular. This follows since${\displaystyle det(A\otimes B)=(detA{)}^q(detB{)}^p,}$ wherep andq are the dimensions ofA andB, respectively.

Atotally unimodular matrix^[1](TU matrix) is a matrix for which 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. Theconverse 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 itstranspose is TU.

Totally unimodular matrices are extremely important inpolyhedral combinatorics andcombinatorial optimization since they give a quick way to verify that alinear program isintegral (has an integral optimum, when any optimum exists). Specifically, ifA is TU andb is integral, then linear programs of forms like${\displaystyle \{min{c}^{\mathrm{\top }}x\mid Ax\ge b,x\ge 0\}}$ or${\displaystyle \{max{c}^{\mathrm{\top }}x\mid Ax\le b\}}$ have integral optima, for anyc. Hence ifA is totally unimodular andb is integral, every extreme point of the feasible region (e.g.${\displaystyle \{x\mid Ax\ge b\}}$) is integral and thus the feasible region is anintegral polyhedron.

1. The unoriented incidence matrix of abipartite graph, which is the coefficient matrix for bipartitematching, is totally unimodular (TU). (The unoriented incidence matrix of a non-bipartite graph is not TU.) More generally, in the appendix to a paper by Heller and Tompkins,^[2] A.J. Hoffman and D. Gale prove the following. Let${\displaystyle A}$ be anm byn matrix whose rows can be partitioned into twodisjoint sets${\displaystyle B}$ and${\displaystyle C}$. Then the following four conditions together aresufficient forA to be totally unimodular:

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

It was realized later that these conditions define an incidence matrix of a balancedsigned graph; thus, this example says that the incidence matrix of a signed graph is totally unimodular if the signed graph is balanced. The converse is valid for signed graphs without half edges (this generalizes the property of the unoriented incidence matrix of a graph).^[3]

2. Theconstraints ofmaximum flow andminimum cost flow problems yield a coefficient matrix with these properties (and with emptyC). Thus, such network flow problems with bounded integer capacities have an integral optimal value. Note that this does not apply tomulti-commodity flow problems, in which it is possible to have fractional optimal value even with bounded integer capacities.

3. The consecutive-ones property: ifA is (or can be permuted into) a 0-1 matrix in which for every row, the 1s appear consecutively, thenA is TU. (The same holds for columns since the transpose of a TU matrix is also TU.)^[4]

4. Everynetwork matrix is TU. The rows of a network matrix correspond to a treeT = (V,R), each of whose arcs has an arbitrary orientation (it is not necessary that there exist a root vertexr such that the tree is "rooted intor" or "out ofr").The columns correspond to another setC of arcs on the same vertex setV. To compute the entry at rowR and columnC =st, look at thes-to-t pathP inT; then the entry is:

• +1 if arcR appears forward inP,
• −1 if arcR appears backwards inP,
• 0 if arcR does not appear inP.

See more in Schrijver (2003).

5. Ghouila-Houri showed that a matrix is TU iff for every subsetR of rows, there is an assignment${\displaystyle s:R\to \pm 1}$ of signs to rows so that the signed sum${\displaystyle \sum _{r\in R}s(r)r}$ (which is a row vector of the same width as the matrix) has all its entries in${\displaystyle \{0,\pm 1\}}$ (i.e. the row-submatrix hasdiscrepancy at most one). This and several other if-and-only-if characterizations are proven in Schrijver (1998).

6.Hoffman andKruskal^[5]proved the following theorem. Suppose${\displaystyle G}$ is adirected graph without 2-dicycles,${\displaystyle P}$ is the set of alldipaths in${\displaystyle G}$, and${\displaystyle A}$ is the 0-1 incidence matrix of${\displaystyle V(G)}$ versus${\displaystyle P}$. Then${\displaystyle A}$ is totally unimodular if and only if every simple arbitrarily-oriented cycle in${\displaystyle G}$ consists of alternating forwards and backwards arcs.

7. Suppose a matrix has 0-(${\displaystyle \pm }$1) entries and in each column, the entries are non-decreasing from top to bottom (so all −1s are on top, then 0s, then 1s are on the bottom). Fujishige showed^[6]that the matrix is TU iff every 2-by-2 submatrix has determinant in${\displaystyle 0,\pm 1}$.

8.Seymour (1980)^[7] proved a full characterization of all TU matrices, which we describe here only informally. Seymour's theorem is that a matrix is TU if and only if it is a certain natural combination of somenetwork matrices and some copies of a particular 5-by-5 TU matrix.

1. The following matrix is totally unimodular:

This matrix arises as the coefficient matrix of the constraints in the linear programming formulation of themaximum flow problem on the following network:

2. Any matrix of the form

isnot totally unimodular, since it has a square submatrix of determinant −2.

Abstract linear algebra considers matrices with entries from anycommutativering${\displaystyle R}$, not limited to the integers. In this context, a unimodular matrix is one that is invertible over the ring; equivalently, whose determinant is aunit. Thisgroup is denoted${\displaystyle {\mathrm{GL}}_n(R)}$.^[8] A rectangular${\displaystyle k}$-by-${\displaystyle m}$ matrix is said to be unimodular if it can be extended with${\displaystyle m-k}$ rows in${\displaystyle R^m}$ to a unimodular square matrix.^[9][10][11]

Over afield,unimodular has the same meaning asnon-singular.Unimodular here refers to matrices with coefficients in some ring (often the integers) which are invertible over that ring, and one usesnon-singular to mean matrices that are invertible over the field.

• Balanced matrix
• Regular matroid
• Special linear group
• Total dual integrality
• Hermite normal form

• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), "Section 13.2",Combinatorial Optimization: Algorithms and Complexity, Mineola, N.Y.: Dover Publications, p. 316,ISBN 978-0-486-40258-1
• Alexander Schrijver (1998),Theory of Linear and Integer Programming. John Wiley & Sons,ISBN 0-471-98232-6 (mathematical)
• Alexander Schrijver (2003),Combinatorial Optimization: Polyhedra and Efficiency, Springer

• Mathematical Programming Glossary by Harvey J. Greenberg
• Unimodular Matrix from MathWorld
• Software for testing total unimodularity by M. Walter and K. Truemper

• Matrices (mathematics)

• Use American English from January 2019
• All Wikipedia articles written in American English
• Articles with short description
• Short description is different from Wikidata