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, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
-N NON-SUB Write a minimal non-balanced submatrix to file NON-SUB; default: skip computation.
-s Print statistics about the computation to stderr.

Advanced options:

--time-limit LIMIT Allow at most LIMIT seconds for the computation.
--algorithm ALGO Algorithm to use, among enumerate and graph; default: choose best.

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 are implemented 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.

C Interface

The corresponding function in the library is

CMRtestBalanced() tests a matrix for balancedness.

and is defined in balanced.h.