Consider a binary matrix \( M \in \{0,1\}^{m \times n} \). A row complement for row \( i \) is obtained by complementing all entries \( M_{r,c} \) with \( r \neq i \) and \( M_{i,c} = 1 \). A column complement is defined as a row complement on the transpose matrix. A binary matrix \( M \) is complement totally unimodular if all matrices obtainable by successive row- and column complements are totally unimodular. It turns out that all such matrices can be obtained already by at most one row complement and at most one column complement. Hence, complement total unimodularity can be checked by checking \( (m+1) \cdot (n+1) \) matrices for total unimodularity.

Usage

The executable cmr-ctu determines whether a given matrix \( M \) is complement totally unimodular or applies row- or column-complement operations (or both at the same time) to \( M \).

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

Options:

-i FORMAT Format of input FILE; default: dense.
-o FORMAT Format of output matrices; default: dense.
-r ROW Perform a row complement operation on \( M \) and do not test for complement total unimodularity.
-c COLUMN Perform a row complement operation on \( M \) and do not test for complement total unimodularity.
-n Output a complement operations that leads tfile:///home/matthias/code/cmr/develop.git/src/main/tu_main.co a non-totally-unimodular matrix (if \( M \) is not complement totally unimodular).
-N Output a complemented matrix that is non-totally-unimodular (if \( M \) is not complement totally unimodular).
-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. If -r or -c (or both) are specified, then \( M \) is not tested for complement total unimodularity.

C Interface

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

CMRcomplementRowColumn() carries out a row- and column-complement operations for a matrix.
CMRtestComplementTotalUnimodularity() tests a matrix for being complement totally unimodular.