Totally unimodular matrix

A totally unimodular matrix is a matrix with integer entries, in which further demands are made on the determinants of all square sub-matrices. Totally unimodular matrices play a role in discrete optimization , since under certain conditions they guarantee the integer solution of a linear optimization problem .

definition

Be a matrix. Then totally unimodular (sometimes also absolutely unimodular or completely unimodular) is called if and only if all minors (determinants of quadratic sub-matrices) have the value or . In particular, all entries ( sub-matrices) are then off . ${\displaystyle A\in \mathbb {R} ^{n\times m}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle -1,0}$ ${\displaystyle 1}$ ${\displaystyle 1\times 1}$ ${\displaystyle \{-1,0,1\}}$

Alternatively formulated, a totally unimodular matrix is ​​a (not necessarily square) matrix in which all square, non-singular sub-matrices are unimodular as an integer .

properties

• The incidence matrix of an undirected bipartite graph is totally unimodular.
• The incidence matrix of a directed graph is totally unimodular.
• If totally unimodular, the transposed matrix is also totally unimodular, because determinants are preserved under transposition. ${\displaystyle A}$ ${\displaystyle A^{T}}$
• Totally unimodular matrices get their meaning due to the following statement: If totally unimodular and , then the polyhedron only has integer vertices. If a linear optimization problem is given under the constraint , the optimal solution is an integer. If, in addition , the objective function value is also an integer. ${\displaystyle A}$ ${\displaystyle b\in \mathbb {Z} ^{n}}$ ${\displaystyle P=\{x\,|\,Ax\leq b\}}$ ${\displaystyle \min c^{T}x}$ ${\displaystyle x\in P}$ ${\displaystyle x^{*}}$ ${\displaystyle c\in \mathbb {Z} ^{n}}$ ${\displaystyle c^{T}x^{*}}$
• The number of sub-matrices in a matrix is ​​exponential in the number of rows / columns in the matrix. Although all of these sub-matrices are used to characterize total unimodularity, there is a polynomial algorithm for deciding whether a matrix is ​​totally unimodular or not.

example

Look at the matrix

${\displaystyle A:={\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&0&1&0\end{pmatrix}}}$

1. All entries are either or and therefore also all sub-matrices ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1\times 1}$
2. If a matrix only contains entries from and at least one zero, its determinant is also from . In particular, the determinants of all -submatrices of the above matrix are off . ${\displaystyle 2\times 2}$ ${\displaystyle \{-1,0,1\}}$ ${\displaystyle \{-1,0,1\}}$ ${\displaystyle 2\times 2}$ ${\displaystyle \{-1,0,1\}}$
3. Using Sarrus' rule one can check that the determinants of the sub-matrices are also off. ${\displaystyle 3\times 3}$ ${\displaystyle \{-1,0,1\}}$

Therefore the matrix is ​​totally unimodular.

literature

• Alexander Schrijver : Combinatorial optimization . Polyhedra and efficiency. Springer, Berlin 2003, ISBN 978-3-540-44389-6 (3 volumes, 1881 pages).