THE S25.000.000.000 EIGENVECTOR 9 where ei=sgn(wi).Note that the ei are not all of one sign,since >:wi=0(unless w=0 in which case the bound clearly holds).Reverse the double sum to obtain (4.1) where aj=eMij.Since the e;are of mixed sign and Mj=1 with<Mij<1,it is easy to see that -1<-1+2,minM≤a≤1-2，minM<1. 1<2<n 1<1n We can thus bound lal≤1-2nMl<1 Let c=maxi<jsn1-2minisisn Mijl.Observe that c<1 and lajl c for all j.From equation (4.1)we have ∑ayl≤c∑ll=cvl, which proves the proposition. Proposition 4 sets the stage for the following proposition. PROPOSITION 5.Every positive column-stochastic matrir M has a unique vector q with positive components such that Mq=q with llql=1.The vector q can be computed as q=limkoo Mxo for any initial guess xo with positive components such that xol=1.Proof.From Proposition 1 the matrix M has 1 as an eigenvalue and by Lemma 3.2 the subspace Vi(M)is one-dimensional. Also,all non-zero vectors in Vi(M)have entirely positive or negative components.It is clear that there is a unique vector qeVi(M)with positive components such that qi=1. Let xo be any vector in R"with positive components such that lxoll1=1.We can write xo =q+v where vEV (V as in Proposition 4).We find that Mk xo Mkq+Mkv=q+Mkv. As a result M*xo -q=M*v. (4.2) A straightforward induction and Proposition 4 shows that Mkv<ckv for 0<c<1(c as in Proposition 4)and so limkMv1=0.From equation (4.2)we conclude that limk Mxo q.☐ Example:Let M be the matrix defined by equation(3.3)for the web of Figure 2.2.We take 0=[0.24,0.31,0.08,0.18,0.19j]as an initial guess;recall that we had q=[0.2,0.2,0.285,0.285,0.03T The table below shows the value of M xo-qll for several values of k,as well as the ratio lMxo-q/xo-q.Compare this ratio to c from Proposition 4,which in this case is 0.94. ‖M*xo-q1 M-ixo-ql 0 0.62 1 0.255 0.411 5 0.133 0.85 10 0.0591 0.85 50 8.87×10-5 0.85 It is clear that the bound Mxo-qll<cllxo-qll is rather pessimistic (note 0.85 is the value 1-m,and 0.85 turns out to be the second largest eigenvalue for M).One can show that in general the power method will converge asymptotically according to Mxk-qll2x-qll1,where A2THE $25,000,000,000 EIGENVECTOR 9 where ei = sgn(wi). Note that the ei are not all of one sign, since P i wi = 0 (unless w ≡ 0 in which case the bound clearly holds). Reverse the double sum to obtain kwk1 = Xn j=1 vj Xn i=1 eiMij! = Xn j=1 ajvj , (4.1) where aj = Pn i=1 eiMij . Since the ei are of mixed sign and P i Mij = 1 with 0 < Mij < 1, it is easy to see that −1 < −1 + 2 min 1≤i≤n Mij ≤ aj ≤ 1 − 2 min 1≤i≤n Mij < 1. We can thus bound |aj | ≤ |1 − 2 min 1≤i≤n Mij | < 1. Let c = max1≤j≤n |1 − 2 min1≤i≤n Mij |. Observe that c < 1 and |aj | ≤ c for all j. From equation (4.1) we have kwk1 = Xn j=1 ajvj =       Xn j=1 ajvj       ≤ Xn j=1 |aj ||vj | ≤ c Xn j=1 |vj | = ckvk1, which proves the proposition. Proposition 4 sets the stage for the following proposition. Proposition 5. Every positive column-stochastic matrix M has a unique vector q with positive components such that Mq = q with kqk1 = 1. The vector q can be computed as q = limk→∞ Mkx0 for any initial guess x0 with positive components such that kx0k1 = 1. Proof. From Proposition 1 the matrix M has 1 as an eigenvalue and by Lemma 3.2 the subspace V1(M) is one-dimensional. Also, all non-zero vectors in V1(M) have entirely positive or negative components. It is clear that there is a unique vector q ∈ V1(M) with positive components such that P i qi = 1. Let x0 be any vector in lRn with positive components such that kx0k1 = 1. We can write x0 = q + v where v ∈ V (V as in Proposition 4). We find that Mkx0 = Mkq + Mkv = q + Mkv. As a result Mkx0 − q = Mkv. (4.2) A straightforward induction and Proposition 4 shows that kMkvk1 ≤ c kkvk1 for 0 ≤ c < 1 (c as in Proposition 4) and so limk→∞ kMkvk1 = 0. From equation (4.2) we conclude that limk→∞ Mkx0 = q. Example: Let M be the matrix defined by equation (3.3) for the web of Figure 2.2. We take x0 = [0.24, 0.31, 0.08, 0.18, 0.19]T as an initial guess; recall that we had q = [0.2, 0.2, 0.285, 0.285, 0.03]T . The table below shows the value of kMkx0 − qk1 for several values of k, as well as the ratio kMkx0 − qk1/kMk−1x0 − qk1. Compare this ratio to c from Proposition 4, which in this case is 0.94. k kMkx0 − qk1 kMkx0−qk1 kMk−1x0−qk1 0 0.62 1 0.255 0.411 5 0.133 0.85 10 0.0591 0.85 50 8.87 × 10−5 0.85 It is clear that the bound kMkx0 − qk1 ≤ c kkx0 − qk1 is rather pessimistic (note 0.85 is the value 1 − m, and 0.85 turns out to be the second largest eigenvalue for M). One can show that in general the power method will converge asymptotically according to kMxk − qk1 ≈ |λ2|kx − qk1, where λ2