CMR
1.3.0

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 Camionsigned 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 \).
The command
cmrcamion INMAT [OPTION]...
determines whether the matrix given in file INMAT
is Camionsigned.
Options:
i FORMAT
Format of file INMAT
, among dense
for densematrix and sparse
for sparsematrix; default: dense.N NONSUB
Write a minimal nonCamion submatrix to file NONSUB
; default: skip computation.s
Print statistics about the computation to stderr.If INMAT
is 
then the matrix is read from stdin. If NONSUB
is 
then the submatrix is written to stdout.
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.
The corresponding function in the library is
and is defined in camion.h.
The command
cmrcamion INMAT S OUTMAT [OPTION]...
modifies the signs of the matrix given in file INMAT
such that it is Camionsigned and writes the resulting new matrix to file OUTMAT
.
Options:
i FORMAT
Format of file INMAT
, among dense
for densematrix and sparse
for sparsematrix; default: dense.o FORMAT
Format of file OUTMAT
, among dense
for densematrix and sparse
for sparsematrix; default: same as format of INMAT
.s
Print statistics about the computation to stderr.If INMAT
is 
then the matrix is read from stdin. If OUTMAT
is 
then the matrix is written to stdout.
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.
The corresponding function in the library is
and is defined in camion.h.