Balanced matrix: Difference between revisions

Revision as of 03:38, 17 August 2019

Latest revision as of 21:01, 14 April 2025

(4 intermediate revisions by 4 users not shown)

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=303–308[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:

Line 53:

If a 0-1 matrix ''A'' has SC(''s'')&nbsp;≤&nbsp;1 for all rows ''s''&nbsp;=&nbsp;1,&nbsp;...,&nbsp;''m'', then ''A'' has a unique subsequence, is totally unimodular<ref name="RyanFalkner" /> 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'')&nbsp;≤&nbsp;1 for all rows ''s''&nbsp;=&nbsp;1,&nbsp;...,&nbsp;''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.<ref>{{citation|doi=10.1016/j.disc.2005.12.033|title=Balanced matrices|journal=Discrete Mathematics|volume=306|issue=19–20|pages=2411|year=2006|last1=Conforti|first1=Michele|last2=Cornuéjols|first2=Gérard|last3=Vušković|first3=Kristina|author3-link= Kristina Vušković |url=http://eprints.whiterose.ac.uk/74351/2/surveyFINAL.pdf}} A retrospective and tutorial.</ref>

== References ==

{{reflist}}

[[Category:Matrices (mathematics)]]