288 CHAPTER 11. LIMITS OF VECTORS AND MATRICES

Lemma 11.1.5 Let A be any Markov matrix and let v be a vector having all its componentsnon negative with ∑i vi = c. Then if w = Av, it follows that wi ≥ 0 for all i and ∑i wi = c.

Proof: From the definition of w,

wi ≡∑j

ai jv j ≥ 0.

Also∑

iwi = ∑

i∑

jai jv j = ∑

j∑

iai jv j = ∑

jv j = c. ■

The following theorem about limits is now easy to obtain.

Theorem 11.1.6 Suppose A is a Markov matrix in which ai j > 0 for all i, j and suppose wis a vector. Then for each i,

limk→∞

(Akw

)i= vi

where Av = v. In words, Akw always converges to a steady state. In addition to this, ifthe vector w satisfies wi ≥ 0 for all i and ∑i wi = c, then the vector v will also satisfy theconditions, vi ≥ 0, ∑i vi = c.

Proof: By Lemma 11.1.4, since each ai j > 0, the eigenvalues are either 1 or have ab-solute value less than 1. Therefore, the claimed limit exists by Theorem 11.1.3. The asser-tion that the components are nonnegative and sum to c follows from Lemma 11.1.5. ThatAv = v follows from

v = limn→∞

Anw = limn→∞

An+1w = A limn→∞

Anw = Av. ■

It is not hard to generalize the conclusion of this theorem to regular Markov processeswhich are those having some power with all positive entries.

Corollary 11.1.7 Suppose A is a regular Markov matrix, one for which the entries of Ak

are all positive for some k, and suppose w is a vector. Then for each i,

limn→∞

(Anw)i = vi

where Av = v. In words, Anw always converges to a steady state. In addition to this, ifthe vector w satisfies wi ≥ 0 for all i and ∑i wi = c, Then the vector v will also satisfy theconditions vi ≥ 0, ∑i vi = c.

Proof: Let the entries of Ak be all positive for some k. Now suppose that ai j ≥ 0 for alli, j and A = (ai j) is a Markov matrix. Then if B = (bi j) is a Markov matrix with bi j > 0for all i j, it follows that BA is a Markov matrix which has strictly positive entries. This isbecause the i jth entry of BA is

∑k

bikak j > 0,

Thus, from Lemma 11.1.4, Ak has eigenvalues {1,λ 1, · · · ,λ r} , |λ r|< 1. The same must betrue of A. If Ax= µx for x ̸= 0 and µ ̸= 1, Then Akx= µkx and so either µk = 1 or |µ|<1. If µk = 1, then |µ| = 1 and the eigenvalues of Ak+1 are either 1 or have absolute valueless than 1 because Ak+1 has all postive entries thanks to Lemma 11.1.4. Thus µk+1 = 1and so

1 = µk+1 = µµ

k = µ

By Theorem 11.1.3, limn→∞ Anw exists. The rest follows as in Theorem 11.1.6. ■