Balanced matrix: Difference between revisions

Revision as of 17:58, 7 October 2010

Latest revision as of 21:01, 14 April 2025

(35 intermediate revisions by 19 users not shown)

Line 1:

In [[mathematics]], a '''balanced matrix''' ''B'' is ana 0-1 [[integerMatrix (mathematics)|matrix]] (a matrix where every entry is either zero or one) that does not contain any odd[[Square order 2-cycle submatricesmatrix|square (submatrix]] of odd order ''n''having whereall ''n''row is oddsums and the row andall column sums equal  to 2).

{{orphan|date=July 2010}}

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 objective 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]].

{{expert-subject|Mathematics}}

In [[mathematics]], a '''balanced matrix''' ''B'' is an [[integer matrix]] that does not contain any odd order 2-cycle submatrices (submatrix of order ''n'' where ''n'' is odd and the row and column sums equal&nbsp;2).

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

Balanced matrices are important in linear programs such as the [[set partitioning problem]], as they are naturally integer. [[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 following matrix is a 3 order 2-cycle submatrix:

:<math>\begin{bmatrix}

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" />

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

:<math>C_3=\begin{bmatrix}

1 & 0 & 1\\

1 & 1 & 0\\

Line 13 ⟶ 21:

\end{bmatrix}</math>

The following matrix is athe balancedincidence matrix asof ita doescycle notgraph contain the above nor any other oddof order 2-cycle submatrix5:

:<math>BC_5=\begin{bmatrix}

1 & 0 & 0 & 0 & 1\\

1 & 1 & 0 & 0 & 0\\

0 & 1 & 1 & 0 & 0\\

0 & 0 & 1 & 1 & 0\\

0 & 0 & 0 & 1 & 1\\

\end{bmatrix}</math>

The above characterization implies that any matrix containing <math>C_3</math> or <math>C_5</math> (or the incidence matrix of any other odd cycle) as a submatrix, is not balanced.

== Connection to other matrix classes ==

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 Journal on Algebraic and Discrete Methods|volume=6|issue=4|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\\

1 & 1 & 0 & 0\\

Line 20 ⟶ 44:

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" />

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|author3-link= Kristina Vušković |url=http://eprints.whiterose.ac.uk/74351/2/surveyFINAL.pdf}} A retrospective and tutorial.</ref>

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, and is also balanced.

== References ==

{{reflist}}

*{{Citation

| last = Berge

| first = C.

| year = 1972

| title = Balanced Matricies

| publisher = Centre National de Recherche Scientifique

| ___location = Paris, France}}

[[Category:Matrices (mathematics)]]