Balanced matrix: Difference between revisions

Revision as of 04:55, 28 April 2017

Revision as of 12:13, 19 June 2017

Line 1:

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 all row sums and all column sumsums 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=1919–31|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]].

== Odd order 2-cycle matrices ==

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 of order 3:

:<math>C_3=\begin{bmatrix}

1 & 0 & 1\\

1 & 1 & 0\\

0 & 1 & 1\\

\end{bmatrix}</math>

It is an [[incidence matrix]] of the [[cycle graph]] of order 3.

Equivalent to the above definition, a matrix is balanced [[if and only if]] it does not contain a submatrix that is the incidence matrix of any ''odd cycle'' (a cycle graph of odd order). For example, the following matrix is a forbidden submatrix resulting from a cyle of order 5:

The following matrix is a 5 order forbidden submatrix:

:<math>C_5=\begin{bmatrix}

1 & 0 & 0 & 0 & 1\\

1 & 1 & 0 & 0 & 0\\

Line 19 ⟶ 20:

0 & 0 & 0 & 1 & 1\\

\end{bmatrix}</math>

The above implies that any matrix containing <math>C_5</math> as a submatrix (possibly after permutation of rows or columns) is not balanced.

== Connection to other matrix classes ==

Every balanced matrix is a [[perfect matrix]].

Balanced matrices are a subset of [[perfect matrix|perfect matrices]]. On the other hand, 0-1 [[totally unimodular]] matrices are a subset of balanced matrices, therefore any 0-1 matrix that is totally unimodular is also balanced.

More restricting than the notion of balanced matrices is the notion of ''totally balanced'' matrices. A 0-1 matrix is called totally balanced if it does not contain a square submatrix having no repeated columns and all row sums and all column sums equal to 2. Equivalently, a matrix is totally balanced if and only if it does not contain a submatrix that is the incidence matrix of any cycle (no matter if of odd or even order). This characterization immediately implies that any totally balanced matrix is balanced. <ref>{{cite journal|doi=10.1137/0606070|title=Totally-balanced and Greedy Matrices|last1=Hoffman|first1=A.J.|last2=Kolen|first2=A.W.J.|last3=Sakarovitch|first3=M.|series=BW (Series)|year=1982|journal=SIAM. J. on Algebraic and Discrete Methods|pages=720–731}}</ref>

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

Moreover, any 0-1 matrix that is [[totally unimodular]] is also balanced. The following matrix is a balanced matrix as it does not contain any submatrix that is incidence matrix of an odd order 2-cycle submatrix:

:<math>B=\begin{bmatrix}

1 & 1 & 1 & 1\\

Line 33 ⟶ 37:

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>

BalancedFor matricesexample, alsobalanced matrices 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 ==