Balanced matrix

In mathematics, a balanced matrix B is a 0-1 matrix that does not contain any square submatrix of odd order having row and column sum equal to 2.

Balanced matrices are important in linear programming such as the set partitioning problem, as they are naturally integer. The result is that the solution to a linear program problem will be integer for these cases, without having to explicitly solve an integer linear program.

0-1 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 forbidden 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}$

The following matrix is a 5 order forbidden submatrix:

$\begin{bmatrix} 1 & 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 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^[1] and therefore also balanced. Note that this condition is sufficient but not necessary for A to be balanced.

Notes

1. Ryan & Falkner 1988

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