Content deleted Content added
Bluelink 1 book for verifiability (prndis)) #IABot (v2.0.1) (GreenC bot |
Citation bot (talk | contribs) Add: url, s2cid. | You can use this bot yourself. Report bugs here. | Suggested by SemperIocundus | via #UCB_webform |
||
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 objectice 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:
Line 53:
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<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'') ≤ 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.<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|url=http://eprints.whiterose.ac.uk/74351/2/surveyFINAL.pdf}} A retrospective and tutorial.</ref>
== References ==
| |||