049 markov
PDF · 5 pages · 104.8 KB
Open PDF file
Textbook chapter section, apparently from a linear algebra course text kept in Phil's linear algebra folder. It defines Markov matrices and proves that eigenvalues have modulus at most 1. For positive and primitive Markov matrices it shows 1 is the only eigenvalue of modulus 1 and that A^m converges to a matrix built from the stationary vector. Worked examples include a 3x3 matrix and a 4x4 primitive matrix tied to the 5x+1 problem.
AI-written summary; may contain errors.
Extracted text (machine-read; may contain errors)
4.9 Markov matrices
DEFINITION 4.3
A realnnmatrixA= [aij]is called a Markov matrix, or row{
stochastic matrix if
(i)aij0for1i; jn;
(ii)nP
j=1aij= 1for1in.
Remark: (ii) is equivalent to AJn=Jn, whereJn= [1;:::; 1]t. So 1 is
always an eigenvalue of a Markov matrix.
EXERCISE 4.1
IfAandBarennMarkov matrices, prove that ABis also a Markov
matrix.
THEOREM 4.9
Every eigenvalue of a Markov matrix satis es jj1.
PROOF Suppose 2Cis an eigenvalue of AandX2Vn(C) is a corre-
sponding eigenvector. Then
AX=X: (13)
Letkbe such thatjxjjjxkj;8j;1jn. Then equating the k{th
component of each side of equation (13) gives
nX
j=1akjxj=xk: (14)
Hence
jxkj=jjjxkj=jnX
j=1akjxjjnX
j=1akjjxjj (15)
nX
j=1akjjxkj=jxkj: (16)
Hencejj1.
89
DEFINITION 4.4
Apositive Markov matrix is one with all positive elements (i.e.
strictly greater than zero). For such a matrix Awe may write \ A>0".
THEOREM 4.10
IfAis a positive Markov matrix, then 1is the only eigenvalue of modulus
1. Moreover nullity (A In) = 1 .
PROOF Suppose jj= 1; AX =X; X2Vn(C); X6= 0.
Then inequalities (15) and (16) reduce to
jxkj= nX
j=1akjxj nX
j=1akjjxjjnX
j=1akjjxkj=jxkj: (17)
Then inequalities (17) and a sandwich principle, give
jxjj=jxkjfor 1jn: (18)
Also, as equality holds in the triangle inequality section of inequalities (17),
this forces all the complex numbers akjxjto lie in the same direction:
akjxj=tjakkxk; ;tj>0;1jn;
xj= jxk;
where j= (tjakk)=akj>0.
Then equation (18) implies j= 1 and hence xj=xkfor 1jn.
Consequently X=xkJn, thereby proving that N(A In) =hJni.
Finally, equation (14) implies
nX
j=1akjxj=xk=nX
j=1akjxk=xk;
so= 1.
COROLLARY 4.3
IfAis a positive Markov matrix, then Athas1as the only eigenvalue
of modulus 1. Also nullity (At In) = 1 .
PROOF The eigenvalues of Atare precisely the same as those of A, even up
to multiplicities. For
chAt= det (xIn At) = det (xIn A)t= det (xIn A) = chA:
Also(At In) =(A In)t=(A In) = 1.
90
THEOREM 4.11
IfAis a positive Markov matrix, then
(i)(x 1)jjmA;
(ii)Am!B, whereB=2
64Xt
...
Xt3
75is a positive Markov matrix and where
Xis uniquely de ned as the (positive) vector satisfying AtX=X
whose components sum to 1.
Remark: In view of part (i) and the equation (A In) = 1, it follows that
(x 1)jjchA.
PROOF As (A In) = 1, the Jordan form of Ahas the form Jb(1)
K, where (x 1)bjjmA. HereKis the direct sum of all Jordan blocks
corresponding to all the eigenvalues of Aother than 1 and hence Km!0.
Now suppose that b>1; thenJb(1) has size b>1. Then9Psuch that
P 1AP =Jb(1)K;
P 1AmP=Jm
b(1)Km:
Hence the 21 element of Jm
b(1) equals m
1
!1 asm!1 .
However the elements of Amare1, asAmis a Markov matrix. Con-
sequently the elements of P 1AmPare bounded as m!1 . This contra-
diction proves that b= 1.
HenceP 1AmP!I10 andAm!P(I10)P 1=B.
We see that rank B= rank (I10) = 1.
Finally it is easy to prove that Bis a Markov matrix. So
B=2
64t1Xt
...
tnXt3
75
for some non{negative column vector Xand where t1;:::;tnare positive.
We can assume that the entries of Xsum to 1. It then follows that t1=
=tn= 1 and hence
B=2
64Xt
...
Xt3
75: (19)
91
NowAm!B, soAm+1=AmA!BA. HenceB=BAand
AtBt=Bt: (20)
Then equations (19) and (20) imply
At[XjjX] = [XjjX]
and henceAtX=X.
HoweverX0 andAt>0, soX=AtX > 0.
DEFINITION 4.5
We have thus proved that there is a positive eigenvector XofAtcorre-
sponding to the eigenvalue 1, where the components of Xsum to 1. Then
because we know that the eigenspace N(At In)is one{dimensional, it
follows that this vector is unique.
This vector is called the stationary vector of the Markov matrix A.
EXAMPLE 4.4
Let
A=2
41=2 1=4 1=4
1=6 1=6 2=3
1=3 1=3 1=33
5:
Then
At I3row{reduces to2
41 0 4=9
0 1 2=3
0 0 03
5:
HenceN(At I3) =*2
44=9
2=3
13
5+
=*2
44=19
6=19
9=193
5+
and
lim
m!1Am=1
192
44 6 9
4 6 9
4 6 93
5:
We remark that chA= (x 1)(x2 1=24).
DEFINITION 4.6
A Markov Matrix is called regular orprimitive if9k1such that
Ak>0.
92
THEOREM 4.12
IfAis a primitive Markov matrix, then Asatis es the same properties
enunciated in the last two theorems for positive Markov matrices.
PROOF Suppose Ak>0. Then (x 1)jjchAkand hence ( x 1)jjchA, as
chA= (x c1)a1(x ct)at)chAk= (x ck
1)a1(x ck
t)at: (21)
and consequently ( x 1)jjmA.
Also as 1 is the only eigenvalue of Akwith modulus 1, it follows from
equation (21) that 1 is the only eigenvalue of Awith modulus 1.
The proof of the second theorem goes through, with the di erence that
to prove the positivity of Xwe observe that AtX=Ximplies (Ak)tX=X.
EXAMPLE 4.5
The following Markov matrix is primitive (its fourth power is positive)
and is related to the 5x+ 1problem:
2
6640 0 1 0
1=2 0 1=2 0
0 0 1=2 1=2
0 1=2 1=2 03
775:
Its stationary vector is [1
15;2
15;8
15;4
15]t.
We remark that chA= (x 1)(x+ 1=2)(x2+ 1=4).
93