CMR  1.3.0
Camion's Signing Algorithm

A key tool for the recognition of network matrices, totally unimodular matrices and balanceable matrices is Camion's signing algorithm. Its input is a binary matrix \( M \in \{0,1\}^{m \times n} \) and it computes a ternary matrix \( M' \in \{-1,0,+1\}^{m \times n} \) with the same support, i.e., the same nonzero entries. The output matrix \( M' \) is guaranteed to be balanced if (and only if) \( M \) was balanceable. This means that for every square submatrix of \( M' \) with two nonzero entries per row and per column the the sum of all entries is divisible by 4. The algorithm always outputs a Camion-signed matrix, regardless of whether the input matrix was balanceable. In particular, it does not recognize whether it deals with a balanceable matrix or not.

If \( M \) is balanceable, then \( M' \) is unique up to scaling rows/columns with \( -1 \).

Usage

The executable cmr-camion checks whether a given matrix \( M \) is Camion-signed.

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

Options:

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

Note
A Camion-signed version of a matrix can be computed via cmr-convert-matrix -c.

Algorithm

The implemented recognition algorithm is based on Section 18 of A decomposition theory for matroids. V. Testing of matrix total unimodularity by Klaus Truemper (Journal of Combinatorial Theory, Series B, 1990). For a matrix \( M \in \{-1,0,1\}^{m \times n} \) it runs in \( \mathcal{O}( \min(m^2 \cdot n, m \cdot n^2) ) \) time.

C Interface

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