Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Balanced matrix
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a balanced matrix is a 0-1 <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> (a matrix where every entry is either zero or one) that does not contain any <a href="/facts/Square_matrix/5TP9mNNn">square submatrix</a> of odd order having all row sums and all column sums equal to 2. </p><p>Balanced matrices are studied in <a href="/facts/Linear_programming/GduXFQxT">linear programming</a>. 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 <a href="/facts/Integer_linear_program/MDaaadoA">integer linear program</a>, but it suffices to find an <a href="/facts/Linear_programming/GduXFQxT">optimal vertex solution</a> of the <a href="/facts/Linear_programming_relaxation/s26bWxAr">linear program itself</a>. </p><p>As an example, the following matrix is a balanced matrix: </p> [ 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 ] {\displaystyle {\begin{bmatrix}1&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1\\\end{bmatrix}}}