Balanced matrix: Difference between revisions

Revision as of 09:51, 14 March 2017

Revision as of 11:59, 7 April 2017

Line 1:

In [[mathematics]], a '''balanced matrix''' ''B'' 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.

{{Expert-subject|Mathematics|date=March 2011}}

In [[mathematics]], a '''balanced matrix''' ''B'' is a 0-1 matrix that does not contain any 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]].

Balanced matrices are important in [[linear programming|'''linear programming''']] such as the [[set partitioning problem]], as they are naturally integer. The result is that the solution to a linear program problem will be integer for these cases, without having to explicitly solve an [[integer linear program]].

== Odd order 2-cycle matrices ==

0-1 [[Totally unimodular]] matrices are a subset of balanced matrices, and balanced matrices are a subset of [[perfect matrix|perfect matrices]], therefore any matrix that is totally unimodular is also balanced, however a balanced matrix may not necessarily be [[totally unimodular]].

The only three by three 0-1 matrix that is not balanced is (up to permutation of the rows and columns) the 3 order 2-cycle matrix:

The following matrix is a 3 order 2-cycle forbidden submatrix:

:<math>\begin{bmatrix}

1 & 0 & 1\\

1 & 1 & 0\\

0 & 1 & 1\\

\end{bmatrix}</math>

The following matrix is a balanced matrix as it does not contain the above nor any other odd order 2-cycle submatrix:

:<math>B=\begin{bmatrix}

1 & 1 & 1 & 1\\

1 & 1 & 0 & 0\\

1 & 0 & 1 & 0\\

1 & 0 & 0 & 1\\

\end{bmatrix}</math>

Line 29 ⟶ 19:

0 & 0 & 0 & 1 & 1\\

\end{bmatrix}</math>

== Connection to other matrix classes ==

0-1 [[Totally unimodular]]Balanced matrices are a subset of balanced[[perfect matrix|perfect matrices]]. On the other hand, and0-1 balanced[[totally unimodular]] matrices are a subset of [[perfect matrix|perfectbalanced matrices]], therefore any 0-1 matrix that is totally unimodular is also balanced, however a balanced matrix may not necessarily be [[totally unimodular]].

The following matrix is a 3balanced matrix as it does not contain any odd order 2-cycle forbidden submatrix:

:<math>B=\begin{bmatrix}

1 & 1 & 1 & 1\\

1 & 1 & 0 & 0\\

1 & 0 & 1 & 0\\

1 & 0 & 0 & 1\\

\end{bmatrix}</math>

Since this matrix is not totally unimodular (its determinant is -2), 0-1 totally unimodular matrices are a [[proper subset]] of balanced matrices. <ref name="Schrijver1998" />

Balanced matrices also arise as the coefficient matrix in special cases of the [[set partitioning problem]]. <ref name="RyanFalkner">{{cite journal|last1 = Ryan | first1 = D. M. | last2 = Falkner | first2 = J. C. | year = 1988 | title = On the integer properties of scheduling set partitioning models | doi = 10.1016/0377-2217(88)90233-0 | journal = European Journal of Operational Research | volume = 35 | issue = 3 | pages = 442–456}}</ref>

== Subsequence count ==

Line 34 ⟶ 39:

:'''SC''' = |{''t'' | [''a''_''sj''&nbsp;=&nbsp;1, ''a''_''ij''&nbsp;=&nbsp;0 for ''s''&nbsp;<&nbsp;''i''&nbsp;<&nbsp;''t'', ''a''_''tj''&nbsp;=&nbsp;1], ''j''&nbsp;=&nbsp;1,&nbsp;...,&nbsp;''n''}|

If a 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>Ryan &name="RyanFalkner" Falkner 1988</ref> and therefore also balanced. Note that this condition is sufficient but not necessary for ''A'' to be balanced.

== Notes ==

Line 40 ⟶ 45:

== References ==

* {{Citation

| last1 = Ryan | first1 = D. M.

| last2 = Falkner | first2 = J. C.

| year = 1988

| title = On the integer properties of scheduling set partitioning models

| doi = 10.1016/0377-2217(88)90233-0

| journal = European Journal of Operational Research

| volume = 35 | issue = 3 | pages = 442–456}}

* {{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}} A retrospective and tutorial.

* {{citation|doi=10.1007/BF01584535|title=Balanced matrices|journal=Mathematical Programming|volume=2|pages=19|year=1972|last1=Berge|first1=C.}}

[[Category:Matrices]]