In [[mathematics]], a '''balanced matrix''' is a 0-1 [[Matrix (mathematics)|matrix]] that does not contain any [[Square matrix|square submatrix]] of odd order having row and column sum equal to 2.
Balanced matrices are studied in [[linear programming|'''[[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. <ref>{{cite journal|doi=10.1007/BF01584535|title=Balanced matrices|journal=Mathematical Programming|volume=2|pages=19|year=1972|last1=Berge|first1=C.}}</ref><ref name="Schrijver1998">{{cite book|author=Alexander Schrijver|title=Theory of Linear and Integer Programming|year=1998|publisher=John Wiley & Sons|isbn=978-0-471-98232-6|pages=303–308}}</ref> 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 [[Linear_programming#Optimal_vertices_.28and_rays.29_of_polyhedra|optimal vertex solution]] of the [[Linear programming relaxation|linear program itself]].
