Totally 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 which is its inverse (these are equivalent under Cramer's rule). Thus every equation Mx = b, where M and b are both integer, and M is unimodular, has an integer solution. The unimodular matrices of order n form a group, which is denoted ${\displaystyle GL_{n}(\mathbb {Z} )}$.

Unimodular matrices form a subgroup of the general linear group under matrix multiplication, i.e. the following matrices are unimodular:

Further:

Concrete examples include:

A totally unimodular matrix (TU 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 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 opposite is not true, i.e., a matrix with only 0, +1 or −1 entries is not necessarily unimodular.

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). Specifically, if A is TU and b is integral, then linear programs of forms like ${\displaystyle \{\min cx\mid Ax\geq b,x\geq 0\}}$ or ${\displaystyle \{\max cx\mid Ax\leq b\}}$ have integral optima, for any c. Hence if A is totally unimodular and b is integral, every extreme point of the feasible region (e.g. ${\displaystyle \{x\mid Ax\geq b\}}$) is integral and thus the feasible region is an integral polyhedron.

...
Wikipedia