Balanced matrix: Difference between revisions

Revision as of 12:16, 19 June 2017

Revision as of 14:16, 28 June 2017

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.}}</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]].

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

== Odd order cycle matrices ==

:<math>\begin{bmatrix}

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

1 & 1 & 1 & 1\\

1 & 1 & 0 & 0\\

1 & 0 & 1 & 0\\

1 & 0 & 0 & 1\\

\end{bmatrix}</math>

== Characterization by forbidden submatrices ==

Equivalent to the definition, a 0-1 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). <ref name="Schrijver1998" />

TheTherefore, the only three by three 0-1 matrix that is not balanced is (up to permutation of the rows and columns) the cyclefollowing incidence matrix of a cycle graph of order 3:

:<math>C_3=\begin{bmatrix}

1 & 0 & 1\\

Line 10 ⟶ 20:

0 & 1 & 1\\

\end{bmatrix}</math>

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

EquivalentThe to the above definition, afollowing 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:

:<math>C_5=\begin{bmatrix}

1 & 0 & 0 & 0 & 1\\

Line 20 ⟶ 29:

0 & 0 & 0 & 1 & 1\\

\end{bmatrix}</math>

The above characterization implies that any matrix containing <math>C_5C_3</math> asor a submatrix<math>C_5</math> (possiblyor afterthe permutationincidence matrix of rowsany orother columnsodd cycle) as a submatrix, is not balanced.

== Connection to other matrix classes ==

Line 26 ⟶ 35:

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

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>

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 the incidence matrix of an odd cycle:

:<math>\begin{bmatrix}

1 & 1 & 1 & 1\\

Line 39 ⟶ 48:

For example, balanced 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>

An alternative method of identifying asome balanced matrix that is also a zero-one matrixmatrices is through the subsequence count, where the subsequence count ''SC'' of any row s of matrix ''A'' is

== Subsequence count ==

An alternative method of identifying a balanced matrix that is also a zero-one matrix is through the subsequence count, where the subsequence count ''SC'' of any row s of matrix ''A'' is

:'''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 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}} A retrospective and tutorial.</ref>

== Notes ==

{{Reflist}}

== References ==

{{reflist}}

* {{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.

[[Category:Matrices]]