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.
(or the incidence matrix of any other odd cycle) as a submatrix, is not balanced.
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.
[2] For example, balanced matrices arise as the coefficient matrix in special cases of the set partitioning problem.
[4] 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 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[4] and therefore also balanced.