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:

• -i FORMAT Format of input FILE; default: dense.
• -o FORMAT Format of output matrices; default: dense.
• -n Output the elements of a minimal non-Camion submatrix.
• -N Output a minimal non-Camion 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.

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: