The Art Gallery Guardian

Totally Unimodular Matrices


Definition1Totally Unimodular Matrices

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

We will use TUTU 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-1,0,1 by consider square submatrix of size 11.

Proposition2

If ATUA \in TU, AjA_j be the jjth row of AA, then

  1. ATTUA^T \in TU,
  2. AA' is a submatrix of AA, then ATUA'\in TU,
  3. [0A1A2A3Am]TU\displaystyle \begin{bmatrix} 0\\ A_1\\ A_2\\ A_3\\ \vdots\\ A_{m} \end{bmatrix} \in TU .
  4. If AA is a square matrix, then A1TUA^{-1} \in TU,
  5. If AA' is formed by row swapping of AA, then ATUA'\in TU.
  6. Multiply by 1,0,1{-1,0,1} to a row.
Proof
  1. det(M)=det(MT)det(M) = det(M^T).
  2. square submatrix of AA' is also square submatrix of AA.
  3. The submatrices that doesn't contain the first row has corresponding submatrix in AA, ones that does contain the first row has determinant 0.
  4. see inverse of a totally unimodular matrix.
  5. row switching. Consider we switched row ii and jj. Consider any submatrix, if it doesn't contain row ii or jj, then it still has determinant 1,0,1-1,0,1. If it contain both row ii and jj, then the determinant is just the negation when the rows are switched back. If it only contain one of row ii and jj, wlog let it be ii, then it has the rows in order a1,,ak,i,ak+1,,ala_1,\ldots,a_k,i,a_{k+1},\ldots,a_l, then there is a submatrix in AA using the rows in sequence a1,,aj,i,aj+1,,ala_1,\ldots,a_j,i,a_{j+1},\ldots,a_l, and the absolute value of their determinants are equal.
  6. multiply by a constant to preserve the 1,0,1-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 TUTU.

TUTU is not closed under matrix multiplication, consider [1101]2=[1201]\begin{bmatrix} 1 & 1 \\ 0 & 1\end{bmatrix}^2 = \begin{bmatrix} 1 & 2 \\ 0 & 1\end{bmatrix}.

Posted by Chao Xu on .
Tags: matrix.