Balanced matrix

In mathematics, a balanced matrix is a 0-1 matrix (a matrix where every entry is either zero or one) 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 objective 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.

As an example, the following matrix is a balanced matrix:

${\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}$

Characterization by forbidden submatrices

Equivalent to the definition, a 0-1 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).

Therefore, the only three by three 0-1 matrix that is not balanced is (up to permutation of the rows and columns) the following incidence matrix of a cycle graph of order 3:

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

The following matrix is the incidence matrix of a cycle graph 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 characterization implies that any matrix containing $C_{3}$ or $C_{5}$ (or the incidence matrix of any other odd cycle) as a submatrix, 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 the incidence matrix of an odd 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.

An alternative method of identifying some balanced matrices 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 0-1 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. In other words, the 0-1 matrices with SC(s) ≤ 1 for all rows s = 1, ..., m are a proper subset of the set of balanced matrices.

As a more general notion, a matrix where every entry is either 0, 1 or -1 is called balanced if in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of 4.