h(YG ) ¤ »A .

On the other hand, for any i we have

m»n ¤ »n vi ¤ (An )ij vj ¤ M (An )ij.

j j

146 CHAPTER 8. SYMBOLIC DYNAMICS.

Summing over j gives

rm»n ¤ M #(Wn (YG )).

Again, taking logarithms and dividing by n proves the reverse inequality h(YG ) ≥

»A . QED

For example, if

11

A=

10

then

21

A2 =

10

so A is primitive. Its eigenvalues are

√

1± 5

2

so that √

1+ 5

h(YG ) = .

2

If A is not irreducible, this means that there will be proper subgraphs from

which there is “no escape”. One may still apply the Perron Frobenius theorem

to the collection of all irreducible subgraphs, and replace the »A that occurs

in the theorem by the maximum of the maximum eigenvalues of each of the

irreducible subgraphs. We will not go into the details.

8.4 The Perron-Frobenius Theorem.

We say that a real matrix T is non-negative (or positive) if all the entries of

T are non-negative (or positive). We write T ≥ 0 or T > 0. We will use these

de¬nitions primarily for square (n — n) matrices and for column vectors (n — 1

matrices). We let

Q := {x ∈ Rn : x ≥ 0, x = 0}

so Q is the non-negative “orthant” excluding the origin. Also let

C := {x ≥ 0 : x = 1}.

So C is the intersection of the orthant with the unit sphere.

A non-negative matrix square T is called primitive if there is a k such that

all the entries of T k are positive. It is called irreducible if for any i, j there is

a k = k(i, j) such that (T k )ij > 0. If T is irreducible then I + T is primitive.

Until further notice in this section we will assume that T is non-negative and

irreducible.

Theorem 8.4.1 Perron-Frobenius,1. T has a positive (real) eigenvalue » max

such that all other eigenvalues of T satisfy

|»| ¤ »max .

147

8.4. THE PERRON-FROBENIUS THEOREM.

Furthermore »max has algebraic and geometric multiplicity one, and has an

eigenvector x with X > 0. Finally any non-negative eigenvector is a multiple of

x. More generally, if y ≥ 0, y = 0 is a vector and µ is a number such that

T y ¤ µy

then

y > 0, and µ ≥ »max

with µ = »max if and only if y is a multiple of x.

If 0 ¤ S ¤ T, S = T then every eigenvalue σ of S satis¬es |σ| < »max . In

particular, all the diagonal minors Ti obtained from T by deleting the i-th row

and column have eigenvalues all of which have absolute value < » max .

Proof. Let

P := (I + T )n’1

and for any z ∈ Q let

(T z)i

L(z) := max{s : sz ¤ T z} = min .

zi

1¤i¤n,zi =0

By de¬nition L(rz) = L(z) for any r > 0, so L(z) depends only on the ray

through z. If z ¤ y, z = y we have P z < P y. Also P T = T P . So if sz ¤ T z

then

sP z ¤ P T z = T P z

so

L(P z) ≥ L(z).

Furthermore, if L(z)z = T z then L(z)P z < T P z. So L(P z) > L(z) unless z is

an eigenvector of T . Consider the image of C under P . It is compact (being

the image of a compact set under a continuous map) and all of the elements of

P (C) have all their components strictly positive (since P is positive). Hence

the function L is continuous on P (C). Thus L achieves a maximum value, Lmax

on P (C). Since L(z) ¤ L(P z) this is in fact the maximum value of L on all of

Q, and since L(P z) > L(z) unless z is an eigenvector of T , we conclude that

Lmax is achieved at an eigenvector, call it x of of T and x > 0 with Lmax the

eigenvalue. Since T x > 0 and T x = Lmax x we have Lmax > 0.

We will now show that this is in fact the maximum eigenvalue in the sense

of the theorem. So let y be any eigenvector with eigenvalue », and let |y| denote

the vector whose components are |yj |, the absolute values of the components of

y. We have |y| ∈ Q and from

T y = »y

and the triangle inequality we conclude that

|»||y| ¤ T |y|.

Hence |»| ¤ L(|y|) ¤ Lmax . So we may use the notation

»max := Lmax

148 CHAPTER 8. SYMBOLIC DYNAMICS.

since we have proved that

|»| ¤ »max .

Suppose that 0 ¤ S ¤ T . Then sz ¤ Sz and Sz ¤ T z implies that sz ¤ T z

so LS (z) ¤ LT (z) for all z and hence

Lmax (S) ¤ Lmax (T ).

We may apply the same argument to T † to conclude that it also has a positive

maximum eigenvalue. Let us call it ·. (We shall soon show that · = »m ax.)

This means that there is a vector w > 0 such that

w† T = ·w.

We have

w† T x = ·w† x = »max w† x

implying that · = »max since w† x > 0.

Now suppose that y ∈ Q and T y ¤ µy. Then

»max w† y = w† T y ¤ µw† y

implying that »max ¤ µ, again using the fact that all the components of w

are positive and some component of y is positive so w † y > 0. In particular, if

T y = µy then then µ = »max .

Furthermore, if y ∈ Q and T y ¤ µy then

0 < P y = (I + T )n’1 y ¤ (1 + µ)n’1 y

so

y > 0.

If µ = »max then w† (T y ’ »max y) = 0 but T y ’ »max ¤ 0 and so w† (T y ’

»max y) = 0 implies that T y = »max y.

Suppose that 0 ¤ S ¤ T and Sz = σz, z = 0. Then

T |z| ≥ S|z| ≥ |σ||z|

so

|σ| ¤ Lmax (T ) = »max ,

as we have already seen. But if |σ| = »max then L(|z|) = Lmax (T ) so |z| > 0 and

|z is also an eigenvector of T . with the same eigenvalue. But then (T ’S)|z| = 0

and this is impossible unless S = T since |z| > 0. Replacing the i-th row and

column of T by zeros give an S ≥ 0 with S < T since the irreducibility of T

precludes all the entries in a row being zero.

Now

d

det(»I ’ T ) = det(»I ’ T(i) )

d» i