Balanced matrix

In mathematics, a balanced matrix B is an integer matrix that does not contain any odd order 2-cycle submatricies (submatrix of order n where n is odd and the row and column sums equal 2).

Balanced matricies are important in linear programs such as the set partitioning problem, as they are naturally integer. Totally unimodular matricies are a subset of balanced matricies, and balanced matricies are a subset of perfect matricies, therefore any matrix that is totally unimodular is also balanced, however a balanced matrix may not necessarily be totally unimodular.

The following matrix is a 3 order 2-cycle submatrix:

${\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\\\end{bmatrix}}$

The following matrix is a balanced matrix as it does not contain the above nor any other odd order 2-cycle submatrix:

$B={\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}$

Subsequence Count

An alternative method of identifying a balanced matrix that is also a zero-one matrix is through the subsequence count, where the subsequence count SC of any row s of matrix A is

SC = |{t | [a_sj=1, a_ij=0 for s<i<t, a_tj=1], j=1,...,n}|

If a matrix A has SC(s) <= 1 for all rows s = 1,...,m, then A has a unique subsequence, and is also balanced.

References

• Berge, C. (1972), Balanced Matricies, Paris, France: Centre National de Recherche Scientifique