Chapter 11

Limits of Vectors and Matrices11.1 Regular Markov Matrices

The existence of the Jordan form is the basis for the proof of limit theorems for certainkinds of matrices called Markov matrices.

Definition 11.1.1 An n×n matrix A = (ai j) , is a Markov matrix if ai j ≥ 0 for all i, j and

∑i

ai j = 1.

It may also be called a stochastic matrix or a transition matrix. A Markov or stochasticmatrix is called regular if some power of A has all entries strictly positive. A vector v ∈Rn,is a steady state if Av = v.

Lemma 11.1.2 The property of being a stochastic matrix is preserved by taking products.It is also true if the sum is of the form ∑ j ai j = 1.

Proof: Suppose the sum over a row equals 1 for A and B. Then letting the entries bedenoted by (ai j) and (bi j) respectively and the entries of AB by (ci j),

∑i

ci j = ∑i

∑k

aikbk j = ∑k

∑i

aikbk j = ∑k

bk j = 1

It is obvious that when the product is taken, if each ai j,bi j ≥ 0, then the same will be trueof sums of products of these numbers. Similar reasoning works for the assumption that∑ j ai j = 1. ■

The following theorem is convenient for showing the existence of limits.

Theorem 11.1.3 Let A be a real p× p matrix having the properties

1. ai j ≥ 0

2. Either ∑pi=1 ai j = 1 or ∑

pj=1 ai j = 1.

3. The distinct eigenvalues of A are {1,λ 2, . . . ,λ m} where each∣∣λ j∣∣< 1.

Then limn→∞ An = A∞ exists in the sense that limn→∞ ani j = a∞

i j, the i jth entry A∞. Herean

i j denotes the i jth entry of An. Also, if λ = 1 has algebraic multiplicity r, then the Jordanblock corresponding to λ = 1 is just the r× r identity.

Proof. By the existence of the Jordan form for A, it follows that there exists an invertiblematrix P such that

P−1AP =

I +N

Jr2 (λ 2). . .

Jrm (λ m)

= J

285