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 equalling 2).

The following matrix is an odd order 2-cycle submatrix:

$A={\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 A 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}}.$

Balanced matricies are important in linear programs 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.

References

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