8.4. THE PERRON-FROBENIUS THEOREM.

and each of the matrices »max I ’ T(i) has strictly positive determinant by what

we have just proved. This shows that the derivative of the characteristic poly-

nomial of T is not zero at »max , and therefore the algebraic multiplicity and

hence the geometric multiplicity of »max is one. QED

Let us go back to one stage in the proof, where we started with an eigenvector

y, so T y = »y and we applied the triangle inequality to get

|»||y| ¤ T |y|

to conclude that |»| ¤ »max . When do we have equality? This can happen only

if all the entries of j tij yj have the same argument, meaning that all the yj

with tij > 0 have the same argument. If T is primitive, we may apply this same

argument to T k for which all the entries are positive, to conclude that all the

entries of y have the same argument. So multiplying by a complex number of

arrange value one we can arrange that y ∈ Q and from T y = »y that » > 0

and hence » = »max and hence that y is a multiple of x. In other words, if T is

primitive then we have

|»| < »max

for all other eigenvalues.

The matrix of a cyclic permutation has all its eigenvalues on the unit circle,

and all its entries zero or one. So without the primitivity condition this result

is not true. But this example suggests how to proceed.

For any matrix S let |S| denote the matrix all of whose entries are the

absolute values of the entries of S. Suppose that |S| ¤ T and let »max =

»max (A), and suppose that Sy = σy for some y = 0,i.e. that σ is an eigenvalue

of S. Then

|σ||y| = |σy| = |Sy| ¤ |S||y| ¤ |S||y|

so

|σ| ¤ »max = Lmax (A).

Suppose we had equality. Then we conclude from the above proof that |y| = x,

the eigenvector of T corresponding to »max , and then from the above string

of inequalities that |B|x = Ax and since all the entries of x are positive that

|B| = A. De¬ne the complex numbers of absolute value one

eiθk := yk /|yk | = yk /xk

and let D denote the diagonal matrix with these numbers as diagonal entries,

so that y = Dx. Also write σ = eiφ »max . Then

σy = eiφ »max Dx = SDx

so

»max x = e’iφ D’1 SDx = T x.

Since all the entries of eiφ D’1 SD have absolute values ¤ the correspond-

ing entries of T , and since all the entries of X are positive, we must have

|eiφ D’1 SD| = T and all the rows have a common phase and in fact

S = eiφ DT D’1 .

150 CHAPTER 8. SYMBOLIC DYNAMICS.

In particular, we can apply this argument to S = T to conclude that if

iφ

e »max for some φ then

T = eiφ DT D’1 .

Since DT D’1 has the same eigenvalues as T , this shows that rotation through

angle φ carries all the eigenvalues of A into eigenvalues.

The subgroup of rotations in the complex plane with this property is a

¬nite subgroup (hence a ¬nite cyclic group) which acts transitively on the set

of eigenvalues satisfying |σ| = »max . It also must act faithfully on all non-zero

eigenvalues, so the order of this cyclic group must be a divisor of the number of

non-zero eigenvalues. If n is a prime and T has no zero eigenvalues then either

all the eigenvalues have absolute value »max or »max has multiplicity one.

We ¬rst de¬ne the period p of a non-zero non-negative matrix as T follows:

s

For each i consider the set of all positive integers s such that Tii > 0 and let pi

denote the greatest common denominator of this set. We show that this does

not depend on i. Indeed, for some other j, there is, by irreducibility an integer

M such that Tij > 0 and an integer N such that Tji > 0. Since Tii +N > M

M N

MN

Tij Tji > 0 we conclude that pi |(M + N ) and similarly that pj |(M + N ). Also,

if Tii > 0 then Tjj +N > Tij Tii Tji Tij > 0 so pj |s and so pj |pi and the

s+M

s MsNM

reverse. Thus pi = pj , and we call this common value p.

s

Using the arguments above we can be more precise. We claim that Tii = 0

unless s is a multiple of the order of our cyclic group of rotations, so this order

is precisely the period of T . Indeed, let k be the order of this cyclic group and

φ = 2π/k. We have

T = eiφ DT D’1

and hence

T s = eisφ DT s D’1 ,

in particular

Tii = eisφ Tii .

s s

Since eisφ = 1 if s is not a multiple of k we conclude that k = p. So we can

supplement the Perron-Frobenius theorem as

Theorem 8.4.2 Perron-Frobenius 2. If T is primitive, all eigenvalues sat-

isfy |σ| < »max . More generally, let p denote the period of T as de¬ned above.

Then there are exactly p eigenvalues of T satisfy |σ| = »max and the entire

spectrum of T is invariant under the cyclic group of rotations of order p.

8.5 Factors of ¬nite shifts.

Suppose that X is a shift of ¬nite type and φ : X ’ Z is a surjective homomor-

phism, i.e. a factor. Then Z need not be of ¬nite type. Here is an illustrative

example. Let A = {0, 1} and let Z ‚ Abf Z consist of all in¬nite sequences such

that there are always an even number of zeros between any two ones. So the

excluded words are

101, 10001, 1000001, 100000001, . . .

151

8.5. FACTORS OF FINITE SHIFTS.

(and all words containing them as substrings). It is clear that this can not be

replaced by any ¬nite list, since none of the above words is a substring of any

other.

On the other hand, let G be the DMG associated with the matrix

11

A= ,

10

and let YG be the corresponding shift. We claim that there is a surjective

homomorphism φ : YG ’ Z. To see this, assume that we have labelled the

vertices of G as 1, 2, that we let a denote the edge joining 1 to itself, b the edge

joining 1 to 2, and cthe edge joining 2 to 1. So the alphabet of the graph YG

and the excluded words are

ac bb, ba, cc

and all words which contain these as substrings. So if ab occurs in an element

of YG it must be followed by a c and then by a sequence of bc™s until the next

a. Now consider the sliding block code of size 1 given by

¦ : a ’ 1, b ’ 0, c ’ 0.

From the above description it is clear that the corresponding homomorphism is

surjective.

We can describe the above procedure as assigning “labels” to each of the

edges of the graph G; we assign the label 1 to the edge a and the label 0 to the

edges b and c.

It is clear that this procedure is pretty general: a labeling of a directed

multigraph is a map:¦ : E ’ A from the set of edges of G into an alphabet

A. It is clear that ¦ induces a homomorphism φ of YG onto some subshift of

Z ‚ AZ which is then, by construction a factor of a shift of ¬nite type.

Conversely, suppose X is a shift of ¬nite type and φ : X ’ Z is a surjective

homomorphism. Then φ comes from some block code. Replacing X by X N

where N is su¬ciently large we may assume that X N is one step and that the

block size of ¦ is one. Hence we may assume that X = YG for some G and that

¦ corresponds to a labeling of the edges of G. We will use the symbol (G, L)

to denote a DMG together with a labeling of its edges. We shall denote the

associated shift space by Y(G,L) .

Unfortunately, the term so¬c is used to describe a shift arising in this way,i.e.

a factor of a shift of ¬nite type. (The term is a melange of the modern Hebrew

mathematical term so¬ meaning ¬nite with an English sounding su¬x.