Balanced matrix

In mathematics, a balanced matrix 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 studied in linear programming. The importance of balanced matrices comes from the fact that the solution to a linear programming problem is integral if its matrix of coefficients is balanced and its right hand side or its objectice vector is an all-one vector. In particular, if one searches for an integral solution to a linear program of this kind, it is not necessary to explicitly solve an integer linear program, but it suffices to find an optimal vertex solution of the linear program itself.

Odd order 2-cycle matrices

The only three by three 0-1 matrix that is not balanced is (up to permutation of the rows and columns) the 3 order 2-cycle matrix:

${\begin{bmatrix}1&0&1\\1&1&0\\0&1&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}}$

Connection to other matrix classes

Balanced matrices are a subset of perfect matrices. On the other hand, 0-1 totally unimodular matrices are a subset of balanced matrices, therefore any 0-1 matrix that is totally unimodular is also balanced.

The following matrix is a balanced matrix as it does not contain any 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}}$

Since this matrix is not totally unimodular (its determinant is -2), 0-1 totally unimodular matrices are a proper subset of balanced matrices.

Balanced matrices also arise as the coefficient matrix in special cases of the set partitioning problem.

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

• Conforti, Michele; Cornuéjols, Gérard; Vušković, Kristina (2006), "Balanced matrices", Discrete Mathematics, 306 (19–20): 2411, doi:10.1016/j.disc.2005.12.033 A retrospective and tutorial.