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; default: dense.
-o FORMAT Format of file OUT-MAT; 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.

Advanced options:

--stats Print statistics about the computation to stderr.
--time-limit LIMIT Allow at most LIMIT seconds for the computation.

Formats for matrices: dense, sparse

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

CMRctuTest() tests a matrix for being complement totally unimodular.

and is defined in ctu.h.

Applying Complement Operations