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 \).

Checking for being Camion-signed

The command

cmr-camion IN-MAT [OPTION]...

determines whether the matrix given in file IN-MAT is Camion-signed.

Options:

• -i FORMAT Format of file IN-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
• -N NON-SUB Write a minimal non-Camion submatrix to file NON-SUB; default: skip computation.
• -s Print statistics about the computation to stderr.

If IN-MAT is - then the matrix is read from stdin. If NON-SUB is - then the submatrix is written to stdout.

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 corresponding function in the library is

• CMRcamionTestSigns() tests a matrix for being Camion-signed.

and is defined in camion.h.

Camion-signing a Matrix

The command

cmr-camion IN-MAT -S OUT-MAT [OPTION]...

modifies the signs of the matrix given in file IN-MAT such that it is Camion-signed and writes the resulting new matrix to file OUT-MAT.

Options:

• -i FORMAT Format of file IN-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
• -o FORMAT Format of file OUT-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: same as format of IN-MAT.
• -s Print statistics about the computation to stderr.

If IN-MAT is - then the matrix is read from stdin. If OUT-MAT is - then the matrix is written to stdout.

Algorithm

The implemented 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 corresponding function in the library is

• CMRcamionComputeSigns() Computes a Camion-signed version of a given ternary matrix.

and is defined in camion.h.