Totally Unimodular Matrices

Definition1Totally Unimodular Matrices

A matrix $A$ is totally unimodular if for all square submatrix $A^{'}$ of $A$ , $det (A^{'}) \in {- 1, 0, 1}$ .

We will use $T U$ to be the set of all totally unimodular matrices.

By this definition, all the entries in a totally unimodular matrix must be $- 1, 0, 1$ by consider square submatrix of size $1$ .

Proposition2

If $A \in T U$ , $A_{j}$ be the $j$ th row of $A$ , then

Proof

$d e t (M) = d e t (M^{T})$ .
square submatrix of $A^{'}$ is also square submatrix of $A$ .
The submatrices that doesn’t contain the first row has corresponding submatrix in $A$ , ones that does contain the first row has determinant 0.
see inverse of a totally unimodular matrix.
row switching. Consider we switched row $i$ and $j$ . Consider any submatrix, if it doesn’t contain row $i$ or $j$ , then it still has determinant $- 1, 0, 1$ . If it contain both row $i$ and $j$ , then the determinant is just the negation when the rows are switched back. If it only contain one of row $i$ and $j$ , wlog let it be $i$ , then it has the rows in order $a_{1}, \dots, a_{k}, i, a_{k + 1}, \dots, a_{l}$ , then there is a submatrix in $A$ using the rows in sequence $a_{1}, \dots, a_{j}, i, a_{j + 1}, \dots, a_{l}$ , and the absolute value of their determinants are equal.
multiply by a constant to preserve the $- 1, 0, 1$ properties, then use the argument similar as above, note the determinant of the submatrix can change only by sign.

The above properties can be useful to prove many simple statements, for example, operations like duplicate a row, column are closed in $T U$ .

$T U$ is not closed under matrix multiplication, consider $[1011]^{2} = [1021]$ .

Posted by Chao Xu on 2013-05-29.

Tags: matrix.