The Art Gallery Guardian

Totally Unimodular Matrices


Definition1Totally Unimodular Matrices

A matrix is totally unimodular if for all square submatrix of , .

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

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

Proposition2

If , be the th row of , then

  1. ,
  2. is a submatrix of , then ,
  3. .
  4. If is a square matrix, then ,
  5. If is formed by row swapping of , then .
  6. Multiply by to a row.
Proof
  1. .
  2. square submatrix of is also square submatrix of .
  3. The submatrices that doesn’t contain the first row has corresponding submatrix in , 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 and . Consider any submatrix, if it doesn’t contain row or , then it still has determinant . If it contain both row and , then the determinant is just the negation when the rows are switched back. If it only contain one of row and , wlog let it be , then it has the rows in order , then there is a submatrix in using the rows in sequence , and the absolute value of their determinants are equal.
  6. multiply by a constant to preserve the 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 .

is not closed under matrix multiplication, consider .

Posted by Chao Xu on .
Tags: matrix.