A ternary matrix \( M \in \{-1,0,+1\}^{m \times n} \) is called balanced if it does not contain a square submatrix with two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A binary matrix \( M \in \{0,1\}^{m \times n} \) is called balanceable if and its nonzero entries can be signed so that the resulting matrix is balanced.

Recognizing Balanced Matrices

The command

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

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

Options:

-i FORMAT Format of file IN-MAT; default: dense.
-N NON-SUB Write a minimal non-balanced submatrix to file NON-SUB; default: skip computation.

Advanced options:

--stats Print statistics about the computation to stderr.
--time-limit LIMIT Allow at most LIMIT seconds for the computation.
--algorithm ALGO Algorithm to use, among enumerate and graph; default: choose best.
--no-series-parallel Do not try series-parallel operations for preprocessing.

Formats for matrices: dense, sparse

If IN-MAT is - then the matrix is read from stdin.

If NON-SUB is - then the submatrix is written to stdout.

Algorithm

Two types of algorithms exist for both, the binary and the ternary case. The first algorithm types enumerate subsets of rows and then finds subsets of columns such that the resulting submatrix defines an odd cycle. Its running time is exponential in the size of the matrix. The second algorithm types are the polynomial-time algorithms by Giacomo Zambelli (Journal of Combinatorial Theory, Series B, 2005). They run in \( \mathcal{O}( (m+n)^9 ) \) time for binary matrices and in \( \mathcal{O}( (m+n)^{11} ) \) time for ternary matrices.

Note: Only the first algorithm is implemented so far.

C Interface

The corresponding function in the library is

CMRbalancedTest() tests a matrix for balancedness.

and is defined in balanced.h.