Balanced matrix: Difference between revisions

Revision as of 11:59, 7 April 2017

Latest revision as of 21:01, 14 April 2025

(11 intermediate revisions by 7 users not shown)

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 sumsums 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 objecticeobjective 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.|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=303–308[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_programmingLinear programming#Optimal_vertices_Optimal vertices .28and_rays28and rays.29_of_polyhedra29 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 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:

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

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

:<math>BC_3=\begin{bmatrix}

1 & 0 & 1\\

1 & 1 & 0\\

Line 11 ⟶ 21:

\end{bmatrix}</math>

The following matrix is the incidence matrix of a 5cycle ordergraph forbiddenof submatrixorder 5:

:<math>C_5=\begin{bmatrix}

1 & 0 & 0 & 0 & 1\\

1 & 1 & 0 & 0 & 0\\

Line 19 ⟶ 29:

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

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 Journal on Algebraic and Discrete Methods|volume=6|issue=4|pages=720–731}}</ref>

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

:<math>B=\begin{bmatrix}

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

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>

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>

== 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 (mathematics)]]