Nonhomogeneous Matrix Products
Darald J. Hartfiel Department of Mathematics Texas A&M University, USA
II
'b World Sci...
28 downloads
687 Views
5MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Nonhomogeneous Matrix Products
Darald J. Hartfiel Department of Mathematics Texas A&M University, USA
II
'b World Scientific
Ii New Jersey. London. Singapore. Hong Kong
l
ublished by
r orld Scientic Publishing Co. Pte, Ltd, o Box 128,
Farer Road, Singapore 912805
;sA offce: Suite lB, 1060 Mai Street, River Edge, NJ 07661
'K offce: 57 Shelton Street, Covent Garden, London WC2H 9HE
Preface
ibrar or Congress Cataoging-in-Publication Data arel, D, J.
Nonhomogeneous matr products I D,1. HareL. p,cm, Includes bibliographical references and index,
ISBN 981024285 (al, paper) 1. Matrce, i. Title, QA188 .H373 2002 512,9'434--dc21
2001052618
ritih Librar Catalogug-in-Publication Data
cataogue record for this book is avaiable from the British Libra,
A matrix product Ak is called homogeneous since only one matrix occurs as opyright ~ 200 by World Scientific Publishig Co, Pte, Ltd,
It rights reserved, This book, or pans thereof, may not be reproduced in any form or by any means, 'ectronic or mechaical, including photocopying, recording or any information storage and retrieval /stem now knwn or to be invented, without written permission from the Publisher.
a factor. More generally, a matrix product Ak... Ai or Ai... Ak is called a nonhomogeneous matrix product. This book puts together much of the basic work on nonhomogeneous matrix products. Such products arise in areas such as nonhomogeneous Markov chains, Markov Set-Chains, demographics, probabilstic automata,
Dr photocopying of material in tIs volume, please pay a copying fee through the Copyrght learance Center, Inc" 222 Rosewood Drive, Danvers, MA 01923, USA, In tIs case pennssion to iotocopy is not requied from the publisher.
production and manpower systems, tomography, fractals, and designing cures. Thus, researchers from various disciplies are involved with this kind of work.
For theoretical researchers, it is hoped that the readig of this book wil generate ideas for futher work in this area. For applied fields, this book provides two chapters: Graphics and Systems, which show how ma-
trix products can be used in those areas. Hopefuly, these chapters will
stimulate futher use of this material. An outlie of the organization of the book follows. II
The fist chapter provides some background remarks. Chapter 2 covers basic fuctionals used to study convergence of infte products of matrices.
limit Chapter 3 introduces the notion of a limiting set, the set containing al points of Ai, A2Ai, . .. formed from a matrix set ¿. Various properties of this set are also studied.
'inted in Singapore by Mainland Press
Preface
Chapter 4 concerns two special semigroups that are used in studies of
fite products of matrices. One of these studies, ergodicity, is covered in iapter 5. Ergodicity concerns sequences of products Ai, A2Ai, . . . , which
Contents
ipear more lie ran 1 matrices as k -- 00. Chapters 6, 7, and 8 provide material on when infte products of malces converge. Various kinds of convergence are alo discussed. Chapters 9 and 10 consider a matrix set E and discuss the convergence
E, E2, . .. in the Hausdorff sense. Chapter 11 shows applications of
is work in the areas of graphing curves and fractals. Pictures of curves id fractals are done with MATLAB*. Code is added at the end of this apter. Chapter 12 provides results on sequences Aix, A2Aix,... of
matrix prod-
:ts that vay slowly. Estimates of a product in terms of the current matrix e discussed. Chapter 13, shows how the work in previous chapters can
! used to study systems. MATLAB is used to show pictures and to make lculations. Code is again given at the end of the chapter. Finally, in the Appendi, a few results used in the book are given. This done for the conveiuence of the reader. In conclusion, I would like to thank my wife, Faye Hartfiel, for typing this ,ok and for her patience in the numerous rewritings, and thus retypings,
it. In addition, I would also like to than E. H. Chionh and World ientifc Publishig Co. Pte. Ltd. for their patience and kindness while I
:ote this book.
Darald J. Hartfiel
Preface
v
1 Introduction
1
2 Fuctionals
5
2.1 Projective and Hausdorff Metrics
2.1.1 Projective Metric.
2.1.2 Hausdorff Metric . . . . . 2.2 Contraction Coeffcients . . . . . 2.2.1 Birkhoff Contraction Coeffcient
2.2.2 Subspace Contraction Coeffcient
*MATLAB is a registered tradem!lrk of The MathWorks, Inc. For product inforLtion, please contact:
2.2.3 Blocking.............. 2.3 Measures of Irreducibilty and F\ Indecomposabilty 2.4 Spectral Radius .
2.5 Research Notes . . . .
rhe Math Works, Inc,
3 Apple Hil Drive \.atick, r\A 01760-2098 reI: 508647-7000 t"ax: 508-647-7001
8-mail: infoi§mathworks.com Web: www.mathworks.com
3 Semigroups of Matrices
3.1 Limiting Sets . . . . . . . . . . 3.1.1 Algebraic Properties . .
3.1.2 Convergence Properties
3.2 Bounded Semigroups . . . . . .
5 5
14 18 19
27 32 33 38 42
45 46 46 49 54
0' .. .. .i
00' c. ~
f- f- f- i-
i: ¡g tD 00 ¡¡ 00
~.. ..
Cl :: ~. 00 Cl 00
t¡ ~ .. :: ~ '1
Cl ... II
Z~OCl o Cl 0 ... ~elCl= ff c. R' ~
P' t: Cl C" = 0
~ &.g ~ C" 0 ii ...
ff ::. g. 3-
:: t: en ="
. . . tD
:: H0~ Cl'-O 0
çx çx çx 'i c. t- f- ~
a-
.§
'1
cr
s:
~.
p.
=
tD
;i 't 't
i~
f- f- f- f- i-
f- f- f- 0 0 ~..O-:-;
Cl
C"
::
()Cl
o-
Cl Cl
~ C"
o ~ ~: ~ o. ():: o Cl
S' 00 g ¡:.
t¡. p. =
t-f-
=
0' c. 00 f- -: -;
5 5 1: 1: 00 00
.. "-
~.
': +. 00
Cl C" ii''~ u. c: 0o(;' Cl.. 0 Cl
~v~
Z ~ tj:: ::g s: o ,$ ii
P' oq' 0 Cl p. tD
Cl ... Cl 0 Cl '1
::5"::O::~ 1( t¡ g. ~ ê"~ ~t?¡¡~g~
Ol..c.
0000000
~
i-
00 -: -: -; 0' 00 f- i-
00
i: ~
00
~
t¡
1ii'
00 C"
~ Cl .. 00'"el
e¡ ~ Š~ g. :: t: z ff 0 o i: ~
1( (t ~ C.
::t:t:&. C' ...... ...
P'P'P't; c. t- f- ~
ii-
00
0'
00
Z o ~ Cl
~ g.
Cl
00
~
~
c.
f- f- f- f- f- ø
00 .. 1: co
~~0l0l
Cl u. u.
C" Cl
... C"
~::. r.
is: ¡:... 00 ii ~ g
Z () ~ o ~!7'1
g.~~~
e¡ ~ E3 p.
Cl ii C" '1 u. o- o- = Cl '- 2: tD
~ t~ f~ ~'i c. .. :: en en tD
~
~ Cl
c.00
en .
:: .
o
... .
..
¡: . C" .
p.
:: o ..
ëi ro ~o- ~ .
.a 0".
p.ff:: 'i-ê Cl 00 'i0 o-0 00
00 S:t=s: o ~ ii C"
t:Ž~ -ê;g
~ 1( S' S 2. t"e¡Cl~a ;i Q. gi o- ...
!7::t:t:'itD~ ¡: Cl ~ Cl o-
~ ~ ~ ~ ~c.
f- f- f- f- f- 00
00
Cl
(;'
~ g o- u.
s: ~.
() ii~ .
g.~. ~ ¡:::' ~(t. Q . Q ... . (6. ~ e: . . ff 00 S' s:
t:tl--. á?t: S o.S.00 ~ ~. -. ~. ~~. ~ Cl ~ . Cl ¡: i:'
~::~. ::p.t;oo. =
o ... ... 0 Cl 0 :: :: 0 p.
~ ;:...~.g¡:0 iiC"a-ii¡:~a-ii ~Cl~~ S 'i Cl u. Q u. :: ff ~. N' ~. u. .. a
Zg-~~~C" ~ C" S 0 gcr
n. ~ ~Z ~...~" ci c. ;: t:Cl!7~ ~ ~::Cl ¡:Z0C+ ¡: 0~ ¡: =...
1( ¡i¡i¡io ~~~~g:~ ~ ~ c.t-f-~.c.t-f-Cl ¡: Cl ~
Cl t-t-t-¡: t-t-t-S- 00 0
:: f- f- f-.o f- f- f- en t? 0 ~
00 e.u.00
Cl u. .. Cl
o 0 ~ ~.
;it:P"~ ~.
Z . 8.i~~
t" C" e: t= .
f-ff-ê-ê~ ~
s:::øøs:'g ;. Cl o- o- ii ...
Ol..c.t-f-
f- f- f- f- f- 00 ~~~~~'1 !' .. !' ~t-t-t-II i-;" ~ Ol..c.t-f-~ 0'
f- fc. t- ff- iiot-oo-;
to
-õ'
... Cl
u.
o ii cr o. :: tD
¡~~g~ 00 00 '1
~¡¡~~O
~~.~. :: e. ¡:Cl~0
~ :: 0 0 en ... ff ál ii .8 S Clel~§O
.. c. t- f- 0
:":":":"0
~ t- t- t- f- ~ f- f- f- f- f- f- f- f- f- f- f- ~ f- f- f- f- f- :; ~ i-~ ~i-01 t-K?::~S~co æ~~~~n~:5R5~~~~-; 85R5~~::i~ -;
~
tD
p.
.. =
~ t;t; t; t; t; ~ t-1:00~~c.~
00
i: .. . ~ 00
ff g. 00 .
~ 1= ~ ::Cl ~..
C" Cl ~...t¡ClCl:: ..
ClelC't¡. :: C" ...
() Cl el Cl u.
o-
~ o°el°'0 Cl o- 00ClC"... ¡:
C"
~ o
o ii Cl cr
z t: ¡: S'
Sc.. . 00 Cl
Z S' ?l & § á? =
g. ,. i=g g, 00 Ò.J .. 0 ál§. ~ g
l€~i-;"t¡S~ 1€~~~ e¡Cl ¡;p.tD e¡ooCl'1 C" 0 o- II g.~ent:~a~ P' ~~ ~ c. ¡: ::.... tD
::O~~Ot:O Cl 0 t- t- 0 0 0
1: 1: 1: 1: 00 555" c. t- f- ~ ;¡ ~ i-;" ~
x.
Ul
a
(1
:: n-
Q o
Ul
:: n-
a(1
Q o
i Introduction
Let P denote either the set R of real numbers or the set C of complex
numbers. Then pn will denote the n-diensional vector space of n-tuples over the field P. Vector norms 11.11 in this book use the standard notation, 1I'llp denotes
the p-norm. Correspondigly induced matrix norms use the same notation. Recal, for any n x n matrix A, IIAII can be defied as IIAII = max IlxAII or II
All = max IIAxll.
IIxll=1 IIxll=1
n n ik=1 L. k=1 i n n ik=1 L. k=1 i
So, if the vector x is on the left
¡IAlli = m?X '" laikl, IIAlIoo = m?X L lakil
whie if x is on the right,
IIAlli = m?X '" lakil, IIAlIoo = m?X L laikl' II
In measuring distances, we wil use norms, except in the case where we use the projective metric. The projective metric occurs in positive vector and nonnegative matrix work.
2
1. Introduction
1. Introduction
3
Let Mn denote the set of n x n matrices with entries from F. By a
Any subset ~ of Mn is caled a matri set. Such a set is bounded if there
matri norm 11.11 on Mn, we wil mean any norm on Mn that also satisfies
is a positive constant ß such that for some matrix norm 11.11 , IIAII :S ß for
IIABII :S IIAIIIIBII
al A E~. The set ~ is product bounded if there is a positive constant ß where IIAk'" Aill :S ß for al k and al Ai,... , Ak E~. Since matrix norms on Mn are all equivaent, if ~ is bounded or product bounded for
for all A, BE Mn. Of course, al induced matrix norms are matrix norms. Tils book is about products, caled nonhomogeneous products, formed
from Mn. An infte product of matrices taken from Mn is an expressed product . . . Ak+iAk . . . Ai
(1.1)
where each Ai E Mn. More compactly, we write 00
II Ak.
k=i
Tils infte product of matrices converges, with respect to some norm, if
the sequence of products Ab A2Ai, A3A2Ai, . . .
converges. Since norms on Mn are equivalent, convergence does not depend on the norm used. If we want to make it clear that products are formed by multiplying on
the left, as in (1.1), we can call this a left infinite product of matrices. A right infinite product is an expression
AiA2... wilch can alo be written compactly as rr~i Ak. Unless stated otherwise,
we wil work with left infite products. In applications, the matrices used to form products are usually taken from a specifed set. In working with these sets, we use that if X is a set of m x k matrices and Y a set of k x n matrices, then X Y =£ AB : A E X and B E YJ .
And, as is customary, if X or Y is a singleton, we use the matrix, rather than the set, to indicate the product. So, if X = r A r or Y = r Bì, we wri~e
AY or XB, respectively.
one matrix norm, the same is true for al matrix norms. All basic background information used on matrices can be found in Horn and Johnson (1996). The Perron-Frobeiuus theory, as used in tils book, is given in Gantmacher (1964). The basic result of the Perron-Frobeiuus theory is provided in the Appendi.
~
2 Functionals
Much of the work on inte products of matrices uses one fuctional or another. In this chapter we introduce these functional and show some of their basic properties.
2.1 Projective and Hausdorff Metrics The projective and Hausdorff metrics are two rather dated metrics. How-
ever, they are not well known, and there are some newer results. So we wil give a brief introduction to them.
2.1.1 JJrojective lk etric
LetxERn wherex=(xi,... ,xn)t. If 1. Xi ~ 0 for all i, then X is nonnegative, whie if II
2. Xi ? 0 for all i, then X is positive.
If x and y are in Rn, we write 1. x ~ y if Xi ~ Yi for al i, and
i
6
2. Functionals
2,1 Projective and Hausdorff Metrics
2. x:; y if Xi :; Yi for al i. The same teriinology wil be used for matrices. The positive orthant, denoted by( Rn) +, is the set of al positive vectors
2. p (x,y) =iIn Yi (max:!imax Xi1/) . In working with p (x, y), for notational simplicity, we defie
in Rn. The projective metric p introduced by David Hilbert (1895), defies a scaled distance between any two vectors in (Rn)+. As we wil see, if X
M(x) y- =~i ~~
and yare positive vectors in Rn, then
p (x, y) = p (ax, ßy)
and
for any positive constants a and ß. Thus, the projective metric does not
depend on the length of the vectors involved and so, as seen in Figue 2.1, p (x, y) can be calculated by projecting the vectors to any desired position.
7
m y = ~in y; .
(x) x.
Some basic properties of the projective metric follow.
Theorem 2.1 For all positive vectors x, y, and z in Rn, we have the following: 1. p(x,y) ~ O.
2. p (x, y) = 0 iff x = ay for some positive constant a.
3. p(x,y) =p(y,x).
4. p(x,y) :Sp(x,z)+p(z,y). 5. p (ax, ßy) = p (x, y) for any positive constants a and ß. FIGURE 2,1. Various scalings of x and y.
The projective metric is defied below.
Proof. We prove the parts which don't follow directly from the definition
ofp. Part (2). We prove that if p (x, y) = 0, then x = ay for some constant a. For this, if p (x, y) = 0,
Definition 2.1 Let x and y be positive vectors in Rn. Then
M(t) m(t)
max i!
p(x,y) =In . x.. ~ min -i
= 1
j Yj
so
Other expressions for p (x, y) follow. 1. p (x, y) = In Ilax ~iYyj, the natural
II i.i¡ J' J Xi Yi ratio in ¡x yJ = .~~ Y2 Xn Yn
M(;)=m(;).
log of the largest cross product Since
M y ~ Yk ~ m Y
,(x) Xk (x)
8
2.1 Projective and Hausdorff Metrics
2. Functionals
for al k,
9
This inequality provides (4). .
Xk = M (~)
Yk Y
From property (2) of the theorem, it is clear that p is not a metric. As
a consequence, it is usually called a pseudo-metric. Actually, if for each positive vector x, we defie
for al k. Thus, setting a = M (t ), we have that ray
x=ay. Part (4). We show that if x, y, and z are positive vectors in Rn, then p (x, y) :: p (x, z) + p (z, y). To do this, observe that
(x) = tax: a 2 Or
then p determines a metric on. these rays. For a geometrical view of p, let x and y be positive vectors in Rn. Let a be the smalest positive constant such that
ax 2 y.
x:: M (~) z:: M (~) M (;) y.
Then a = M (Ð. Now let ß be the smalest positive constant such that
Thus,
ax :: ßy.
~: :: M (~) M (;) Thus, ß = M ( 0:; ). (See Figure 2.2.) Calculation yields for al j and so
M(~) ::M(~)M(;). Sinuarly,
ßy
m(~) 2m(~)m(;). Putting together,
p(x,y)=ln M(t)
m(t)
FIGURE 2.2, Geometrical view of p(x, y).
-:In M(~)M(t) - m(~)m(t)
ß = aM (~) = M (~) M (~) II
=In M(!) +In M(t)
m(z) m(t)
=p(x,z)+p(z,y).
so p(x,y) = lnß.
10
2.1 Projective and Hausdorff Metrics
2. Functionals
Thus, as a few sketches in R2 can show, if x and yare close to horizontal or vertical, p (x, y) can be large even when x and Y are close in the Euclidean distance.
Part (1). Using the defiitions of rand M, we show that mi~ e€ -1 and
that x = r (y + My). For the fist part, suppose that p (x, y) ~ €. Then
Another geometrical view can be seen by considering the curve C =
Inmax-.. XdYi /' € i,j Xj/Yj -
t ( :~ J : XiX2 = 11 in the positive orthant of R2. Here, p(x,y) is two times the area shaded in Figue 2.3. Observe that as x and yare rotated
so we have
max-..e. i,j Xj/YjXdYi /' €
Thus, for any i,
Xi/Yi 0: e€ rrnxj/Yj -
j
y
and so by subtracting 1, XïfYi - rrnxj/Yj J
minx , J'/Y' J J
~ e€ - 1
or
mi ~ e€ - 1. Now note for the second part that
l+mi=l+ . /
XïfYi - rrnxj/Yj J IIn Xj Yj
J
FIGURE 2.3. Another geometrical view of p(x, y).
XdYi = rrnxj/Y/ J
Since r = rrn !2, we have
j Yj
---,
toward the x-axs or y-axs, the projective distance increases.
1 Xi
1 + mi - r Yi
In the last two theorems in this section, we provide numerical results
showing somethig of what we described geometrically above.
so
r (1 + mi) Yi = Xi
Theorem 2.2 Let x and Y be positive vectors in Rn.
or r (y + My) = x. 1. Ifp (x, y) ~ €, r = mln :2y:' and mi = xi/~i-r, then we have that mi ~ J 3 e€ -1 and x=r (y + My) where the matri M = diag (mi,... , mn).
Part (2). Note by using the hypothesis, that
p(x,y) =p(ry+rMy,y) =p(y+My,y) Yi+miYi
e. Suppose x = r (y + My), M = diag (mi,... , mn) 2: 0 and r ? O. If
mi ~ e€ -1 for all i, thenp(x,y) ~€.
=maxIn~ i,j Yj+m;Yj Yj
l+m'
Proof. We prove both parts.
11
i,J 1 + mj i
=1I~In~ ~m?XIn(I+mi) ~lne€ = €
12
2. Functionals
2.1 Projective and Hausdorff Metrics
the desired result. .
13
Proof. We argue both parts.
Observe in the theorem, taking r and M as in (1), we have that X =
r (y + My). Then, r is the largest positive constant such that
Part (1). For any given i, if Xi ;: Yi, then, since t; ~ M (t) and
m(t) ~ 1,
1 -x - Y ;: O.
r -
Xi - Yi ~ M (~) Yi - m (~) Yi.
And i
mi = ;Xi -Yi
And if Yi ;: Xi, then since M (t) ;: 1 and t; ;: m (t),
Yi
Yi - Xi ~ M (~) Yi - m (~ ) Yi.
for al i. Thus, viewing Figue 2.4, we estimate that m2 ~ 1, so, by (2), p(x,y) ~ ln2. Tunig Y toward X yields a smaler projective distance.
Thus,
¡Xi - Yil ~ M (~) Yi - m (~) Yi.
-x-y r 1
It follows that
IIx-ylli ~ M (~) -m (~)
m (t)(t) = (M _ 1) m Y (::) ~ eP(x,y) - 1.
FIGURE 2.4, A view of mi and m2,
In the following theorem we assume that the positive vectors X and Y
have been scaled so that Ilxlli = lIylli = 1. Any nonnegative vector z in Rn such that IIzlli = 1 is caled a stochastic vector. We also use that
Part (2). Note that
M (::) = mtl f 1 + Xi - Yi 1. ~ 1 + Iix - ylli .
Y i 1. Yi f m (Ð
(2.1)
And, if m (;) ;: 211x - ylli, simiarly we can get
e = (1,1,... ,1)\ the vector of 1's in Rn.
Theorem 2.3 Let X and Y be positive stochastic vectors in Jl. We have the following: II
m (::) ;: 1 _ IIx - ylli ;: O.
Y - m (Ð
Now using (2.1) and (2.2), we have
1. ¡Ix - Ylli ~ eP(x,y) ~ 1.
2. p (x, y) ~ i ii:(;i~, provided that m (Ð ;: 211x - ylli.
M(t) m (t)
1+ iiX?I~'
0: m ~ - 1 - iiX?I~' .
m 11e
(2.2)
14
2.1 Projective and Hausdorff Metrics
2. Fuctionals
And, using calculus
15
Hence, we can defie
m(Ð m(~)
p(x,y) :S in (1 + iix - Ylli) -in (1- IIx - Ylli)
I .c ~ IIx - ylli
.
- 3 m (~) ,
k
which is what we need. _
we scale positive vectors x and Y to ii:ili and g, and mjn ii~ili is not too smal, then x is close to Y in the projected sense iff ii:ili is close to ii:ili in the I-norm. See Figure 2.5. This theorem shows that if
x
FIGURE 2.6. A view of land k, y
d (l, K) = iind (l, k). kEK
Note that if d (l, K) :S E, then
lEK+E where K+E = tx: d(x,k) :S E for some k E Kl as shown in Figure 2.7. We can also show that if L is a compact subset of X, then sup d (l, K) = IEL
d (i, K) for some i E L. Using these observations, we defie FIGURE 2.5. Projected vectors in R2.
8 (L, K) = maxd (l, K) IEL
= max iin d (l, k) IEL kEK
2.1.2 Hausdorff Metric
The Hausdorff metric gives the distance between two compact sets. It can be defied in a rather general setting. To see this, let (X, d) be a complete
metric space where X is a- subset of Fn or Mn and d a metric on X.
If K is a compact subset of X and lEX, we can take a sequence ki, k2,... in K such that d (l, ki) , d (l, k2) , ... converges to inf d (l, k).
=d(i,k) . If 8 (L, K) = E, then observe, as in Figue 2.8, that L ç K + E .
The Hausdorff metric h defies the distance between two compact sets,
say Land K, of X as
kEK
AiM, take a subsequence kii , ki2 , . .. that converges to, say k E K as de-
picted in Figue 2.6. Then, inf d (l, k) = d (l, k) .
kEK
h(L,K) = maxt8(L,K) ,8(K,Ln.
So if h(L,K) :SE, then L ç K + E and K ç L + E
16
2. Functionals
2,1 Projective and Hausdorff Metrics
17
. K
K+e
FIGURE 2,7. A sketch for d(l,K), FIGURE 2,8. A sketch showing lj (L, K) -c E.
and vice versa.
In the following we use that H (X) is the set of all compact subsets of X.
Theorem 2.4 Using that (X, d) is a complete metric space, we have that
where d (r, i) = mind (r, t) = d (r, T). Finally, tET
8 (R, S) = maxd (r, S) rER
~ maxd (r, i) + maxd(t, S)
(H (X), h) is a complete metric space.
rER tET = maxd (r, T) + maxd (t, S) rER tET
Proof. To show that h is a metric is somewhat straightforward. Thus, we
wil only show the triangular inequalty. For this, let R, S, and T be in H(X). Then for any r E R and tE T, ( d (r, S) = mind (r, s)
= 8 (R, T) + 8 (T, S). Putting together, we have
sES
~ min(d(r,t) +d(t,s))
sES
= d(r,t) +mind(t,s) sES
= d (r, t) + d (t, S) . II
Since this holds for any t E T,
d(r,S) ~ d(r,i) +d(i,S)
h (R, S) = maxr8 (R, S),8 (S, R)l ~ maxr8 (R,T) + 8 (T, S),8 (S,T) + 8 (T,R)l ~ maxr8(R,T) ,8
(T,R)l +maxr8(T,S) ,8
(S,T)l
= h (R, T) + h (T, S) .
The proof that (H (X), h) is a complete metric space is somewhat intricate as well as long. Eggleston (1969) is a source for this argument. -
18
2.2 Contraction Coeffcients
2. Functionals
To conclude this section, we link the projective metric p and the Hausdorff metric. To do this, let S+ denote the set of all positive stochastic vectors in Rn. As shown below, p restricted to S+ is a metric.
Theorem 2.5 (S+,p) is a complete metric space. Proof. To show that p is a metric, we need only to show that if x and y are in S+ and p (x, y) = 0, then x = y. This follows since if p (x, y) = 0, then y = ax for some scalar a. And since x, y E S+, their components satisfy Yi + . . . + Yn = a (xi + . . . + xn) .
2.2.1 Birkhoff Contraction Coeffcient
The contraction coeffcient for the projective metric, introduced by G. Birkhoff (1967), is defied on the special nonnegative matrices described below.
Definition 2.2 An m x n nonnegative matri A is row allowable if it has a positive entry in each of its rows. Note that if A is row alowable and x and Y are positive vectors, then Ax and Ay are positive vectors. Thus we can compare p(Ax, Ay) and p (x, y).
To do this, we use the quotient bound result that if ri, . .. , r n and Si, . .. , Sn are positive constants, then
So a = 1. Thus, x = y.
min ri :: ri + ... + rn :: m?X ri. (2.3)
i Si Si + . . . + Sn i Si
Finaly, to show that (S+,p) is complete, observe that if (Xk) is a Cauchy sequence from S+, then the components ofthe Xk'S are bounded away from
O. Then, apply Theorem 2.3. _
19
This result is easily shown by induction or by using calcruus.
Lemma 2.1 Let A be an m x n row allowable matri and x and y positive As a consequence, we have the following.
vectors. Then p
Corollary 2.1 Using that (S+,p) is the complete metric space, we have that (H (S+) , h) is a complete metric space.
(Ax,
Ay) :: p(x,y).
Proof. Let x = Ax and y = Ay. Then
Xi aiiXi +... + ainxn Yi aiiYi + . .. + ainYn 2.2 Contraction Coeffcients
Thus using (2.3),
. Xk Xi xk
Let L be a matrix set and
min - .. - .. max -
k Yk - Yi - k Yk
A=:EU:E2U... .
for al i. So
-- .. max.! max :h
A nonnegative function r
r:A-lR
i Yi k Yk min Ei - min .! k Yk i Yj
and thus,
is called a contraction coeffcient for :E if p(X,y) ::p(x,y)
r(AB):: r(A)r(B) II
for al A, B E A.
Contraction coeffcients are used to show that a sequence of vecto:is or a
or p
(Ax,
Ay) :: p(x,y),
which yields the lemma. _
sequence of matrices converges in some sense. il this section, we look at
two kids of contraction coeffcients. And we do this in subsections.
For slightly different matrices, we can show a strict inequalty resrut.
20
2.2 Contraction Coeffcients
2. Functionals
Lemma 2.2 Let A be a nonnegative matri with a positive column. If x and yare positive vectors, and p (x, y) :: 0, then
21
the desired result. .
Lemma 2.1 shows that ray (Ax) and ray (Ay) are no farther apart than
ray (x) and ray (y) as depicted in Figue 2.9. And, if A has a positive
p (Ax, Ay) .: p (x, y) .
Proof. Set x = Ax and fj = Ay. Defie ri = ~ and ri = t for al i.
colum, ray (Ax) and ray (Ay) are actualy closer than ray (x) and ray (y).
i i i i
n () n - 6 iJ J J
Futher, defie M = m?Xri, m = ninri, M = m?Xri, and m = ninri.
Now
J'-l 'Ç a..y' x'
ri = L aijYj = j=l L aijYj yj'
j=l j=l ?= aij Yj
FIGURE 2,9. A ray view of p(Ax,Ay) :: p(x,y).
~ O. Then
3=1
Defie the projective coeffcient, caled the Birkhoff contraction coeffcient, of an n x n row allowable matrix A as
n
ri = ¿aijrj, j=l a convex sum.
Suppose
(2.4)
n n j=l j=l
M = ¿apjrj and m = ¿aqjrj . Using that these are convex sums, M :S M and m ~ m. Without loss of generality, assume the fist colum of A is positive. If M = M and m = m, then since ail:: 0 for all i, by (2.4), r1 = M = m, which means p(x,y) = 0, denying the hypothesis. Thus, suppose one of M .: M or m :: m holds. Then
M-m.:M-m
TB ( Ay) ) (A)- _sup p (Ax, p x,y where the sup is taken over al positive vectors in Rn. Thus, p (Ax, Ay) :S TB (A) p (x, y)
for al positive x, y. And, it follows by Lemma 2.1 that TB (A) :S 1.
Note that TB indicates how much ray (x) and ray (y) are drawn together
when multiplying by A. A picture of this, using the area view of p (x, y), is shown in Figure 2.10. Actualy, there is a formula for computing T B (A) in terms of the entries of A. To provide this formula, we need a few preliminary remarks.
Let A be an n x n positive matrix with n :: 1. For any 2 x 2 submatrix of A, say
and so
II
~AY
~y
L aijXj n
Set"",-~ ""iJ - n
Ax
M M ---1.:--1. m m
arq ar (apq apss J
the constants
It follows that
-,apqars apsarq
p(Ax,Ay) .:p(x,y),
apsarq apqars
22
2.2 Contraction Coeffcients
2. Functionals
23
for al row allowable matrices A and positive vectors x and y. Using our previous example, where A = (~ ~ J, we have
1 - ¡¡ ~.1O
TB(A) 1+=V"3 !2 y
x
so for any positive vectors x and y, ray (Ax) and ray (Ay) are closer than ray (x) and ray (y). This theorem alo assures that if A is a positive n x n matrix and Di, D2,
n x n diagonal matrices with positive mai diagonals, then TB (DiAD2) =
TB (A). Thus, scaling the rows and colum of A does not change the contraction coeffcient.
It is interesting to see what TB (A) = 0 means about A. area view of TB (A) = ~.
FIGURE 2.10. An
Theorem 2.7 Let A be a positive n x n matri. If T B (A) = 0, then A is rank 1.
Proof. Suppose TB (A) = O. We wil show that the i-th row of A is a
are cross ratios. Define
scalar multiple of the I-st row of A. Defie a =~. Then, since TB (A) = 0, ø (A) = 1 which assures that ø (A) = min apqars
arqaps
al cross ratios ol A are 1. Thus, anaij = 1
where the minium is over all cross ratios of A. For example, if A = (~ ~ J, then ø (A) = min U' n = ¡.
If A is row allowable and contains a 0 entry, defie ø (A) = O. Thus for
any row alowable matrix A,
The formula for TB (A) can now be given. Its proof, rather intricate, can be found in Seneta (1981).
Theorem 2.6 Let A be an n x n TOW allowable matri. Then
1 - JØ(A)
TB(A) = I+JØ(A)' II
Note that this theorem implies that T (A) .: 1 when A is positive and T (A) = 1 if A is row alowable and has at least one 0 entry. And t4at (Ax,
for al j. Thus, aa~~j = 1 or aij = aalj' Since this holds for al j, the i-th
row of A is a scalar multiple of the fist row of A. Since i was arbitrary, A
is ran 1. .
Ø(A)::i.
p
ail alj
Ay) :: TB (A)p(x,y)
Probably the most usefu property of TB follows.
Theorem 2.8 Let A and B be n x n row allowable matrices. Then TB (AB) :: TB (A) TB (B) .
Proof. Let x and y be positive vectors in Rn. Then Bx and By are alo positive vectors in Rn. Thus p(ABx,ABy) :: TB (A) TB (B)p(x,y). And, since this inequalty holds for all positive vectors x and y in Rn,
TB (AB) :: TB (A) TB (B)
24
2.2 Contraction Coeffcients
2. Functionals
25
I
as desired. _ We use this property as we use induced matrix norms.
Ax
Corollary 2.2 If A is an n x n row allowable matri and y a positive eigenvector for A, then for any positive vector x, p (Akx, y) :: TB (A)k P (x, y). Proof. Note that
p(Akx,y) =p(Akx,Aky) :: TB (A)k P (x, y)
for al positive integers k. _ Tils corollary assures that for a positive matrix A, li P (Akx,y) = 0, k-+oo
so ray (Akx) gets closer to ray (y) as k increases. We wi conclude tils section by extending our work to compact subsets.
FIGURE 2.11. A view of WA,
To do tils, recal that (S+,p) is a complete metric space. Defie the
Thus, ~pU is the projection of ~U onto S+. Since ~ and U are compact, so is ~U. And thus, ~pU is compact.
metric on the compact subsets (closed subsets in the I-norm) of S+ by using the metric p. That is,
Hausdorff
Now using the metric p on S+, defie
8 (U, V) = max (minp (u, v))
T (~) = sup h (~pU, ~p V)
uEU vEV
u,v h (U, V)
and
= sup h (~U, ~V) U,V h (U, V)
h(U, V) = max~ß(U, V) ,8(V,Un
where the sup is over all compact subsets U and V of S+.
where U and V are any two compact subsets of S+. Let ~ be any compact subset of n x n row alowable matrices. For each
Using the notation described above, we have the following.
Theorem 2.9 T(~):: maxTB (A).
A E ~, defie the projective map
AEL
~~ '
W A : S+ -- S+
Proof. Let U and V be compact subsets of S+. Then
by WA (x) = ii1:ili' as shown in Figue 2.11. Defie the projective set for
II
8 (~pU, ~p V) = max p (Au, ~V) AuELU
= P ( Âû, ~V)
~p = t WA: A E ~r.
for some ÂÛE ~U. So
Then for any compact subset of U of S+, ~pU = tWA (x): WA E ~p and x E Ur.
8 (~pU, ~pV) :: p (Âû, Â'Û)
l
~
26
2,2 Contraction Coeffcients
2. Functionals
where 'Û satisfiesp(û,'Û) =p(û, V). Thus, 8
27
This corollary shows that if we project the sequence EU, E2U, E3U,. . .
(EpU,EpV) ~ TB (Â)p(û,'Û)
into S+ to obtain
= T B (Â) p (û, V)
EpU, E;U, E;U,...
~ T B (Â) 8 (U, V) .
then if T B (E) 0: i, this sequence converges to V in the Hausdorff metric.
Simiarly, 8 (EpV,
EpU) ~ TB (Â) 8
2.2.2 Subspace Contraction Coeffcient
(V, U)
We now develop a contraction coeffcient fora subspace of pn. When this setting arises in applications, row vectors rather than colum vectors are
for some à E E. Thus,
usualy used. Thus, in this subsection pn wi denote row vectors.
h (EpU, Ep V) ~ maxTB (A) h (U, V)
To develop this contraction coeffcient, we let A be an n x n matrix and
AEI:
E an n x k fu column rank matrix. FUrther, we suppose that there is a k x k matrix M such that
and so
T(E) ~~~TB(A),
AE = EM.
Now extend the colum of E to a basis and use trus basis to form
which is what we need to show. .
P = lE GJ .
Equality, in the theorem, need not hold. To see this, let
Partition
E = r A : A is a colum stochastic 2 x 2 matrix with 3 l 0:- a" ii 0: - 3£
p-1 = ( ~ J
for all i,jJ.
A E E, then l ~ (Ax)i ~ ~ for ali, andso = lAxAxJ E E. Thus, for y E S+, Ax = Ây, which can be used to show T (E) = Ü. Yet
where H is k x n. Then we have
Ifx E S+ and
AP=AlEGJ
A = (l l J E E and T B (A) ;; Ü.
We defie
=(EGJ(~ ~J
TB (E) = maxTB (A). AEI:
where
And, we have a corollary paralel to Corollary 2.2. dorollary 2.3 If V is a compact subset of S+, where Ep V = V, then for
( ~ J = p-1 AG.
any compact subset U of s+ ,
Now set
h (E;U, V) ~ TB (E)k h (U, V) .
W=rxEpn:xE=ül.
l
(2.5)
~
28
2.2 Contraction Coeffcients 29
2. Functionals
Proof. We fist show that TW (A) ~ IINIIJ. For this, let x be a vector such that xE = a. Then
Then W is a subspace and if x E W, xA E W as well. Thus, for any vector norm 11.11, we can defie
TW (A) = max IIxAl1 "EW
IIxAII = iix ¡E Gl (~ ~ J ( ~ J II
11,,11=1
max IlxAII
= II ¡a xGJ (~ ~ J ( ~ J II
""e: IIxll . Notice that from the defition,
= II ¡a xGNJ ( ~ J II = IlxGNJII
IlxAII ~ TW (A) IlxlI
= IIxGNIIJ
for all x E W. Thus, if TW (A) = l, then A contracts the subspace W by
~ IlxGIIJ IINIIJ .
(2.6)
at least l. So, a circle of radius r ends up in a circle of radius lr, or less,
Now
as shown in Figure 2.12.
IlxGllJ = IlxGJl1 = ii¡a xGl ( ~ J II
= Ilx¡EGl ( ~ J II = Ilxll. Thus, plugging into (2.6) yields
IIxAII ~ IINIIJ IIxll.
FIGURE 2,12. A view of TW (A) = ~.
And, since this holds for all x E W,
If B is an n X n matrix such that BE = EM for some k x k matrix M,
TW (A) ~ IINIIJ.
then for any x E W,
We now show that IINIIJ ~ TW (A). To do this, let z E pn-k be such that IIzllJ = 1 and IINIIJ = IIzNIIJ'
IlxABII ~ TW (B) IlxA11 ~ TW (A) TW (B) IlxlI.
Now,
Thus,
IINIIJ = IlzNIIJ = IlzNJl1
TW (AB) ~ TW (A) TW (B) .
We now link TW (A) to N given in (2.5). To do this, defie on pn-k
= II(a, z) (~ ~ J ( ~ J II IIzllJ = IIzJII.
= IlzJAII
II
~ IlzJII TW (A)
It is easily seen that 11.IVis a norm. We now show that TW (A) is actualy IINIIJ.
~ IlzIIJ TW (A) = TW (A) ,
Theorem 2.10 Using the partition in (2.5), TW (A) = IINIIJ.
~
30
)
2. Functionals
wmch gives the theorem. _
2,2 Contraction Coeffcients
31
Theorem 2.12 Let A be an n x n matri and 11.11 a vector norm on Rn
that produces a unit ball which is a convex polytope K in W. If f Vi, . .. , Vs L
A converse of tms theorem follows.
are the vertices of K, then
Theorem 2.11 Let A be an n x n matrix and P an n x n matri such that
TW (A) = m?X fllviAlll. i
p-i AP = (M C J
ON'
Proof. Let x E K where IIxll = 1. Write x = C¥iVi +... + C¥sVs
where M is k x k. Let 11.11 be any norm on Fn-k. Then there is a norm 11'110 on Fn and thus on W, such that TW (A) = IINII.
a convex combination of Vi,... , VS' Then it follows that
Proof. We assume P and p-i are partitioned as in (2.5) and use the notation given there. We first fid a norm on
IlxA11 = lit C¥iViA
W=fx:xE=Ol.
s
For tms, if x E W, defie
:: L C¥i IlviAl1
i=i :: m?X fllviAlll.
IlxlIo = IlxGII.
i
To see that 11'110 is a norm, let IlxlIo = O. Then IlxGII = 0, so xG = O.
Thus,
Since x E W, xP = 0 and so x = O. The remaining properties assuring
TW (A) :: m?X fllviAlll.
that 11'110 is a norm are easily established. Now, extend 11'110 to a norm, say 11,110, on Fn. We show the contraction
i
coeffcient TW, determied from tms norm, is such that TW (A) = IINII. Using the norm and part of the proof of the previous theorem, recall that if z E Fn-k,
That equalty holds can be seen by noting that no vertex can be interior to the unt ball. Thus, II
Vi II = 1 for al i, so max IIxAl1 is acmeved at a "EW
11"11=1
vertex. _
IIzllJ = IIzJllo = IIzJGII = IIzIIl = IIzlI.
We wil give several examples of computing TW (A), for various W, in
Thus, IINIIJ = IINII and hence
Chapter 11. For now, we look at a classical result.
An n x n nonnegative matrix A is stochastic if each of its rows is stochas-
TW (A) = IINII ,
tic. Note that in this case
as requied. _
Ae=e,
Formulas for computing TW (A) depend on the vector norm used as well
where e = (1,1,. .. , i)t, so we can set E = e. Then using the I-norm,
as on E. We restrict our work now to Rn so that we can use convex polytopes. If the vector norm, say II-II, has a unt ball wmch is a convex
K = fx E Rn : xe = 0 and Ilxlli :: Il.
polytope, that is The vertices of this set are those vectors having precisely two nonzero
II
K = fx E Rn: xE = 0 and IlxlI :: Il
entries, namely ~ and -~. Thus,
is a convex polytope, then a formula, in terms of the vertices of tms cònvex polytope, can be found. Using tms notation, we have the following.
TW (A) = max II~a' - ~a'il
i#j 2 i 2 J i
l
32
2.3 Measures of Irreducibility and Full Indecomposability
2. Functionals
33
Proof. We prove the result for TB. Let Ai, A2Ai, A3A2Ai,... be a
where ak denotes the k-th row of A. Written in the classical way,
sequence of products taken from 2:. Partition, as possible, each product
1
Ak... Ai in the sequence into r-blocks,
Ti (A) = '2 lrff Ilai - ailli '
7r s . . . 7riAt . . . Ai is called the coeffcient of ergodicity for stochastic matrices.
where k = sr + t, t -( r, and 7ri, . .. , 7r s are r-blocks. Then
To conclude this subsection, we show how to describe subspace coeffcients on the compact subsets. To do this we suppose that 2: is a compact matrix set and that if A E 2:, then A has partitioned form as given in (2.5).
T (7r s . . . 7riAt . . . Ai)
S T (7rs)'" T (7ri) T (At)'" T (Ai)
Let S ç pn such that if x, YES, then x - yEW (a subset of a tranlate of W). We defie
S T~ßt.
Thus T (Ak . . . Ai) -t 0 as k -t 00. Conceriung the geometric rate, note that for T r :; 0,
T (2:) = max h (R2:, T2:)
RlS h (R, T)
kt r-r
T~ = Tr
where the maxmum is over all compact subsets Rand T in S.
k _.!
S dTr r
A bound on T (2:) follows.
1£ -i
Theorem 2.13 T (2:) S ~~TW (A).
ST;:Tr
Proof. The proof is as in Theorem 2.9. _
= T-i ( f:)k r Tr Thus,
We now defie
T (Ak'" Ai) S T;i (Tn k ,
TW (2:) = maxTw (A). AE2:
which shows that the rate is geometric. _ 2.2.3 Blocking
In applications of products of matrices, we need the requied contraction coeffcient to be less than 1. However, we often fid a larger coeffcient. How this is usually resolved is to use products of matrices of a specified
2.3 Measures of Irreducibility and Full Indecomposability
length, caled blocks. For any matrix set 2:, an r-block is defied as any product 7r in 2:r. We now prove a rather general, and usefi, theorem.
Measures give an indication of how the nonzero entries in a matrix are distributed within that matrix. In this section, we look at two such measures.
For the fist measure, let A be an n x n nonnegative matrix. We say that
Theorem 2.14 Let T be a contraction coeffcient (either TB or TW) for a
A is reducible if there is a O-submatrix, say in rows numbered ri, . . . , r s and
matri set 2:. Suppose T (7r) S T r for some constant T r -( 1 and all r-blocks
colums numbered Ci, . . . , Cn-s, where ri, . .. , r s, Ci, . .. , Cn-s are distinct.
7r of 2:, and that T (2:) S ß for some constant ß. Mien all products are taken from 2:, we have the following. If T = T B, then T (Ai) , T (A2Ai) , T (A3A2Ai) , . .. converges to O. If T = TW, then T (Ai), T (AiA2) , T (AiA2A3) , . .. converges to O. And, both have rate of
(Thus, a 1 x 1 matrix A is reducible iff au = 0.) For example
¡1 2 1J
A= 0 4 0
i
3 0 2
convergence T;: .
l
34
2.3 Measures of Irreducibility and Full Indecomposability
2. Functionals
35
ri, . .. , r s and colums numbered Ci, . .. , Cn-s' (Thus a 1 x 1 matrix A is partly decomposable if au = 0.) For example,
¡i 2 OJ
A= 4 0 3 2 0 1
is partly decomposable since there is a O-submatrix in rows 2 and 3, and
colum 2. If we let P and Q be n x n permutation matrices such that P permutes rows ri,... , r s into rows 1,... , sand Q permutes colums Ci,... , Cn-s into colums s + 1, . .. ,n, then
FIGURE 2,13, The graph of A,
PAQ = A2i A22
is reducible since in row 2 and colum 1 and 3, there is a O-submatrix.
(Au 0 J
If p is a permutation matrix that moves rows ri,... , rs into rows 1,... , s,
then
where Au is s x s. An n x n nonnegative matrix A is fully indecomposable if it is not partly decomposable. Thus, A is fully indecomposable iff whenever A contain a p x q O-submatrix, then p + q :: n - 1. There is a link between irreducible matrices and fuly indecomposable matrices. As shown in Brualdi and Ryser (1991), A is irreducible if A + I is fuly indecomposable.
P Apt = A2i A22
(Au 0 J
where Au is s x s. In the example above,
¡o 1 OJ
p= 1 0 0
A measure of full indecomposability can be defied as
o 0 1 An n x n nonnegative matrix A is irrducible, if it is not reducible. As shown in Varga (1962), a directed graph can be associated with A by using vertices Vi, . .. , Vn and defug an arc from Vi to Vj if aij ;: O. Thus for our example, we have Figure 2.13. And, A is irreducible if and only if there is a path (diected), of positive length, from any Vi to any Vj. Note
U(A) = min ( max ai') , ieS.jET
S T S,T J
where S = t ri, . .. , r s J and T = t Ci, . .. , Cn-s J are nonempty proper subsets of -(,... ,nJ'
We now show a few basic results about fuy indecomposable matrices.
that in our example, there is no path from V2 to V3, so A is reducible.
A measure, called a measure of irreducibility, is defied on an n x n nonnegative matrix A, n ;: 1, as
Theorem 2.15 Let A and B be n x n nonnegative fully indecomposable matrices. Suppose that the largest O-submatrices in A and B are SAX t A
and SB x tB, respectively. If
u (A) = nu (maxai ,)
R iER J ;En'
SA + tA = n - kA SB + tB = n - kB,
w~re R is a nonempty proper subset of -(, . .. , n J and R' its complient. Tils measure tell how far A is from being reducible. .
then the largest O-submatri, say a p x q submatri, in AB satisfies
For the second measure, we say that an n x n nonnegative maÚix A is partly decomposable if there is a O-submatrix, say in rows numbered
p + q :: n - kA - kB.
l
~
36
2,3 Measures of Irreducibility and Full Indecomposability
2. Functionals
Proof. Suppose P and Q are n x n permutations such that
37
Corollary 2.5 Let A1, . .. , An-1 be n x n fully indecomposable matrices. Then A1 . . . An-1 is positive.
P(AB)Q = (011 012 J 021 022
Proof. Note that kAiA2 ;: kAi + kA2' And kAi"'An-i ;: kAi +... + kAn_i
where 012 is p x q and the largest O-submatrix in AB.
;:1+...+1 =n-1.
Let R be an n x n permutation matrix such that
PAR = A21 A22
Thus, if A1 . . . An-1 has a p x q O-submatrix, then
(Aii 0 J where Aii is p x s and has no 0 colum.
p + q :S n - kAi...An-i
Partition
:S n - (n - 1)
= 1. RtBQ = (Bii B12 J B12 B22
Tils inequalty cannot hold, hence A1 ... An-1 can contain no O-submatrix.
The result follows. . where Bii is s x (n - q). Thus, we have
A21 0A22 B21B12 B22 021 (Aii J (Bii J (011
The measure of ful indecomposability can also be seen as giving some information about the distribution of the sizes of the entries in a product
~2 J.
of matrices. Theorem 2.16 Let A and B be n x n fully indecomposable matrices. Then
Now,
U (AB) ;: U (A) U (B) .
AiiB12 = 0
Proof. Construct  = ¡âijj where
and since Aii has no 0 colums
A f 0 if aij -: U (A)
aij = 1. aij otherwise.
B12 = O.
Thus, s + q :S n - k B. And, using A, p + (n - s) :S n - k A, so
Construct ÊJ in the same way. Then both  and ÊJ are fuy indecomposable. Thus ÂÊJ is fuy indecomposable, and so we have that U ( ÂÊJ) ? O.
p+q:S (s-kA)+(n-kB-s) :S n - kA - kB,
If (ÂÊJ) ij ? 0, then (ÂÊJ) ij ;: U (A) U (B). Hence, U (AB) ;: U (A) U (B) ,
the desired result. .
the indicated result. .
Several corollaries are immediate. An immediate corollary follows. Corollary 2.4 Let A and B be n x n fully indecomposable matrices. Then
AB II is fully indecomposable.
Corollary 2.6 If A1, . .. , An-1 are n x n fully indecomposable matrices,
then Proof. If AB contais a p x q O-submatrix, then by the theorem, p + q :S
(A1 . . . An-1)ij ;: U (Ai) . . . U (An~1)
n -1- 1 = n - 2. Thus, AB is fully indecomposable, as was to be shown. .
for all i and j.
,
38
2.4 Spectral Radius
2. Functionals
2.4 Spectral Radius
39
and so
Recal that for an n x n matrix A, the spectral radius P (A) of A is
P (L;, ¡j'lIa) = P (L;, 11.11) .
P (A) = max flXI : À is an eigenvalue of A r. À
Hence, the value P (L;, 11.11) does not depend on the matrix norm used, and we can write P (L;) for P (L;, 11.11). In addition, if the set L; used in P (L;) is
It is easily seen that
clear from context, we simply write p for p (L;).
We can also show that if P is an n x n nonsinguar matrix and we defie
1
p(A) = (p (Ak)) k
(2.7)
PL;P-1 = t P AP-1 : A E L;ì
and that for any matrix norm 11.11
then
1
p(A) = lim k-+ooIIAkllk .
(2.8)
P (PL;P-1) = P (L;) .
In tlus section, we use both (2.7) and (2.8) to generalze the notion of spectral radius to a bounded matrix set L;. To generalze (2.7), let
Futher, for any matrix norm 11.11, IIAllp = IIPAp-111 is a matrix norm.
p.(E) ~ sup f p (g A;) ,Ai E E fm al i J . The generalized spectral radius of L; is
Thus p (PL;P-1) = P (L;). So both p and p are invariant under similarity tranformations. Our fist reslÙt links the generaled spectral radius and the joint spectral radius.
1 1
Lemma 2.3 For any matri norm, on a bounded matri set L;, 1
P (L;) = k-+oo lim sup (Pk (L;)) k . To generalze (2.8), let 11.11 a matrix norm and define
P. (E, 1I.11l ~ sup fllg Aill ,A; E E for al i J'
Pk (L;)i' ~ P (L;) ~ P (L;) ~ Pk (L;) k .
Proof. To prove the fist inequalty, note that for any positive integer m, Pk (L;)m ~ Pmk (L;) .
Thus, takig the mk-th roots,
The joint spectral radius is ,ô (L;, 11.11) = lim sup f Pk (L;, 1i.lirH.
k-+oo 1. f
Note that if 1I'lla is another matrix norm, then since norms are equivalent, there are positive constants a and ß such that
a IIAlIa ~ IIAII ~ ß IIAlIa
for tl n x n matrices A. Thus,
1 1
Pk (L;) k ~ Pmk (L;) mk .
Now computing lim sup, as m -- 00, of the right side, we have the fist inequalty. The second inequality follows by observing that
ik...1,1 P (k1,k ... k1,1 ) -0_ Ilk k II for any matrices Aii, . .. , Aik'
For the tlurd inequality, let L be a positive integer and write
at DAi ~ DAi
IIi-lk a lit i-l II kiit
~ ßt D Ai
iia IIi=1kiit
l = kq + r
40
2.4 Spectral Radius
2. Functionals
41
Berger and Wang (1995), in a rather long argument, showed that for bounded sets E, P (E) = P (E). However, we wil not develop this relationship since we use the traditional P, over P, in our work.
where 0 :: r -( k. Note that for any product of L matrices from E,
IIAI . . . Aiii:: IIAkq+r . . . Akq+1Akq . . . AiII :: ßr IIAkq . . . A(k-l)q+l . . . Aq . . . Aiii
We now give a few results on the size of p. A rather obvious such bound follows.
:: ßrpk (Eq)
Theorem 2.18 If E is a bounded set of n x n matrices, then P (E) -(
where ß is a bound on the matrices in E. Thus,
sup IIAII. AEL
Pi (E) t :: ßÍ Pk (E) T
For the remaining result, we observe that if E is a product bounded matrix set, then a vector norm ¡1.llv can be defied from any vector norm
= ßÍ Pk (E) ~~ Pk (E)t 1
11.11 by
= (ßrpdE)-ff Pk(E)t.
IIxllv = sup rIIAil . . . Aii xii: Aii", Aii E Eì I?:O
Now, computing lim sup as L -- 00, we have
(when L = 0, IIAil . . . Aii xii = Ilxll). Using this vector norm, we can see
1
that if A E E, then
P (E) :: Pk (E) 'k
as required. _
IIAxllv :: Ilxllv
1 1
Using this lemma, we have simpler expressions for P (E) and P (E).
for al x. Thus we have the following.
Theorem 2.17 If E is a bounded matri set, then we have that p (E) =
Lemma 2.4 If E is a product bounded matri set, then there is a vector
k-+oo k-+oo
norm 11,lIv such that for the induced matri norm,
li Pk (E) 'k and P (E) = li Pk (E) 'k .
Proof. We prove the second inequality. By the lemma, we have
IIAllv :: 1.
This lemma provides a last result involving an expression for P (E).
1
P (E) :: pdE) 'k
Theorem 2.19 If E is a bounded matri set,
1 1
for al k. Thus, for any k,
P (E) = inf sup IIAII. 11,11 AEL
P (E) :: tnf Pi (E) J :: sup Pi (E) J
:l?:k i?:k
1 1
from which it follows that
Proof. Let € :; 0 and defie
Ê=f~A:AEEl. lP+E f
k-+oo k-+oo
P (E):: lim infpk (E) 'k :: Hm sup Pk (E) 'k = P (E) .
So, II
Then Ê is product bounded since, if B E Êk, 1
1 A
, lim Pk (E)'k = p(E), k-+oo
IIBII:: A )kPk'
i .
the desired result. _
(P+E
Note that (p+ € )k Pk -- 0 as k -- 00.
L
42
2.5 Research Notes
2. Functionals
Thus, by Lemma 2.4, there is a norm 1I'llb such that
43
authors. Seneta (1981) as well as Rothblum and Tan (1985) showed that
for a positive stochastic matrix A, TB (A) ;: T1 (A) where T1 (A) is the
subspace contractive coeffcient with E = (1, 1, . ., ,1)t. More recently,
IIGllb :S 1
Rhodius (2000) considered contraction coeffcients for inte stochastic
for al GEt.
. 1 A
matrices. It should be noted that these authors call contraction coeff-
Now, 1f A E ~, p+€ A E ~, so
cients, coeffcients of ergodicity.
Thus,
General work on measures for irreducibilty and ful indecomposabilty were given by Hartfiel (1975). Christian (1979) also contributed to that area. Hartfiel (1973) used measures to compute bounds on eigenvaues and
and since E was arbitrary,
eigenvectors. Rota and Strang (1960) introduced the joint spectral radius ,ô, while Daubechies and Lagaries (1992) gave the generalzed spectral radius p. Lemma 2.3 was also done by those authors. Berger and Wang (1992)
IIAllb :S ,ô + €.
inf sup IIAII :S ,ô + E, 11,11 AEL
proved that p (~) = ,ô (~), as long as ~ is bounded. This theorem was also inf sup IIAII :S ,ô.
proved by Elsner (1995) by different technques. Beyn and Elsner (1997)
11.11 AEL
proved Lemma 2.4 and Theorem 2.19. Some of this work is implicit in the paper by Rota and Strang.
Finally by Theorem 2.18, inf sup IIAII ;: ,ô. 11,11 AEL
The result follows from the last two inequalities. _
2.5 Research Notes Some material on the projective metric can be found in Bushell (1973), Golubinsky, Keller and Rothchild (1975) and in the book by Seneta (1981). Geometric discussions can be found in Bushell (1973) and Golubinsky, Keller
and Rothchild. Artzroui (1996) gave the inequalities that appeared in Theorem 2.2. A source for basic work on the Hausdorff metric is a book by Eggleston (1969).
Birkhoff (1967) developed the expression for TB. A proof can also be
found in Seneta (1981). Arzroui and Li (1995) provided a 'simple' proof
for this result. Bushell (1973) showed that ((Rn)+ n U,p), where U is thellunit sphere, was a complete metric space. Altham (1970) discussed
measurements in general.,
Much of the work on TW in subsection 2 is based on Hartfiel and Roth-
blum (1998). However, special such topics have been studied by numerous I \
L
3 Semigroups of Matrices
Let ~ be a product bounded matrix set. A matri sequence of the sequence (~k) is a sequence 71i, 712, . .. of products taken from ~, ~2, . . . , respectively. A matri subsequence is a subsequence of a matri sequence.
The limiting set, ~oo, of the sequence (~k) is defied as ~oo = iA: A is the
liit of a matrix subsequence of (~k)l.
Two examples may help with understandig these notions.
Example 3.1 Let ~ = t (~ ~ J J' Then k~~ (~ ~ J k does not exst. However, ~oo = t (~ ~ J ' (~ ~ J J'
Example 3.2 Let ~ = t (i i J ' (! ! J J' Then we can show that II
~oo = t (i i J ' (~ ~ J J . As we will see in Chapter 11, limiting sets can be much more complicated.
ì i
L
46
3.1 Limiting Sets
3. Semigroups of Matrices
47
Theorem 3.3 IfE is product bounded and compact, it follows that EEoo =
3.1 Limiting Sets
EOO = EOOE.
This section describes various properties of limiting sets.
Proof. We only show that Eoo ç EEOO. To do this, let B E EOO. Since B E Eoo, there is a matrix subsequence 71 ii , 71 i2 , . .. that converges to B.
Factor, for k ;: 1,
3.1.1 Algebraic Properties
Some algebraic properties of a limiting set Eoo are given below.
71ik = AikCik
Theorem 3.1 If E is product bounded, then Eoo is a compact semigroup.
where Ai2' Ai3, . .. are in E. Now, since E is compact, this sequence has a
Proof. To show that EOO is a semigroup, let A, B E Eoo. Then there are matrix subsequences of (Ek), say
subsequence, say
Ah, Ah , . . .
71ii, 71 i2' . . .
which converges to, say, A. And, likewise Ch, C h , . .. has a subsequence,
7rj¡,7rj2'" .
say
that converge to A and B, respectively. The sequence
Ck2, Gk3,...
71ii 7rji' 71i27rj2" . .
which converges to, say, C. Thus Ak2Ck2, Ak3Ck3,'" converges to AG. Noting that A E E, C E Eoo and that
is a matrix subsequence of (Ek) which converges to AB. Thus, AB E Eoo and since A and B were arbitrary, Eoo is a semigroup. The proof that Eoo is topologically closed is a standard proof, and since
AC=B, we have that Eoo ç EEoo and the reslÙt follows. -
E is product bounded, EOO is bounded. Thus, Eoo is a compact set. _
When E = tAl, multiplying EOO by any matrix in Eoo doesn't change that set.
A product reslÙt about EOO follows.
Theorem 3.2 If E is product bounded, then EooEoo = Eoo.
Theorem 3.4 If E = tAl is product bounded, then for any B E Eoo,
Proof. Since Eoo is a semigroup, EooEoo ç Eoo. To show equalty holds,
BEOO = EOO = EOO B.
let A E Eoo and 71i, 712, . .. a matrix subsequence of (Ek) that converges to
A. If 71k has lk factors, k;: 1, factor
Proof. We prove that BEoo = Eoo.
71k = BkCk
Since Eoo is a semigroup, BEoo ç EOO. Thus, we need only show that equalty holds. For this, let C E EOO. Then we have by Theorem 3.3
where Bk contains the fist ¡lk!2J factors of 71k and Ck the remaiiung factors.
AkEoo = Eoo
Since E is product bounded, the sequence Bi, B2,... has a conver-
gent matrix subsequence Bii, Bi2, . .. which converges to, say, B. Since
for al k. Thus, there is a sequence Ci, C2, . . . , in EOO such that
Cii, Ci2, . .. is bounded, it has a convergent subsequence, say, Cii, Ch, . . . which converges to, say, C. Thus 71j¡ ,7Ih,'" converges to BC. Since B
AkCk = C
anJ C are in Eoo and A. = BC, it follows that Eoo ç EooEoo, and so EooEoo = Eoo. _
for al k.
Now suppose the sequence
Actually, multiplying Eoo by E doesn't change that set.
A ki , A k2 , . . .
¡ i
L
48
3.1 Limiting Sets
3. Semigroups of Matrices
converges to B. Since ~oo is bounded, there is a
subsequence ofCki ,Ck2"'"
49
For tils, let D E ~oo. Then by using Theorem 3.4, we can write
say
D=BT
Cill Ch,... for some T E ~oo. Now
that converges to, say, ê. Thus
CD = CBT
Bê=c.
=BT =D.
And, as a consequence ~oo ç B~oo. _
Using tils theorem, we can show that, for ~ = tAL ~oo is actually a group.
And, by commutivity, DC = D. Thus, C is the identity in ~oo. For inverses, let H E ~oo. Then, by Theorem 3.4, there is a E E ~oo, such that
Theorem 3.5 If ~ = t A ì and ~ is product bounded, then ~oo is a com-
HE=C,
mutative group.
Proof. We know that ~oo is a semigroup. Thus, we need oiùy prove the additional properties that show ~oo is a commutative group. To show that ~oo is commutative, let Band C be in ~oo. Suppose the sequence
Aii,Ai2,... and
so E = H-l. The parts above show that ~oo is a group. _
3.1.2 Convergence Properties In tils subsection, we look at the convergence properties of
~,~2,...
Aii , Ah , . . .
converge to B and C, respectively. Then BC = li Aik lim Aik k-+oo k-+oo = lim Aik+ik k-+oo
= lim Aik lim Aik
where ~ is a product bounded matrix set. Recal that in tils case, by Theorem 3.1, ~oo is a compact set. ConcerIUg the long run behavior of products, we have the followig.
Theorem 3.6 Suppose ~ is product bounded and E :; O. Then, there is a constant N such that if k :; Nand 7lk E ~k, then
k-+oo k-+oo
d (7lk, ~OO) 0( E.
=CB. Thus, ~oo is commutative.
To show ~oo has an identity, let B E ~oo. Then by using Theorem 3.4,
Proof. The proof is by contradiction. Thus, suppose for some E :; 0, there is a matrix subsequence from the sequence (~k), no term of wilch is in ~oo + E. Since ~ is product bounded, these products have a subsequence
we iihave that
that converges to, say, A, A E ~oo. Tils implies that d (A, ~OO) 2: E, a
CB=B for some C in ~oo. We show that C is the identity in ~oo.
contradction. _ Note that tils theorem provides the following corollary.
50
3.1 Limiting Sets
3. Semigroups of Matrices
51
Theorem 3.8 If E is a product bounded set and W a compact set, then
Corollary 3.1 Using the hypothesis of the theorem, for some constant N,
Woo = EooW.
Ek ç Eoo + I:
Proof. Let Wo E Woo' Then Wo is the limit of a vector subsequence, say, 7IiWi,7I2W2,... of (EkW). Since W is compact and E product bounded,
for all k ): N.
we can fid a subsequence 7Iii Wi1l7li2 Wi2'''' of our sequence such that In the next result we show that if the sequence (Ek) converges in the
Hausdorff Sense, then it converges to Eoo.
Wii , Wi2 , . .. converges to, say, W and 71 ii , 71 i2 , . .. converges to, say, 71 E EOO. .
Thus
Theorem 3.7 Let E be a product bounded compact set. If t is a compact subset of Mn and h (Ek, t) -- 0, then t = Eoo.
Proof. By the previous corollary, we can see that t ç Eoo. Now, suppose t =l Eoo; then there is an A E EOO such that A tf t. Thus,
d(A,t) =1:,
where I: is a positive constant. Let 7Iki, 7Ik2, . .. be a matrix subsequence of (Ek) that converges to A.
Then there is a positive constant N such that for i ): N, d(7Ii,t)): ~.
Wo = 7IW
and we can conclude that Woo ç EooW. Now let 7IOWo E EooW, where Wo E Wand 710 E Eoo. Then there is a matrix subsequence 71 ii , 71 i2' . .. that converges to 710. And we have that 7Iii Wo, 7Ii2 Wo,... is a vector subsequence of (EkW), wruch converges to 7IOWo. Thus, 7IOWo E Woo, and so EooW ç Woo' .
Theorem 3.9 If E is a product bounded compact set, W a compact set, and h (Ek, Eoo) -- 0 as k -- 00, then h (EkW; Woo) -- 0 as k -- 00.
Proof. By Theorem 3.8, we have that Woo = EooW, and so we wil show that h (EkW, EooW) -- 0 as k -- 00. Since W is compact, it is bounded by, say, ß. We now show that, for all k,
Thus,
h (EkW, EOOW) 5, ßh (Ek, EOO) (3.1) Ó (Eki, t) ): ~
from wruch the theorem follows.
for all i ): N. Trus contradicts that h (Eki, t) -- 0 as i -- 00. Thus
To do trus, let 7IkWO E EkW where Wo E W and 7Ik E Ek. Let 71 E EOO be such that d(7Ik,71) 5, h (Ek,EOO). Then
t = Eoo. . d(7IkWO,7IWO) 5, ßd(7Ik,7I)
In many applications of products of matrices, the matrices are actualy
5, ßh (Ek,EOO).
multiplied by subsets of pn. Thus, if
And since 7IkWO was arbitrary,
wçpn, we have the sequence
II
Ó (EkW, EOOW) 5, ßh (Ek, EOO) .
Similarly,
W;EW;E2W,... .
In trus sequence, we use the words vector sequence, vector subsequence,
Ó (EOOW, EkW) 5, ßh (Ek, EOO)
from wruch (3.1) follows. .
and limiting set Woo with the obvious meanngs. A way to calculate Woo, in terms of Eoo, follows.
A result, wruch occurs in applications rather often, follows.
52
3,1 Limiting Sets
3. Semigroups of Matrices
Corollary 3.2 Suppose E is a product bounded compact set and W a com-
pact set. IfEW ç W, then h (EkW; Woo) -+ 0 as k -+ O.
53
Lemma 3.1 Suppose tAr is product bounded and W a compact set. Given an E )- 0 and any B E Eoo, there is a constant N such that
Proof. It is clear that Ek+1W ç EkW, so Woo ç EkW for al k. Thus, we need only show that if E )- 0, there is a constant N such that for all k )- N
d(ANw,Bw).. E
for all w E W. EkW ç Woo + E.
Tils follows as in the proof of Theorem 3.6. .
We conclude tils subsection by showig a few results for the case when
E is fute. If E = tAi,... ,Amr is product bounded and W compact, then since
EEoo = Eoo,
Woo = EWoo = AiWoo u... UAmWoo. For m = 3, tils is somewhat depicted
The theorem follows.
Theorem 3.10 Using the hypothesis of the lemma, suppose that L (x) =
Ax is nonexpansive. Given E )- 0 and B E Eoo, there is a constant N such that for k 2: 1,
h(AN+kW,AkBW).. E.
Proof. By the lemma, there is a constant N such that d(ANw,Bw).. E
in Figure 3.1. Thus, although each Ai
for al w E W. Since L is nonexpansive,
d(AN+kw,AkBw).. E
for al w E Wand k 2: 1. From tils inequalty, the theorem follows. . Since EooW = Woo, BW ç Woo' Thus this theorem says that AN+kW stays within E of AkBW ç Woo for al k. We now show that on Woo, L (x) = Ax is an isometry, so there can be no more collapsing of Woo'
Theorem 3.11 Let E = tAr be product bounded and W a compact set. If L (x) = Ax is nonexpansive, then L (x) = Ax is an isometry on Woo'
Proof. We first give a preliuunary result. For it, recall that Woo = EooW and that EOO is a group. Let B E EOO and Aii, Ai2, . .. a matrix subsequence of (Ek) that converges to B.
Let x, fj E Eoo W. Then, since L (x) = Ax is nonexpansive, we have FIGURE 3.1. A view of ~Woo'
o ~ d (AikX, Aikfj) - d (AAikX, AAikfj) ~ d (AikX, Aikfj) - d (Aik+ix, Aik+1fj) .
mal contract Woo into Woo, the unon of those contractions reconstructs Woo.
When E = tAh we can give sometilng of an E-view of how AkW tends to Woo' We need a lemma.
Taking the limit at k -+ 00, we get o ~ d (Bx, By) - d (ABx, ABfj) = 0
54
3.2 Bounded Semigroups 55
3. Semigroups of Matrices
or
d (Bx, By) = d (ABx, ABfj.
(3.2)
Theorem 3.13 Suppose that ~ is a bounded matri set. Suppose further that each matri M E ~ has partition form
Now let x,y E Woo' Since Woo=~ooW=~oo~OO =~ooWoo, x ~ Bix
o Ci B23 ... B2k
and y = B2Y where x,Y E Woo and Bi,B2 E ~oo. Using (3.2), and that
M = 0 0 C2 . . . B3k
~oo is a group,
d(x,y) = d(Bix,B2y) = d (Bix, BiBii B2y) = d (ABix, ABi (Bii B2y))
. . . .. .Ck Lo A0 Bi20Bi3 Bik i where all matrices on the block main diagonal are square. If there are vector norm 11,lIa' 1I.lle! ,... , 11.llek such that
= d(Ax,Ay), the desired result. .
IIAlla -: i and I¡Cillei -: Q .: i for all M E ~, there is a vector norm 11.11 such that IIMII -: i forall M E ~.
Proof. We prove the result for k = 1. For this, we drop subscripts, using M = (~ ~ J. The general proof then follows by induction.
3.2 Bounded Semigroups In this section, we give a few results about product bounded matrix sets ~. Theorem 3.12 Let ~ be product bounded matri set. Then there is a norm, say 11.11, such that II All -: i for all A E ~.
For all x E pn, partition x = ( ~~ J compatible with M. Now, for any constant K ? 0, we can defie a vector norm 11.11 by
¡ixil = Ilxi lIa + K Ilx21le'
Then we have, for any M E ~,
Proof. Let A = ~ U ~2 U . . '. Defie a vector norm on pn by II
IIMxl1 = IIAxi + BX211a + K I1Cx211e -:IIAxilla + IIBx211a + K IICx211e
xII = sup (lIxIl2' II7rx112 : 7r E Al.
-: IIxi lIa + liB
Then if A E ~,
II IIx211e + K IICx2 lie
where IIAxl1 = sup (IIAxIl2, II7rAxI12 : 7r E Al,
IIBx211a. IIBII =:~ Ilx211e
and since A, 7r A E A,
-: sup (lIxIl2, I17rXIl2 : 7r E Al
= IlxlI.
Thus, IIMxll -: IIxilla + (IIBII + K IICIU IIx211e
Since this inequality holds for al x,
(IIBII )
= Ilxilla + K + IIClle K Ilx21le' II
which is what we need. . A special such result follows.
IIAII -: i,
Since ~ is bounded, IIBII, over al choices of M, is bounded by, say, ß. SO we can choose K such that
ß
K+Q':1.
56
3, Semi
groups of Matrices
3.2 Bounded Semigroups
Then,
57
Theorem 3.14 If all infinite products from a matrix set ~ converge, then ~ is product bounded. IIMxlI ~ Ilxilla + K IIx211c
Proof. Suppose al infte products from ~ converge. Futher let A =
= Ilxll.
~ U ~2 U . .. and defie
This shows that IIMII ~ 1, and since M was arbitrary
X = rx E pn : Ax is boundedr.
IIMII ~1
Then X is a subspace and 11 : X ~ X for all 11 E A. By the Uiuform Boundedness Lemma, there is a constant ß such that
for al M E~. _
sup 111Ixii
In the same way we can prove the following.
xEX Ilxll = ß -c 00, Alia ~ a, then for any ó,
Corollary 3.3 If IIAlla ~ 1 is changed to II
for al
a -c Ó -c 1, there is a norm 11.11 such that IIMII ~ ó for all M E ~.
11 E A.
If X = pn, then ~ is product bounded. Thus, we suppose X i= pn. We now show that given an x ft X and c:; 1, there are matrices Ai,... , Ak E ~
Our last result shows that convergence and product bounded are connected. To do this, we need the Uiuform Boundedness Lemma.
such that
IIAk . . . Aixli 2: c
Lemma 3.2 Suppose X is a subspace of pn and
(3.3)
and sup 111IxII -c 00
Ak . . . Aix ft X. 11 in A = ~ U ~2 U . .. and the inequality holds for
where the sup is over all
Since x ft X, there are matrices Ai, . .. , Ak E ~, such that
any x E X, where IIxll = 1. Then ~ is product bounded on X.
IIAk . . . Aixll :; max (1, ß II~II) c.
Proof. We prove the result for the 2-norm. We let r Xi, . .. , Xr r be an X E X and IIxII2 = 1,
orthonormal basis for X. Then, if
(3.4)
If Ak... Aix ft X, we are through. Otherwise, there is at, t -c k, such that At'" Aix ft X, while AtH (At... Aix) EX. Thus, we have
x = aiXi +... + arXr
IIAk . . . At+2 (AtH . . . Aix) II ~ ß IIAtH . . . Aixli
where laii2 +... + lari2 = 1. Now letß be such that
:: ß 1I~IIIIAt . . . AixlI.
Thus, by (3.4), sup 111IXil12 :: ß
c ~ IIAt . . . Aixll for i = 1,... , rand al
11 E A. It follows that if 11 E A and IIxII2 = 1, then 1I11XII2 ~.laiII11IxiIl2 + . .. + larl1l1lxrll2
II
::nß.
bounded. _ .
Thus, since x was arbitrary 111111 ~ nß. Since 11 was arbitrary, ~ is product
I,
which gives (3.3). Now, applying result (3.3), suppose x ft X. Then there are 1Ii, 112,... in A such that
1I11ixll 2: 1 and 1IiX ft X 1I11211ixll 2: 2 and 1I211iX ft X
3. Semi
groups of Matrices
4
'hus,
1l =.. .1lk.. .1li
Patterned Matrices ; not convergent. This contradicts the hypothesis, and so it follows that C = pn. And, E is product bounded. .
Putting Theorem 3.12 and Theorem 3.14 together, we obtai the followig norm-convergence result.
Jorollary 3.4 If all infinite products from a matri set E converge, then All :: 1 for all A E E. here is a vector norm 11.11 such that II
t3 Research Notes lection 1 was developed from Hartfiel (1981, 1991, 2000). Linuting sets, inder different names, such as attactors, have been studied elsewhere. Theorem 3.12 appears in Elsner (1993). Also see Beyn and Elsner (1997). lheorem 3.14 was proved by G. Schechtman and published in Berger and Nang (1992).
In this chapter we look at matrix sets E of nonnegative matrices in Mn.
We find conditions on E that assure that contraction coeffcients TB and TW are less than 1 on r-blocks, for some r, of E.
4. i Scrambling Matrices The contraction coeffcient TB is less than 1 on any positive matrix in Mn. The fist result provides a set E in which (n - I)-blocks are all positive. In Corollary 2.5, we saw the following.
Theorem 4.1 If each matri in E is fully indecomposable, then every (n - 1) -block from E is positive.
For another such result, we describe a matrix which is somewhat like a fuy indecomposable matrix. An n x n nonnegative matrix A is primitive if Ak :; 0 for some positive integer k.
II
Intead of computing powers, a matrix can sometimes be checked for
primitivity by inspecting its graph. As shown in Varga (1962), if the graph of A is connected (There is a path of positive length from any vertex i to any vertex j.) and
L
4,1 Scrambling Matrices
4. Patterned Matrices
61
and q = the smallest exponent k such that A k ? 0 for all
ki = goo of the lengths of al
paths from vertex i to
(0,1) -primitive matrices A.
itself,
Let r = p + 1 and Aii"" , Air matrices in:E. Then, by hypothesis
ien A is primitive if and Oiùy if ki = 1. (Actualy, ki can be replaced by
Aii, Ai2 Aii' . .. , Air' . . Aii is a sequence of primtive matrices. Since there
rryki.
are r such matrices, the sequence Aii' (Ai2AiJ* ,. . . , (Air" . Aii)* has a duplication, say
For example, the Leslie matrix
i8 ii it ii
¡i 2 1 i
(A- ... A- )* = (A- ... A- )*
A = .3 0 0
o .4 0
where s ? t. Thus
it+1 itA- ii it... i1 (A-i8 ... A) * (A- ... )* = (AA- )*
as the graph shown in Figure 4.1 and is thus primitive.
where the matrix arithmetic is Boolean. Set
B = (Ai. ... Ai,+i)* and A = (Ai, ... AiJ* . So we have
BA=A. From this it follows that since Ba ? 0, Ba A = A ? 0;
thus, Ai, . . . Aii ? 0, and so Air' . . Aii ? 0, the result we wanted. _ FIGURE 4.1. The graph of A.
A rather well known result on matrix sets and primtive matrices follows.
A fial result of this type uses the following notion. If B is an n x n
ro give it, we need the following notion. For a given matrix A, defie
(0, I)-matrix and A* :: B, then we say that A has pattern B.
t * = (aij J, caled the signum matrix, by
Theorem 4.3 Let B be a primitive n x n (0, I)-matri. If each matri in :E has pattern B, then for some r, every r-block from :E is positive.
* fIifaij?O
aij = 1. 0 otherwise
Proof. Since B is primitive, BT ? 0 for some positive integer. Thus, since (Air'" AiJ* :: (BT)*, the result follows. _
rheorem 4.2 Let:E be a matri set. Suppose that for all k = 1,2,. .. , ~ach k-block taken from :E is primitive. Then there is a positive integer r
In the remaiiung work in this chapter, we wil not be interested in r-
iuch tMt each r-block from :E ?- positive.
blocks that are positive but in r-blocks that have at least one positive
colum. Recall that if A has a positive colum, then
?roof. Let
p (Ax, Ay) .c p (x, y)
p = number of (0,1) -primtive n x n matrices
l
r
62
4. Patterned Matrices
4, i Scrambling Matrices
for any positive vectors x and y. Thus, there is some contraction. We can obtain vaious results of this type by looking at the graph of a matrix. Let A be an n x n nonnegative matrix. Then the ij-th entry of AS is
63
where each Ak is either an nk x nk irreducible matrix or it is a 1 x 1 0matrix. Here, the partitioned form in (4.2) is caled the canonical form of
A. IT for some k, Aki,. .. ,Akk-i are all O-matrices, then Ak is caled an
L aiki akik2 . . . ak._ii
isolated block in the canonical form. If Ak has a positive column for some k, then Ai must be priuutive since
where the sum is over all ki,. .. , ks-i. This entry is positive iff in the
if Ai is not priuutive, as shown in Gantmacher (1964), its index of imprimitivity is at least 2. This assures that A~, and hence Ak, never has a
graph of A, there is a path, say Vi, Vki, Vk2,. . . , Vk._i, Vj from Vi to Vj. In terms of graphs, we have the following.
positive column for any k. Corollary 4.2 Let A be an n x n nonnegative matrix. Suppose the canon-
Theorem 4.4 Let A be an n x n nonnegative matri in the partitioned form
ical form (4.2) of A satisfies the following:
1. Ai is a primitive m x m matri.
A=(~ ~J
(4.1)
where P is an m x m primitive matri.
If, in the graph of A, there is a path from each vertex from C to some vertex from P, then there is a positive integer s such that AS has its first m columns positive.
2. The canonical form for A has no isolated blocks. Then there is a positive integer s such that AS has its first m columns positive.
Proof. Observe in the canonical form that since there are no isolated blocks, each vertex of a block has a path to a vertex of a block having
Proof. Since P is priuutive, there is a positive integer k such that pk+t :; 0 for all t 2: O. Thus, there is a path from any vertex of P to any vertex of
a lower subscript. This implies that each vertex has a path to any vertex in Ai. The result now follows from the theorem. _
P having length k + t. Let ti denote the length of a path from Vi, a vertex from C, to a vertex
A different kind of condition that can be placed on the matrices in L to
of P. Let t = maxti. Then, using the remarks in the previous paragraph,
assure r-blocks have a positive colum, is that of scrambling. An n x n nonnegative matrix A is scrambling if AAt :; O. This means, of course,
if Vi is a vertex of C, then there is a path of length k + t to any vertex in
P. Thus, AS, where s = k + t, has its fist m colum positive. _ An immediate consequence follows.
Corollary 4.1 Let A be an n x n nonnegative matri as given in (4.1). If each matri in L has pattern A, then for some r, every r-block from L has
a positive column.
We extend the theorem, a bit, as follows. Let A be an n x n nonnegative matrix. As shown in Gantmacher (1964), there is an n X n permutation matrix P such that
A2i A2 L A... As ""
II PApt =¡ Ai... 0 ::: ~ J '.(4.2) Asi s2
that for any row indices i and j, there is a colum index k such that aik :; 0 and ajk :; O. A consequence of the previous corollary follows. Corollary 4.3 If an n x n nonnegative matri is scrambling, then AS has
a positive column for some positive integer s.
Proof. Suppose the canonical form for A is as in (4.2). Since A is scrambling, so is its canonical form, so this form can have no isolated blocks. And, Ai must be priuutive since, if this were not true, Ai would have index of imprimitivity at least 2. And this would imply that Ai, and thus A, is not scrambling. _
It is easily shown that the product of two n x n scramblig matrices is itself a scrambling matrix. Thus, we have the following.
Theorem 4.5 The set of n x n scrambling matrices is a semigroup.
~
64
4.2 Sarymsakov Matrices
4. Patterned Matrices
65
then F(t21) = U,21 and F(t1,21) = t1,2,31.
If L contai only scrambling matrices, L U L2 U . .. contains only scram-
Let B be an n x n nonnegative matrix and Fi, F2 the consequent functions belonging to A, B, respectively. Let Fi2 be consequent niction belonging
blig matrices. We use this to show that for some r, every r-block from such a L has a positive colum.
toAB.
Theorem 4.6 Suppose every matri in L is scrambling. Then there is an r such that every r-block from L has a positive column.
Lemma 4.1 F2 (Fi (S)) = Fi2 (S) for all subsets S.
Proof. Consider any product of r = 2n2 + 1 matrices from L, say Ar . . . Ai.
Proof. Let j E F2 (Fi (S)). Then there is a k E Fi (S) such that bkj )- 0 and an i E S such that aik )- O. Since the ij-th entry of AB is
Let a (A) = A*, the signum matrix of the matrix A. Note that there are at most 2n2 distinct n x n signum matrices. Thus,
n
L airbrj r=i
a (As' .. Ai) = a (At" . Ai)
(4.3)
that entry is positive. Thus, j E Fi2 (S). Since j was arbitrary, it follows
for some sand t with, say, r 2: s )- t. It follows that
that F2 (Fi (S)) ç Fi2 (S).
Now, let j E Fi2 (S). Then by (4.3), there is an i E S and a k such that aik )- 0 and bkj )- O. Thus, k E Fi (S) and j E F2 (tk1) ç F2 (Fi (S)). And, as j was arbitrary, we have that Fi2 (S) ç F2 (Fi (S)).
a (As' . . AtH) a (At. . . Ai) = a (At. . . Ai) when Boolean arithmetic is applied. Thus, using Boolean arithmetic, for
Put together, this yields the result. _
any k )- 0, a (As' . . At+i)k a (At' . . Ai) = a (At. .. Ai) .
The corollary can be extended to the following. Theorem 4.7 Let A i, . .. , Ak be n x n nonnegative matrices and Fi, . .. , Fk
We know by Corollary 4.3 that for some k, a (As'" AtH)k has a column of 1's. And, by the defution of L, a (At' . . Ai) has no row of O's. Thus, a (At... Ai) has a positive colum, and consequently so does At... Ai. From this it follows that since r )- t, any r-block from L has a positive
consequent functions belonging to them, respectively. Let Fi...k be the consequent function belonging to Ai ... Ak. Then
Fk (. . . (Fi (S)) = Fi,..k (S)
colum. _
for all subsets S ç U,... ,n1.
We now defie the Sarymsakov matrix. Let A by an n x n nonnegative matrix and F its consequent function. Suppose that for any two disjoint nonempty subsets S, S' either
4.2 Sarymsakov Matrices
1. F (S) n F (S') i- ø or
To describe a Sarymakov matrix, we need a few preliminary rerrarks.
Let A be an n X n nonnegative matrix. For al S ç U,... , n J, defie
2. F (S) n F (S') = ø and IF (S) U F (S')I )- IS U S'I.
the consequent function F, belonging to A, as
Then A is a Sarymsakov matri.
F (S) = U : aij )- 0 for some i E 81.
A diagram depicting a choice for S and S' for both (1) and (2) is given in Figue 4.2.
Thus, F (S) gives the set of all consequent indices of the indices in S. For example, if
Note that if A is a Sarymakov matrix, then A can have no row of O's
since, if A had a row of O's, say the i-th row, then 8 = ti1 and S' = t1,... ,n1- S would deny (2). The set K of all n x n Sarymsakov matrices is caled the Sarymsakov
A= 1 1 0
class of n x n matrices. A major property of Sarymsakov matrices follows.
o 1 1 (101J
L
66
4.2 Sarymsakov Matrices 67
4. Patterned Matrices
~
S r
S'I
Lemma 4.2 Let A be an n x n nonnegative matri and F the consequent
F(S')
F(S)
~I
function belonging to A. The two statements, which are given below, are
equivalent.
F(S) F(S')
x
i
x
I
0
0
I
x
I
x
or
S'I
0
0
1. A is a 8arymsakov matri. 2. lfC is a nonempty subset of
I
x
I
row indices of A satisfying IF (C)I ~ ICI,
then
0
F (B) n F (C - B) =l ø
-
L
for any proper nonempty subset B of C. ,
Proof. Assumng (1), let Band C be as described in (2). Set 8 = Band S' = C - B. Since Sand S' are disjoint nonempty subsets, by defiition,
FIGURE 4,2. A diagram for Sarymsakov matrices.
Theorem 4.8 Let Ai, . .. , An-i be n x n 8arymsakov matrices. Then Ai . . . An-i is scrambling. Proof. Let Fi,... , Fn-i be the consequent fuctions for the matrices Ai,..., An-i, respectively. Let Fi...k be the consequent fuctions for the
products Ai . . . Ak, respectively, for al k. Now let i and j be distinct row indices. In the following, we use that if Fi..,k ( I il ) n Fi...k ( Ül) =l ø
F (S) n F (S') =l ø or F (S) n F (S') = ø and IF (S) U F (S')I ? IS U S'I. In the latter case, we would have IF(C)I ? ICI, wmch contradicts the hypothesis. Thus the fist condition holds and, using that B = S, C - B = S', we have F (B) n F (C - B) =l ø. This yields (2). Now assume (2) and let S and S' be nonempty disjoint subsets of indices. Set C = S U 8'. We need to consider two cases.
Case 1. Suppose IF (C)I ~ ICI. Then, setting S = B, we have F (S) n F (8') =l ø, thus satisfying the fist part of the defition of a Sarymakov matrix. Case 2. Suppose IF (C)I ? ¡Ci. Then we have IF (S) U F (S')I ? IS U s'i, so the second part of the defition of a Sarymsokov matrix is satisfied.
for some k 0: n, then
Fi...n-i (I il) n Fi...n-i (Ül) =l ø.
(4.4)
Thus, A is a Sarymsakov matrix, and so (2) implies (1), and the lemma is proved. _
Using the defition, either Fi (Iil) n Fi (Ül) =l ø, in wmch case (4.4)
We conclude by showing that the set of al n x n Sarymsakov matrices
holds or
is a semigroup.
lFi (Iil) U Fi (Ül)1 ? 2. In the latter case, either Fi2 ( Ii 1 ) n Fi2 ( Ü 1) =l ø, so (4.4) holds or
lFi2 (I il) U Fi2 (Ül)1 ? 3.
And continuig, we see that either (4.4) holds or
lFi...n-i (I il) U Fi...n-i (Ül)1 ? n. ThJlatter condition canot hold, so (4.4) holds. And since thi is true for
al i and j, Ai... An-i is scramblig. _ A different description of Sarymakov matrices followS.
Theorem 4.9 Let Ai and A2 be in K. Then AiA2 is in K. Proof. We show that AiA2 satisfies (2) of the previous lemma. We use that Fi, F2, and Fi2 are consequent functions for Ai, A2, and AiA2, respectively. Let C be a nonempty subset of row indices, satisfying tms inequality lFi2 (C)I ~ ICI, and B a proper nonempty subset of C. We now argue two cases.
Case 1. Suppose IF¡ (C)I ~ ICI. Then since Ai E K, it follows that Fi (B) n Fi (C - B) =l ø. Thus, ø =l F2 (Fi (B)) n F2 (Fi (C - B))
= Fi2 (B) n Fi2 (C - B) .
68
4.3 Research Notes
4. Patterned Matrices
The proof of Theorem 4.2 is due to Wolfowitz (1963). The bulk of Section 2 was formed from Sarymsakov (1961) and Hartfiel and Seneta (1990). Rhodius (1989) described a class of 'almost scrambling' matrices and showed tils class to be a subset of K. More work in tils area can be
Case 2. Suppose lFi (C)I ;: ICI. Then, using our assumption on C,
lFi2 (C)i S ICI .. lFi (c)i. Thus,
i .. IFi(C)I. Now, using that A2 E K and the previous lemma, if D is any proper 1F2 (Fi(C))
found in Seneta (1981).
nonempty subset of Fi (C), then F2 (D) n F2 (Fi (C) - D) =I ø.
Pulan (1967) described the columns that can occur in infte products of Boolean matrices. Also see the references there.
(4.5)
Now, we look at two subcases.
Subcase a: Suppose Fi (B) n Fi (C - B) = ø. Then Fi (B) is a proper subset of Fi (C) and Fi (C - B) = Fi (C) - Fi (B). Thus, applying (4.5),
with D = Fi (B), we have ø =I F2 (Fi (B)) n F2 (Fi (C) - Fi (B))
= F2 (Fi (B)) n F2 (Fi (C - B)) = Fi2 (B) n Fi2 (C - B),
satisfying the conclusion of (2) in the lemma. Subcase b:Suppose Fi (B)nFi (C - B) =I ø. Then we have F2 (Fi (B))n F2 (Fi (C - B)) =I ø or Fi2 (B) n Fi2 (C - B) =I ø, again the conclusion of
(2) in the lemma. Thus, AiA2 E K. .
The obvious corollary follows. Corollary 4.4 The set K is a semigroup.
To conclude tils section, we show that every scrambling matrix is a Sarymsakov matrix. Theorem 4.10 Every scrambling matrix is a Sarymsakov matri. Proof. Let A be an n x n scrambling matrix. Using (2) of Lemma 4.2, let
C and B be as the sets described there. If i and j are row indices in B and C - B, respectively, then since A is scramblig F (til) n F (Ul) =I ø. Thus F (B) n F (C - B) =I ø and the reslÙt follows. .
i I ,
I
4.3 Research Notes II
As shown in Brualdi and Ryser (1991), if A is primitive, then A(n-i)2-i ;:
O. Tils, of course, provides a test for printivity. Other such reslÙfs are also given there.
69
5 Ergodicity
This chapter begins a sequence of chapters concerned with various types of
convergence of infte products of matrices. In this chapter we consider
row alowable matrices. If Ai, A2,... is a sequence of n x n row alowable matrices, we let
Pk = Ak . . . Ai
for all k. We look for conditions that assure the columns of Pk approach being proportionaL. In general 'ergodic' refers to this kind of behavior.
5. i Birkhoff Coeffcient Results
In this section, we use the Birkhoff contraction coeffcient to obtain several results assuring ergodicity in an infite product of row alowable matrices. The preliminary results show what TB (Pk) --0 as k -- 00 means about the entries of Pk as k -- 00. The fist of these results uses the notion that (1) (2) II
the sequence (Pk) tends to column proportionality iffor al r, s, ~, ~, . . . Pis Pis
converges to some constant ars, regardless of i. (So, the r-th and the s-th
colums are nearly proportional, and become even more so as k -- 00.) An example follows.
72
5.1 Birkhoff Coeffcient Results
5. Ergodicity
Example 5.1 Let
73
Conversely, suppose that lim TB (Pk) = O. Define
k-+oo
if k is odd,
(k) (k) Pis Pis
(k) -_rrn . Pir _ Pir mrs (k)'M(k) rs - mF (k)'
Ak = ¡ k (i t J
k(ì ìJ
if k is even.
The idea of the proof is made clearer by letting x and y denote the r-th and s-th colums of Pk-l, respectively. Then
Then ¡ k! (l l J if k is odd,
(k)
Pk =
. Pir (k) ='Pis IIn W mrs
k! (ì ì J if k is even.
~ (k)x' L. aij J = ~n -- (k) , '" L.a.. 'J Yj j=1
Note that Pk tends to column proportionality, but Pk doesn't converge. Here
j=1
0:12 = 1.
, where pik) and plk) are column vectors, a picture
If we let Pk = (pik) plkJ)
n (k) '2
of how colum proportional might appear is given in Figue 5.1.
L aij Yj Yj
. j=1 = min n (k) i L aij Yj
plk+l) p.(k+2)
Ý p;""
(k)
L-PllkJ
P2
:=1( a~~)YJ' ) Xj
~ p~k+2)
iJ _. = ~n L n (k), Yj , '=1 L aij YJ J j=1
FIGURE 5,1. A view of column proportionality.
n ( (k) )
Lemma 5.1 If Ai, A2, . .. is a sequence of n x n positive matrices and
l- L naij Yj (k) Yj Yi ' , Yn ' J=1
Since '" aij Yj '2 is a convex sum of:E ... .: we have
Pk = Ak... Ai for all k, then lim TB (Pk) - 0 as k - 00 iff Pk tends to
column proportionality.
k-+oo
;=1
Proof. Suppose that Pk tends to colum proportionality. Then m(k) rs ? -minj XjYj= m(k-l). rs (k) (k)
li m ,h( 'l r k D= )1ml',Ilin . Pir -(k) -(k) Pjs k-+oo k-+oo ',J,r,s p, p, Jr 's
Sirrlarly,
= 1. 'thus,
M(k) TB -:-M(k-l) TS , 1- "'if(Pk) = O.
lim TB (Pk) = k~~ 1 + Jif(Pk) k-+oo
and it follows that lim m~~) = mrs, as well as lim M;~) = Mrs, exist.
k-+oo k-+oo
-i ,
74
5, Ergodicity
5,1 Birkhoff Coeffcient Results
Finally, since lim TB (Pk) = 0, lim ø (Pk) = 1, so
Let
k-+oo k-+oo
8 = f R : R is an n x n ran 1 nonnegative matrix where
(k) (k)
-m mi (k) (k) k-+oo i"j,r,s p, P'
1 - li . Pir Pjs
os 3r
IIRIIF = 1¡.
(k)
=k-+oo li m .nunmrs r,s M(k) rs
_ mpq - Mpq
75
Recalng that
d CIP:IIF Pk,8) = ~~p(Pk,R), for some P and q. And thus mpq = Mpq. Since 1 2:!!M 2: Mmpq for all r
rs pq
and s, it follows that mrs = Mrs' Thus,
we see that
li m P(k) ..
d (IIP:IIF Pk, 8) ~ 0 as k -HXJ.
k-+ooPis(k) = mrs
for al i and Pi, P2, . .. tend to colum proportionality. _
Thus, iip~iiFPk tends to 8. So, in a projective sense, the Pk's tend to the
rank one matrices.
Formally the sequence PI, P2,... is ergodic if there exists a sequence of
The result linking ergodic and T B follows.
positive rank one matrices 81,82,... such that
Theorem 5.1 The sequence PI, P2,... is ergodic iff lim TB (Pk) = O.
(k)
m --1 k-+oo s(~) li Pij
k-+oo
(5.1)
Proof. If PI, P2, . .. is ergodic, there are ran 1 positive n x n matrices
OJ
81,82,... satisfying (5.1). Thus, using that 8k is ran one,
for all i and j. To give some meaning to this, we can thi of the matrices Pk and 8k as n2 x 1 vectors. Then
(k) p~k)
. Pir 3S
ø (Pk) =o,J,r,s ,IIllPis WW Pjr
(k) (k)
Pij Srt
p(Pk,8k) = ln~ax WW o,J,r,t Sij Prt
(k) (k) (k) s~k)
. Pir Pjs Sis .. = 0,3,r,s ,IIll WWW Pis Pjr Sir ~k)' S3S
where P is the projective metric. Now by (5.1), so
-lim P (Pk, 8k) = 0
k-+oo
lim ø (Pk) = 1.
k-+oo
and so II
. (1 1)
Hence,
k~~P IIPkllF Pk, 118kliF 8k = 0 1- '¡Ø(Pk) = O.
lim TB (Pk) = k~~ 1 + '¡Ø(Pk)
where II'IIF is the FTobenius norm (the 2-norm on the n2 x 1 vectors).
k-+oo
L
76
5. Ergodicity
5.1 Birkhoff Coeffcient Results
Conversely, suppose lim TB (Pk) = O. For e = (1,1,... , 1)t, defie
77
00
k-+oo
Proof. Since L ý''P(Ak) = 00, it follows by Theorem 51 (See Hyslop
k=l (1959) or the Appendi.) that kDi (1 + ý''P (Ak)) = 00. Thus, since
Sk = Pkeet Pk
et Pke
TB (Pk) :: TB (Ak) . . . TB (Ai) = ¡rti p~;) . 8ti p~;)J
n n (k)
_ (1 - yG) ( 1 - yG)
L L pr8
, 1
r=l 8=1
- (1+ý''P(Ak))'" (1+ý''P(Ai)) an n x n ran one positive matrix. Then
(k) n n (k)
(1 + ý''P (Ak)) ... (1 + ý''P (Ai)) ,
(k) L L Pr8 Pij _ Pij r=18=1
wS oo
iJ
n n
li TB (Pk) = o. k-+oo
L p~;) L p~;)
r=l 8=1
_
A corollary, more easily applied than the theorem, follows.
n n (k) (k) L L Pij Pr8 r=18=1
Corollary 5.1 Let mk and Mk be the smallest and largest entries in Ak,
- n n (k) (k)'
respectively. If l: (!£) = 00, then Pi, P2,... is ergodic.
L LPir P8j r=18=1
k=l k Proof. Since
Using the quotient bound result (2.3), we have that
mk
(k) ,_. 1 Pij
Mk :: ý''P(Ak),
Ø(Pk):: W - Ø(Pk)
the corollary follows. _
Soo iJ
A fial such result follows.
And since lim ø (Pk) = 1, we have
k-+oo Theorem 5.3 Let Ai, A2,... be a sequence of row allowable matrices. (k)
Suppose that for some positive integer r and for some 'l :; 0, we have
. Pij = 1. k-+oo Sij
lim W
that ø (A(k+1)r . . . Akr+i) ~ 'l2 for all k. Then
Thus, the sequence PI, P2, . .. is ergodic. _
TB (Ak... Ai) :: (1 - 'l) l~J
1 + 'l .
We now give some conditions on matrices Ai, A2,... that assure the Proof. Write
sequence Pi, P2, . .. is ergodic. Basicaly, these conditions assure that (Ø \Ak)) doesn't converge to 0 too fast.
k = rq + s where 0 :: s , r.
Theorem 5.2 Let Ai,A2,... be a sequence ofn x n row allowable matri-
Block Ak'" Ai into lengths r forming
00 ces. If L ý''P (Ak) = 00, then Pi, P2,... is ergodic.
k=l
Ak... Arq+iBqBq-l'" Bi.
1.
78
5,2 Direct Results
5. Ergodicity
Then
79
where A is ni x ni. 1fT is a positive constant, T -: 1, and TB (A) -: T for TB (Ak... Ai) :: TB (Ak... Arq+i) TB (Bq)... TB (Bi)
1+, -:(I-I)q
all matrices M in~, then ~ is an ergodic set. And the rate of convergence
is geometric. Proof. Let Mi, M2,... be matrices in ~ where
1+, ' =(I-I)¡~J
Mk = Bk 0 '
( Ak 0 J
which yields the result. _
and Ak is ni x ni for al k. Then
aij::O i,j
Mk . . . Mi = BkAk-i . . . Ai
A lower bound for " using m = inf aij and M = SUpaij, where the
inf and sup are over all matrices Ai, A2,..., can be found by noting that inf (B)ij ~ mr, sup (B)ij :: nr-i Mr for all r-blocks B = Ark'" Ar(k-i)+1' Thus
( Ak . .. Ai
~J.
Now, let x and Y be positive vectors where
x = ( ~~ J ' Y = ( ~~ J
2
Ø(B) ~ (nr:~r)
partitioned compatibly to M. Then
and so 1 can be taken as
Mk'" Mix = Bk 0 Bk-iAk-2" .Ai
mr
1= nr-iMr'
( Ak 0 J ( Ak-i . . . Ai
FUthermore, types of matrices which produce positive r-blocks, for some r, were given in Chapter 4.
~Jx
= ( ~: J Ak-i.. .AiXA
and
5.2 Direct Results
Mk . .. Miy = ( ~: J Ak-i . .. AiYA.
In this section, we look at matrix sets ~ such that if Ai, A2, . . . is a sequence taken from ~ and x, Y positive vectors, then p (PkX, PkY) -t 0 as k -t 00.
Note that this implies that ii~:~ii and ii~:~ii' as vectors, get closer. So we
wil call such sets ergodic sets. As we wil see, the results in this section apply to very special matrices. However, as we wil point out later, these
Thus,
P (Mk'" Mix, Mk'" Miy)
= p (( ~: J Ak-i . . . AiXA, ( ~: J Ak-i . .. AiYA) and by Lemma 2.1, we continue to get
matrices arise in applications.
A prelinary such result follows. Theorem 5.4 Let ~ be a set of n X n row-allowable matrices M of the form
M=(~ ~J
:: P (Ak-i . . . AiXA, Ak-i .. . AiYA)
:: TB (Ak-i).. 'TB (Ai)p(XA,YA) :: Tk-ip (XA, YA) .
Thus, as k -t 00, P (Mk'" Mix, Mk... Miy) -t O. -
so
5. Ergodicity
5.2 Direct Results
A special set 'Ê of row allowable matrices M = (~ ~ J ' where A is ni x ni, occurring in practice has mni +i,ni )- 0 and C lower trianguar with 0 main diagonal. For example, Leslie matrices have this property. A corollary now follows.
S1
Proof. Let
P(1,k) = Mk" .Mi, P(t,k) = Mk' ..Mt where each Mi E E and 1 ~ t .c k. Partition these matrices as in (5.2),
Corollary 5.2 Suppose for some integer r, 'Êr satisfies the hypothesis of
P (1, k) = P2i (k) P22 (k) ,
( Pii (k) 0 J
the theorem. Then 'Ê is an ergodic set and the convergence rate of products is geometric.
( Pii(t,k) 0 J.
P (t, k) = P2i (t, k) P22 (t, k)
The next result uses that E is a set of n x n row alowable matrices with form
M= (~ ~ J
(5.2)
Note that
Pii (k) = Ak'" Ai k
where A is ni x ni, B is row alowable, and Cis n2 x n2. Let EA be the set of al matrices A which occur as an upper left ni x ni submatrix of some
ME E. Concerning the submatrices A, B, C of any M E E, we assume ah, bh, Ch, ai, bi, Cl, are positive constants such that
P2i (k) = L Ck . . . Cj+iBjAj-i . .. Ai
j=i where Ck . . . Cj+i = I if j = k and Aj-i . . . Ai = I if j = 1,
maxaij ~ ah, maxbij ~ bh, maxcij ~ Ch,
P22 (k) = Ck'" Ci.
min aij ~ at, min bij ~ bt, min Cij ~ ct.
Thus, for k ~ r, Pii (k) )- 0 and since Bk is row allowable, for k )- r,
aij)oO bij)oO Cij)oO The major theorem of this section follows.
Theorem 5.5 Let E be described as above and suppose that TB (EÁ) ~ T .c 1 for some positive integer r. Further, suppose that there exists a constant Ki where Ch
n2Ki .c 1 and - ~ Ki,
at
and that a constant K2 satisfies
Ch bh ah ah -.cK2 -.cK2-.cK2-.cK2. bi - , ai - , bt - , ai -
Let x and Y be positive vectors. Suppose
x: y' i,) Yj i,) Xj
iiB: -- ~ K2 and iiB: -. ~ K2.
P2i (k) )- O. Futher, by rearrangement, for any t, 1 ~ t .c k,
P2i (1, k) = P22 (t + 1, k) P2i (1, t) + P2i (t + 1, k) Pii (1, t) .
Now,. husing P (tt at1*ik) +, = (Pii P2i (t (t ++1,1, k) ,k) partitionig J ... ( xx =AXcJ' Y = ( ~~ J as is M, and applying the triangle inequality, we get
p(P(1,k)x,P(1,k)y) ~ p (P (1, k) x, P *i (t + 1, k) Pii (1, t) XA) + p (P*i (t + 1, k) Pii (1, t) XA, P *i (t + 1, k) Pii (1, t) YA)
+ p (Pd (t + 1, k) Pii (1, t) YA, P (1, k) y) .
We now fid bounds on each of these terms. To keep our notation compact when necessary, we use P = P (t + 1, k) and P = P (1, t).
Then there is a positive constant T, T .c 1, such that
1. p (P (1, k) x, P *i (t + 1, k) Pii (1, t) XA). To bound this term, we need
II
p(PkX,Pky) ~ KTk where K is a constant. Thus E is an ergodic set. (This K depends on x
and y.)
to consider the expressions
¡P (1, k) x Ji ri = lP*i (t + 1, k) Pii (1, t) XAJi'
82
5.2 Direct Results
5. Ergodicity
By defition, it is clear that ri 2: 1 for all i with equalty assured
Thus,
when i ~ ni. So,
maxri = maxri.
ri -1 t
-i 2L.2 ii 2 2i 2 j=i
ITnri
.. Kk-tnk-t "nt-j-inj Kt-j KHi + nk Kk-i K2
Since
t
t'
~ (n2K i)k-t 2 L. n2 iK ni 2 jKj + n2K22 (n2K i K ,,( )t-j )k-i
P (1, k) = P2i (~ll P22 AO JP2i (~llP22 _0 J
( Fii?ii 0 J
= F2i?1i + F22?2i F22?22 '
ri =
(F2i?llXA + F22?2iXA + F22?22XC J i
(F2i?llXA L
= 1 + i
j=i
( )k-t ( )t"j=i(niK2)) 2 k-i 2i
= n2Ki K2 n2Ki L. n K + n2K2 (n2Ki) . For simplicity, set ß = ~~~~. Since niK2 2: 1, n2Ki .. 1,
k (ßt-1) 2 k-i
ri -1 ~ (n2Ki) K'iß ß -1 + n2K2 (n2Ki) ,
(F22?2iXA + F22?22XCJ,
(F2i?llXA L
We wi defie several numbers the importance of which wil be seen
ri - 1 ~ (n2Ki)k K2ß ß~ 1 + n2K~ (n2Ki)k-i . For the fist term of this expression,
later. Set Q = niK2 (n2Ki)! and let f be sufciently large that (n2Ki)k ßt = (n2Ki)k (niK2) n2Ki lf~lJ
Q .. 1 and t = (f~i J. (We assume k :; f + 1.) Then using that
P2i (t + 1, k) Pll (1, t) XA 2: BkAk-i . .. AiXA, we get
ri .. 1 + i
~ (n2Ki)k (niK2) n2Ki T-
¡ Ck . . . Ct+! Cti Ct. . . Cj+!BjAj_i . . . Ai) XA J '
n2Ki f~l = ((n2Ki)f+i (niK2)J
- lBkAk-i . . . AiXAJi
+ lCk . . . CixcJi
= ((n2Ki)f (niK2)J T-
lBkAk-i . . . AiXAJi .
k
~ Qf+1 We now bound this expression by one involvig Ki and K2. Let
= (Q:r)k.
Xl = ITnxi and Xh = maxxi. Then II
Continuing,
2 +n2chxh k-iXi ri ~ 1h )-i +lbiat-ixi biai Ck-t ~ nt-j-in)i' c~-jbha~-ixh k k
ß ( l)k 2 k-i
ri - 1 ~ K2 ß _ 1 QT0 + n2K2 (n2Ki)
83
84
5.3 Research Notes
5. Ergodicity
and thus,
p (P (1, k) X, P*i (t + 1, k) Pii (1, t) XA)
85
and so the theorem can be applied to blocks from~. For blocks we w01ùd use the previous theorem together with the following one.
Theorem 5.6 Let ~ be a row proper matri set and x, Y positive vectors.
:S maxln ri
ß ( i) k 2 k-i
Suppose K, T, with T -: 1, are constants such that
:S K2 ß _ 1 QT+ + n2K2 (n2Ki) . Let Ti = max t Q ¡li , n2Ki ~, so T -: 1. Then by setting K3 = :~~ +
5. d t" Ki an con inwng
p (Bq... Bix, Bq... Biy) :S K'J for all r-blocks Bi,... , Bq from~. Then p(Mk...Mix, Mk...MiY) :SKTi~J
p (P (1, k) X, P*i (t + 1, k) Pii (1, t) XA) :S K3Tt.
for any matrices Mb . .. , Mk in~.
Similarly we can show p (P*i (t + 1, k) Pii (1, t) YA, P (1, k) y) :S K4Tr for some constant K4. 2. p (P*i (t + 1, k) Pii (1, t) XA, P*i (t + 1, k) Pii (1, t) YA)
Proof. Write Mk . . . Mi = Mk . . . Mrq+iBq . . . Bi where the subscripts satisfy k = rq + t, 0 :S t -: r. Then
P (Mk . . . Mix, Mk'" Miy) :S p (Bq . . . Bix, Bq... Biy) :S KTq
:S p (Pii (1, t) XA, Pii (1, t) YA)
=KT¡~J,
:S T~Jp (XA, YA) the desired result. _
t
:S Trp(XA,YA) :S Tr p (XA, YA) ( i) ¡~i
:S (p(f~i))k P(XA,YA)
= K5T2k i
where T2 = Trr and K5 = P (XA, YA).
Putting (1) and (2) together, p (P (l,k) x, P (1, k) y) :S K3Tr + K4Tt' + K5T~
:S KTk
where T = max rTi, T2J and K = K3 + K4 + K5, the desired result. _
ah - n2
The condition S! -: Ki, Ki -: -l, which we need to assure T -: 1, may
seem a bit restrictive; however, in applications we would expect that for large k and Pk = P2i (k) Ok." Oi '
( Ak" .Ai 0 J Ak . . . Ai :: Ok . . . Oi
5.3 Research Notes The results in Section 1 were based on Hajnal (1976), while those in Section 2 were formed from Cohen (1979).
In a related paper, Cohn and Nerman (1990) showed results, such as those in this chapter, by linkng nonnegative matrix products and nonhomogeneous Markov chains. Cohen (1979) discussed how ergodic theorems apply to demographics. And Geraita and Pullan (1984) provided numerous examples of demographic problems in the study of biology.
1'-
¡i
~
t:
Õ'
00
p:
00
~ CD
P"
CD
0'
s
Gl
tj
e: 00
c-
(" cS"
¡:
.. 0 p.
"d
~ ..
-~ '-..
C' = ., ~ I~
l~
HS
II
0;
to
.,
CD.SOCD
io:i i-
~ tj
0
S 00
0 ..
tj
0 ..
c-
("
S'
~
tj
(" p:
~
~
~.
c-
("
CD
"d
00
..CD
'"
"i;:
Q" § p.
00
¡:
to "i
CD 00
("
t-;: S p: c::t
x
CD
.. ~
~
.. ~ ~ .. tj
~
:a 9-
~ ël
p: "d
00 cCD
s. .. CD .
$ ~
00 :a ~ g.. tj
..CD
p:
00
~ :a ~ CD
tj
tj 0
i-. ...
0' CD c(" p: c-
o 00
c53 00 e:
Q"
~ ~ CD
0 ê" ("
("
CJ to
ii
~.
gei g' ... ;: CD 00 00
c- C' .. _CD
Õ' .. S
¡s
p.
~. cõ'
ei
CD
en
C"
~
...
~ I-
~
P-
CD
~ C"
P-
g;
I-
OJ
"d
P"
~
P"
c-
~
..~
tj~ ~ei
sp.~P"$ 0= s ¡:
S
;:
x
;:
~ tj
6 p: ei ¡: ... .. tj ... (" 00
p:., S';::i
g. 'Q¡::a ~~CDg.g~ 00 ..
P" Ë. ...
o c- p. I
tj 0
00 ..
"d "d
p: CD
iP" .. ~
0' ¡: tj0
¡SOË. ~P:&r
.. ~ fJ
g- P" ..
p: CD tj c- :a 16
CD 0 Q" .. S CD
ei 00 g¡
g¡CD~
p: c- (" "d c- 00 ei ("0
(" 00 ~
e: CD CD 00' ti 0'
c- 00 S
S' ;. CD 00 0
CD .. 00 s CD 0 p; Ë. 0 p: ~ i- i:
g¡ (f ~
;. ¡i :i
CDCD .. o ("
. q..."d c-
p: p:
~S~
tj .. 00
p; 0 i:
~ ~~ t: &r c-
CD
(J
~~
l-
CD
~
Q 0
OJ
88
6. Convergence
6,1 Reduced Matrices
Lemma 6.1 Let B be an ni x n2 matri.
"'1
Thus, IIDijllb =
1. If A is an ni x ni matri, then
IILjHllaIlBjllbl¡Cj-i" 'Cille+' .+IILilla IIBi-i!lb IICi-2... Cille ::Kiß'lj-i +... + Kiß'li-2.
IIABllb :: IIAlIa IIBllb .
From this it is clear that the sequence is Cauchy, and thus converges. _
2. If C is an n2 x n2 matrix, then
The theorem about convergence of infiite products of reduced matrices
IIBCllb :: IIBllb IIClle'
follows.
Proof. We wil show the proof of (2). For it, note that IIBxlia :: liB
89
Theorem 6.1 Suppose each n x n matri in the sequence (Mk) has the form
lib llxlle
¡ Aik) Bi~) Bi~) . . .
for al n2 x i vectors x. Thus,
Mk_ -0 dk) B(k) . i 23" o 0
IIBCxlla :: IIBllb IICxlle :: IIBllb IIClle Ilxlle.
Thus, lJ "
IIBCllb :: IIBllb IIClle'
which is what we need. _
B(k) ir J B(k) 2r
dk)
where the Aik) 's are ni x ni, cik) 's are n2 x n2, . . ., and the C$k) 's are nr+i x nr+i. We suppose there are vector norms 1I,lla on Fni and 1I,llei on Fni+i such that 1. IlcIk) Ilei :: 'l for some constant'l -( i and all i, k.
Using this lemma, we wil show the convergence of a special infte series
which we need later.
2. As given in (6.1), there is a positive constant K3, such that
Lemma 6.2 In the infinite series L2Bi + L3B2Ci +... + LkBk-iCk-2'" Ci +...
IIB¡:) IIbii :: K3
the matrices L2, L3,... are ni x ni, the matrices Bi, B2v" are ni x n2,
for all i, j, and k.
and the matrices Ci, C2, . .. are n2 x n2. The series converges if, for all k,
Finally, we suppose that for all s, the sequence (Ak .. . As) converges to
1. IILklla:: Ki for some vector norm 11'lla and constant Ki,
a matri Ls and that
2. IICklle:: 'l for some vector norm 11.lle and constant 'l, 'l -( i, and
3. IILslla :: K2 for all s and ilLs - Ak.. .Aslla :: Kiak-sH for some constants K i and a -( 1.
3. IIBkllb:: ß for some cónstant ß.
Then the sequence (Mk . . . Mi) converges.
Proof. We show that the series, given in the theorem, converges by showing the sequence (L2Bi + . . . + LkBk-i Ck-2 . . . Ci) is Cauchy. To see this, observe that if i :; j, the difference between the i-th and j-th terms of the
Proof. We prove this result for r = 1. The general case is argued using Corollary 3.3. We use the notation
sequence is
Mk = 0 Ck .
Dij = Lj+iBjCj-i'" Ci +... + LiBi-iCi-2'" Ci.
( Ak Bk J
1
90
6.2 Convergence to 0
6, Convergence
Then Mk . . . Mi =
91
Proof. Note that
o Ck . .. Ci .
o Ck . .. Ci .
AaB2Ci +.. .+BkCk-i" ,Ci J
Mk . .. Mi = (I Bi + B2Ci + . . . + BkCk-i . . . Ci J
( Ak" .Ai Ak" .A2Bi +Ak" .
By hypotheses, the sequence (Ak'" As) converges to Ls, and the sequence
By (2) of the theorem, liCk'" Cill :: 'Y¡~J and by (1) of the theorem,
(Ck'" Ci) converges to O. We fish by showing that the sequence with
k-th term
IIBk+iCk'" Ci + Bk+2Ck+1'" Ci +.. 'Ilb Ak . . . A2Bi + Ak . . . AaB2Ci + . . . + BkCk-i . . . Ci (6.2)
:: rß'Y¡~l + rß'Y¡~J+i +...
-(-. rß'Y¡~J
converges to
- 1-1'
L2Bi + LaB2Ci + . . . + Lk+iBkCk-i . . . Ci + . .. .
(6.3)
Thus, (Mk'" Mi) converges to
Now letting Dk denote the difference between (6.3) and (6.2), and using Lemma 6.1, IIDkllbi2 = (~ Bi + B2Ci + oBaC2Ci + . .. J
II (L2 - Ak'" A2) Bi + (La - Ak'" Aa) B2Ci + ... + (Lk+1 - I) BkCk-i'" Ci + Lk+2Bk+1Ck'" Ci +.. '11bi2
:: (Kici-i Ka + Kiak-2 K3' +... + KiK3'k-i) + K2Ka'Yk + . . . + K2K3'k+1 + . . .
( ßk-i k-i) k 1
:: KiKa + . . . + KiKaß + K2Kaß 1 - ß where ß = maxfa,'Y1. 80
IIDkllbi2 :: kKiKaßk-i + K2Kaßk 1 ~ ß :: Kkßk-i
and at a geometric rate. _
A special case of the theorem follows by applying (6.3).
Corollary 6.2 Assume the hypothesis of the theorem and that each Ls = O. Then the sequence (Mk) converges to O.
6.2 Convergence to 0
where K = KiKa + K2Kai:ß' Thus, as k -+ 00, Dk -+ 0 and so the
There are not many theorems on infte products of matrices that converge to O. In the last section, we saw one such result, namely Corollary 6.2. In the next section, we wil see a few others. In this section, we show three
sequence from (6.2) converges to the sum in (6.3). _
direct results about convergence to O.
The fist result concerns nonnegative matrices and uses the measure U of fu indecomposabilty as described in Chapter 2. In addition, we use
Corollary 6.1 Let Mk =( ~ ~: J be an n x n matri with I the m x m identity matri. Suppose for some norm 1I'llb' as defined in (6.1), and constants ß and 1', l' -( 1, and a positive integer r
that n
ri (A) = L aik, k=i
~. IIBkllb:: ß 2. IICklle:: 1 and IICk+r'" Ck+ille :: l' for all k. Then (Mk . . . Mi) converges at a geometrical rate.
the i-th row sum of an n x n nonnegative matrix A.
Theorem 6.2 Suppose that each matrix in the sequence (Ak) of n x n nonnegative matrices satisfies the following properties:
92
6,2 Convergence to 0
6. Convergence
93
Thus, since
1. mtlri (Ak) :: r. ,
2. U (Ak) 2: u :; O.
iin B'II, ~ Iin (B,.B,.-it
3. There is a number 8 such that i:, ri (Ak) :: 8.
m
:: IT II(B2sB2s-i)lli
s=i :: im
4. (rn-i - un-i) rr-i + un-i (8rn-2) = L 0: 1.
00
Then I1 Ak = O.
00
k=l
it follows that I1 Ak converges to O. . k=i
Proof. We fist make a few observations.
This corollary is especially usefu for substochastic matrices since in this case, we can take r = 1 and simplify (4).
Using properties of the measure of full indecomposabilty, Corollary 2.5,
iffors=I,2,...
The next result uses norms together with infte series. To see this
(s+l)(n-i)
result, for any matrix norm 11.11, we let
Bs = IT Ak k=s(n-i)+i
IIAII+ = maxillAII, Il and
then the smalest entry in B s,
IIAII_ = minillAII, Il.
And, we state two conditions that an infte sequence (Ak) of n x n matrices
i,j '3 - .
minb~~) :; un-i
And,
might have. 00 1. L (1IAkll+ - 1) converges.
, ,
k=i
mtl ri (Bs) :: rn-1, mln ri (Bs) :: 8rn-2.
00
2. L (1 - IIAkii) diverges.
k=l
Then,
We now need a preliminary lemma.
n n ri (Bs+1Bs) = LLb~~+1)b~1
Lemma 6.3 Let Ai,A2,... be a sequence ofn x n matrices and 11.11 a ma-
j=i k=i
tri norm. If this sequence satisfies (1) and Aii, Ai2, . .. is any rearrange~
n
,,(s+1) ( ) = L.bik rk Bs
ment of it, then IIAiill+ ' IIAi211+ IIAiill+ ,. .. and IIAiil1 , IIAi2Aiill , . .. are bounded.
k=i ,n
Proof. First note that
:: L b~~+1)rk (Bs) + b~~~i) (8rn-2)
k=i
k'lko
IIAik . . . Aiill :: IIAik 11+ . . .IIAii 11+
whe:e we assume rko (Bs) ii: the smalest row sum. So
for al k. Now, using that 00
ri (Bs+1Bs) :: (rn-1 - un-i) rn-i + un-i (8rn-2)
L (1IAikll+ - 1)
= L 0: 1.
k=l
l
94
6, Convergence
6.2 Convergence to 0
converges, by Hyslop's Theorem 51 (See the Appendi.),
95
Hence, all infte products from ~ converge to O.
Conversely, suppose that all infte products taken from ~ converge to
00
O. Then by the norm-convergent result, Corollary 3.4, there is a norm 1\.11 IT IIAik 11+
such that
k=l
converges. But this implies that IIAi 11+ ' IIAi211+ IIAii 11+ ,. .. is bounded. _
The following theorem says that if (IIAkll+) converges to 1 fast enough
(condition 1) and (1IAkIL) doesn't approach 1 or, if it does, it does so 00 slowly (condition 2), then I1 Aik = O. k=i
IIAil1 :: 1
for al Ai E~. We will prove that P (~) .. 1 by contradiction. Suppose P (~) ~ 1. Then P (~) = 1. Since Pk is decreasing here, there exists a sequence Ci, C2,... where Ck is a k-block taken from~, such that IICklI ~ 1 for all k. Thus, IICklI = 1 for al k. We use these Ck'S to form an infte product which does not converge to O.
Theorem 6.3 Let Ai, A2,... be a sequence of n x n matrices and 11.11 a matri norm. If the sequence satisfies (1) and (2) and Aii, Ai2, . ,. is any
To do this, it is helpful to write
Oi =
00 rearrangement of the sequence, then we have I1 Aik = O.
Au
C2 =
k=i
C3=
Proof. Using that IIAij II = IIAij 11_IIAij 11+
A33
A2i A3i
A22 A32
(6.4)
,. .
Ck = Ak4 Ak3
Aki
Ak2
IIAik . . . Aii II :: IIAik 11- . . 'IJAii 11- M,
where M is a bound on the sequence (1lAik 11+ . . .IIAii 11+). Since (2) is 00
satisfied, by Hyslop's Theorem 52 (given in the Appendi), I1 IIAik 11k=l
converges to 0 or does not converge to any number. Since the sequence
where the Ai,j's are taken from~. Now we know that ~ is product subsequence Ali,i, AI2,i,." that converges to, say Bi and IIBil1 = 1. Thus, there is a constant L such that if k ~ L, bounded, and so the sequence Ai,i, A2,i,.., has a
IIAii 11- , IIAi211_IIAi 11- ,'" is decreasing, it must converge. Thus, this sequence converges to 0, and so
1
IIAlk,i - BiI .. S'
Aii, Ai2 Aii , , . . Set 8i (1) = IL, 8i (2) = IL+1,'" so IIAsi(k),i - Bill .. l for al k. Now,
consider the subsequence Asi(i),2, Asi(2),2,.... As before, we can fid a
converge to O. _
subsequence of this sequence, say AS2(i),2, AS2(2),2,.. . , which converge to The fial result involves the generalzed spectral radius P discussed in
B2 and
Chapter 2. IIAs2(k),2 - B211 :: 116 for al k.
Theorem 6.4 Let ~ be a compact matri set. Then every infinite produCt,
taken from ~, converges to 0 iff P (~) .. 1.
Continuing, we have
Proof. IT P (~) .. 1, then by the characterization of P (~), Theorem 2.19, the~e is a norm 11.11 such that II
All :: "ý,"ý .. 1, for al AE ~. Thus for a
product Aik . . . Aii, from ~, we have
1 IIAsj(k),j - Bjll :: 21+2
for all k. Using (6.4), a schematic showing how the sequences are chosen IIAik . . . Aii II :: "ýk -+ 0 as k -+ 00.
is given in Figure 6.1. We now construct the desired product by using
96
6,2 Convergence to 0
6. Convergence
97
~.
.
/" /. . . .
IIB311=1
,i'
.
.
.
.
.
IIBill=l
IIBill=l
FIGURE 6,2, Diagonal product view,
I,
3. Using a collapsing sum expression,
FIGURE 6,1. A diagram of the sequences,
7ri - ASi(i),iAsi(i),i-i . . . ASi(i),i =
7ri = Ami, 7r2 = Am2Ami, . .. where
Ami' .. Am2 (Ami - ASi(i),i) +
Ami = Asi(i),i
Ami' . . Ams (Am2 - ASi(i),) ASi(i),i + . . . +
Am2 = AS2(i),2
(Ami - ASi(i),i) ASi(i),i-i . . . ASi(i),i
and taking the norm of both sides, we have from (1),
Amk = Ask(i),k
II7ri - ASi(i),iAsi(i),i-i . . . ASi(i),ill
which can be caled a diagonal process. We now make three important observations. Let i :; 1 be given.
22+ 23 -: (~ ~ + .. . ) 1
1. If j :: i,
2' 1
IIAmj - ASi(i),j II = IIAsj(i),j - ASi(i),j II :: 2jH'
Putting together, by (2), IIAsi(i),iAsi(i),i-i." ASi(i),ill ~ 1 and by (3), II7ri - ASi(i),iAsi(i),i-i '" ASi(i),ill :: l. Thus l17rill ~ l for al i, which pro-
(Note here that Si (k) is a subsequence of Sj (k).)
vides an infte product from I; that does not converge to O. (See Figue
2. Using (6.4),
6.2.) This is a contradiction. So we have p (I;) -: 1. .
1 = IICSi(i) II
Concerning convergence rate, we have the following.
li
= IIAsi(i),Si(i) . . . ASi(i),ill
:: IIAsi(i),Si(i) .. . ASi(i),i+iIIIIAsi(i),i' .. Asi(i),ill
Corollary 6.3 If I; is a compact matri set and p (I;) -: 1, then all sei
:: IIAsi(i),i'" ASi(i),ill.
L
quences Aii, Ai2Aii, AisAi2Aii,' .. converge uniformly to O. And this convergence is at a geometric rate.
r
98
6.3 Results on II (Uk + Ak)
6. Convergence
Proof. By the characterization of p, Theorem 2.19, there is a matrix norm "' oe 1. Thus
11.11 such that IIAkll :: "' where "' is a constant and
99
We show that the sequence Pi,P2,... is Cauchy. For this, note that if t ). s, then
IIAilo . . . Aii - 011 = IIAilo . . . Aii II
11Ft - Psil = II L Api + L ApiAp2 +... + At. ..Ai
:: IlAïIo II. . .IIAii II
Pi;:S Pipi:;P2 :;s
:: "'k.
Thus, any sequence Aii, Ai2 Aii , . .. converges to 0 at a geometric rate.
:: L IIApiI + L IIApiIIIAp211 + .. . + IIAtll.. .¡IAill Pi;:s
And, since this rate is independent of the sequence chosen, the convergence
Pl ~B
pi:;P2
is unorm. .
:: IIAs+ill 1 + f;IIAill + - 2! +...
Putting together two previous theorems, we obtai the following norm-
convergence to 0 result.
( t C~IIAili)2)
Corollary 6.4 Let E be a compact matri set. Then every infinite product, taken
from E, converges to 0 iff
there is a norm 11.11 such that IIAII :: ",,,, oe
1, for all A E E.
+IIAs+211 1+f;IIAill+ - 2! +... +... Proof. If every infte product taken from E converge to 0, then by the
theorem, ß(E) oe 1. Thus by Theorem 2.19, there is a norm 11.11 such that IIAII :: "', "'oe 1, for al A E E. The converse is obvious. .
( t C~ IIAill) 2 )
t t
and using the power series expanion of eX, E IIAill E II
Ai II
:: IIAs+111 ei=l + IIAs+211 ei=i +...
00 f IIAill
6.3 Results on II (Uk + Ak)
:: L IIAkl1 ei=l .
k=s+i
In this section, we look at convergence results for products of matrices
of the form Uk + Ak. In this work, we wi use that if a¡, a2 . .. , ak are
00
Now, given E :; 0, since L IIAkll converges, there is an N such that if k=i
nonnegative numbers, then
(1 + ai) . . . (1 + ak) :: eai +..+alo.
(6.5) Wedderburn (1964) provides a result, given below, where each Uk = 1.
s :;N,
00 =
Ai II
L. k e,=i oe E.
" IIA II ¡: II Theorem
6.5 LetAi,A2,... be
a
sequence
00 _
ofnxn
00 matrices. IfL IIAkl1
k=i
k=s+ i
Thus, Pi, P2, . .. is Cauchy and hence converges. .
converges, then I1111 + Akll converges.
k=i
Whle Wedderburn's result dealt with products of the form 1+ Ak, Ostrowski (1973) considers products using U + Ak.
Proof. Let li
Pk = (I + Ak) , . . (1 + Ai)
= 1 + L Api + L Api AP2 + . . . + Ak . . . Ai. Pi;:P2
Theorem 6.6 Let U + A¡, U + A2, . .. be a sequence of n x n matrices. Given E :; 0, there is a Ó such that if IIAklI oe ó for all k, then 11(U + Ak)'" (U + Ai)11 :: a (p + E)k
~
100
6. Convergence
6,3 Results on II (Uk + Ak)
for some constant a and p = p (U).
101
Proof. Observe that by (6.5),
Proof. Using the upper triangular Jordan form, factor
II (Ur + Ar) . . . (Ui + Ai) - Ur . . . Uili
U = PKP-i
:: L IIAil1 + L IIAilllIAjll +... + IIArll.. .IIAill
i i:;j
where K is the Jordan form with a super diagonal of O's and ~ 's. Thus,
f IIAkll
= (1 + IIArll)... (1 + IIAill) - 1:: ek=l - 1
IIKlli :: p + ~. Write (U + Ak) . . . (U + Ai)
the required inequality. .
= (PKP-i +Ak)'" (PKP-I +Ai)
= P (K + p-l AkP)", (K + p-l AiP) P-i.
As a consequence, we have the following. 00
Let Ó = n"~" ~~_'" so that
Corollary 6.5 Suppose IIUklI :: 1 for k = 1,2,... and that L IIAkl1 -( 00. k=l
Given € ? 0, there is a constant N such that if r ~ Nand t ? r, then IIp-i AkPIli :: IIp-illillPlllllAklli :: IIp-illlllPllió = ~ .
Then,
II(Ut + Ad... (Ur + Ar) - Ut... Uril -( €. From these results, we might expect the following one.
11(U + Ak)'" (U + Ai)lIi :: 1lPllillp-illi ((p + ~) + ~ r
= IIPllillp-illl (p+€)k.
Theorem 6.8 Suppose IIUklI :: 1 for all k. Then the following are equivalent.
00 00 k=i k=i 00
1. I1 Uk converges for all r. k=r
Setting a = IIPlli IIp-Illi' and noting that norII are equivalent, yields the
2. I1 (Uk + Ak) converges for all sequences (Ak) when L IIAkl1 -( 00.
theorem. .
This theorem assures that if p (U) -( 1 and €
IIAklll:: 211PIiillp-ilil'
Suppose (1), that I1 Uk converges for al r and L IIAkl1 -( 00. Define,
for t ? r,
00
where p + € -( 1, then I1 (U + Ak) = O. So, slight perturbations of the
Pt = (Ut + At) . . . (Ui + Ai)
k=l entries of U, indicated by A¡, A2,..., wil not change convergence to 0 of
the inte product.
00 00 k=r k=i
Proof. That (2) implies (1) follows by using Ai = -Ui + I, then A2 = -U2 + I,. .. , Ar-i = -Ur-i + I and Ar = .. . = O.
00 00 k=i k=i .
We now consider inte products I1 (Uk + Ak) and I1 Uk. How far these products can dier is shown below.
Th~orem 6.7 Suppose IIUklI :: 1 for k = 1,... , r. Then
Pt,r = Ut." Ur+i (Ur + Ar)... (Ui + Ai). We show Pt converges by showing the sequence is Cauchy. For this, let € ? 0 be given.
Using the triangular inequalty, for s, t ? r,
IlPt - PslI :: IIPt - Pt,rli + IIPt,r - Ps,rll + IIPs,r - PslI' (6.6) We now bound each of the three terms. We use (6.5) to observe that
f IIAkll
II(Ur + Ar)... (Ui + Ai) - Ur... UilL :: ek=l - 1.
f IIAkll
IlPrlI :: ß, where ß = ek=l .
102
6, Convergence
6.4 Joint Eigenspaces
€ €
1. Using the previous corollary, there is an Ni such that if r = Ni, then
103
Since I1 Uk = 0, there is an N2 such that for t :; N2 :; r, k;:r+i
11Ft - Pt,rll .: 3 and IIPs,r - PslI .: 3'
€
IlUt'" Ur+i (Ur + Ar)... (Ui + Ai) - 011 .: 2'
2. lIPtr - Ps,rll :: IIUt... UrH - Us'" UrHIIII(Ur + Ar)... (Ui + Ai)lI. 00
Since I1 Uk converges, there is an N2, N2 :; r, such that if s, t :; k=r+i
Thus, by the trianguar inequality,
II(Ut + At) . . . (Ui + Ai) - 011 ::
II(Ut + At)'" (Ui + Ai) - Ut... Ur+i (Ur + Ar)... (Ui + Ai)1I
€ €
N2, then
+ IlUt'" Ur+i(Ur + Ar)... (Ui + Ai) - 011 :: 2 + 2 = € .
€
IlFt,r - Ps,rll :: 3'
00
Hence, I1 (Uk + Ak) = O. .
Putting (1) and (2) together in (6.6) yields that
k=i
IIPt - PslI,: € for al t, s 2: N2. Thus, Pt is Cauchy and the theorem is established. . From Theorems 6.7 and 6.8, we have something of a continuity result 00 for infte products of matrices. To see this, defie II (Ak) II = L IIAk Ii k=i
00 for (Ak) such that II(Ak)/1 .: 00. If I1 Uk converges for all r, so does
k=r
00
I1 (Uk + Ak) and given € :; 0, there is a 8 :; 0 such that if II (Ak) II .: 8, k=i
then
6.4 Joint Eigenspaces
In this section we consider a set L of n x n matrices for which al left 00 infte products, say, I1 Ak, converge. Such sets L are said to have the
k=i
left convergence property (LCP). The eigenvaue properties of products taken from an LCP-set follows.
Lemma 6.4 Let L be an LCP-set. If Ai, . . . , As E L and), is an eigenvalue of B = As . . . Ai, then 1. 1).1 .: 1 or
lñ Uk - ñ (Ud Ak)ll" , Another corollary follows.
00 00 00 k=i k=r k=i
Corollary 6.6 Let IIUklI :: 1 for k = 1,2,... and let (Ak) be such that L IIAkll .: 00. If I1 Uk = 0 for all r, then I1 (Uk + Ak) = O.
00
Proof. Theorem 6.8 assures us that I1 (Uk + Ak) converges. Thus, using k=i
torollary 6.5, given € :; 0, there is an Ni such that for r :; Ni and any t:; r,
€ IIUt... UrH (Ur+Ar)... (Ui +Ai)-(Ut+At)... (Ui +Ai)II.: 2'
2. ). = 1 and this eigenvalue is simple.
Proof. Note that since L is an LCP-set, lim Bk exists. Thus if), is an k-+oo
eigenvalue of B, 1).1 :: 1 and if 1).1 = 1, then). = 1. Finaly, that). = 1
must be simple (on 1 x 1 Jordan blocks) is a consequence of the Jordan form of B. .
For an eigenvector result, we need the following notation: Let A be an n x n matrix. The 1-eigenspace of A is
E (A) = r x : Ax = xl. Using this notion, we have the following.
~
104
6,5 Research Notes
6. Convergence 00
Theorem 6.9 Let B = 11 Ai be taken from an LCP-set L. If A E L k=i
In the next theorem we use the defition
E (L) = nE (Ai)
00
occurs infinitely often in the product 11 Ai, then every column of B is in k=i
E(A).
105
where the intersection is over al Ai E L. 00
Proof. Since A occurs innitely often in the product 11 Ak, there is a
Theorem 6.10 Let L be an LCP-set. If E (Ai) = E (L) for all Ai E L, then there is a nonsingular matri P such that for all A E L,
k=i
subsequence of Ai, A2Ai, . .. with leftmost factor A, say,
p-i AP = (~ ~ J
ABi, AB2, . . .'
where the Bj's are products of Ak'S. Since Ai, A2Ai, . .. converges to B,
where I is s x sand p (C) .: 1. Proof. Let Pi,... ,Ps be a basis for E (L). If A E L, Lemma 6.4 assures
so does ABi, AB2,... and Bi, B2,.... Thus,
that A has precisely s eigenvalues .x, where .x = 1, and all other eigenvaues
.x satisfy i.xi .: 1. Extend Pi,... ,Ps to Pi,... ,Pn, a basis for Fn, and set
AB = li ABk k-+oo
P = ¡Pi,... ,PnJ. Then,
= lim Bk k-+oo
=B.
AP = P (~ ~ J
Hence, the colums of B are in E (A). .
for some matrices B and C. Thus, 00
p-i AP = (~ ~ J .
As a consequence of this theorem, we see that for B = 11 Ak k=l
Finally, since p (A) :: 1, P (C) :: 1. If p (C) = 1, then A has s + 1 eigen-
columns of B ç nE (Ai)
vaues equal to 1, a contradiction. Thus, we have p (C) .: 1. . where the intersection is over all matrices Ai that occur inftely often in 00
11 Ak. Thus, we have the following.
k=i
It is easily seen that L is an LCP-set if and only if
Lp = r B : B = p-i AP where A E L)
00
Corollary 6.7 If 11 Ak is convergent and nE (Ai) = tOl, where the in-
k=l 00
tersection is over all E (Aï) where Ai occurs infinitely often, then 11 Ak = k=i
O.
is an LCP-set. Thus to obtain conditions that assure L is an LCP-set, we need only obtain such conditions on Lp. In case L satisfies the hypothesis, Corollary 6.1 can be of help.
00
The sets E (B), B = 11 Ak, and E (Ai)'s are also related.
6.5 Research Notes
~ 00
k=i
Corollary 6.8 If B = n Ak is convergent, then E (B) ç nE (Ai) where
k=i 00 the intersection is over all Ai that occur in 11 Ak infinitely often. k=l
"-
In Section 2, Theorem 6.2 is due to Hartfiel (1974), Theorem 6.3 due to Neumann and Schneider (1999), and Theorem 6.4 due to Daubechies and Lagarias (1992). Also see Daubechies and Lagarias (2001) to get a view of the impact of this paper.
106 6. Convergence
The results given in Section 3 are those of Wedderbur (1964) and Os-
7
trowski (1973), as indicated there. Section 4 contai results given in
Daubechies and Lagarias (1992).
In related work, 'fench (1985 & 1999) provided results on when an in-
Continuous Convergence
00 nite product, say Il Ak, is invertible. Holtz (2000) gave conditions for an
k=l infte right product, of the product form il (~ ~k J, to converge.
k=l k
Stanford and Urbano (1994) discussed matrix sets E, such that for a given 00
vector x, matrices Ai, A2... can be chosen from E that assure Il Akx = O. k=i
00 Artzroun (1986a) considered fu (A) = Il (Uk + Ak), where he defined
k=l U = (Ui, U2,"') and A = (Ai, A2,...). He gave conditions that assure
the fuctions form an equicontinuous fany. He then applied this to perturbation in matrix products.
In this chapter we look at LCP-sets in which the initial products essentially determie the infte product; that is, whatever matrices are used,
beyond some initial product, has little effect on the infte product. This continuous convergence is a type of convergence seen in the construction of
cures and fractals as we wil see in Chapter 11.
7. i Sequence Spaces and Convergence Let E = rAo,.., ,Am-i1, an LCP-set. The associated sequence space is
D=rd:d=(di,d2,...n where each di E rO,... ,m - 11. On D, defie
a (d,d)
= m-k
where k is the fist index such that dk =f dk. (So d and dk agree on the
\
fist k - 1 entries.) This a is a metric on D.
Given d = (di, d2,...), defie the sequence
Adi , Ad2 Adi , Ada Ad2 Adi , . .. .
i
1
108
7. Continuous Convergence
7,1 Sequence Spaces and Convergence 109
the p-adic expansion of x. Recall that if a -c j -c m, then
~x 0
dim-i +... + dsm-s + jm-S-i
\f
~
/..(1)
+ am-s-2 + am-s-3 +...
( , J1)- m-s-i = dim-i+d. .-s. ++sm
\f(O)
+ (m - 1) m-s-2 + (m - 1) m-s-3 + . . .
1
R
M.
give the same x E ¡a,lj. Thus, to define
\l: ¡a,lj -7 Mn FIGURE 7,1. A view of iJ.
by \l (x) = 'P (d), we would need that Since ~ is an LCP-set, this sequence converges, Le.
'P(di,... ,ds,j,a,...) ='P(di,... ,ds,j-l,m-l,...). 00
When this occurs, we say that the continuous LCP-set ~ is real definable. A theorem that describes when ~ is real defiable follows.
II Adi = A
i=i
Theorem 7.1 A continuous LCP-set ~ = rAo,... , Am-il is real defin-
for some matrix A. Defie 'P : D -7 Mn by
able iff AO' Aj = A~_iAj-i
'P(d)=A.
for j = 1,... m - 1. Proof. If Aõ Aj = A~_iAj-i, then
If this function is continuous using the metric a on D and any norm on Mn, we say that ~ is a continuous LCP-set.
Continuity of 'P can also be described as follows: 'P is continuous at
'P(di,... ,ds,j,a,...) ='P(di,... ,ds,j-l,m-l,m-L...)
d E D if given any E ). a there is an integer K such that if k ). K,
for any s 2' 1 and al di, . .. , ds' Thus, ~ is real defiable. Now suppose ~ is real defiable. Then
then II'P (d) - 'P (d) II -c E for al d that dier from d after the k-th digit.
(The infite product will not change much regardless of the choices of
Ad" k+ ,Ad" 1 k+2 ,....)
'P (j, a, a,...) = 'P (j - 1, m - 1, m - 1...)
Not all LCP-sets are continuous. For example, if
for al j 2' 1. Thus, AO' Aj = A~_i Aj_i,
~ = fl, P), P = (t t J
as given in the theorem. .
then 'P is not continuous at (a, a, . . . ). Now we use 'P to defie a fuction \l : ¡a, Ij -7 Mn. (See Figure 7.1.) As
An example may help.
we wil see in Chapter 11, such functions can be used to describe special
Example 7.1 Let
cures in R2.
If x E ¡a, 1 J, we can writ~
1 a Ao~ ¡ .5 .5
x = dim-i +d2m-2 +...
.25 .5
L
a J ¡ .25
a , Ai = a
.25 a
.5 .25 J
.5 .5
a 1
110
7.2 Canonical Forms
7. Continuous Convergence
and ~ = fAo,Ail. In Chapter 11 we will show that ~ is a continuous
111
Hence
LCP-set. For now, note that li A~ Aky = A?Oy
¡IOOl ¡OOll AO' = 1 0 0 , Al = 0 0 1 .
1 0 0 0 0 1
k-.oo J i i or
Ajy = y.
Since By considering the Jordan form of Aj, we see that Ajy = y also. Hence, AO'Ai =
AlAo,
m-i
y E E (Aj) from which it follows that E (~) = n E (Ai) as required. . i=O
~ is real definable.
The canonical form follows. Theorem 7.2 Let ~ = fAo".. , Am-il. Then ~ is a continuous LCP-set
iff there is a matri P such that
7.2 Canonical Forms In this section we provide a canonical form for a continuous LCP-set ~ =
p-i'EP - f (I Bi 1 . (I Bi J - p-1 A-P L
- iOCi J' 0 Ci - i f
fAo,... , Am-il. We again use the defition m-l E(~) = n E(Ai) i=O
where E (Ai) is the I-eigenspace of Ai, for al i. We need a lemma.
where p (~e) 0( 1, 'Ee = fCo,... , Cm-1l.
Proof. Suppose ~ is a continuous LCP-set. Let P = (Pi.. 'PsPsH" ,PnJ, a nonsingular matrix where Pi,... ,Ps are inE(~) and dimE(~) = s. Then for any Ai E ~,
Lemma 7.1 If ~ is a continuous LCP-set, then E (~) = E (Ai) for all i.
AiP = P 0 Ci ( I Bi J
Proof. Since E (~) ç E (Ai) for all i, it is clear that we only need to show
that E (Ai) ç E (~), for al i. For this, let y E E (Ai)' Then y = Aiy. For any j, defie d(k) -- (i,... , i,j,j,...)
where i occurs k times. Then
d(k) -- i, i,(" . . .)ask-- 00.
Now, since 'E is a continuous LCP-set, so is ~e' Thus for any infte 00 product I1 Ck from 'Ee, by Theorem 6.9, its nonzero columns must be
k=i eigenvectors, belonging to 1, of every Ci that occurs inftely often in the
product. Since 1 is not an eigenvalue of any Ci, Lemma 7.1, the colums 00 of I1 Ck must be O. Thus, by Theorem 6.4, P (~e) 0( 1. k=l
Conversely, suppose p-i'EP is as described in the theorem with P (~e) 0( 1. Since p (~e) 0( 1 by the defition of P (~e)' there is a positive integer r
Since ~ is continuous ~
for some Bi and Ci where I is the s x s identity matrix.
cp ( d(k)) -- cp (( i, i, . .. )) as k -- 00,
so
and a positive constant ì 0( 1 such that 117f1l1 :: ì for all r-blocks 7f from ~e' Now by Corollary 6.1, p-l~p is an LCP-set, and thus so is~. Hence,
by Theorem 3.14, ~ is a product bounded set. We let ß denote such a
Aj Af -- Ai as k -- 00.
bound.
112
7. Continuous Convergence
7.2 Canonical Forms
Let d = (di, d2, . . .) be a sequence in D and E )- O. Let N be a positive number such that
113
I the s x s identity matri and s = dim E (L). Also, we have the following.
2ß IIPllillp-illi "IN -: E.
Corollary 7.2 If L = tAo,... , Am-il is a continuous LCP-set, then in-
Let d = (di, d2,.,,) be a sequence such that 8 (d, d) -: m-rN. Then
finite products from E converge uniformly and at a geometric rate. Proof. Note that in the proof of the theorem, ß and "I do not depend on
Ilcp(di,d2,...) - cP (di,d2,...) Ili
the inte products considered. .
:: II II Adk - II AJk II Adk
k=rN+irN k=i lIi (k=rN+i 00 00)
=11(p( ~ ~i Jp-i_p( ~ ~2 Jp-i)p( ~ ~3 Jp-illi where
8iJp-i IIoo AA=p(I82Jp-i
00
II Adk = P ( I k=rN+i 0
o 'k=rN+i dk 0 0
As a fial corollary, we show when the function \I, introduced in Section
1, is continuous. Corollary 7.3 Let L = tAo,... , Am-il be a continuous LCP-set and
suppose L is real definable. Then \I is continuous.
Proof. We wil only prove that \I is right side continuous at x, x E ¡0,1). Left side continuous is handled in the same way. Write
rN and II Adk = P ( I
x = dim-i + d2m-2 + . .. .
~3 J p-i.
k=i 0
We wil assume that this expansion does not terminate with repeated m 1 's. (Recal that any such expansion can be replaced by one with repeated
Continuig the caculation, 8i ~ 82 J p-i p ( ~
O's.) ~3 Jp-illi
= lip (~
Let E )- O. Using Corollary 7.2, choosing N, where we have dN+i i= m- 1, and such that if any two infte products, say B and Ê have their fist k
8i ~82 J p-ip (~ ~ J p-illi
factors identical, k ;: N, then
= lip (~
IIB-ÊII-:E.
:: lip (~ ~i J p-i - p (~ ~2 J p-illill7rllillFllilip-illi :: 2ßII7rlliIIPllillp-illi :: 2ß"IN IlFlli IIp-illi -: E.
Let y E (0,1) where y)- x and y - x -: m-N-i. Thus, say,
-i +... + d Nm -N i: -N-i + UN+2m i: -N-2 +.... y=dim +uNHm Now, let
Thus, L is a continuous LCP-set. .
00 A = II Adk and  = . . . A6N+2A6N+l AdN . . . Ad1,
As pointed out in the proof of the theorem, we have the following.
Corollary 7.1 If L = tAo,... , Am-il is a continuous LCP-set, then
the-re is a nonsingular matrix P, such that for any sequence (di, d2, , . .),
there is a matri 8 where
k=i Then, using (7.1),
II\l (x) - \l (y)1I = IIA - ÂII-: E
00
i=i 0 0 ' II Ad; == P (I 8 J p-i
which shows that \I is right continuous at x. .
(7.1)
114
7,3 Coeffcients and Continuous Convergence
7. Continuous Convergence
115
7.3 Coeffcients and Continuous Convergence
Again, in this section, we use a fite set L = f Ao, . .. ,Am- il of n x n i~J
matrices. We wil show how subspace contraction coeffcients can be used to show that L is a continuous LCP-set.
To do this, we wil assume that L is T-proper, that is
(x~; J
E(L) = E(Ai) for al i. If Pi, . .. , Ps is a basis for that eigenspace and Pi, . . . , Pn a basis
for pn, then P = ¡Pi,... ,PnJ is nonsingular. FUther, FIGURE 7.2. Convergence view of Corollary 7.4.
A k- P (I 0 Bk Ck J p-i
notation there, p (Le) 0( 1, there is a positive integer r such that IlCIIJ 0( 1
k=i k=i J
where I is s x s, for all Ak E L. Let
for al r-blocks C from Le. Thus, since TW (ri Adk) = II ri Cdk II ' it follows that TW (71) 0( 1 for al r-blocks from L.
E= ¡Pi,... ,PsJ and
W=fx:xE=Ol.
Conversely, suppose TW is a contraction coeffcient such that TW (1f) 0( 1
for all r-blocks 1f from L. Thus, 1I1lIlJ 0( 1 for al r-blocks 1l from Le. So, Pr (Le) 0( 1 which shows that P (Le) 0( 1. This shows, by using Theorem 7.2, that L is a continuous LCP-set. . We can alo prove the following.
Recal from Chapter 2 that
Corollary 7.4 If L is aT-proper compact matrix set and we have TW (1f) ::
TW (A) = max IlxA11 "':"'~o IixlL
is a subspace contraction coeffcient. And, if Ak E L and we have Ak =
P (~ ~~ J p-i, then
T 0( 1 for all r-blocks 1f in L, then L is an LCP-set. A view of the convergence here can be seen by observg that
(~ ~ J ( ~ J = ( x ~:y J ' T(Ak) = IICkllJ
where the norm 11.11 J is defied there. Recal that subspace contraction
coeffcients are all equivalent, so to prove convergence, it doesn't matter which norm is used.
Theorem 7.3 Let L= fAo,.,. ,Am-il be T-proper. The set L is a continoous LCP-set iff there is a subspace contraction coeffcient TW and a positive integer r such that TW (1f) 0( Ifor all r-blocks 1f from L.
where ( : J is partitioned compatibly to (~ ~ J. SO the y vector con-
tracts toward 0 while the x vector is changed by some (bounded) matrix constant of y, namely By. A picture is given in Figue 7.2. We conclude with the following observation. In the defition
TW (A) = max IIxAIl , "'EW
11"'11=1
matrix multiplication is on the right. And, we showed that TW (AiA2) ::
Proof. If L is a continuous LCP-set, using any norm, a subspace COn-
TW (Ai) TW (A2), so we are taling about right products. Yet, TW defined
traction coeffcient TW can be defined. Since by Theorem 7.2, using the
in this way establishes LCP-sets.
,
116 7. Continuous Convergence
Example 7.2 Let E = t (t t J ' (t i J l' Set E = ( ~ J. Then
TW (E) = 0 and E is an LCP-set. But, E is not an RCP-set.
8 Paracontracting
7.4 Research Notes The sequence space and continuity results of Section 1 and the canonical form work in Section 2 are, basicaly, as in Daubechies and Lagarias (1992a). Section 3 used the subspace contraction coeffcients results of Hartfiel and
Rothblui (1998). Applications and futher results, especialy concerning differentiabilty of \l, rather than continuity, can be found in Daubechies and Lagarias (1992b) and Micchell and Prautzsch (1989).
An n x n matrix A is paracontracting or PC with respect to a vector norm 11.11, if IIAxl1 -0 II
xii whenever Ax .¡ x
for al vectors x. Note that this implies that IIAII :: 1. We can view paracontracting by noting that L (x) = Ax is the identity on E (A) but
contracts al other vectors. This is depicted, somewhat, in Figue 8.1.
If there is a positive constant 'l such that IIAxl1 :: ILXLI - 'l IIAx - xii
E(A)
A) L(x)=Ax
~
~
FIGURE 8,1. A view of paracontracting.
118
8, i Convergence
8. Paracontracting
119
for al x, then A is caled "ý-paracontractingor "ýPC. It is clear that "ýPC
such that Aiyl, AiY2,'" are in the sequence. And from this, take a con-
implies PC. Paracontracting and "ý-paracontracting sets are sets containing
vergent subsequence, say, Yii ' Yi2, . . . -- y. Thus, AiYii, AiYh, . . . -- Aiy. Since Y is the limit of Yii , Yh, . . . ,
those kinds of matrices.
In this chapter we show that for a fiite set ~of n x nmatrices, paracon-
AiYik II
tracting and "ý-paracontracting are the same. In addition, both paracontracting and "ý-paracontracting sets are LCP-sets.
IlylI :: II
for al k so in the limit
Ilyll :: IIAIYII.
8. i Convergence
Thus, since A is paracontracting, lIyll = IIAiYII and so Aiy = y.
For any matrix set ~and any vector Xl, the sequence
We show that Aiy = Y for i = 1,... , s. For this, suppose Al,... , Aw satisfies Aiy = Y for some w, 1 :: w 0: s. Consider a sequence, say without loss of generalty Aw+1'1iYill Aw+l7l2Yh, . .. where the matrices in the
X2 = AiiXi
products 'Ik are from tAl,... ,Awl. The sequence converges to Aw+IY
X3 = Ai2X2
and thus,
IlylI :: IIAw+iYII. where each Aik E ~, is caled a trajectory of~. Any fite sequence,
So lIylI
Xi, . .. , xpis caled an initial piece of the trajectory.
that
IIAw+IYII and consequently Aw+1Y = y. From this, it follows
Trajectories are linked to infite products of matrices by the following
Aiy = Y
lemma.
Lemma 8.1 A matri set ~ is an LCP-set iff all trajectories of~ converge.
for al i :: s. Finally,
Proof. The proof follows by noting that if Xi = ei, ei the (0, 1 )-vector with
IIxk - Yll = II'IkZk - Yll
a 1 only in the i-th position, then Aik . . . Aii ei = i-th colum of Aik . . . Aii .
So convergence of trajectories implies colum convergence of the infte products and vice versa. And from this, the lemma follows. .
where 'IkZk = Xk, 'Ik a product of Ai, . . . , As and Zk the vector in Yii, Yh, . . . that immediately proceeds Xk. (Here k is large enough that no As+I, . .. , Am
reappears as a factor.) Then, Using this lemma, we show that for fite ~, paracontracting sets are
LCP-sets. The converse of this result wil be given in Section 2.
IIxk - Yll = lI'1kzk - 'IkY11
:: IIzk -Yll. Theorem 8.1 If~ = tAi".. ,Aml is a
para
contracting set with respect
to 11,11, then ~ is an LCP-set. Proof. Let Xi be a vector and set
So Ilxk - yll -- 0 as k -- 00. It follows that (lli AijXi) converges, and thus by the lemma, the result follows. .
X2 = Aii Xl, X3 = Ai2Aii Xl, . .. .
~ '
\ Since IIAyll :: lIylI for al Y and all A E ~, the sequence is bounded. Actually,
if p:: q, then IIxpll ::lIxqll. Suppose, reindexig if necessary, that Ai,... , As occur as, fiictors infitely often in I1 Aik. Let Yl, Y2, . ,. be the subsequence of Xi, X2, . . .
k=i
The example below shows that this result can be false when ~ is infte.
Example 8.1 Let
f r 1 0 0 J 2k - 1 1 ~ = il ~ ~k ~k : ak = 2k for k = 2,3, ... f .
120
8, Paracontracting
8,1 Convergence
Using the vector 2-norm, it is clear that ~ is a para
contracting set. Now,
121
for al i, where p (~e) -( 1. Thus by a characterization of p (~), Theorem
let a :; O. Then
2.19, there is an induced norm 11.11 and an a -( 1 such that
22 4
a2a = (1 - ~) a = a - ~a
IICil1 ::a
for al i.
a3a2a = a3 (a - ~a) = (1 - ;3 ) (a - ~a )
Now, partitioning x = ( ~~ J compatible to A~, defie, for € :; 0, a
1 :; a - 4 -a -1 8-a
vector norm Ilxll. = II ( ~~ J II. = € IIxill2 + Ilx211'
a4a3a2a :; a4 (a - ~a - ~a ) Thus,
IIA~xll. = II ( Xi ~i~:X2 J II.
= (1 - 214) (a - ~a - ~a )
:; a - 1 -a -1-a -1-a
4 8 16'
And, in general
= € Ilxi + BiX2112 + IICix21I
1 1 1 22 23 2k
:: € IIxil12 + (€ IIBillb + a) IIx21I
where
ak . . . a2a :; a - -a - -a - . . . - -a
=a- 4~1 (~)a -"2
IIBillb = max IIBiX2112
"'dO IIx2"
Take € such that
1
= 2a. Thus, the sequence (ak'" ai) does not converge to O. Hence, by
'Y = € IIBillb + a -( 1
for al i. Then
observing
entries, the sequence
IIA~xll. :: € IIxil12 + 'Y IIx21I
/r~ ~ ~kJ...r~ ~ ~2J) \ l 0 ak 0 L 0 a2 0
:: € IIxil12 + IIx21I
= IIxll..
does not converge, and so ~ is not an LCP-set.
And equalty holds iff IIx21I = 0, i.e. X2 = O. Thus,
In the next section, we wil show that for fute sets, paracontracting sets, IIA~xll. :: IIXII.
'Y-paracontracting sets, and LCP-sets are equivalent. Concerning continuous LCP-sets, we have the following.
with equality iff A~x = x. And it follows that ~' = t Aí, . .. , A~ r, and thus ~, is a paracontracting set. (Use ¡Ixll = IIp-ixll..)
Theorem 8.2 Let ~ = tAi,... ,Amr. Then ~ is a continuous LCP-set
Conversely, suppose ~ is a paracontracting set, which satisfies E (~) =
iff ~ is a paracontracting set and E (~) = E (A) for all i.
i i 0 Ci .
E (Ai) for all i. Then there is a matrix P such that A~ = p-i AiP has form given in (8.1). Since E (Ci) = tOr for al i and since ~ is an LCP-set, by
Pryof. Suppose ~ is a continuous LCP-set. By Lemma 7.1, E (~) = E (Ai) for al i. Theorem 7.2 assures a P such that
A~ = p-i A,P = (I Bi J "'('81)
00
i I
Theorem 6.9, I1 Cdi = 0 for any sequence (di, d2,...). Thus, by Theorem i=l 6.4, P (~e) -( 1. Hence, by Theorem 7.2, ~ is a continuous LCP-set. .
122
8,2 Types of Trajectories
8, Paracontracting
123
I
8.2 Types of Trajectories
to properties 1 through 3. To do this, notationally, throughout this section, we wil assume that
We describe three kinds of matrix sets 2; in terms of the behaviors of the trajectories determined by them.
2; = tAi,.,. ,Am)-.
We need a few preliminary results. The fist of these alows us to trade
Definition 8.1 Let 2; be a matri set.
our given problem for one with a special feature. Since E (2;) = t X : Ax = X for al Ai E 2;)- ,
1. The set 2; is bounded variation stable (B VS) if
there is a nonsingular matrix P such that, for all i,
CX
L Ilxi+l - xiII 0: 00
A~ = p-i AiP = (~ ~: J (8.2)
i=i
CX
where I is s x s, s = dimE (2;). We let 2;' = tA~ : Ai E 2;)- and prove our
2;. Here, L IIxi+1 - xiiI is called the i=i
for all trajectories Xi,X2,'" of
fist result for 2;'.
variation of the trajectory Xl, X2, . . . .
Lemma 8.3 Suppose 2;' is VS. Then there exist positive constants a and
2. The set 2; is uniformly bounded vaiation stable (uniformly BVS) if there is a constant L such that
ß such that if X = ( ~ J, partitioned as in (8.2), a IICiq - qll :: IIA~x - xii:: ß IICiq - qll
CX
L Ilxi+i - XiII :: L Ilxill
for all i.
i=l
Proof. By equivalence of norms, we can prove this result for 11'112' For this, note that
for all trajectories Xi, X2, . .. of 2;.
3. The set 2; has vanshing steps (VS) if
A~x = ( p + Biq J Ciq
lim Ilxi+l - Xiii = 0
so
k-+ CX
for all trajectories Xi, X2, . ,. of 2;.
IIA~x - xll2 = II ( Ci~i~ q J 112 .
q q q
An immediate consequence of BV follows.
If iq e, - dB,q--an 0 thiq (P+Biq Î ,J (P+2Biq en , J, (P+3Biq , . ,J
CX
Lemma 8.2 If L IIxi+1 - XiII converges, then (Xi) converges. i=l
.
is a trajectory of 2;'. This trajectory is not V.S. Thus, we must have that Biq = O. This implies that the nul space of Ci - I is a subset of the null space of Bi. And thus there is a matrix Di such that Di (Ci - I) = Bi. From this we have that
Proof. Note that (Xi) is a Cauchy sequence, and thus it must converge. .
It should be noticed that deciding if 2; has one of the properties, 1 through 3, does not depend on the norm used (due to the equivalence of norms).
( 2 2 2) !
II ( Ci~i~ q J 112 = (IIBiqll~ + II(Ci - I) qll~)!
Ai.d, in addition, if 2; has one of these properties, so does p-i2;p for any nonsingular matrix P.
What we wil show in this section is that, if 2; is fite, then al of,lroperties, 1 through 3, are equivalent. And for fite 2;, we wil show that
:: IIDi11211(Ci - I) qll2 + II(Ci - 1) qll2
LCP-sets, paracontracting sets, and ¡-paracontracting sets are equivalent
:: (IIDill~ + 1) 2 II (Ciq - q)112'
1
L
r 124
i ! i - ¡
8. Paracontracting
8.2 Types of Trajectories
We argue by contradiction. Thus suppose there is a sequence of initial pieces xi, xt,. ., , xtj where j = 1,2, . .. and such that
Setting ß = mF ~ (1IDill~ + I)! J yields the upper bound. A lower bound is obviously seen as a = 1. .
pj-l L Ilxi+i - xl II ~ 00
Since paracontracting, ')-paracontracting, LCP, BVS, and unformly BVS all imply VS, this lemma alows us to change our problem of showing the
i=i
equivaence of the properties, 1 through 3, to the set ~" = f C¡, . .. , Cml.
as j ~ 00. By the uniformly BVS property, i~~ Ilxi II = 00.
A useful tool in actualy showing the equivaence results follows.
Now let ~k = ~" - f Cd for k = 1, . .. , r. Each ~k satisfies the induction hypothesis so there is a number Mk such that
Lemma 8.4 Suppose ~" is a uniformly BVS-set. Then there is an E ? 0 such that
p-i Mk 2' L IIxi+l - Xiii
p-i rnax Ilxi+i - XiII 2'i=i E L IIxi+i - XiII i::i::p-i
i=i
(8.3)
for initial pieces of trajectories of ~k with rnax IlxiH -Xiii:: 1 for al i. i::i::p-i Let
for all initial pieces Xi, X2,... , Xp of trajectories Xi, X2,.., of~.
M? maxMk.
Proof. We prove the theorem using that E (~II) = fOl. We precede by
k
induction on r, the number of matrices in ~". If r = 1, by Lemma 8.2,
p.-i Now since it Ilxi+i - xl II -t 00 as j -t 00, the initial pieces where
p(Cl) 0: 1. Thus, there is a vector norm 11.11 such that IICii 0: 1. From
this, we have
p.-l
p-l p-i L IICfxi - cf-ixill :: L IICilli-illCixi - xill i=i i=i
3 3
it II xl+ i - xl I I ? M must use al matrices in ~". Take al of these initial pieces xi, xt, . " , xpi. and from them take initial pieces xi, xt, . .. , x~ .
(ni :: Pi) such that
1 ::. II~ II IICixi - xill.
nj-i
8 Ilxi+i - xiii:: M
Setting E = 1 - IICii yields the result. Now suppose the theorem holds for al ~" having r - 1 matrices. Let ~" be such that it has r matrices. Since ~" is a unformly BVS-set, all
and
trajectories converge, and thus, by Corollary 3.4, there is a vector norm 11,11
L IIx+l - Xiii? M,
such that ¡ICill :: 1 for al i., We now use this norm.
i=l
Note that (8.3) is true iff it is true for initial pieces of trajectories Xi, X2,... , xp such that ,- rnax Ilxi+l - XiII :: 1. (This is a matter of l::i::p-i
Note that nj
scaling.) Thus we show that there is a number K such that '\
125
L IIx+i - xiii:: M + 1. i=i
p-i K 2' L IlxiH - Xiii
Now let
i=i
, xi
YÎ= IHII
where rnax IIxiH - XiII :: 1. i::i::p-l I
~ I
li
(8.4)
, 126
8.2 Types of Trajectories
8, Paracontracting
127
and h the limit of a subsequence, say y~i, y~2 , . . .. We show that h is an eigenvector, belonging to the eigenvaue 1, of each matrix in 'E/'.
Rewriting (8.4) yields nj
l= IIY;¡l Ilx~j - y;j II :: M II +1 i=l so we have lim ~ II kj k .11
j--oo ~ Yi+i - Yi J = O.
(8.5) FIGURE 8,2, Sketch for E,8 view.
Suppose Ci (reindexing if necessary) occurs as the leftmost matrix in y~i, y~2,.... Then from (8.5), h is an eigenvector of Ci. Now, of those products yii , y~i , . .. ; yi2 , y~2 , . .. ;. . . , take the largest initial products that
1. We show that if E ? 0, then there is a 8 such that if IIxll ~ E and lIy - xii -( 8, then IICiY - yll ? 8 E for some Ci. (Ci depends on x.) Note that if this is false, then taking 8 = l, there is an IIxkll ~ E
etc.) and such that C2 (reindexing if necessary) occurs as the fist factor
and a Yk, IIYk - Xk II -( l such that II CjYk - Yk II :: l E for al j. (See
conain t. C i,sayYmi,Ym2'.... li 12 (S li - C ...oYmiC li 12 i iYi,Ym2- C ... Ci lYl' 12
in each of the iterates Y~i+1'Y~2+1"'" Then by (8.5), h is an eigen-
Figue 8.2.) Thus, IICj 11;:11 - 11;:11 II :: l. Now there is a subsequence
vector of C2. Continuing this procedure, we see that h is an eigenvector,
II::: II' II::: 11"" of 1I~:Ii' 1I~~Ii'''' that converges to, say x. Hence, ~Yi ~i t llTh'
belonging to the eigenvalue 1, of al matrices in E", a contradiction. Thus,
the lemma is true for E" and the induction concluded. The result follows. .
, , . ., converges 0 x as we. us, since
Xii Xi2
We now establish the main result in this section.
J IlxiJI Ilxik II - k'
Theorem 8.3 If E" is VS, then E" is uniformly BVS.
IIC,~ _ ~II-( 1
Proof. We prove the theorem by induction on r, the number of matrices in E".
we have that Cjx =x for al j. This implies E (E") =I '¡Oh a contra-
diction.
If E" contains exactly one matrix, then p (Ci) -( 1. Thus, there is a
vector norm 11.11 such that IICil1 -( 1 and so
2. Let X be a trajectory of E". We show that variations of segments
00 00
determined by a partition on X converge to O.
We fist need an observation. Let S be the set of all fite sequences from trajectories, determined from proper subsets of E". Lemma 8.4
L IIxi+1 - xiII :: L IICilii-lllx2 - xill
i=i i=i
assures that there is a constant L such that if Zl, . . . , Zt is any such
-( , IICi - IlIllxiI, 1
sequence, then
t-i
i=i - -
So, using L = i-lìCill IICi - III, we see that E" is unformly BVS.
BVS. '.
L Ilzi+i - zill :: L igi~_illzi+i - zili.
Suppose the theorem is true for al E" containig r - 1 matrices. Now
suppose E" has r matrices. Then, since every proper subset of E" is VS, we
have by the induction hypothesis that these proper subsets are unforTIY
Now partition X in segments Xii,SllXi2,S2"" where
We now argue several needed smaller results.
Xik,Sk is Xik",. ,XSk, ik = Sk-l + 1
l
(8.6)
128
8,2 Types of Trajectories
8. Paracontracting
129
I since IICil1 .: 1 for all i assures that IIxk+ill :: IIxkll for al k. And using
and each Xik,Sk is deterllned by a proper subset of :E" but Xik,ik+i is not. However, using (8.6), the variation S (Xik,Sk)' of Xik,Sk' con-
Xi2,i3
i3-1 i2-2
verges to 0 as k -- 00. And using that :E" is VS on the last term of
the expression, it follows that the variation S (Xik,ik+J converges to
L IlxiH - xiII = L IIXi+1 - xiii + IIxi3 - xi3-ill
o as k -- 00 as welL.
i=i2
i=i2
:: L IIxs211 + C IIxs211
3. We show that X, as given in (2), converges to O. We do this by contradiction; thus suppose X does not converge to O. Then there is an E :; 0 (We can take E .: 1.) and a subsequence Xjll xh,' ., of
:: (L + C) q IIx111'
Continuing, we get
X such that IIxjk II ~ E for all k. But now, by (1), there is a 8 :; 0 such that if IIY - Xjk II .: 8, then IICjy - Yll ~ 8 E for some j. Since
ik+l -1
by (2) S (Xik,ik+i) --0 as k -- 00, we can take N sufciently large
L IIXi+1 - xiII :: (L + C) qk-i IIXill.
so that if k ~ N, S (Xik,ik+J .: 8. Now take an interval ik, ikH
i=ik
where k ~ N and ik :: jk :: ikH. Then, every Ci occurs in the
00 1
trajectory Xik' C ik Xik' . . . , Cik+i . . . Cik Xik' and IIxt - Xjk II .: 8 for all
Finaly, putting together
t, ik :: t :: ikH' Since all matrices in :E" are involved in Xik,ikH'
there is a t, ik :: t :: ikH such that CjXt = XtH, and this Cj is
i=l q
L IIxi+i - xiii = ~ (L + C) Ilxill
as described in (1). But, IICjxt - xtll :; 8 E, which contradicts that
X is VS. Hence, X must converge to O. Since X was arbitrary, all
Thus :E" is unforTIY BVS. .
trajectories converge to O. Thus, there is a vector norm 11.11 such that
IICilL .: 1 for al i (Corollary 6.4). Since all norms are eqtUvalent, we can complete the proof using this norm, which we wil do. F\ther,
Theorem 8.4 The properties ,PC and uniformly BVS are equivalent.
we use
Proof. Suppose :E is ,PC. Then:E is PC, and so :E is an LCP-set. By the defution of ,PC, there is a norm 11.11 and a, :; 0 such that
q = m?X I¡Cill i
IIAxlI :: Ilxll - ,IIAx - xii
in the remaining work.
for al A E :E and all x. Then, for any vector Xl, the trajectory Xi, X2, . . . satisfies
00 1 k
Now, we show that :E" is uniforTIY BVS. Since each proper subset of :E" is unforTIY BVS, there are individual L's, as given in the definition for these sets. We let L denote the largest of these numbers, and let C = m?X IICj - Iii. Take any trajectory X of
J
:E" and write X in terms of
Lllxi+i-xill:: - lim L(llxill-llxiHII)
i=i ' k--oo i=i
segments as in (2). Then using Xii,i2
= .! lim (lIx111-lIxkHII)
i2-i i2-2
, k--oo
1
, = -llx111' ,
L IlxiH - xiII = L IIxiH - xiII + IIxi2 - xi2-111
li
i=ii
:: - (21Ixill)
i=ii :: L IIxiill + C Ilxsill :: L IIxill + C Ilxill
2
Hence, :E is uniforTIY BVS.
= (L + C) Ilxill
l
130
8,3 Research Notes
8, Paracontracting
Now suppose E is uniformly BVS. Since any trajectory of bounded vaiation converges, E is an LCP-set. Thus, by Corollary 3.4, there is a
131
I
vector norm 11,11, such that IIAII :: 1 for all A E E. Set 00
LCP
IlxillE = sup L IIXi+i - xiII i=l
vs
where the sup is over all trajectories starting at Xi. This sup is fite
since E is unformly BVS. FUrthermore, for any vectors y and z, we have IIY + zilE :: IIYIIE + IIzlb and for every scalar a, lIaYIIE :: laillylb Using
the defition,
IIAxllE :: IlxlIE - IIAx - xII
for any A E E. Now defie a norm by
FIGURE 8.3, Relationships among the various properties, 1
Ilxllb = "2l1xll + IIxllE .
(1965) used similar such notions in their work. Theorem 1 was given in Elsner, Koltracht, and Neumann (1990) while Theorem 2 was shown by
Then, for any A E E
Beyn and Elsner (1997). Beyn and Elsner also introduced the defition of
"ý- paracontracting.
1
IIAxllb = "2 !IAxll + IIAxllE
The results of Section 2 occurred in Vladimirov, Elsner, and Beyn (2000).
1
Gurits (1995) provided similar such work.
:: "2 ¡Ixll + (11x1IE - IIAx - xiI)
= IIxllb - IIAx - xii :: IIxllb - "ý ¡lAx - xilb using the equivalence of norms to determine "ý. Thus, E is an "ýPC-set, as required. .
Implications between the various properties of E are given in Figue 8.3. The unlabeled implications are obvious.
1. This follows from Theorem 8.1.
2. This follows by Theorem 8.3. 3. This follows by Theorem 8.4.
8.3 Research Notes The notion of paracontracting, as given in Section 1, appeared in N~lson and Neumann (1987) although Halperin (1962) and Amemiya and Ando
l
9 Set Convergence
In this chapter we look at convergence, in the Hausdorff metric, of sequences of sets obtained from considering al possible outcomes in matrix products.
9.1 Bounded Semigroups Recal, from Chapter 3, that if L is a product bounded subset of n x n matrices, then the limiting set for (Lk) is Loo = r A: A is the limit of a matrix subsequence of (Lk) l, In this section, we give several results about how (Lk) -7 Loo in the Hausdorff metric. A first such result, obtained by a standard arguent, follows.
Theorem 9.1 Let E be a compact subset of n x n matrices. If L2 ç L, 00
\
then (Lk) converges to n Ek in the Hausdorff metric. k=i Now let
too = r A E Mn : A is the limit of a matrix sequence of (Lk) l. If LOO = too, we call Eoo the strong limiting set of (Lk). When Loo is a strong limiting set is given below.
134 9, Set Convergence
9,1 Bounded Semigroups
/ /\ \
Theorem 9.2 Let E be a compact product bounded subset of Mn. Then Hausdorff metric.
Proof. For the direct implication suppose that Eoo is the strong linuting set contradiction. Thus, suppose there is an t ). 0 such that h (Ek, Eoo) ). t
for inftely many k's. We look at cases. Case 1. Suppose å (Ek, EOO) ). t for inftely many k's. From these
d(7rk;,EOO)). t
AiAi
. . .
AiAiAi
Ek,s, we can find matrix products 7rkl, 7rk2, . .. such that
for all i. Since E is product bound, there is a subsequence 7rjl, 7ri2,' ., of 7rkll 7rk2 that converges, say to 7r. But by defition, 7r E Eoo, and yet we
AiAi
AiAi
for (Ek). We prove that (Ek) converges to Eoo in the Hausdorff metric by
i
Ai
Ai
Eoo is the strong limiting set of (Ek) iff (Ek) converges to Eoo in the
135
FIGURE 9,1. A possible tree graph of G,
Theorem 9.3 Let E = tAi,.., , Aml be an LCP-set. Then
have that
EOO = L.
d(7r,EOO) ~ t,
Proof. By definition, L ç Eoo. To show Eoo ç L, we argue by contradic-
tion.
a contradiction.
Case 2. Suppose å (Eoo, Ek) ). t for inftely many k's. In this case
Suppose 7r E Eoo where d (7r, L) ). t, t ). O. Defie a graph G with ver-
the Ek,s yield a sequence 7r ki , 7r k2 , . '. in Eoo such that d (7r k; , Ek;) ). t for
tices al products Aik . . . Aii such that there are matrices Ai, , . , . , Aik+i , t ).
al i. Since Eoo is bounded, 7rkll7rk2, . .. has subsequence which converges
k, satisfying
to, say, 7r. Thus d (7r, Ek;) ). ~ for all i sufciently large. But this means that 7r is not the linut of a matrix sequence of (Ek), a contradiction. Since both of these cases lead to contradictions, it follows that Ek converges to Eoo in the Hausdorff metric.
Conversely, suppose that Ek converges to Eoo in the Hausdorff metric. We need to show that Eoo is the strong linuting set of (Ek). Let 7r E Eoo. Since h (Ek, Eoo) -- 0 as k -- 00, we can fid a sequence 7r1,7r2,..., taken from E1,E2,..., such that (7rk) converges to 7r. Thus,
d(Ai,., ,Aik., .
Aill7r) 0( t,
Since 7r E Eoo, there are infitely many such Aik . . , Aii' If Aik+1 . . . Aii is in G, then so is Aik . . ,Aii, and we defie an arc (Aik . , . Aii, Aik+l ' . , Aii) from Aik . . . Aii to Aik+i . , . Aii' This defies
a tree, e.g., Figure 9.1. Thus, Sk = tAik'" Aii: Aik ,.. Aii E Gl is the
k-th strata of G. Since this tree satisfies the hypothesis of König's infi00
7r is the linut of a matrix sequence of (Ek) and thus 7r E too. Hence,
ity lemma (See the Appendi.), there is a product I1 Aik such that each
Eoo ç too.
Aik ' . ,Aii E G for all k. Thus,
k=l
Finally, it is clear that too ç EOO and thus Eoo = too. It follows that Eoo is the strong linuting set of (Ek). .
d (IT Aik, 7r) :: t k=i
For a stronger result, we defie, for an LCP-set E, the set L which is the
closure of al of its inite products, that is, ~
lk=l f
L = f IT Aik : Aik E E for al k l.
which contradicts that
d(7r,L)).t and from this, the theorem follows. .
136
9,2 Contraction Coeffcient Results
9, Set Convergence
Corollary 9.1 If ¿: is a finite subset of Mn and ¿: is an LCP-set, then (¿:k) converges to ¿:oo in the Hausdorff metric.
137
(Scalng A wil not afect projected distances.) 3. There is a positive integer r such that all r-blocks from ¿: are positive.
Proof. Note that since L ç f;oo ç ¿:oo, and by the theorem L = ¿:oo, we
have that ¿:oo = f;oo, from which the result follows from Theorem 3.14 and
By (3) it is clear that each matrix in ¿: has nonzero columns. Thus for any A E ¿:, WA is defied on S. And
Theorem 9.2. .
¿:pS ç S ¿:;S ç ¿:S ç S.
9.2 Contraction Coeffcient Results Thus, we can define
We break this section into two subsections.
00
L = n ¿:;S
k=i
9.2.1 Bi'rkhoff Coeffcient Results
Let ¿: denote a set of n x n row alowable matrices. Let U be a subset of n x 1 positive vectors. In this section, we see when the sequence (¿:kU) converges, at least in the projective sense.
To do this, recall from Chapter 2 that S+ denotes the set of n x 1 positive
stochastic vectors. And for each A E ¿:, recall that WA (x) = ii.t:iii' ¿:p = tWA : A E ¿:L and for any U ç S+
a compact set of positive stochastic vectors. The following is a rather standard argument.
Lemma 9.2 The sequence (¿:;S) converges to L in the Hausdorff metric. Using this lemma, we have the following.
Lemma 9.3 h (¿:pL, L) = O.
¿:pU = tWA (x) : WA E ¿:p and x E U1.
We intend to look at the convergence of these projected sets. If U and ¿: are compact, then so is ¿:pU. Thus, since p is a metric on S+, we can
Proof. Using Lemma 9.1, for any k ~ 1 we get h (¿:pL, L) :: h (¿:pL, ¿:;S) + h (¿:;S, L)
use it to defie the Hausdorff metric h, and thus measure the difference
between two sets, say ¿:pU and ¿:p V of S+. A lemma in this regard follows.
Lemma 9.1 Let ¿: be a compact set of row allowable n x n matrices. If U and V are nonempty compact subsets of S+, then
:: h (L, ¿:;-iS) + h (¿:;S, L) .
Thus, by the previous lemma, taking the limit as k -- 00, we have the
equation h (¿:pL, L) = 0,
h (¿:pU, ¿:p V) :: T B (¿:) h (U, V) .
the desired result. .
Proof. As in Theorem 2.9. .
For the remaining work, we wil assume the following. ~ 1. ¿: is a compact set of row allowable matrices.
2. There is a positive number m such that for any A E ¿:
m:: min aij :: max aij :: 1. aij?O
Theorem 9.4 Let U be a compact subset of Sand ¿:, as described in 1 through 3. IfTB (7T) :: Tr for all r-blocks 7T of¿:, then
h( ¿:pU,L) Trr h(U,L). k ¡ ::1£J Thus, if Tr 0: 1, ¿:;U -- L with geometric rate.
138
9, Set Convergence
9,3 Convexity in Convergence
Proof. Using Lemma 9.1 and Lemma 9.3,
139
Theorem 9.6 If TW (Er) .: 1 for some integer r, then Ek -t EOO at a geometric rate.
h (E;U, L) = h (E;U, E;L)
Proof. Defie W = IB E Mn: BE = Oì and let
= h (E; (E;-ru) , E; (E;-r L)) .: T h (Ek-rU Ek-r L)
S = IB E I + W: IIBII :: lì,
_rp,p
Then SE ç Sand L follows. Now use the I-norm so that IIBAlli :: TW (A) IIBlli
:: Ti~Jh(U,L).
for all B E S, and mimic the previous results. Finally, use U = I Iì and
This proves the theorem. .
the equivalence of norms. .
9.2.2 Subspace Coeffcient Results
9.3 Convexity in Convergence
Let E be a compact, T-proper product bounded set of n x n matrices. Since E is product bounded by Theorem 3.12, there is a vector norm 11.11 such that IIAII :: 1 for all A E E. Let TW be the corresponding subspace contractive coeffcient. Let Xo E Fn and G = xoE. Then
To compute Ek U and E; U, it is helpfu to know when these sets are convex. In these cases, we can compute the sets by computing their vertices. Thus in this section, we discuss when EkU and E;U are convex.
A matrix set E is column convex if whenever A, BEE, the matrix an + ßnbnJ of convex sum of corresponding columns, is in E. Colum convex sets can map convex sets to convex sets.
Xo + W = I x E Fn : xE = Gì .
¡aiai + ßi bi, .,. , an
We suppose S ç Xo + W such that
Theorem 9.7 Let E be a column convex matri set of row allowable ma-
SEÇS.
trices. If U is a convex set of nonnegative vectors, then EU is a convex
set of nonnegative vectors.
(For example, S = Ix: ¡Ixll :: lì.) Then
Proof. Let Ax, By E EU where A,B E E and X,Y E U. We show the
SE2ÇSEÇS
convex sum aAx + ßBy E EU.
Defie
and we defie
L = nSEk.
K = (aAX + ßBY) (aX + ßY)+ + R
Then mimicking the results of the previous section, we end with the following.
where X = diag (Xb'" , xn), Y = diag (Yi".. , Yn), (aX + ßY)+ the generalzed inverse of
Theorem 9.5 Let U be a compact subset of S. If TW (il') :: Tr for all
aX
+ ßY, and R such that
r" 0 ifaxj + ßYj ? 0 ii =1.J aij otherwise.
r-blocks 7l of E and T r .: 1, then UEk -t L at a geometric rate.
Using that aj, bj denote the j-th colums of A and B, respectively, the j-th colum of K is
~ common situation in which this theorem arises is when we have E = e,
= aj + j
E the set of stochastic matrices, and S the set of stochastic vectors.
aajxj + ßbjYj aXj ßYj b
We conclude this section with a result which is a bit stronger thàh the previous one.
aXj + ßYj aXj + ßYj aXj + ßYj i
1
140
9. Set Convergence
9,3 Convexity in Convergence
ifaxj + ßYj :; 0 and aj if aXj + ßYj = O. Thus, K E~. FUthermore, for
141
Xl
e = (1,1, . . . , l)t,
K (ax + ßy) = K (aX + ßY) e
Xi
L
= (aAX +ßBY)e
~
X3
= aAx + ßBy
which is in ~U. From this, the result follows. . Applying the theorem more than once yields the following corollary.
FIGURE 9.2. A view of EU,
Corollary 9.2 Using the hypotheses of the theorem, ~kU is convex for all
Theorem 9.9 If ~ = convextAi,... , As) is a column convex matri set
k:: 1.
of nonnegative matrices and U = convex tXi,... , Xt) a set of nonnegative vectors, then
The companon result for ~p uses the following lemma.
Lemma 9.4 If U is a convex subset of nonnegative vectors, none of which are zero, then Up = t ii:ili : u E U 1 is a convex subset of stochastic vectors.
~U = conVeXtAiXj: 1:: i:: s, 1:: j:: t).
Not al vectors Aixj need be vertices of ~U. The appearance may be as it appears in Figue 9.2. The more intricate theorem to prove uses the
Proof. Let IIxlli ' g E Up where x, y E U. Then any convex sum ax+ßy E
following lemma.
U. us, Th11~~.Lf.... ax+ßy II E U p and
Lemma 9.5 Let U be a subset of nonnegative, nonzero, vectors. If
= -+
ax+ßy allxlli x ßllylli y
U = convex t Xi, , . . , Xt)
lIax + ßylli lIax + ßylli Ilxlli lIax + ßylli IIYlli
then
is a convex sum of ii:ili' g E Up. And when a = 0, the vector is IIYlli' while when ß = 0, it is ii:ili' Thus, we see that al vectors between IIxlli and ii:ili are in Up. So Up is convex. .
Xi ,Xt Up = convexJillxilli"" IIXtlliLJ'
As a consequence, we have the following theorem.
Proof. Let x = aiXi +... + atXt be a convex sum. Then
t L akXk
Theorem 9.8 Let ~ be a column convex matri set of row allowable ma-
~ _ k=i
trices. If U is a convex set of positive stochastic vectors, then ~;U is a
convex set.
Ilxlli - IIxlli
Proof. Using the previous corollary and lemma and that ~;U is the projection of ~kU to norm 1 vectors, since ~kU is convex, so is ~;U. .
(ak IIXklli) Xk = tk=i IIxlli Ilxklli'
It is known (Eggleston, 1969) and easily shown, that the limit of convex set~, assuing the limit exists, is itself convex. Thus, the previous two
t
Since L (akIlXklli)
k=i IIxlli
theorems can be extended to show ~~ U is convex.
vectors listed in Up.
Actually, we would like to know about the vertices of these sets. "The following theorem is easily shown.
= 11:1:: = 1, it follows that ii:ili is a convex sum of That Up is convex follows from Lemma 9.4. .
The theorem follows.
i¡
142 9. Set Convergence
10
z ."....
Perturbations in Matrix Sets
.........
~,....,""""""
y
x
FIGURE 9,3, A projected symplex,
Theorem 9.10 Let ~ = convex tAi,... , As)-, a column convex matrix set of row allowable matrices, and U = convex t Xl, . ,. , Xt)-, containing positive vectors. Then
~U p = convex 1.IIAixjlli : 1 , :: i :: s, :: t f . () f Aixj .1:: J1. Let ~ and t be compact subsets of Mn. In this chapter we show conditions
Proof. The proof is an application of the previous theorem and lemma. .
assuring that when ~ and t are close, so are X~OO and ytoo.
We give a view of this theorem in Figure 9.3.
10.1 Subspace Coeffcient Results
9.4 Research Notes
Let ~ and t be product bounded compact subsets of Mn. We suppose that ~ and tare T-proper, E(~) = E (t), and that TW is a corresponding
Section i extends the work of Chapter 3 to sets. Section 2 is basically con-
contraction coeffcient as described in Section 7.3. Also, we suppose that
tained in Seneta (1984) which, in turn, used previously developed material
S ç pn such that
from Seneta and Sheridan (1981).
Computing, or estimating, the linuting set can be a problem. In Chap-
1. S ç Xo + W for some vector Xo,
ters 11 and 13, we show how, in some cases, this can be done. In Hartfiel (1995,1996), iterative techniques for fiding component bounds on the vec-
2. s~ ç s, st ç s.
tors in the liting set are given. Both papers, however, are for special
Our perturbation result of this section uses the following lemma.
matrix sets. There is no known method for fiding component bounds in general. M"ch of the work in Section 4 generalizes that of Hartfiel (1998).
Lemma 10.1 Let Ai, A2".. and Bi, B2"" be sequences of matrices taken from ~ and t, respectively. Suppose TW (Ak):: T and IIAk - Bkll :: E for
all k. Then
IlxAi . . . Ak - yBi . . . Bk II :: Tk IIx - ylI + (Tk-l + . . . + 1) ßE
.L
144
10, Perturbations in Matrix Sets
10,2 Birkhoff Coeffcient Results
where x, yES and ß = sup IlyBi... Bill.
145
So,
i
8 (X2;k, Y:Êk) :: Tkh(X, Y) + (Tk-i +... + 1) h (2;,:Ê) ß.
Proof. The proof is done by induction on k. If k = 1,
Similarly,
IIxAi - yBiI :: IIxAi - yAiI + lIyAi - yBill
8 (Y:Êk, X2;k) :: Tk h (Y, X) + (Tk-i + ' . . + 1) h (2;, :Ê) ß.
:: TW (Ai) iix - ylI + IlyllllAi - Bill
:: dx-yll +ßE.
Thus,
Assume the result holds for k - 1 matrices. Then
h (X2;k, Y:Êk) :: Tkh (X, Y) + (Tk-i +... + 1) h (2;,:Ê) ß,
IlxAi . . . Ak -yBi . . . Bk II:: IIxAi . . . Ak-iAk-yBi . . . Bk-iAk II
which yields (1).
For (2), Theorem 9.6 assures that 2;00 and :Êoo exist. Thus, (2) is ob-
+ lIyBi... Bk-iAk-yBi ... Bk-iBkll
tained from (1) by calculating the limit as k -t 00. .
:: TW (Ak) IlxAi... Ak-i-yBi... Bk-ill + lIyBi... Bk-illllAk - Bkil
For r-blocks, we have the following.
:: T IlxAi... Ak-i -yBi... Bk-ill+ßE,
Corollary 10.1 Suppose TW (2;r) :: Tr and TW (:Êr) :: Tr. Let X and
and by the induction hypothesis, this leads to
Y be compact subsets of Fn such that X, Y ç S. Then
:: T (Tk-iiix - Yll + (Tk-2 +... + 1) ßE) + ßE = Tk iix - Yll + (Tk-i +... + 1) ßE.
h (X2;k, Y:Êk) :: Ti~i Mxy + (Ti~J-i +... + 1) h (2;r,:Êr) ß,
The perturbation result follows. . where Mxy = max h (X2;t, Y:Êt) and ß as given in the theorem. O:StoCr
Theorem 10.1 Suppose TW (2;) :: T and TW (:Ê) :: T. Let X and Y be compact subsets of Fn such that X, Y ç S. Then
Proof. The proof mimics that of the theorem where we block the products. The blocking of the products can be done as in the example
1. h (X2;k, Y:Êk) :: Tkh (X, Y) + (Tk-i + .. . + 1) h (2;,:Ê) ß, where ß = max (sup IIxAi ... Ai
Ai ' , . Ak = Ai ' . . AsBi . . , Bq
II , sup lIyBi... Bill) and the sup is over all
where k = rq + s. .
x E X, Y E Y, and all Ai, . .. , Ai E 2; and BT",~.-,-BiE :Ê.
A consequence of this theorem is that we can approximate 2;00 by a :Êoo ,
1fT -c 1, then
where :Ê is fite. And, in doing this our fiite results can be used on :Ê.
2. h (X2;oo, Y:Êoo) :: i~; h (2;,:Ê) ß.
Proof. To prove (1), let Ai... Ak E 2;k and x E X. Take y E Y such that
10.2 Birkhoff Coeffcient Results
IIx -~II :: h (X, Y). Take Bi,.., , Bk in:Ê such that IIAi - Bill :: h (2;,:Ê)
Let 2; be a matrix set of row allowable matrices. In this section, we develop some perturbation results for 2;p. Before doing this, we show several basic results about projection maps.
for al i. Then, by the previous lemma,
IIxAi . . , Ak-yBi ' . . Bkll::Tk IIX - yll+( Tk-i+ . . . +1) h (2;,:Ê) ß.
Equality of two projective maps is given in the following lemma.
l-
146
10,2 Birkhoff Coeffcient Results
10, Perturbations in Matrix Sets
Lemma 10.2 For projective maps, WA = WB iff P (Ax, Bx) = 0 for all
147
Example 10.1 We can show by direct calculation, if A = (~ ~ J and
xE S+.
B = (~ ; J, then W A = W B, while if A = (~ ~ J and B = (~ ~ J,
Proof. Suppose
then WA =I WB.
WA (x) = WB (x)
for al x E S+. Then
Let 'E be a compact set of row alowable n x n matrices such that if A, B E 'E, then for corresponding signum matrices we have A* =B*, Le. A
Ax Bx
and B have the same O-pattern. Defie
IIAxlli = IIBxlli
'Ep=rwA:AE'EJ.
and If WA, WB E 'Ep, then
p(Ax,Bx) = 0
for al x E S+. B (i1.::iIJ
Conversely, suppose p (Ax, Bx) = 0 for al x E S+. Then
WB 0 WA (x) = liB (ii:iIJ Ili
Ax = c(x)Bx BAx
where c (x) is a constant for each x. Thus
Ax IIBxlli Bx
- IIBAxlli'
a projective map. And in general,
IIAxlli = c (x) IIAxlli IIBxlli .
ince IIAxlli S. Ax andIIBxIli Bxarets ochastic. vectors,
Aik . . . Aii X
WAik 0", 0 WAi (x) = IIAik ... Aïixlli'
Ax IIBxlli Bx
ellAxlli = ec(x) IIAxlli IIBxlli We defie a metric on 'Ep as follows. If WA, WB E 'Ep, then
where e = (1,1, . .. ,1), or 1 = c(x)
p(WA,WB) = sup p(Ax,Bx). xES+
IIBxlli IIAxlll
A formula for p in terms of the entries of A and B follows.
It follows that Ax
Bx
IIAxlli
IIBxlli
have thatp WB) = (WA, ~ax In ~irbj'~~isb;r , where the quotient contains only positive entries.
Theorem 10.2 ForprojectivemapswA andwB, we
i,;i,r,s 1.raJB 'l8aJr
or
Proof. By defition, ~
WA (x) = WB (x).
P(WA,WB) = supp(Ax,Bx) X?o
Hence WA = WB. .
aix bjx
= sup Il8? In --
X?o i,J bix ajx
An example follows.
l-i
148
10,2 Birkhoff Coeffcient Results
10, Perturbations in Matrix Sets
149
We now show that p (WAil WA) -- 0 as i -- 00, thus showing (~p,p) is
where ak, bk are the k-th rows of A, B, respectively. Now
complete. For this, let f ~ O. Then there is an N ~ 0, such that if i, j ~ N, aiX bjx _ aiiXi +... + ainXn bj1Xi +... + bjnxn
bix ajX - biiXi +... + binxn ajiXi +... + ajnxn
p ( W Ai' W Aj) .: f.
Thus, if ik ~ N,
L (airbjs + aisbjr) XrXs
r,s
L (birajs + bisajr) XrXs
r,s
P(WAik,WAj)': f,
airbjs+aisb,Jr.
.: max b, a' + bisajr
and so, letting k -- 00, yields
- rJs ir 38
That equalty holds is seen from this inequality by letting Xr = Xs = t and
p (WA, WA,) :: f.
Xi = l for i # r, s and letting t -- 00. .
But, this says that WAj -- WA as j -- 00 which is what we want to show. To show that ~p is also compact is done in the same way. .
For intervls of matrices in ~, p (w A, W B) can be bounded as follows.
Corollary 10.2 If
We now give the perturbation result of this section. Mimicking the proof of Theorem 10.1, we can prove the following perturbation results.
A - fA :: B :: A + fA
Theorem 10.4 Let ~ and t be compact subsets of positive matrices in
for some f ~ 0 and A-fA,A+fA E~, then
Mn. Suppose TB (~) :: T and TB (t) :: T. Let X and Y be compact
subsets of positive stochastic vectors. Then, using p as the metric for h, p(WA,WB)::In l+f
1 - c'
1. h ~pX, ~pY :: T h (X, Y) + T - +... + 1 h ~p, ~p .
( k Ak) k (k 1 ) ( A)
Proof. By the theorem,
And ifT': 1, p (WA, ) WB In =!lax airbjs + aisbjr
2. h (L, t) :: l~Th (~p,tp) and by definition L = lim ~;X and t =
',J,r,s birajs + bisajr
k-+oo
Ak
lim ~pY.
.: max In air (1 + f) ajs + ais (1 + f) ajr
k-+oo
- i,j,r,s (1 - f) airajs + (1 - f) aisajr
Converting to an r-block result, we have the following.
In (1 + f)
= (1 - f)'
Corollary 10.3 Let ~ and t be compact subsets of row allowable ma-
the desired result. .
trices in Mn. Suppose TB (~r) :: Tr, TB (tr) :: Tr. Let X and Y be
Actually, (~p,p) is a complete metric space which is also compact.
compact subsets of stochastic vectors. Then, h (~;X, t;y) :: Ti~ J Mxy+
Theorem 10.3 The metric space (~p,p) is complete and compact.
(T¡~J-i +... + 1) h (~;, t;) where Mxy = O~~r h (~~X, t~Y).
Proc1. To show that ~p is complete, let W Ai , W A2 , . .. be a Cauchy sequence
Computing TB (~k), especially when k is large, can be a problem. If
in ~p' Since Ai, A2, , ., are Ìn ~, and ~ is compact, there is a subseque!lce
there is a B E ~ such that the matrices in ~ have pattern B and
Aii' Ai2 , . ,. of this sequence that converges to, say A E ~. So by Theorèm
B::A
10.2, p (WAik' WA) -- 0 as k -- 00.
i
L
150 10. Perturbations in Matrix Sets
for all A E ~, then some bound on TB (~k) can be found somewhat easily. To see this, let
RE = max AELaijb- bij
11 Graphics
bij ).0 ij
the largest relative error in the entries of B and the A's in~. Then we have the following.
Theorem 10.5 If Bk :; 0, then
TB (Aik ... AJ :: 1 - (HkE)k..
1 + 1 C(' (HRE)k V ep ~Bk)
Proof. Note that
B :: Ai :: B + (RE) B
for al i, and Bk :: Aik . . ,Aii:: (1 + RE)k Bk
This chapter shows how to use infnite products of matrices to draw curves
for al ii, . . . , ik. Then if A = Aik . . . Aii and ep (A) = aij.a~B ,
ari ais
and construct fractals. Before looking at some graphics, we provide a
section developing the technques we use.
(k) (k)
ep (A) 2: bij brs :; 1 (Bk) . (1 + RE)2k b~;) b~;) - (1 + RE)2k ep So,
11.1 Maps
TB (A) = 1 - MA -C 1 - (HkE)k..
,
1 + Vep (A) - 1 + (U~k"k Vep (Bk)
the desired result. .
In this section, we outline the general methods we use to obtain the graphics in this chapter.
Mathematicaly, we take an n x k matrix X (corresponding to points in R2) and a fite set ~ of n x n matrices. To obtain the graphic, we need to
10.3 Research Notes li
The work in this chapter is new. To some extent, the chapter contains theoretical results which parallel those in Hartfiel (1998).
compute ~= X and plot the corresponding points in R2. We wil use the subspace coeffcient TW to show that the sequence (~k) converges in the Hausdorff metric. To compute the linuting set, ~= X, it wil be sufcient to compute ~s X for a 'reasonable's. To compute ~s X, we could proceed directly, computing ~X, then ~ (~X), and ~ (~2 X) ,.., ,~(~S-l X). However, ~k X can contain i~ik IXI matri-
ces, and this number can become very large rapidly. Keeping a record of these matrices thus becomes a serious computational problem.
152
11. Graphics
11.2 Graphing Curves
To overcome this problem, we need a method for computing ~8 X which doesn't require our keeping track of lots of matrices. A method for doing this is a Monte Carlo method, which we wil describe below.
153
OB D
E
F
Monte-Carlo Method 1. RandoITY (unform distribution) choose a matrix in X, say Xj.
c
A
2. RandoITY (unform distribution) choose a matrix in~, say Ai. Compute AiXj.
FIGURE 11.2, A corner cut into two corners.
3. If Ait ... Aii Xj has been computed, randoITY (unform distribution) choose a matrix, say Ait+1 in~. Compute Ait+1 Ait . . . Aii Xj.
4. Continue until Ai. . . . Aii Xj is found. Plot in R2.
c
A
5. Return to (1) for the next run. Repeat sufciently many times. (This may require some experimenting.)
FIGURE 11.3. A curve generated by corner cutting. Mathematically, this amounts to taking points A (xi, Yi), B (X2, Y2), and
11.2 Graphing Curves
C (X3, Y3) and generating
A=A
In this section, we look at two examples of graphing curves.
D = ,5A+ .5B
Example 11.1 We look at constructing a curve generated by a comer cutting method. This method replaces a comer as in Figure 11.1 by less sharp comers as shown in Figure 11.2. This is equivalent to replacing 6.ABC
E = .25A + .5B + ,25C
and E = ,25A + .5B + .25C
F = ,5B + .5C
C=C. This can be achieved by matri multiplication
c
¡Xl Yi J Ai X2 Y2 X3
FIGURE 11.1. A corner. ~
with 6.ADE and 6.EFC: This comer cutting can then be continu~d on polygonal lines (or triangles) ADE and EFC. In the limit, we have 'Some curve as in Figure 11.3.
¡ Xi
Yi J
, A2 X2
Y2
X3
Y3
Y3
where
1 0 A, ~ ¡ ,5 .5
.25 .5
o J
o, .25
¡ .25 .5 A2 = 0 .5
o 0
.25 J
.5 . 1
154
11,2 Graphing Curves
11. Graphics
And, continuing we have
155
CUM frm comer eutting
':¡
AiAiP, A2AiP, AiA2P, A2A2P
¡ xi Yi J 00
(11.1)
Xa Ya k=i
0.8r
where P = X2 Y2 ,etc. The products TI Aik P are plotted to give the
0.6
points on the curve.
'"
.x
Calculating, we can see that 2; = t Ai, A2Ì is a T-proper set with
II 0.4
,.
//\
E~ ¡t) a
The corresponding subspace contraction coeffcient satisfies
-0,2
a 0.2 0.4 0,6 0.8 1 1.2 1.4 1.6 1.8 2
TW (Ai) = .75 and TW (A2) = .75,
x axis
using the I-norm. Thus by Theorem 9.6, (2;k P) converges. FIGURE 11.4, Curve from corner cutting.
Given a oome P ~ ¡ ~ ~ J ' we apply the co cut/in. 'ocnique 10
I~ °B I
times. Thus, we compute 2;10 P by Monte-Carlo where the number of runs
(Step 5) is 5,000. The graph shown in Figure 11.4 was the result.
Example 11.2 In this example, we look at replacing a segment with a
FIGURE 11.5. A segment.
polygonal line introducing comers. If the segment is AB, as shown in
Figure 11.5 we partition it into three equal parts and replace the center segment by a comer labeled CDE, with sides congruent to the replaced
To find CD, we use a vector approach to get
segment. See Figure 11. 6. D = A + ~ (B - A) + ~ (B - A) ( CO~ ~7r sin i J
3 3 -Sll"3 cos"3
Given A (xi, Yi) and B (X2, Y2), we see that
2626' 6262'
C 3'A + 3'B = C 3'xi + 3'x2, 3'Yi + 3'Y2 .
= D (~xi + J3 Yi + ~X2 - J3 Y2 - J3 Xi + ~Yi + J3 X2 + ~Y2)
(2 1) (2 1 2 1)
Thus, listing coordinates columnwise, if
Thus,
Ai ( ~ J = ( ~ J '
A2 ( ~ J = ( ~ J
where
then ~
o A, ~ L i
1
o 2 "3
o o i "3
o
0 2
n
1 I ! i i
A, ~ L !
-~ 6
~ 6
i
"2
i "3
0
i
~ -~ ) "2
6
156
11,3 Graphing Fractals
11. Graphics
157
sphere in the
where Ui = (1,0,-1,0) and U2 = (0,1,0,-1). The unit
1 -norm is
convex ~ ::~ui, ::~U2 J . A
c
E
B
Hence, using Theorem 2.12,
FIGURE 11.6. A corner induced by the segment.
TW (A) = max ~ 1l::~uiAlli ' 1I::~U2AIIJ
Continuing,
= max ~ ~ lIai - a3l1i, ~ IIa2 - a311i J
A3(~J=(~J for
where ak is the k-th row of A. Applying our formula to E, we get
i ¡ l2 .f6 ~l _.f ~ l6 2 A3 = _.f i "3 ° 3 ° i ° -2°
TW (E) = ~
3'
Thus, by Theorem 9.6, EOO P exists. To compute and graph this set, we
i6 "2
3
"3
..e L" P where P ~ ¡ ~ i, and we take , ~ 6. TI reult of applying the
and
A4(~J=(~J
Monte-Carlo techniques, with 3,000 runs, is shown in Figure 11.7. lines can be used to replace a segment, e.g., Of course, other polygonal see Figure 11.8.
for
i 1.3 Graphing Fractals
¡ i ° ~
3 i 3° °-
A4= ° Õ 1 ° ° °
n
The set E = t Ai, A2, A3, A41 is a T-proper set and
In this section, we use products of matrices to produce fractals. We look at two examples.
Example 11.3 To construct a Cantor set, we can note that if ( ~ J is an interval on the real line, then for
E=¡~1~i °. '\
Ai = (~ l J, Ai ( ~ J = ( ~a: lb J
° 1
gives the first l of the interval and for Thus,
W = SpantUi,u21
A2 = ( !ï J, A2 ( ~ J = ( la t ~b J
158
11,3 Graphing Fractals
11. Graphics
159
CuM! frm comr inducing ¡I
2 1 -a+3 3b
a
1 !
1.5
~
Ul '~
,.
0.5 0.5
1 2 -a+-b 3 3
b
FIGURE 11.9, One third of segment removed,
where ak is the k-th row of A. Thus 1
TW P~) = :3'
1.5 x axis
2
2.5
and so ¿;oo ( ~ J exists. To see a picture, we computed ¿;s ( ~ J where s = 4. With 1,000 runs,
FIGURE 11,7, Curve from corner inducing,
we obtained the graph in Figure 11.10. Cantor set
0.6 0.4 0.2 Ul
.~ 0
,. I
I
-0,2 f i
FIGURE 11,8. Square induced by segment,
-o4~ -0,61
gives the second third of the interval. See Figure 11.9. Thus, graphing all -0,5
products ¿;oo ( ~ J gives the l Cantor set.
Calculation shows ¿; = f Ai, A21 is a T-proper set where,
E=(~J. ~
0.5 x axis
1.5
FIGURE 11.10, The beginning of the Cantor set, The l Canter set, etc. can also be obtained in this manner. Example 11.4 To obtain a Sierpenski triangle, we take three points which
So 1
TW (A) = -2 IIax Ilai - ajlli i,i
form a triangle. See Figure 11.11. We replace this triangle (See Figure 11.12.) with three smaller ones,
6ADF,6DBE, 6FEC.
160
11.3 Graphing Fractals
11. Graphics
A
A
c
B FIGURE 11.11. A triangle.
If A(xu,Yu), B(XL,YL), C(XR,YR) are given, we obtain the coordinates of A, D, F as
B
A. ¡ ~ J ~ ¡ ~ J
FIGURE 11.12, One triangle removed,
or numerically,
0
0
0
0
1
0
"2
0
"2
0 0
1
i
i
0
"2
"2
0
i
0
1 "2
i
1
0 0 0
"2
0 0
0 0 0 0
0 0
Xu
Xu
Yu
Yu
0
XL YL
"2
0 0
XR
-Xu + -XR
0
1 "2
YR
"2Yu + "2YR
i
provides 6F EC. The set ~ = tAi,A2,A31 is a T-proper set with
¥ ri ¥ ¥r
!Xu + !XL
=
-Yu + -YL
E=
And 1 "2
0
0 1 "2
1 "2
0
0
0
0
"2
0
0 0
i
0
1
0
0
1
0 0
0
0 0
1 "2
0
"2
0
0
0
"2
0
i "2
0
0
"2
0
"2
0 0
0
0
0
"2
0
"2
0
"2
0 0
1
0
0
1
0 A2 = I 0
i
i
c
E
1 o 1 o 1 o
0 1 0 1 0 1
This yields that
0 0
TW (A) = ~ max r lIai - a311i, lIai - a511i, IIa3 - a511i 1. 2 1. lIa2 - a411i, lIa2 - a6111 , lIa4 - a611i r.
i
"2
provides L:DBE, while ~
A3 - I 0
- 0 0 0
1
0 0 0 0
1 "2
0 0 0
1
i i
0
Thus,
i
"2
i
1
TW(~) = 2' This assures us that (~k P) converges.
161
162
11.5 MATLAB Codes
11. Graphics
11.5 MATLAB Codes
1
J3 o o
Using P =
, s = 6, and 3, 000 runs, we obtained the picture
Curve from Corner Cutting Al=(l 0 0;.5 .5 0; .25 .5 .25J;
2
o
given in Figure "11.13~ Other triangles or polygonal shapes can also be used
A2=(.25 .5 .25;0 .5 .5;0 0 lJ; axis equal
xlabel ( 'x axis')
ylabel('yaxis') Sierpenski triangle
1,6 1.6
title('Cuve from corner cutting') hold on for k=l: 5000
1.4
P= (0,0; 1, sqrt (3) ; 2, OJ ;
1.2
for i=l: 10
.:..
G=rand;
1
if G.(=1/2
~0.6
P=Al*P;
else
0.6
P=A2*P;
0.4
end
end
W=(P(l,l) P(2,1) P(3,1) P(l,l)J; z=(P(1,2) P(2,2) P(3,2) P(1,2)J;
x axis
plot (w ,z)
FIGURE 11,13. Sierpenski triangle. in this setting.
end Contraction Coeffcient
A=(l 0 0;.5 .5 0; .25 .5 .25J; ./
11.4 Research Notes
T=O; for i=1:3 for j=1:3 M=.5*norm(A(i,:) '-A(j,:)', 1);
The graphing method outlned in Section 1 is well known, although not
T=max( (T ,MJ);
end
particularly used in the past in this setting. Barnsley (1988) provided a diferent iterative method for graphing fractals; however, some of that work,
end
on designing fractal, is patented. Additional work for Section 2 can be found in Micchell and Prautzsch
T
helpfuL. '.
(19~9) and Daubechies and Lagarias (1992). References there are alo
For Section 3, Diaconis and Shahshani (1986), and the references thère,
are usefuL.
Curve from Corner Inducing
Al=(l 0 0 0;0 1 0 0;2/3 0 1/3 0;0 2/3 0 1/3J;
A2=(2/3 0 1/3 0;0 2/3 0 1/3; 1/2 sqrt(3)/6 1/2
163
164
ll, Graphics
-sqrt(3)/6;-sqrt(3)/6 1/2 sqrt(3)/6 1/2);
A3=(1/2 sqrt(3)/6 1/2 -sqrt(3)/6;-sqrt(3)/6 1/2
11.5 MATLAB Codes for k=l: 1000
x=(l;O) ;
sqrt(3)/6 1/2; 1/3 0 2/3 0;0 1/3 0 2/3);
for i=1:4
A4=(1/3 0 2/3 0;0 1/3 0 2/3;0 0 1 0;0 0 0 1);
G=rand;
hold on axis (.5 2.5 0.5 2.5) axis equal
if Go:.5, B=Al; else, B=A2;
xlabel ( 'x axis')
x=B*x;
end
ylabel('yaxis')
end
plot(x(l) ,0,'. ')
title( 'Curve from corner inducing') for k=l: 3000
P=(1;1;2;1) ;
plot(x(2) ,O,'.~) end
for i=l: 10
G=rand; if GO:1!4
P=AhP; end if GO:=1!4&GO:1!2
P=A2*P;
end
Serpenski Trangle
Al=(l 0 0 0 0 0;0 1 0 0 0 0;.5 0 .5 0 0 0; o . 5 0 .5 0 0;. 5 0 0 0 . 5 0; 0 . 5 0 0 0 .5); A2= (. 5 0 .5 0 0 0; 0 .5 0 .5 0 0; 0 0 1 0 0 0;
o 0 0 1 0 0; 0 0 .5 0 .5 0; 0 0 0 .5 0 .5);
end
A3=(.5 0 0 0 .5 0;0 .5 0 0 0 .5;0 0 .5 0 .5 0; o 0 0 .5 0 .5;0 0 0 0 1 0;0 0 0 0 0 1); axis equal
if G?=3/4 P=A4*P;
xlabel ( 'x axis') ylabel ( 'y axis')
if G?=3/4 P=A3*P;
end
title (, Serpenski triangle')
end
hold on
plot (p (1) ,P (2))
plot (0,0)
plot(P(3) ,P(4))
plot (1, sqrt (3) )
end
plot(2,0) for k=1:3000
x=(0;0;1;sqrt(3) ;2;0); Cantor Set
for i=1:5
G=rand;
Al=(l 0;2/3 1/3);
if GO:l/3
A2=(1/3 2/3;0 1); axis (-.5 1.5 -.5 .5) axis equal
elseif G?=1/3&Go:2/3
x'tabel ( 'x axis')
else
title ( , Cantor set')
end
x=Al*x; x=A2*x;
ylabel('yaxis') hold on
x=A3*x;
end
165
166 11. Graphics
w=(x(i) ,x(3) ,x(5) ,x(i)) ; z=(x(2) ,x(4) ,x(6) ,x(2));
fill(w,z, 'k') end
12 Slowly Varying Products
When fite products Ai, A2Ai, . .. , Ak . . . A2Ai vary slowly, some terms in the trajectory (tli AiX) can sometimes be estimated by using the current
matrix, or recently past matrices. This chapter provides results of this type.
12.1 Convergence to 0 In this section, we give conditions on matrices that assure slowly vary-
ing products converge to O. The theorem wil require several preliminary results. We consider the equation
A*SA-S=-I, where A is an n x n matrix and I the n x n identity matrix. ..
Lemma 12.1 If p (A) -: 1, then a solution S to (12.1) exists.
Proof. Defie
S = ~ f (A* - z-i 1) -i (A - zi)-i z-idz 27fi
(12.1)
168
12,1 Convergence to 0
12. Slowly Varying Products
where the integration is over the unit circle.
169
or setting G = A - éO I,
To show that 8 satisfies (12.1), we use the identities 8 = l- ln (G-1)* G-idB,
27f -n
(A - z1)-l A = 1+ z (A - zi)-i A*(A*-z-lI)-i = 1+z-1(A*-z-iI)-1.
which is HerITtian. To show that 8 is also positive defute, note that (G-i) * G-i is positive
Then
defute. Thus, if x =f 0, x* (G-i)* G-1x :: 0 for all B and so
1 ln *
A*8A= ~ fA* (A* - z-iI)-i (A- zi)-l Az-1dz 27fi
x* 8x = - x* (G-i) G-ixdB:: O. 27f -n
= 2~if(i + z-i (A*-z-lifi) (i + z (A-zi)-l) z-idz (A-zi)-l+(A*z- I)-iz-i) dz + 8
= 2~i f (z-lI +
= I +~f(A-Zi)-i dz+~ f (A*z-I)-l z-idz+8. 27fi 27fi Now, since f (A) = 2~i f f (z)(1z - A)-i dz for any analytic fuction f,
Hence, 8 is positive definite. The bounds are on the largest eigenvalue p (8) and the smallest eigen-
vaue a (8) of 8 follow.
Lemma 12.2 If p (A) 0( 1, then 1. p (8) :: (IIAII2 + 1)2n-2 / (1 _ p (A))2n
takig f (z) = 1, we have 2. a (8) 2: 1.
2~i f (A - z1)-i dz = -i.
Changing the variable z to z-l and replacing A by A* yields
Proof. For (1), since G = A - eiO i, then, using a singuar value decomposition of G, we see that IIGI12 is the largest singular vaue of G, IIG-1112 is
the reciprocal of the smalest singular value of G, and Idet GI is the product
of the singular values. Thus, 27fif (A*z - 1)-1 z-ldz = -I. ~
IIGIi~-i. IIG-iI12:: Idet GI
Plugging these in, we get
A*8A=8-1
And, since Idet GI = l.Ai - eiO I. . . l.An - eiO I, where .Ai, . .. ,.An are the eigenvaues of A,
or
A*8A-8=-I, which proves the lemma. .
¡IG-iI12:: IIA - eiO 111;-1 / ¡.Ai - eiOI.. .
:: (IIAII2 + it-i / (1 - p (A)t .
Since 8 is HerITtian, We now need a few bounds on the eigenvaues of 8. To get these bounds,
we note that for the parametrization
\
Z = eiO , -7f:: B :: 7f,
p (8) = 118112
1 ln :: 27f -n IIG-iii~ dB
_ (IIAII2 + 1)2n-2 8 = l- l7r (A* _ e-iO i) -i (A _ eiO i) -i dB
27f -7r
(1 - P (A))2n .
¡.An - eiOI
170
12. Slowly Varying Products
12,1 Convergence to 0
For (2), we use Hermitian forms. Of course,
171
Proof. Let q ? 1, q an integer to be determined. We consider the interval o :: k :: 2q,
(J (8) x*x :: x* 8x Xk+l = BqXk + ¡Bk - BqJ Xk. for al x. Setting x = Ay, we have
Since IIBsH - BslI :: € for al s, then (J (8)
y*A*Ay :: y*A*8Ay. II ¡Bk - BqJ Xk II :: Iq - klllxk II €.
Using that A*8A = 8 - I, we get
To shorten notation, let (J (8) (J (A * A) y*y :: y* 8y - y*y
A=Bq
or
f (k) = ¡Bk - BqJ Xk.
(1 + (J (8) (J (A* A)) y*y :: y* 8y.
So we have
Since this inequality holds for all y, and thus for al y such that 8y = (J (8) y,
XkH = AXk + f (k).
1 + (J (8) (J (A* A) :: (J (8).
By hypothesis p (A) :: ß, so p (ß-i A) -( 1. Thus, there is a positive defite Hermitian matrix 8 such that
1 :: (J (8) ,
(ß-1 A) * 8 (ß-1 A) - 8 = - I
Hence,
or the required inequality. .
A*8A = ß28 - ß2i.
We now consider the system
Let V (Xk) = X'k8Xk' Then Xk+l = BkXk ,
(12.2)
where
1. IIBklI :: K
V (Xk+i) = x'kA* 8Axk + f (k)* 8f (k) + x'kA* 8f (k) + f (k)* 8Axk.
(12.3)
Now we need a few bounds. For these, let a? O. (A particular a will
2. p (Bk) :: ß -( 1 for positive constants K, ß and al k ~ 1. Theorem 12.1 Using the system 12.2 and conditions (1) a'nd (2), there is an € ? 0 such that if ~
IIBk+l - Bkil :: € for all k, then (Xk) ~ 0 as k ~ 00.
be chosen later.) Since
(af (k)* - x'kA*) 8 (af (k) - AXk) ~ 0,
af (k)* 8f (k)+a-ix'kA* 8Axk ~ f (k)* 8Axk+X'kA* 8f (k),
Plugging this into (12.3), we have
V (Xk+i) :: (1 + a) f (k)* 8f (k) + (1 + a-i) x'kA* 8Axk = (1 + a-I) (af (k)* 8f (k) + x'kA* 8Axk) .
172
12, Slowly Varying Products
Continuing the calculation
12,1 Convergence to 0 173 Finally, we have
v (Xk+i) :: (1 + a-i) (af (k)* 8f (k) + ß2x'k (8 - I) Xk)
= (1 + a-i) (af (k)* 8f (k) + ß2v (Xk) - ß211xk112) .
a (8) IIx2qii2 :: p (ß2 + pq2f.2)2q IIxoii2 .
So, by Lemma 12.2
Now,
IIX2qll :: Vp (ß2 + pq2f.2)2q IIxoll. f (k)* 8f (k) :: p (8) IIf (k) 112 :: p (8) (q - k)2 f.211xk1i2 .
Now, choose f. and q such that
So, by substitution,
p (ß2 + pq2f.2)2q 0: 1
V(Xk+1)::(I+a-i) (ß2V(xk)+(ap(8)(q-k)2f.2_ß2) IlxkI12).
and set T = V P (ß2 + pq2f.2)2q
ß2
Let a = ,_" ,," n to get
so
v (Xk+i) :: (1 + a-i) ß2V (Xk)
= (ß2 + P (8) (q - k)2 f.2) V (Xk)'
IIX2qll :: T IIxoll.
This inequalty can be achieved for the interval ¡2q,4qJ to obtain IIX4qll :: T IIx2Qll j
By Lemma 12.2, continuing, p (8) :: (11A1I2 + 1)2n-2 (1 - P (A))2n
0: (K + 1)2n-2
IIX2(m+l)QII :: T I\X2mQII
which shows that xmQ -- 0 as m -- 00. Repeating the argument, for intervals ¡2mq + r, 2 (m + 1) q + rJ yields
- (1 - ß)2n
IIX2(ri+l)Q+rll :: T Ilx2mQ+rll,
Set
so X2mQ+r -- 0 as m -- 00. Thus, putting together Xk -- 0 as k -- 00. .
p = (K + 1)2n-2
(1 - ß)2n
Corollary 12.1 Using the hypotheses of the theorem
By continuing the calculation V (Xk+l) ~ (ß2 + P (q - k)2 f.2) V (Xk)'
lim Bk'" Bi = O. k-*oo Proof. By the theorem
lim Bk'" B1Xi = 0 k-*oo
Thus,
, and by iteration,
V (xi) :: (ß2 + pq2f.2) V (xo) ,
for al Xi. Thus,
lim Bk'" Bi = 0,
k-- 00 the desired result. . V (X2q) :: (ß2 + pq2f.2)2Q V (xo) .
174
12,2 Estimates of Xk from Current Matrices
12, Slowly Varying Products
175
Proof. By the triangle inequalty P (XkH, Vk) ::
12.2 Estimates of Xk from Current Matrices
Aixi,Ak .. .Aivi) + p(Ak" .
Let Ai, A2,. .. be n x n prilltive nonnegative matrices and Xi an n x 1
p(Ak" .
positive vector. Defie the system
+ . . . + P (AkAk-i Vk-i, AkVk)
A2Aivi,Ak .. .A2V2)
and using that Asvs = Àsvs for al s,
Xk+i = AkXk.
The Perron-Frobenius theory (Gantmacher, 1964) assures that each Ak has a simple positive eigenvalue Àk such that Àk :; IÀI for al other eigenvalues À of Ak. And there is a positive stochastic eigenvector Vk belonging to Àk' If the stochastic eigenvectors Vk, , . . , Vs ofthe last few matrices, Ak, . .. , As vary slowly with k, then Vk may be a good estimate of "~k'''~S",S,,. In this section we show when this can happen.
We make the following assumptions.
= p(Ak" .A2Aixi,Ak... A2Aivi) + p(Ak" .A2Vi,Ak" .A2V2)
+ . .. + P (AkVk-i, AkVk)
:: Ti~Jp (X2, Vi) + Tr;:1 Jp (Vi, V2) +,.. + Ti~Jp (Vk-i, Vk) which gives (12.4). .
If
1. There are positive constants m, and M such that
8 = sUPP(Vj,VjH),
j
m.. inf a~~)
then the theorem yields
- a(k)::O i3 '3
¡l£J k-i ¡oiJ
M :;-supa~~) i3 '
p(XkH,Vk):: Trr P(X2,Vi) + ¿Trr 8,
where inf and sup are over all i, j, and k.
j=i
2. There is a positive constant r such that
Thus, if in the recent past, starting the system at. a recent vector so k is smal, we see that if 8 and T r are smal, Vk gives a good approximation of Xk+i.
At+r'" At+i :; 0
This gives us some insight into the behavior of a system. For example, suppose we have only the latest tranition matrix, say A. We know
for all positive integers t.
These two conditions assure that
Xk+i = AXk
mr :: (At+r . .. AtH)ij :: nr-i Mr
t t. t ~
but don't know Xk and thus neither do we know Xk+i. However, we need
for al i, j, and t. Thus,
o es ima e II Ii' Xk+l 1
Let v be the stochastic eigenvector of A belonging to p (A). The theorem
ø (At+r'" At+i) ;: (nr~~r ) 2
tells us that if we feel that in recent past the eigenvectors, say Vi, , .. , Vk, didn't vary much and T r is small, then v is an estimate of ~11 Xk 111 . (We Xk+l 1
Set ø _ - nr-1Mr and Tr HV; .. 1. We see that ( mr)2 _- i-V;
llght add here that some estimate, reasonably obtained, is often better
than nothing at all.) Some numerical work is given in the following example.
TB (in:: Tr.
Tlreorem 12.2 Assuming conditions 1 and 2,
¡~J k-i ¡~J
P (Xk+i, Vk) :: Tr P (X2, Vi) + ¿ Tr P (Vk-j, Vk-i+i).
j=i
Example 12.1 Let
¡.2 .4 .4 J
(12.4)
A= .9 0 0 o .9 0
176
12, Slowly Varying Products
12,2 Estimates of Xk from Current Matrices
and let ~ be the set of matrices C, such that
177
And, using Theorem 10.5, TB (~3) :: 0.5195, so
A - .02A :: C :: A + .02A.
P(X51,V50):: 0.0899. Thus, ¡w~.3~~~WJa 2% variation in the entries of A. Now, we start with
The actual calculation is P(X5i,V50) = 0.0609, and the error is Xl = 0.3333 and randomly generate Ai = (aW J where
0.3232
error = 0.029.
(i) _ ( )
To see that 8 is always fite, we can proceed as follows. Let
aij - bij + rand .04 aij
for all i, j, where rand is a randomly generated number between 0 and 1
Av = Àv
and B = A - .02A. Then,
where A = Ak, V = Vk, À = Àk for some k. Suppose
X2 = AiXi
Xq = maxxk
and
k
_ X2 X2 = Ilx211l
where v = (Xl, . .. , xn)t. Then, since v is stochastic,
etc. We now apply this technique to demonstrate the theoretical bounds
1
given in Theorem 12.2.
xq ~-.
n
Let Vk denote the stochastic eigenvector for Ak; we obtain for a run of
50 iterates the data in the table. k 48 0.3430 Xk+1 0.3299 0.3262
Vk
p (Xk+l, Vk)
Now, since A is printive, Ar )- 0 for some r. Thus a~~J ~ mr for all 49 0,3599 0.3269 0.3132
0.3445 0.3470 0.3085
¡ 0.3474 J
¡ 0.3541 J
¡ 0.3476 J
0.3330 0.3196 0.0301 0.0224
0.3330 0.3129 0.0351 0.0403
0.3354 0.3170 0.0609 0.0314
50
p(Vk,Vk-i) Using Theorem 12.2 and three iterates, we have
i,j. Now
(NV)i Xi = IIArvlli
n (r)
nn, L aik Xk
k=i
L L a~~Xk 8=1 k=i
and since there are no more than nr-l distinct paths from any Vi to any
Vj, of length r,
X49 = A48X48 X50 = A49X49 X5i = A5oX50.
Xi ~ n n
(r) Xq aiq
L L nr-l MrXk 8=i k=l
mrx )q - n2nr-i MrXq
So iP (X5l, V50) :: TB (~3) P (X49, V48) + TB (~2) P (V48, V49)
+ TB (~)p (V49,V50).
mr
n2nr-iMr'
178
12,3 State Estimates from Fluctuating Matrices
12, Slowly Varying Products
Since this inequality holds for al i,
. Xi:; mr2 i :; O. min i - n nr- Mr
179
Hence,
(Xk)i (Vk + MVk)i
I (Xk+i)i - Àkl = I (ÀkVk + AkMvk)i - Àk (Vk + MVk)i I (Vk +-MVk)i = I (AkMvk)i Àk (MVk)i I
And, from this it follows that p (Vj, vj+i) is bounded. We add to our assumptions.
(Vk)i , I (AkMvk)i - Àk (MVk)i I
3. There are positive constants ß and À such that
Vk i kmi - (AkMvk)i () -I - À '\ , IIAkMvklloo + À ' Vk i _ () kmi
_ki
IIAklloo :: ß and Àk:: À
, IIAklloo IIMlIoo IIvklloo + À m'
for all k. And 'Y :; 0 is a lower bound on the entries of Vk for all k.
'Y
:: ß IIMlloo + Àk IIMlIoo '
An estimate of Àk can be obtained as follows.
'Y
And since by Theorem 2.2, IIMlloo :: eP(Xk,Vk) - 1, we get the bound
Theorem 12.3 Assuming the conditions 1 through 3, :: (~ + Àk) (eP(Xk,Vd - 1) ,
(Xk)i 'Y
Now we can write
I (Xk+i)i - Àkl :: (~ + À) eP(Xk,Vk) p (Xk, Vk).
eU - 1 :: ueu
Proof. Using Theorem 2.2, for fied k, there is a positive constant r and a diagonal matrix M, with positive main diagonal, such that the vectors Xk
for any u ~ 0, so we have
and Vk satisfy
(Xk)i 'Y
I (Xk+i)i - Àkl :: (~ + À) eP(Xk,Vk) P (Xk, Vk)
Xk=r(Vk+Mvk).
for al i. .
From this theorem, we see that if
Thus,
the Vk'S and Xk'S are near, then (X(k+)l); Xk i
is an estimate of Àk. Of course, if the Vi'S vary slowly then the Xi+ls are close to the vi's and are thus themselves close, so the vi's and xi's are close. Xk+l = AkXk
= r (ÀkVk + AkMvk),
12.3 State Estimates from Fluctuating Matrices and ~o
Let A be an n x n prinutive nonnegative matrix and Yi an n x 1 positive
(Xk+i)i _ r (ÀkVk + AkMvk)i (Xk)i - r (Vk + MVk)i
vector. Defie Yk+! = AYk.
180
12.3 State Estimates from Fluctuating Matrices
12, Slowly Varying Products
It can be shown that (lI;kt) converges to 7r, the stochastic eigenvector
Proof. Let x :; O. For simplicity, set
belonging to the eigenvaue p (A) of A.
Zk = (Ax)k
Let A¡, A2,... be fluctuations of A and consider the system
XkH = AkXk (12.5)
ek = (Exh . Then
where Xi :; O. In this section, we see how well 7r approximates lI:kÎli' sup- =
I(Ex)il leilxi +... + einxnl sup
x~o (Ax)i x~o aiiXi +... + ainxn
especialy for large k.
It is helpful to divide this section into subsections.
.: sup £iiXi
+... + £inXn
- x~o ailXI + . . . + ainXn and by using the quotient bound result (2.3),
12.3.1 Fluctuations
By a fluctuation of A, we mean a matrix A + E :: 0 where the entries in E = ¡eijJ are smal compared with those of A. More particularly, we
£ij ':max- aij~O aij
suppose the entries of E are bounded, say I eij I :: £ij
=RE. Futhermore, using that
z. + ej = z' 1 + e'-l -l Z' J
where
J
aij - £ij :; 0
and that when aij :; 0 and £ij = 0 when aij = O. Thus,
Zi 1 Zi+ei = 1+~' Zi
A - £ :: A + E:: A + £.
we have
Defie
(AX)i ((A + E) x)j _ ~ Zj + ej
8 = supp(Ax, (A + E) x)
((A + E) x)i (Ax)j - Zi + ei Zj
-- 1+~ -1 + 2.
where the sup is over al positive vectors x and fluctuations A + E. To
.: .
show 8 is fite, we use the notation,
Zi
I+RE
£.. aij
- l-RE
RE = max -3
, .
where the maxmum is over al aij :; O.
Theorem 12.4 Using that RE.: 1,
8::Inl+RE l-RE'
Thus, T'' p (Ax, (A + E) x) :: In 1..+i'RE
the inequalty we need. .
181
182
12,3 State Estimates from Fluctuating Matrices
12. Slowly Varying Products
12.3. 2 Normalized Trajectories Suppose the trajectory for (12.5) is Xi, X2,..,. We normalize to stochastic vectors and set
_ Xk
Xk = IIxklll
12.3.3 Fluctuation Set
The vectors Xk need not converge to 7r. What we can expect, however, is that, in the long run, the Xk'S fluctuate toward a set about 7r. By using Theorem 12.5, we take this set as
1. 1 - Tr f
C = f x E S+ : P (x, 7r) :: ~ + (r - 1) o 1. .
We wil assume that TB (Ar) = Tr 0: 1. How far Xk is from 7r is given in the following theorem.
Theorem 12.5 For all k and 00: t :: r,
Using
d (x, C) = minp (x, c),
p (7r, XkrH) :: T~P (7r, Xi) + (T~-i + .. . + T r + 1) ro + (t - 1) o.
eEC
Proof. We fist make two observtions.
1. For a positive vector x and a positive integer t,
we show that
d(xk,C) -t 0 as k -t 00.
P (Atx, At... Aix) :: p (Atx, AAt-i . . . Aix) + P (AAt-i . . . Aix, At. . . Aix) :: p (At-lx, At-i . , . Aix) + o, and by continuing,
We need a lemma.
Lemma 12.3 If x E S+ and 0 :: a :: 1, then p (7r, x) = p (7r, a7r + (1 - a) x) + p (a7r + (1 - a) x, x) .
:: (t - 1) o + o = to.
Proof. We assume without loss of generality (We can reindex.) that
2. For all k )- 1,
7ri 7r n -)-.")--. Xi - - Xn
P (7r, Xkr+1) = P (Ar7r, ArX(k_i)r+1)
+ p (ArX(k_i)r+i. Akr' . . A(k-i)r+1X(k-i)r+i) :: T rP (7r, X(k-i)r+1) + ro
Thus, if i 0: j, then
and by continuing
-'7r')-7r' -l
Xi - Xj
p (7r, Xkr+i) :: T~P (7r, xJ + (T~-i +... + Tr + 1) ro.
Now, putting (1) and (2) together, we have for 0 0: t :: r,
or 7riXj ~ 7rjXi.
p (7r, XkrH)
= p (At-l7r, Akr+t-i .:. Akr+ixkr+i)
/':: P(At-i At-l)+ (At-iA' - ) 7r, Xkr+i P Xkr+i, kr+t-l'.'A kr+iXkr+l
So
a7ri7rj + (1 - a) 7riXj ~ a7ri7rj + (1 - a) 7rjXi
li 0:- p (7r, Xkr+l) + (t - 1) o :: T~P (7r, Xl) + (T~-i + . .. + T r + 1) ro + (t - 1) O,
the desired inequalty. .
183
and
7r' i )-7r. J
a7ri+(I-a)xi - a7rj+(I-a)xj
184
12,3 State Estimates from Fluctuating Matrices
12. Slowly Varying Products
185
Thus,
From this, we have that
d(xkr+t'C):: T~P(Xi,7l),
p(7l,X) = In 7li Xn
which is what we need. .
Xi 7l n
=In,( 7li a7ln+(I-a)xn)
a7li +(1 - a) Xi 7ln
+ In (a7li +(I-a) Xi Xn ) Xi a7ln+(I-a) Xn
Using the notation in Chapter 9, we show how C is related to limiting sets.
Corollary 12.2 If U is a compact subset of S+ and L;U -- L as k -- 00, then L ç C.
= p(7l,a7l + (1 - a) x) + p(a7l + (1 - a)x,x),
Using this corollary, Theorem 12.4, and work of Chapter 10, we can compute a bound on L, even when L itself canot be computed.
as required. .
We conclude this section by showing how a pair Xi, xi+i from a trajectory
The theorem follows.
indicates the closeness of Xi to C.
Theorem 12.6 For any k and 0 .. t :: r,
Theorem 12.7 If Tr .. 1, then
d(xkr+t'C):: T~p(xi,7l).
d (Xi, C) :: -1 r p (Xi, Xi+!).
-Tr
Proof. If Xkr+t E C, the result is obvious. Suppose Xkr+t t/ C. Then choose a, 0.. a .. 1, such that
Proof. Throughout the proof, i wil be fied. Generate a new sequence
x (a) = a7l + (1 - a) XkrH satisfies
Xi,.., ,xi,AiXi,Atxi,." . Since Ai is primitive, using the Perron-Frobenius theory
r8
Afxi
p(x(a),7l)=I_Tr +(r-l)8.
Thus, x (a) E C. By the lemma
lim -,II = 7li, k-+= IIAi Xi i
the stochastic eigenvector for the eigenvalue p (Ai) of Ai. Thus, lim p (A~Xi' 7li) = 0, k-+=
P (Xkr+t, 7l) = P (XkrH, X (a)) + p (x (a), 7l)
, -Tr
=P(Xkr+t,x(a))+-1 r8 +(r-l)8.
Hence, using the sequence
Now, by Theorem 12.5, we have
,
, - Tr
P (Xkr+t, 7l) :: T~P (Xl, 7l) + -1 r8 + (r - 1) 8,
Al, A2, , .. , Ai, Ai, Ai, ., .
since Theorem 12.6 stil holds,
d(7li,C) = 0
so
P(Xkr+t,x(a)):: T~p(xi,7l).
and so 7li E C.
186
12. Slowly Varying Products
12.4 Quotient Spaces
Now, using the triangle inequalty
187
Let 2; be the set of matrices C such that
P (Xi, Afr+txi+i) :: P (Xi, XiH) + P (AiXi, AiXi+i)
A - .02A :: C :: A + .02A,
+... + P (Afr+txi, Afr+txiH) :: rp (Xi, XiH) + rTrP (Xi, Xi+i) + . . . + rT~p (Xi, Xi+i)
r ::-1 -Tr P(Xi,XiH)'
thus allowing for a 2% variation in the ent¡ri~~3~~:i'
The stochastic eigenvector for A is 7r = 0.3331 . Starting with Xi = 0.3174
¡ 0.3434 i 0.3333 0.3232
Now, letting k -- 00,
r
and randomly generating the Ak 's, we get
_ XkH
P (Xi, 7ri) :: -1 P (Xi, Xi+i) - Tr
Xk+i = AkXk and Xk+i = -II II'
Xk+i i
and since 7ri E C, d (Xi, C) :: -1 r P (Xi, XiH) ,
Iterations 48 to 50 are shown in the table.
-Tr
as desired. .
k
The intuition given by these theorems is that in fluctuating systems, the
Xk+i
iterates need not converge. However, they do converge to a sphere about
7r. See Figure 12.1 for a picture. P(Xk+i,7r)
48 0.3440 0.3299 0.3262 0.0432
49
50
0.3599 0.3269 0.3132 0.0483
0.3445 0.3470 0.3085 0.0692
Using three iterates, we have P (X51, 7r) :: TB (A3) P (7r, X48) + 2ó = 0.1044.
This compares to the actual difference
P (x5i, 7r) = 0.0692. The error is FIGURE 12,1, A view of iterations toward C.
error = 0,0352.
An example providing numerical data follows.
Ex~ple 12.2 Let
12.4 Quotient Spaces .2 .4
A= ¡ .9 0
o ,9
.4 i
o, o
The trajectory Xi, X2, . .. determined from an n x n matrix A, namely, Xk+i = AXk
-188
12. Slowly Varying Products
12.4 Quotient Spaces
may tend to inty. When this occurs, we can stil discern something about
189
Since this max is achieved for some Ck, it follows that eauality holds.
the behavior of the trajectory. For example, if A and Xl are positive, then
we can look at the projected vectors ii:kt. In this section we develop an
additional approach for studying such trajectories. We do this work in Rn
We conclude this subsection by showing how close a vector is to a coset. To do this, we defie the distance from a vector y to a coset x + W by
so that formulas can be computed for the vaious norms. Let e be the n x 1 vector of l's. Using Rn, defie
tel.
W = span
The quotient space R' /W is the set
d(y,x + W) = min Ily - (x + w)lll' wEW
We need a lemma.
Lemma 12.4 Let C E C where C = (Cl,'" , en). Then
tX+ W: x E Rni
2 i 2 i i-n i
~ maxc. - ~ minc. ? ..LLCLL .
where addition and scalar multiplication are done the obvious way, that is,
(x + W) + (y + W) = (x + y) + W, a (x + W) = ax + W. This arithmetic is well defied, and the quotient space is a vector space.
Proof. Without loss of generality, suppose that c = (Pi, , . . , Pr, ai , . , . , as)
12.4.1 Norm on Rn/w
where r + 8 = nand
Let Pi 2: . . . 2: Pr 2: 0 2: ai 2: . . . 2: as'
r s
C = t c : ctw = 0 for al w E Wl and
Note that L Pk = - L ak. Ci = t c E C : iicii = 1 l.
(Cl depends on the norm used.) Then for any x E Rn/w, ¡Ix + Wllc = max Ictxl, eECi
It is easily seen that 11.11 c is well defied and a norm on Rn /W.
Now,
k=i k=l
1 i 1 (pi + ' . . + Pr ) 1 (al + . . . + as)
1 1
2"Pi - 2"as 2: 2" r - 2" 8 = 2r (Pi + . .. + Pr) - 28 (al + . .. + as)
Example 12.3 Let 11'111 denote the I-norn. It is known that, in this case, Cl is the convex set with vertices those vectors with precisely two nonzero
entries, l and - l. Thus,
IIx + Wllc = max Ictxl ' eECi s
and if c = L akCk, a convex sum of the vertices Ci,. .. , Cs of Ci, then
28(Pi + .. . + Pr) = (~2r+ ~)
2 (P , 2:r-+ l+"'+Pr) 8
1 1 r+8 r+8
= - (Pi +... + Pr) - - (ai +... + as)
k=i
1
s
,
iix + WLLC ::eECi max L aklc~xl k=l
=maxl4xl k 1
= -2 maxlxp - xql. p,q
= r + s Ilclli , the desired result. .
Using the I-norm to determine Cl, we have the following.
Theorem 12.8 Suppose lI(y + W) - (x + W)llc :: €. Then we have that d(y,x + W) :: n€.
12.4 Quotient Spaces 191
190 12. Slowly Varying Products
Proof. First suppose that y, x E C. Then, using the example and lemma, we have lI(y + W) - (x + W)lIc
= (~mrx (Yi - Xi) - ~ nr (Yj - x j) )
It can be observed that this is a coset map, not a set map. In terms of sets, A (x + W) ç Ax + W with equality not necessarily holding. The map A: Rn /W -+ Rn /W is well defined and linear on the vector space Rn /W. Inverses, when they exist, for maps can be found as follows. Using the Schur decomposition
A=P(~ 1Jpt
i=i ~ (~tIYi-Xil) 1
where P is orthogonal and has In as its fist colum. If B is nonsinguar,
= -IIY n - xlli .
set
Now, let X,Y ERn. Write x = x + Wi, Y = iì + W2 where x,iì E C and
A + = P (~ B~ 1 J pt,
Wi, W2 E W. Then, using the fist part of the proof,
II(Y + W) - (x + W)lIc = ii(iì + W) - (x + W)llc ~ .! Iliì - xlli n 1 = -11(Y - W2) - (x - wi)lIi
n 1
(Other choices for A+ are also possible.) Lemma 12.5 A + is the inverse of A on Rn /W.
Proof. To show that A+: W -+ W , let W E W. Then W = ae for some scalar a. Thus,
=-lIy-(x+w)111 n
A+w = A+ (ae)
where W = W2 - Wi. And, from this it follows that
= aP (p oY B-iJ pt e
d (y, x + W) :: nE,
- aPp0 Y B-1,¡ 0
( J(nJ
which was requied. .
= aP ( p t J
12.4.2 Matrices in Rn / w Let A be an n x n matrix such that
= ape E W Now,
A :W -+ W
AA+ = P (p2 py + yB-1 J t
o I P.
Thus Ae = pe for some real eigenvaue p. (In applications, we will have
p = p(A).)
If x E C, then
Defie
,
A: Rn/W -+ Rn/W
by
AA+X=P( ~ =P (~2
A (x + W) = Ax + W
PY + ¡B-i J ptx
PY + yB-1 J ( 0 J
I P2x
192
12, Slowly Varying Products
12.4 Quotient Spaces
193
where ak is the k-th row of A. Since iix + Wile = 1,
where pt = ¡ ~ l
1
-maxlx. - x-I = 1.
2 -,J" _ J
= p r (py + yB-i) P2X J
L P2X
=p( P2X ßJ where ß = (py + yB-i) P2X,
et
= ß .. + P2P2X
And, since x + ae E x + W for all a, we can assume that Xi is nonnegative
for all i and 0 for some i. Thus, the largest entry Xi in x is 2. It follows that
IIa; I (ai - aj) xl -,J over all x, 0:: Xi :: 2 is achieved by setting Xk = 2 when the k-th entry in ai - aj is positive and 0 otherwise. Hence,
e =ß..+XEX+W
Thus, AA+ (x + W) = x + Wand since x was arbitrary AA+ is the identity on æi jW. Sinularly, so is A+ A. So A+ is the inverse of A on Rn jW. .
i,J iJJ
IIa; I (ai - aj) xl = IIa; lIai - aj II i . Thus, 1
IIAx + Wile = -2 IIa; Ilai - ajlli -,J
When A : W -t W, we can defie the norm on the matrix A : Rn jW -t Rn jW as
and so 1
IIAII = max Ilx IIAx + Wile e x~w + Wile
= max IIAx + Wile' IIx+wllc=i
IIAlle = -2ma; -,J Ilai - aj lIi .
To obtain the usual notation, set
For special norms, expressions for norms on A can be found. An example for the I-norm follows.
Ti (A) = IIAlle . This gives the following result.
Example 12.4 For the I-norm on Rn: Define
Theorem 12.9 Using the I-norm on Rn,
IIAII = max IIX IIAx Wile e x~w + +Wile
IIAlle = Ti (A) .
= max IIAx + Wile' IIx+wllc=i
Now
IIAx + Wile = max eEei Ict Axl
12.4.3 Behavior of Trajectories To see how to use quotient spaces to analyze the behavior of trajectories, let
which by Example 12.3, ~
Xk+i = AXk + b 1
- max la'x - a 'xi
2 -,J,,- J
where A : W -t W. In terms of quotient spaces, we convert the previous equation into
1
= -maxl(a'-a')xl 2 " _ J -,J
xk+i + W = A (Xk + W) + (b + W) .
(12.6)
194
12.4 Quotient Spaces
12, Slowly Varying Products
195
To solve this system, we subtract the k-th equation from the (k + 1)-st one. Thus, if we let
ZkH + W = (xk+i + W) - (Xk + W) ,
then Zk+i + W = A (Zk + W) so
ZkH + W = Ak (zQ + W) .
Using norms,
IIzkH + Wile:: 71 (A)k Ilzi + Wile'
(12.7)
If 71 (A) -: 1, then Zk + W converges to W geometricaly. As a consequence, (Xk + W) is Cauchy and thus converges to say x + W. (It is known that the quotient space is complete.) So we have
x + W = A (x + W) + (b + W) .
FIGURE 12.2. Iterates converging to W, Then, using (12.9) with x = 0, we have
d (Xk, W) :: 271 (A)k IIXl + Wile'
(12.8)
Then, since Ti (A) = .5,
Now, subtracting (12.8) from (12.6), we have
Xk+l - x + W =A (Xk - x) + w.
d (Xk, W) :: 2 (.5)k Ilxl + Wile' So, Xk converges to W at a geometric rate.
Thus, by (12.7),
A sample of iterates, letting Xi = ( ~ J, follows in the table below. By
Ilxk-i - x + Wile:: 7i (A)k Ilxi - x + Wile'
direct calculation, Ilxl + Wile = .5.
And, using that d(xk - x, W) = d(xk,x + W), as well as Theorem 12.8, d (Xk, x + W) :: n7i (A)k ¡IXi - x + Wile'
k
4
8
12
d(xk, W)
(0,763,0,3700) 0,125
(1.073,1.069) 0.0078
(1.569,1.569) 0.0005
(12.9) Xk
It follows that Xk converges to x + W at a geometric rate.
Example 12.5 Let A = (_:~ :~ J and
After 12 iterations, no change was seen in the
first
four digits of
Extending a bit, let Xk+l = AXk.
Ai = (.8,3 .3 J '.8 A2 = .5 (.2 .5 .2 J ' A3.9 = (, .7.7 .9 J
Nole that (Ak) tends componentwise to 00. The eigenvalues for A are 1.1 and .5, with 1.1 having ei~envector e = ( ~ J. Let
W = span t e J .
the Xk 'So
However, growth in the direction of e still occurred, as seen in Figure 12.2.
and ~ = tAi, A2, A3J.
196
12. Slowly Varying Products
12.4 Quotient Spaces
Since W, for each matri in E, is span r e L where e = ( ~ J, and Ti (E) =
197
at a geometric rate. Noting that
m?X T (Ai) = .5, we have the same situation for the equation
d (D-iYk,D-1W) :: m?X Idiii d(Yk, W),
i
i
it follows that
Xk+l = AikXk
d(xk,D-iW) converges to 0
where (Aik) is any sequence from E.
The followig examples show vaious adjustments that can be made in applying the results given in this section.
at a geometric rate.
Example 12.7 Consider
Example 12.6 Consider
XkH = AXk + b Xk+l = AXk
where A = (:~ :i J and b = ( ~ J. Note that e = ( ~ J is an eigen-
where
vector of A belonging to the eigenvalue 1.1 and so we have W = spanrel. .203 .604 A = Lr 2.~2
o
2.02
n
Further, Ti (A) = .3. The corresponding quotient space equation is
Xk+i + W = A (Xk + W) + (b + W) .
The sequence (Xk + W) converges to, say, x + W. Thus,
H.. th ,;,enva.," of A are 1.01, -.4060, and 0 with ¡ ~ i an eigen-
vector belonging to 1.01. Let D = diag (1, 2, 4). Then
x + W = A (x + W) + (b + W) . Solving for x + W yields
DXk+l = DAD-i DXk
or
(I - A) (x + W) = b + W, so
(x + W) = (I - A)+ (b + W),
YkH = BYk
where Yk=Dxk and B = DAD-i. Here ¡ .604
B = ' 1.01
- 0
where
.406 0 i
(I - A)+ = (.9 .2.2.9J '
o0.
1.01 0
and thus (I - A)+ b = ( 123 J '
and."" ,"envector of B for 1.01 is ,~ ¡ ¡ 1- So we have W ~ spa (, ¡. Now, Ti (B) = 1.01; however, Ti (B3) ~ .1664. Thus, frm (12.9),
d (Yk, W) converges to 0
It follows by (12.8) that
Xk + W ~ ( 123 J + W,
198 12. Slowly Varying Products
13
or using Xi = ( ~ J,
Systems
d(Xk,X + W) :: 2 X .3k X IIx + Wile :: 2 x .3k x .35:: .7 x .3k.
A few iterates follow. k
2
4
8
Xk
(2.5, 3.8)
(6.253, 7.70)
d(Xk,X + W)
0.063
(16.44, 17.87) , 0.000046
0.00567
12.5 Research Notes The results in Section 1, slowly varying products and convergence to 0,
are basicaly due to Smith (1966a, 1966b). Some alterations were done to obtain a simpler result. Section 2 contain a result of Artzrouni (1996). For other such results, see Artznouni (1991). Application work can be found in Artzroun (1986a, 1986b).
Section 3 is due to Hartfiel (2001) and Section 4, Hartfiel (1997). Rhodius (1998) also used material of this type.
Often bound work is not exact, but when not exact, the work can stil
give some insight into a system's behavior. In related research, Johnon and Bm (1990) showed for slowly vaying positive eigenvectors, p (Ai . . . Ak) ~ p (Ai) . . . P (Ak). Bounds are alo provided there.
This chapter looks at how infte products of matrices can be used in
studying the behavior of systems. To do this, we include a fist section to outline technques.
13.1 Projective Maps Let E be a set of n x n row allowable matrices and X a set of positive n x 1
vectors. In this section, we outline the general idea of finding bounds on the components of the vectors in a set, say ES X or E~X. Basically we use that for a convex polytope, smalest and largest component bounds occur at vertices as depicted in Figue 13.1.
Let E also be a colum convex and U a convex subset of positive vectors.
If E = convex tAi,.,. , Ap)-
and ~
U=conveXtXi,... ,xq)-, then, as shown in 9.3, EU is a convex polytope of positive vectors, whose
vertices are among the vectors in V = tAiXj : Ai and Xj are vertices in E
200
13, Systems
-~
13,2 Demographic Problems
201
4. Repeat (1) and (2). Mter the k + I-st run, set
i 1.i,iJ'i l.i,if
i\k+i) = rrn r i\k) x,l h\k+1) = max r h~k) x,l
£ ( (k+i)) ( (k+1))
and orm Lk+i = li , Hk+1 = hi .
5. Continue for sufciently many run. (Some experimenting may be required here.)
13.2 Demographic Problems This section provides two problems involvig populations, partitioned into
vaious categories, at discrete interva of time. FIGURE 13,1. Component bounds for a convex polytope.
Takng a small problem, suppose a population is divided into three groups: l=young, 2=rrddle, and 3=01d, where young is aged 0 to 5, rrddle 5 to 10, and old 10 to 15.
Let x~i) denote the population of group k for k = 1,2,3. After 5 years,
and U, respectively 1. Thus, if we want component bounds on ES X, we need only compute them on Ai. . . . Aii Xj over all choices of is, . .. , ii, and j. For Ep, component bounds are found by fidig them on WAi. O. . . 0 wAii (Xj)
suppose this population has changed to
(2) (i) (i) (i)
Xi = bl1xi + b12X2 + bi3x3
over al choices of is,'" ,ii, and j.
To compute component bounds on these vectors, we use the Monte-Carlo method.
x~2) = 82ix~1) x~2) = 832X~i)
or
Component Bounds
1. Radoiiy (unform distribution) generating the vertex matrices in-
X2 = AXi
volved, compute
1 , 2 , 3 - , ,
where Xk = (x(k) x(k) x(k)) for k - 1 2 and x = Aiixj or x = wAii (Xj).
b12 bl1 A = Lr 8~1
2. Suppose x = Ai,...Aiixj or x = WAit o",oWAii (Xj) have been
found. If t -( 8, randoiiy (unorm distribution) generating the vertex matrix involved, compute ~
x = Ait+i .. .
s i8 1.1 -', Aiixj or x = WAit+i 0... 0 WAii (Xj).
832
The matrix A is caled a Leslie matri. Continuig, after 10 years, we have
X3 = AX2 = A2xi,
Continue until x = Ai ... Aii Xi' or x = WA" 0... 0 W A- (xi") is found.
3. Set Li = Hi = x.
b~3 J
o
etc.
202
13, Systems
13,2 Demographic Problems
Data indicates that birth (the bij's) and surviva (the Sij'S) rates change
Final wetors for 10 iterates.
during time periods, and thus we wil consider the situation
I ... .
0.41
Xk+i = Ak . . . Aixi
0,405
where Ai, . ,. , Ak are the Leslie matrices for time periods 1, . .. , k. In this
0.4 0.395
ø ~ 0.39 '"
Example 13.1 Let the Leslie matri be .4 J
A= ,9 0 o . o .9
ii . :I¡~ .....~..t.i ii :. :
'. :~;.~;:i;~... '.:: \..
:, '.. ...~~ ::1'::\ ii .
section, we look at component bounds on XkH'
¡.2 .4
203
Allowing for a 2% variation in the entries of A, we assume the transition
~ i~:,' .~ y.......~ '~¡ .,' ~~.' .:''''::r. . ."i:~: . . .. ...~
0,385
:~... v""~n''':., .. .r.., ":"'.~'\':~':1: :,.. .' '. "Il- ..'l~":'ol" '.
0.38
. : .......~l.l...;..:.:_. . .
0,375
o
'. S~l..' :\-l~(:(.:.....: i, '. .......~:'~,'-",..
i,.";1\ , 't.', i'
._.i''',' I ...'i'. i. :.'
. .; .....:~~ .-."!..:~~:
i O,37~ I
0,67 0,68
. '. '. . -0.69
matrices satisfy
0.7
0.71
0.72
x axis
A - .02A :: Ak :: A + .02A
FIGURE 13,2. Final vectors of 10 iterates,
for all k. Thus, E is the convex polytope with vertices
to map S+ into R2.
C = ¡aij :I .02aijJ .
Recall that E~ox is the convex hull of vertices. Yet as can be seen, many, many calculations Akio... AkiX do not yield vertices ofE~ox. Infact, they
¡ 0.3434 J
We start the system at x = 0.3333 , and estimate the component
end up far in the interior of the convex hull.
0.3232 bounds on E~ox, the 50-year distribution vectors of the system by Monte
the lower and upper bounds after 200,000 runs, namely
Taking some point in the interior, say the projection of the average of
Carlo. We did this for 1000 to 200,000 runs to compare the results. The results are given in the table below.
k 1000 5000 10, 000 100, 000 200, 000
ave = (0,3514,0,3425,0.3062) ,
Lk
Hk
(0.3364,0,3242,0.2886) (0.3363,0.3232,0.2859) (0.3351,0.3209,0.2841) (0.3349,0.3201,0.2835) (0.3340,0,3195,0.2819)
(0.3669,0.3608,0.3252) (0.3680,0.3632,0.3267) (0.3682,0.3635,0.3286) (0.3683,0.3641,0.3313) (0.3690,0.3658,0.3318)
we can empirically estimate the probability that the system is within some specified distance 8 of average. Letting c denote the number of times a run
ends with a vector x, IIx - avellcx ' 8, we have the results shown in the table below. We used 10,000 runs.
Of course, the accuracy of our results is not known. Still, using experimental probability, we feel the distribution vector, after 50 years, will be
bounded by our Land H, with high probability. A'picture of the outcome. of 1000 runs is shown in Figure 13.2. We used
T=rO v' 4J
lO 0 ~ 2
~,
8 c ,005 1873 .009 5614
.01 6373 .02 9902
Interpreting 8 = .01, we see that in 6373 runs, out of 10,000 runs, the result x agreed with those of ave. to within .01.
204
13,3 Business, Man Power, Production Systems
13. Systems
205
The probabilities of the drivers' actions on (1) and (2) are given by the matrices
Ten Iteraes of a traectory.
0.415 0.41
0.40~ ~ o0.3951 0.41 I I_ ~
A = ( ,55 .6.45 .4J '
B = .4 .6 ( 5 .5 J
for each of the towns, as seen from the diagram in Figure 13.4.
0.391 --r
.55
0.38~__.L/// l' '"
.4
0.38r l/ L~/)) 0,3751
0,68 0,685 0,69 0,695 0,7 0,705
0.71
x axis
806
FIGURE 13.4, Diagram of taxi options.
FIGURE 13.3. Ten iterates of a trajectory,
We can get the possible probabilities of the cab driver being in (1) or (2) Finally, it may be of some interest to see the movement of Xi, X2, . , . , XlQ
for some run. To see these vectors in R2, we again use the matri
T- 0 02-l
¡o vI .YJ
by finding 2;CX where 2; = iA, BL, a T-proper set. Here E = ( ~ J and the
corresponding subspace coeffcient is TW (2;) = ,2. Three products should be enough for about 2 decimal place accuracy. Here,
2
A3 = (0,5450 0.4550 J 0,5460 0.4540 '
and plotted TXi, TX2,. .. ,TxlQ. A picture of a trajectory is shown in Fig-
A2 B = (0.4550 0.5450 J 0.4540 0.5460
ure 13.3.
AB2 = (0.4450 0,5550 J 0.4460 0.5540 '
In this figure, the starting vector is shown with a * and other vectors with a o. The vectors are linked sequentually by
segments to show where vectors
go in proceeding steps.
13.3 Business,
BAB = (0.4550 0.5450 J
Man Power, Production Systems
ABA = (0.5550 0.4450 J 0.5540 0.4460
0.4560 0,5440 '
B2 A = (0,5550 0.4450 J 0.5560 0.4440
BA2 = (0.5450 0.4550 J 0.5440 0.4560 '
BA2= (0.5450 0.4550 J 0.5440 0.4560
B3 = (0.4450 0.5550 J
Three additional examples úsing inte products of matrices are given in
0.4440 0.5560 .
this section.
Example 13.2 A taxi driver takes fares within and between two towns, say'Ti and T2. When without a fare the driver can 1. cruise for a fare, or
2. go to a taxi stand.
If Pij = probability that if the tax driver
is in i initially, he eventually (in the long run) ends in j,
206
13.3 Business, Man Power, Production Systems
13, Systems
then
207
then our model would be .44 :: Pll :: .56
.44 :: Pi2 :: .56
.44 :: P21 :: .56
.44 :: P22 :: .56.
Note the probabilities vary depending on the sequence of A's and B 'so How-
Xk+l = xkAk + b
(13.1)
where b = (ß,O) and numerically,
ever, regardless of the sequence, the bounds above hold. In the next example, we estimate component bounds on a liting set.
Example 13.3 A two-phase production process has input ß at phase 1. In both phase 1 and phase 2 there is a certain percntage of waste and a certain percentage of the product at phase' 2 is returned to phase 1 for
- (0.105 0 J. ( 0.095 0 0.90250J 0: k A 0: 0 0.9975 If we put this into our matri equation form, we have (I,Xk+l) = (l,xk) (~ lk J '
a repeat of that process. These percentages are shown in the diagram in
Figure 13.5. .10
ß ~
(We can ignore the first entries in these vectors to obtain (13.1).) Then L is convex and has vertices
¡i ß 0 J o .095 0 ¡i ß 0 J A2 = 0 0 .9025 , o .105 0 ¡i ß 0 J As = 0 0 .9975 , o .095 0 ¡i ß 0 J A4 = 0 0 .9975 .
Ai = 0 0 .9025 ,
I ~I .~ ~.05 I I .~ .05
FIGURE 13,5, A two-phase production process. For the mathematical model, let aij = percentage of the product in
o .105 0
process i that goes to process j.
Then
As in the previous example, we estimate component bounds on yLlO.
A = (0 .950J . .10 And if we assume there is a fluctuation of at most 5% in the entries of A at time k, then
A - .05A :: Ak :: A + .05A.
~' - l' 2
Thus if Xk - (xCk) xCk)) where
Using ß = 1, Y = (1,0.5,0.5), and doing 10,000 and 20,000 runs, we have the data in the table below.
no. of runs
L
H
10, 000 20, 000
(1, 1.0938, 0.9871)
(1, 1.1170, 1.1142)
(1, 1.0938, 0.9871)
(1, 1.1170, 1.1142)
We can actually calculate exact component bounds on yLoo by using
xik) = amount of product at phase 1
L = yA~O = (1, 1.0938, 0.9871)
x~k) = amount of product at phase 2,
H = yA10 = (1, 1.1170, 1.1142).
208
13, Systems
13,3 Business, Man Power, Production Systems 209
i
Final \ectors br 100 runs
',14r
"'21
... n.
110
II .
1,1
3
.t )' 1\
00 .
U.
.. .
loss
i..
fO .
1.08
/.05 ,o5,,
1= 1.06
~
1.04
,.02f
0,98
.I.
.. 0
n. u.
1 ~ :::
¡ It.
1:09 1.095 1.1
1.105 1.11 x axis
2
II . II .
.10
1.115 1.12 1.125
FIGURE 13,7, Management structure,
FIGURE 13,6. Final vectors for 1000 runs.
Thus, our estimated bounds are corrct. To see why, it may be helpful to
we have IIBlId = IID-i BDlli for any 3 x 3 matri B, and so
plot the points obtained in these runs. Projected into the yz-plane (All x
TW (E) = 0.2294.
coordinates are 1.), we have the picture shown in Figure 13.6. Observe that in this picture, many of the points are near vertices. The picture, to some extent, tells why the estimates were exact.
By Theorem 9.5,
To estimate convergence rates to yEOO, note that E is T-proper where
E~ ¡ ~ J .
h (yEk, yEOO) :: TW (E)k h (y, yEOO)
(13.2)
which shows more rapid convergence.
The last example concerns management structures. Thus,
Example 13.4 We analyze the management structure of a business by TW (B) = maxfllb2l1i' Ilb3l1il,
where bk is the k-th row of BEE. So,
partitioning all managing personal into categories: 1 = staff and 2 = executive. We also have 3 = loss (due to change of job, retirement, etc.) state. And, we assume that we hire a percentage of the number of people lost.
Suppose the 1 year flow in the structure is as given in the diagmm in TW (E) = ,9975. The value of TW (E) can be made smaller by simultaneously scaling rows
and columns to get each row sum the same. To do this let
¡i 0
D= 0 1 ,
o 0
Figure 13.1. If Pk = (Xk, Yk, Zk) gives the number of employees in 1,2,3, respectively, at time k, then 1 year later we would have
o o J= ¡i00100J'.
Xk+1 = .85xk + .10Yk + .05Zk
Yk+i = +.95Yk + .05Zk
0.525 0 0 0.2294
Zk+i = ,15xk + .02Yk + .83zk
0,9975
Then, using the norm
or 11(I,x)lId ~ 11(I,x)Dlli,
Pk+i = APk
210
13.4 Research Notes
13" Systems
¡ ,85 .10 ,05 J
211
Final letOrs frm 1,000 runs, 0.493
where A = 0 .95 .05 . .15 .02 .83
0.4925
Of course, we would expect retirements, new jobs, etc. to fluctuate some,
and thus we suppose that matri A fluctuates, yielding
0,492
0.4915
Pk+i = AkPk.
For this example, we will suppose that each Ak has no more than 2% fluctuation from A, so
A - .02A :: Ak :: A + .02A for all k. Let E denote the set of all of these matrices.
The ,,' L i, T-proper with E ~ ¡ t J. Then
0,605
x axis
FIGURE 13,8, Final vectors of 1000 runs,
w~,pan -n,UD
L
H
(122,54, 73,63, 130.90)
(125.42, 75.33, 134.01)
(122.16, 73.73, 130.87)
(125.32, 75,33, 134.05)
(121.98, 73,51, 130.53)
(125.42, 75.47, 134.20)
k
500 1000 10,000
whose unit circle in the 1 -norm is convex t Ci, C2, CSJ
where Ci = ::~
¡ ~i J ,'2 ~ ~l ¡ ii J ,C3 dl ¡ 2i J
Thus, using
A picture, showing where the system might be, depending on the run, can be seen, for 1,000 runs, in Figure 13.8.
Theorem 2.12
The points occurrng at the end of the runs were mapped into R2 using
r1 1 1 L
TW (A) = max l211ai - a211i, 211ai - aslli' 211a2 - aSlli r
, ¡0v'4J the matri T = ~ . o 0 2
where ak is the k-th row of A. Using the formula, we get TW (E) :: 0.9166. s~ Eoo exts; however, convergence may be very slow. Thus, we only show
what can occu¡r ~~othJis system in 10 years by finding component bounds ElOx for x = ~~ . Using k runs, we find the following.
13.4 Research Notes
The work in this chapter extends that in Chapter 11. The tax problem can be found in Howard (1960).
Hartfiel (1998) showed how to obtain precise component bounds for those
E which are intervals of stochastic matrices. However, no general such technique is known.
212
13,5 MATLAB Codes
13. Systems
13.5 MATLAB Codes
hold on for r=l: 1000
x=(.3434; .3333; .3232);
Component Bounds for Demographic Problem
for k=l: 10
A=(.2 .4 .4; .9 0 0; 0 .9 0);
for i=l: 3
B=(.196 .392 .392; .882 0 0;0 .882 0)
for j=1:3
L=ones(l,3) ; H=zeros(l,3) ;
G=rand; if GOC=.5
for m=l: 5000
d=l;
x=(.3434; .3333; .3232);
else
for k=l: 10
d=O;
for i=1:3 for j=1:3
end
C(i,j)=B(i,j)+d*.04*A(i,j) ;
G=rand;
end
if GOC=.5
end x=C*x/norm(C*x,l) ;
d=l;
else
end
d=O;
y=T*x
end
C(i,j)=B(i,j)+d*.04*A(i,j) ; end end x=C*x/norm(C*x,l) ; end for i=l: 3 L(i)=min( (L(i), x(i))); H(i)=max( (H(i), x(i)));
end
plot(y(1) ,y(2)) end
Trajectory for Demographics Problem A=(.2 .4 .4; .9 0 0; 0 .9 0);
B=(.196 .392 .392; .882 0 0;0.882 0); T=(O sqrt(2) 1/sqrt(2);0 0 sqrt(6)/2); y=(.3434, .3333, .3232);
end
z=T*y;
L
x=(.3434; .3333; .3232); xlabel ( , x axis') ylabel ( , y axis') ti tle ( , Ten iterates of a traj ectory' )
H
Final Vectors Graph for Demographics Problem A=(.2 .4 .4; .9 0 0; 0 .9 0);
B=(.196 .392 .392; .882 0 0;0 .882 0); T=(O sqrt(2) 1/sqrt(2);0 0 sqrt(6)/2); hold on
hold on
plot(z(l) ,z(2), 'k:*') for k=l: 10
for i=1:3 for j=1:3
ë&is equal xlabel ( 'x axis')
G=rand;
ti tle ( 'Final vectors for 10 iterates')
else
ylabel('yaxis')
if GOC=.5
d=l;
213
214 13, Systems
Appendix
d=O;
end
C(i,j)=B(i,j)+(d*.04)*A(i,j) ; end end x=C*x/norm(C*x, 1) ; p=T*x; q=T*y;
plot(p(l) ,p(2), '0') plot( (p(l) ,q(l)J ,(p(2) ,q(2)J)
y=x
end
We give a few results used in the book.
Perron-Frobenius Theory:
Let A be an n x n nonnegative matrix. If A k ). 0 for some positive integer k, then A is primitive. If A isn't primtive, but is irreducible, there
is an integer r called A's index of imprimitivity. For this r, there is a permutation matrix P such that
p Apt = 0 0
o A2
0 o r Ar 0 Ai : J where the r main diagonal O-blocks are square and r the largest integer producing this canonical form.
If A is nonnegative, A has an eigenvaue p = p (A) where Ay = py ~
and y is a nonnegative eigenvector. If A is primitive, it has exactly one eigenvalue p where p). IAI
L
216 Appendix
for all eigenvalues À. i= p of A. If A is irreducible, with index r, then A has eigenvalues
Bibliography
i,.2r i,!1r
p, pe , pe , . . . al of multiplicity one with al other eigenvalues À. satisfying
IÀ.I ~ p.
For the eigenvalue p, when A is irreducible (includes primitive), A has a U1que positive stochastic eigenvector y, so that
Ay = py.
Hyslop's Theorems: We give two of these theorems. In the last two theorems, divergence includes convergence to O.
Theorem 14, Hyslop Let ak ;: 0 for all positive integers k. Let aii, ai2, , . , 00
be a rearrangement of ai, a2, , . ,. Then L ak converges if and only if k=l
00
L aik converges.
B 32, 63-73
k=l
00
Theorem 51, Hyslop Let ak ;: 0 for all positive integers k. Then L ak k=l
00 and I1 (1 + ak) convèrge or diverge together.
Amemya, 1., Ando, T. (1965): Convergence of random products of contractions in Hilbert space. Acta. ScL Math. (Szeged) 26, 239-244 ArtzroU1, M. (1986a): On the convergence of inte products of matrices.
k=i
Linear Algebra Appi. 74:11-21
00 00
Theorem 52, Hyslop If -1 ~ ak :: 0, then L ak and I1 (1 + ak) converge or diverge together.
Althan, P.M.E. (1970): The measurement of association of rows and colums for the r x s contingency table. J. Roy. Statist. Soc. Ser
k=i k=i
König's Infinity Lemma: The statement of this lemma follows.
Lemma Let Si, S2, . .. be a sequence of fite nonempty sets and suppose
ArtzroU1, M. (1986b): On the dynamcs of a population subject to slowly changing vital rates. J. Math. BioI. 80, 265-290
ArtzroU1, M. (1991): On the growth of infte products of slowly varying
primtive matrices. Linear Algebra Appi. 145:33-57
ArtzroU1, M., Li, X. (1995) A note on the coeffcient of ergodicity of a colum-alowable nonnegative matrix. Linear Algebra Appi. 214, 93-101
that S = USk is infite.. Let I: ç S x S be such that for each k, and
each x E SkH, there is ayE Sk such that (y, x) E 1:. Then there..exist elements Xi, X2,... of S such that Xk E Sk and (Xk, XkH) E I: for all );;.
ArtzroU1, M. (1996): On the dynamcs of the linear process y (k) = A (k) y (k - 1) with irreducible matrices. Linear Algebra Appi. 17, 822-833
218
Bibliography
Bibliography
Barnsley, M. (1988): Fractals everywhere. AcadeßUcPress, New York
Berger, M., Wan, Y. (1992): Bounded seßUgroups of matrices. Linear Al-
Elsner, L. (1993): Inte products and paracontracting matrices. Unpublished preprint Elsner, L. (1995): The generalzed spectral-radius theorem: an analytic-
gebra Appl. 166, 21-27
Beyn, W.J., Elsner, L. (1997): Inte products and paracontracting matrices, The Electron. J. Linear Algebra 2, 1-8
Birkhoff, G. (1967): Lattice theory, 3rd ed. Amer. Math. Soc. Colloq. Pub. XXV, Providence, Rhode Island Brualdi, R.A., Ryser, H.J. (1991): Combinatorial matrix theory. Cambridge University Press, New York
Bushell, P. (1973): Hilbert's metric and positive contraction in Banach space. Arch. Rational Mech. Anal. 52, 330-338
geometric proof. Linear Algebra Appl. 220, 151-159
Elsner, L. Koltracht, I., Neuman, M. (1990): On the convergence of asynchromous paracontractions with applications to tomographic reconstruction from incomplete data. Linear Algebra Appl. 130, 65-82
Gantmacher, F.R. (1964): The theory of matrices. (voL. 2). Chelsea Publishing Co., New York
Geraßta, J.M., Pulan, N.J. (1984): An introduction to the application of
nonnegative matrices to biological systems. Queen's Papers in Pure
and Appl. Math. 68, Queen's University, Kingston, Ontario, Canada
Christian, Jr., F.L. (1979): A k-measure of irreducibilty and doubly stochastic matrices. Linear Algebra AppL 24, 225-237 Cohen, J. E. (1979a): Ergodic theorems in demography. Bul. Amer. Math.
Golubitsky, M., Keeler, E.B., Rothschild, M. (1975): Convergence of age structure: application of the projective metric. Theoret. Population Biology 7, 84-93
Guruits, L. (1995): Stabilty of discrete linear inclusion. Linear Algebra
Society 1, 275-295
non-negative
Cohen, J.E. (1979b): Contractive inhomogeneous products of
matrices. Math. Proc. Cambridge PhiL. Soc. 86, 351-364 Cohn, H., Nerman, O. (1990): On products of
219
nonnegative matrices. Ann.
AppL Probab. 18, 1806-1815 Daubechies, I, Lagarias, J. C. (1992a): Sets of matrices al infte products
of which converge. Linear Algebra Appl. 161, 227-263
Daubechies, I., Lagarias, J.C. (1992b): Two-scale difference equations II.
Local regularity, infite products of matrices and fractals. SIAM J. Math. AnaL. 23, 1031-1079
Daubechies, I., Lagarias, J.C. (2001): Corrigendum/addendum to: Sets of matrices al inte products of which converge. Linear Algebra AppL
327, 69-83
Dtaconis, P., Shahshahan, M. (1996): Products of random matrices and
computer image generation. Contemp. Math. Amer. Math. Soc. 50, 173-182
Eggleton, H.G. (1969): Convexity. Cambridge University Press, Cambridge
AppL 231, 47-85
nonnegative matrices. Math. Proc. Cam-
Hajnal, J. (1976): On products of
bridge Philos. Soc. 79, 521-530
Halperin, i. (1962): The product of projection operators. Acta. Sci. Math. (Szeged) 23, 96-99
Hartfiel, D.J. (1973): Bounds on eigenvalues and eigenvectors of a nonnegative matrix which involve a measure of irreducibilty, SIAM J. AppL Math. 24, 83-85 Hartfiel, D,J, (1974): On
infite
products
of
nonnegative
matrices. SIAM
J. AppL Math. 26, 297-301
Hartfiel, D.J. (1975): Results on measures of irreducibilty and ful indecomposibilty. Trans. Amer. Math. Soc. 202, 357-368
Hartfiel, D.J. (1981): On the lißUting set of stochasticproductsxAi .. . Am.
Proc. Amer. Math. Soc. 81, 201-206
Hartfiel, D.J. (1991): Sequential lits in Markov set-chains. J. Appl. Probab. 28, 910-913
220
Bibliography
Hartfiel, D.J. (1995): Indeteruunate Markov systems. AppL Math. Comput. 68, 1-9
Hartfiel, D.J. (1996): Concerning interv Leslie matrix calculations. Linear Multilnear Algebra 41, 95-106
Hartfiel, D.J. (1997): Systems behavior in quotient systems. AppL Math. Comput. 81, 31-48 Hartfiel, D.J. (1998): Markov set-chains. LNM 1695, Springer, New York
Bibliography
221
Neuman, M., Schneider, H. (1999): The convergence of general products of matrices and the weak ergodicity of Markov chain. Linear Algebra AppL 287, 307-314
Ostrowski, A.M. (1973): Solutions of equations in Euclidean and Banach spaces. Acadeuuc Press, New York Pulan, N. (1967): A property of inte products of Boolean matrices.
SIAM J, AppL Math. 15, 871-873
Hartfiel, D.J. (2000): Difference equations in a general setting. Linear Algebra AppL 305, 173-185
Rhodius, A. (1989): On alost scrambling matrices. Linear Algebra AppL
Hartfiel, D.J. (2001): Numerical bounds on fluctuating linear processes. J. Math. AnaL. AppL 254, 43-52
Rhodius, A. (1998): On dualty and explicit forms for Ergodicity Coeffcients, unpublished preprint
Hartfiel, D.J., Rothblum, U.G. (1998): Convergence of inhomegeneous products of matrices and coeffcients of ergodicity. Linear Algebra AppL 277, 1-9
Hartfiel, D.J., Seneta, E. (1990): A note on seuugroups of regular stochastic matrices. Linear Algebra AppL 141, 47-51
Hilbert, D. (1895): Über die gerade linie a1 kürzeste verbindung zqwier pune. Math. An. 46, 91-96 Holtz, O. (2000): On convergence of inte matrix products. The Electron J. of Linear Algebra 7, 178-181
126, 79-86
Rhodius, A. (2000): On ergodicity coeffcients of infte stochastic matri-
ces. J. Math. Anal. AppL 19,873-887
Rota, G. C., Strang, W.G. (1960): A note on the joint spectral radius. Indag. Math. 22, 379-381
Rothblum, U. R., Tan, C,P. (1985): Upper bounds on the maxum modulus of subdouunant eigenvalues of nonnegative matrices. Linear Algebra AppL 66, 45-86
Sarymsakov, T. A. (1961): Inhomogeneous i\,farkov chains (in Russian), Teor. Varoiatnost. i. Primen. 6, 194-201
Horn, R.A., Johnon, C.R. (1996): Matrix analysis. Cambridge University Press, New York
Seneta, E. (1981): Non-negative matrices and Markov chai, 2nd ed.
Howard, R. (1960): Dynauuc programuung and Markov processes. MIT Press, Cambridge, Massachusetts
Seneta, E. (1984): On the liuuting set of non-negative matrix products.
Hyslop, J. M. (1959): Inte Series. Oliver and Boyd, Edinburgh
Seneta, E., Sheridan, S. (1981): Strong ergodicity of nonnegative matrices.
Johnson, C., Bru, R. (1990): The spectral radius of a product of nonnegative matrices. Linear Algebra AppL 141, 227-240
Micchell, C.A., Prautzsch, H. (1989): Uniorm refinement of curves. Lin, ear Algebra AppL 114/115, 841-870
Nelson, S., Neuman, M. (1987): Generalization of the projection method " with applications to SOR theory for Hermitian positive seuudèfite linear systems. Numer. Math. 51, 123-141
Springer-Verlag, New York
Statist. Probab. Letters 2, 159-163
Linear Algebra AppL 37, 277-292 Suuth, R. (1966a): Matrix calculations for Liapunov quadratic forms. J. Differential Equations 2, 208-217
Smith, R. (1966b): Suffcient conditions for stabilty of a solution of difference equations. Duke Math. J. 33, 725-734 Stanord, D.P. and Urbano, J.M. (1994): Some convergence properties of
matrix sets. SIAM J. Matrix AnaL. AppL 15, 1132-1140
222 Bibliography Trench, W.F. (1995): Inventibly convergent infte products of matrices,
with application to dierence equations. J. Comput. AppL. Math. 30, 39-46
Index
Trench, W.F. (1999): Inventibly convergent infte products of matrices.
J. Comput. AppL. Math. 101,255-263
Varga, R. S. (1962): Matrix iterative analysis. Prentice-Hall, Englewood Cliffs, N. J.
Vladinurov, A. Elnser, L., Beyn, W.J. (2000): Stabilty and paracontractivity of discrete linear inclusions. Linear Algebra AppL. 312, 125-134
Wedderburn, J.H.M. (1964): Lectures on matrices, Dover Publications, Inc., New York
Wolfowitz, J. (1963): Products of indecomposable, aperiodic, stochastic matrices. Proc. Amer. Math. Soc. 14, 733-737
1 -eigenspace, 103
ergodic sets, 78
Birkhoff contraction cooeffcient,
ì-paracontracting, 118
21
generalzed spectral radius, 38
r-block, 32 blocks, 32
bounded, 3
bounded vaiation stable, 122 canonical form, 63
initial piece, 118 irreducible, 34 isolated block, 63
coeffcient of ergodicity for stochastic matrices, 32 coeffcients of ergodicity, 43
joint spectral radius, 38
colum convex, 139 colum proportionalty, 71
left convergence property, 103
continuous, 108
Leslie matrix, 201 linuting set, 45
contraction coeffcient, 18 ~
Hausdorff metric, 15
LCP, 103
left infnite product, 2
cross ratios, 22 matrix norm, 2 directed graph, 34
matrix sequence, 45
matrix set, 3 ergodic,
74
matrix subsequence, 45
224 Index
measure of ful indecomposabilty, 35
measure of irreducibilty, 34 nonhomogeneous products, 2 norm-convergence result, 58 norm-convergence to 0, 98
partly decomposable, 34 pattern B, 61
positive orthant, 6 primitive, 59
product bounded, 3
projective map, 24 projective metric, 6 projective set, 24
quotient bound result, 19 real defiable, 109
reduced, 87
reducible, 33 right infte product, 2 row
allowable, 19
Sarymsakov matrix, 65 scrambling, 63
sequence space, 107
signum matrix, 60 spectral radius, 38 stochastic vector, 12 strong linuting set, 133
trajectory, 118
unformly bounded variation stable, 122
vanishing steps, 122
vaiation of the trajectory, 122