CMR
1.3.0
|
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.
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.
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.
The corresponding function in the library is
and is defined in balanced.h.