Content deleted Content added
mNo edit summary |
added subsequence count information |
||
Line 1:
In [[mathematics]], a '''balanced matrix''' ''B'' is an [[integer matrix]] that does not contain any odd order 2-cycle submatricies (submatrix of order n where n is odd and the row and column sums equal 2).
Balanced matricies are important in linear programs such as the [[set partitioning problem]], as they are naturally integer. [[Totally unimodular]] matricies are a subset of balanced matricies, and balanced matricies are a subset of [[perfect matricies]], therefore any matrix that is totally unimodular is also balanced, however a balanced matrix may not necessarily be totally unimodular.▼
The following matrix is an odd order 2-cycle submatrix:▼
:<math>A=\begin{bmatrix}▼
1 & 0 & 1\\
1 & 1 & 0\\
0 & 1 & 1\\
\end{bmatrix}
The following matrix is a balanced matrix as it does not contain
:<math>B=\begin{bmatrix}
1 & 1 & 1 & 1\\
Line 14 ⟶ 18:
1 & 0 & 1 & 0\\
1 & 0 & 0 & 1\\
\end{bmatrix}
==Subsequence Count==
▲Balanced matricies are important in linear programs as they are naturally integer. [[Totally unimodular]] matricies are a subset of balanced matricies, and balanced matricies are a subset of perfect matricies, therefore any matrix that is totally unimodular is also balanced, however a balanced matrix may not necessarily be totally unimodular.
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''<sub>sj</sub>=1, ''a''<sub>ij</sub>=0 for ''s''<''i''<''t'', a<sub>tj</sub>=1], ''j''=1,...,n}|
If a matrix ''A'' has SC(s) <= 1 for all rows s = 1,...,m, then A has a unique subsequence, and is also balanced.
== References ==
| |||