Balanced matrix: Difference between revisions

Revision as of 20:25, 8 September 2020

Revision as of 15:04, 27 November 2020

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 objecticeobjective vector is an all-one vector.<ref>{{cite journal|doi=10.1007/BF01584535|title=Balanced matrices|journal=Mathematical Programming|volume=2|pages=19–31|year=1972|last1=Berge|first1=C.|s2cid=41468611}}</ref><ref name="Schrijver1998">{{cite book|author=Alexander Schrijver|title=Theory of Linear and Integer Programming|url=https://archive.org/details/theorylinearinte00schr_718|url-access=limited|year=1998|publisher=John Wiley & Sons|isbn=978-0-471-98232-6|pages=[https://archive.org/details/theorylinearinte00schr_718/page/n315 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]].

As an example, the following matrix is a balanced matrix: