Implementation of Balanced Matrix Recognition Algorithms

A {0,±1} matrix is balanced if it does not contain a square submatrix with two nonzero elements per row and column in which the sum of all entries is 2 modulo 4. G. Zambelli provided a polynomial algorithm to test balancedness of a matrix. This paper discusses the algorithm and its implementation, and compares it against a naive approach using an exponential algorithm. The running time of the polynomial algorithm is O(n^9) for {0, 1} matrices and O(n^11) for {0,±1} matrices, where n is the number of rows and columns of the input matrix.