Balanced matrix

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

Balanced matrices are important in linear programs such as the set partitioning problem, as they are naturally integer. Totally unimodular matrices are a subset of balanced matrices, and balanced matrices are a subset of perfect matrices, 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, is totally unimodular and therefore also balanced. Note that this condition is sufficient but not necessary for A to be balanced.

References

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

• Ryan, D. M.; Falkner, J. C. (1988), "On the integer properties of scheduling set partitioning models", European Journal of Operational Research, 35 (3): 442–456, doi:10.1016/0377-2217(88)90233-0