CMR  1.3.0
Totally Unimodular Matrices

A matrix \( M \in \mathbb{Z}^{m \times n} \) is totally unimodular if all its square submatrices have a determinant in \( \{-1,0,+1\} \). Here, a submatrix does not need to be contiguous, i.e., the matrix \(M = \begin{pmatrix} 1 & 0 & -1 \\ 1 & 0 & 1 \end{pmatrix} \) is not totally unimodular since the submatrix indexed by rows \( \{1, 2 \} \) and columns \( \{ 1,3 \} \) has determinant 2. In particular, every totally unimodular matrix has only entries in \( \{-1,0,+1\} \) as these are the 1-by-1 submatrices.

Usage

The executable cmr-tu determines whether a given matrix \( M \) is totally unimodular.

./cmr-tu [OPTION]... FILE

Options:

Formats for matrices are dense-matrix and sparse-matrix. If FILE is -, then the input will be read from stdin.

Algorithm

The implemented recognition algorithm is based on Implementation of a unimodularity test by Matthias Walter and Klaus Truemper (Mathematical Programming Computation, 2013). It first runs Camion's Signing Algorithm to reduce the question to that of recognizing regular matroids. Please cite the paper in case the implementation contributed to your research:

@Article{WalterT13,
  author    = {Walter, Matthias and Truemper, Klaus},
  title     = {Implementation of a unimodularity test},
  journal   = {Mathematical Programming Computation},
  year      = {2013},
  volume    = {5},
  number    = {1},
  pages     = {57--73},
  issn      = {1867-2949},
  doi       = {10.1007/s12532-012-0048-x},
  publisher = {Springer-Verlag},
}

C Interface

The functionality is defined in tu.h. The main functions are: