18 GENERALIZATIONS O F TH E PERRON-FROBENIUS THEORE M
LEMMA
3.8. Assume that S = {pi,P2, ?P/c}5 where 1 pi n for 1 i k
and pi 7^ pj for 1 i j k. Let BPi be subsets of E = {j | 0 j n 1} with
|BPi | = Pi. If there is an integer r such that
k
^Tpj rn,
3 = 1
then there exist r + 1 integers I ji J2 ' - jr+i k such that
r+ 1
n^j^0-
2 = 1
Furthermore, if r = k 1,
k k
\f)BPi\Y,Pj-(k-l)n.
2 = 1
j=l
PROOF. Let \j; : ^ ~* {01} denote the characteristic function of BPj, i.e.,
Xj(q) = 1 if q e Bp. and Xj(q) = 0 if q e Tl\BPj. For E i C E define
k
fc(Ei) :=rnaxY]xj(4)
J = l
and for i 1
fc
^ := {? G E | 5^Xi((7) = *i}, where k{ = fc(E \ n } -
1
^ ) -
i = i
If an integer s is chosen such that ks r and fcs+i r,
A; k k
j = l J ^ I Q G S 9 E j = l
x;^ii+»-(n-x;M-
So
s k
Y,{ki-r)\Li\
Y^Pj~rn'
2=1 j = l
Prom this identity it follows that there exists an ZQ such that \Li0\ ^ 0. This proves
the first part of the lemma. For the second part observe that if r = k 1 then s = 1
and we have
k k
|Q BpJ^Lxl $,--(A;-l)n.
2 = 1
J = l
D
Previous Page Next Page