Balanced matrix

In mathematics, a balanced matrix is a 0-1 matrix that does not contain any square submatrix of odd order having all row sums and all column sums 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 cycle matrices

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

$C_{3}={\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\\\end{bmatrix}}$

It is an incidence matrix of the cycle graph of order 3.

Equivalent to the above definition, a matrix is balanced if and only if it does not contain a submatrix that is the incidence matrix of any odd cycle (a cycle graph of odd order). For example, the following matrix is a forbidden submatrix resulting from a cyle of order 5:

$C_{5}={\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}}$

The above implies that any matrix containing $C_{5}$ as a submatrix (possibly after permutation of rows or columns) is not balanced.

Connection to other matrix classes

Every balanced matrix is a perfect matrix.

More restricting than the notion of balanced matrices is the notion of totally balanced matrices. A 0-1 matrix is called totally balanced if it does not contain a square submatrix having no repeated columns and all row sums and all column sums equal to 2. Equivalently, a matrix is totally balanced if and only if it does not contain a submatrix that is the incidence matrix of any cycle (no matter if of odd or even order). This characterization immediately implies that any totally balanced matrix is balanced.

Moreover, any 0-1 matrix that is totally unimodular is also balanced. The following matrix is a balanced matrix as it does not contain any submatrix that is incidence matrix of an odd order cycle:

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

For example, balanced matrices 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.