Balanced matrix

In mathematics, a balanced matrix is a matrix in which 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 objective 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: : \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1\\ \end{bmatrix}

In mathematics, a balanced matrix is a matrix in which 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 objective 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: \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1\\ \end{bmatrix} 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: 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. SC = |{t | [a sj  = 1, a ij  = 0 for s  tj  = 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376847937 under CC BY-SA 4.0; modifications have been made.