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 | [asj = 1, aij = 0 for s < i < t, atj = 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. References Matrices