Complement Totally Unimodular Matrices

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.

Recognizing Complement Totally Unimodular Matrices

The command

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

determines whether the matrix given in file IN-MAT is complement totally unimodular.

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 for IN-MAT.
• -n OUT-OPS Write complement operations that leads to a non-totally-unimodular matrix to file OUT-OPS; default: skip computation.
• -N OUT-MAT Write a complemented matrix that is non-totally-unimodular to file OUT-MAT; default: skip computation.
• -s Print statistics about the computation to stderr.

If IN-MAT is - then the matrix is read from stdin. If OUT-OPS or OUT-MAT is - then the list of operations (resp. the matrix) is written to stdout.

C Interface

The corresponding function in the library is

• CMRtestComplementTotalUnimodularity() tests a matrix for being complement totally unimodular.

and is defined in ctu.h.

Applying Complement Operations

The command

cmr-ctu IN-MAT OUT-MAT [OPTION]...

applies a sequence of row or column complement operations the matrix given in file IN-MAT and writes the result to 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 for IN-MAT.
• -r ROW Apply row complement operation to row ROW.
• -c COLUMN Apply column complement operation to column COLUMN.
• -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.

C Interface

The corresponding function in the library is

• CMRcomplementRowColumn() carries out a row- or column-complement operation for a matrix.

and is defined in ctu.h.