Content deleted Content added
Joerg Bader (talk | contribs) More changes. |
m task, replaced: SIAM. J. on Algebraic and Discrete Methods → SIAM Journal on Algebraic and Discrete Methods |
||
Line 1:
In [[mathematics]], a '''balanced matrix''' is a 0-1 [[Matrix (mathematics)|matrix]] (a matrix where every entry is either zero or one) that does not contain any [[Square matrix|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.
As an example, the following matrix is a balanced matrix:
Line 12:
== 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:
Line 35:
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:
Line 44:
1 & 0 & 0 & 1\\
\end{bmatrix}</math>
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
Line 53:
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<ref name="RyanFalkner" /> 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 ==
| |||