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.[1][2] 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:
\( {\displaystyle {\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).[2]
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:
\( {\displaystyle 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:
\( {\displaystyle 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.[3]
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:
\( {\displaystyle {\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.[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
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[4] 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.[5]
References
Berge, C. (1972). "Balanced matrices". Mathematical Programming. 2: 19–31. doi:10.1007/BF01584535. S2CID 41468611.
Alexander Schrijver (1998). Theory of Linear and Integer Programming. John Wiley & Sons. pp. 303–308. ISBN 978-0-471-98232-6.
Hoffman, A.J.; Kolen, A.W.J.; Sakarovitch, M. (1982). "Totally-balanced and Greedy Matrices". SIAM Journal on Algebraic and Discrete Methods. BW (Series). 6 (4): 720–731. doi:10.1137/0606070.
Ryan, D. M.; Falkner, J. C. (1988). "On the integer properties of scheduling set partitioning models". European Journal of Operational Research. 35 (3): 442–456. doi:10.1016/0377-2217(88)90233-0.
Conforti, Michele; Cornuéjols, Gérard; Vušković, Kristina (2006), "Balanced matrices" (PDF), Discrete Mathematics, 306 (19–20): 2411, doi:10.1016/j.disc.2005.12.033 A retrospective and tutorial.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
