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 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.
As an example, the following matrix is a balanced matrix:
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:
The following matrix is the incidence matrix of a cycle graph of order 5:
The above characterization implies that any matrix containing or (or the incidence matrix of any other odd cycle) as a submatrix, is not balanced.
...
Wikipedia