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:

• -i FORMAT Format of input FILE; default: dense.
• -o FORMAT Format of output matrices; default: dense.
• -d Output the decomposition tree of the underlying regular matroid.
• n Output the elements of a minimal non-totally-unimodular submatrix.
• N Output a minimal non-totally-unimodular submatrix.
• s Print statistics about the computation to stderr.

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: