8.3. TOPOLOGICAL ENTROPY.

Now let us specialize to the case (YG , σY ) for some DMG, G. We claim that

1

ζσ (t) = . (8.4)

det(I ’ tA)

Indeed,

pn (σ) = tr An = »n

i

where the sum is over all the eigenvalues (counted with multiplicity). Hence

(»i t)n 1 1

ζσ (t) = exp = = . QED

1 ’ »i t det(I ’ tA)

n

8.3 Topological entropy.

Let X be a shift space, and let Wn (X) denote the number of words of length n

which appear in X. Let wn = #(Wn (X) denote the number of words of length

n. Clearly wn ≥ 1 (as we assume that X is not empty), and

wm+n ¤ wm · wn

and hence

log2 (wm+n ) ¤ log2 (wm ) + log2 (wn ).

This implies that

1

lim

log2 wn

n’∞ n

exists on account of the following:

Lemma 8.3.1 Let a1 , a2 . . . be a sequence of non-negative real numbers satis-

fying

am+n ¤ am + an .

1

Then limn’∞ n an exists and in fact

1 1

lim an = inf an .

n’∞ n n’∞ n

1

Proof. Set a := inf n’∞ n an . For any > 0 we must show that there exists

an N = N ( ) such that

1

an ¤ a + ∀ n ≥ N ( ).

n

Choose some integer r such that

1

ar < a + .

2

Such an r ≥ 1 exists by the de¬nition of a. Using the inequality in the lemma,

if 0 ¤ j < r

amr+j am r aj

¤ + .

mr + j mr + j mr + j

144 CHAPTER 8. SYMBOLIC DYNAMICS.

Decreasing the denominator the right hand side is ¤

amr aj

+ .

mr mr

There are only ¬nitely many aj which occur in the second term, and hence by

choosing m large we can arrange that the second term is always < 1 . Repeated

2

application of the inequality in the lemma gives

amr mar ar 1

¤ = < a + . QED.

mr mr r 2

Thus we de¬ne

1

h(X) = lim log2 #(Wn (X)), (8.5)

n’∞ n

and call h(X) the topological entropy of X. (This is a standard but unfortu-

nate terminology, as the topological entropy is only loosely related to the concept

of entropy in thermodynamics, statistical mechanics or information theory). To

show the it is an invariant of X we prove

Proposition 8.3.1 Let φ : X ’ Y be a factor (i.e. a surjective homomor-

phism). Then h(Y ) ¤ h(X). In particular, if h is a conjugacy, then h(X) =

h(Y ).

Proof. We know that φ is given by a sliding block code, say of size 2m + 1.

Then every block in Y of size n is the image of a block in X of size n + 2m + 1,

i.e.

1nlog2 #(Wn (Y )) ¤ 1nlog2 #(Wn+2m+1 (X)).

Hence

1 n + 2m + 1 1

1nlog2 #(Wn (Y )) ¤ 1nlog2 #(Wn+2m+1 (X)).

n n n + 2m + 1

The expression in parenthesis tends to ! as n ’ ∞ proving that h(Y ) ¤ h(X).

If φ is a conjugacy, the reverse inequality applies. Box

The entropy of YG from A(G).

8.3.1

The adjacency matrix of a DMG has non-negative integer entries, in particular

non-negative entries. If a row consisted entirely of zeros, then no edge would em-

anate from the corresponding vertex, so this vertex would make no contribution

to the corresponding shift. Similarly if column consisted entirely of zeros. So

without loss of generality, we may restrict ourselves to graphs whose adjacency

matrix contains at least one positive entry in each row and in each column. This

implies that if Ak has all its entries positive, then so does Ak+1 and hence all

higher powers. A matrix with non-negative entries which has this property is

called primitive. A matrix is called irreducible if In terms of the graph G, the

condition of being primitive means that for all su¬ciently large n any vertices

i and j can be joined by a path of length n. A slightly weaker condition is that

145

8.3. TOPOLOGICAL ENTROPY.

of irreducibility which asserts for any i and j there exist (arbitrarily large)

n = n(i, j)) and a path of length n joining i and j. In terms of the matrix,

this says that given i and j there is some power n such that (An )ij > 0. For

example, the matrix

01

10

is irreducible but not primitive.

The Perron-Frobenius Theorem whose proof we will give in the next

section asserts every irreducible matrix A has a positive eigenvalue »A such

that »A ≥ |µ| for any other eigenvalue µ and also that Av = »A v for some

vector v all of whose entries are positive, and that no other eigenvalue has an

eigenvector with all positive entries. We will use this theorem to prove:

Theorem 8.3.1 Let G be a DMG whose adjacency matrix A(G)is irreducible.

Let yG be the corresponding shift space. then

h(YG ) = »A(G) . (8.6)

Proof. The number of words of length n which join the vertex i to the vertex

j is the ij entry of An where A = A(G). Hence

(An )ij .

#(Wn (YG )) =

ij

Let v be an eigenvector of A with all positive entries, and let m > 0 be the

minimum of these entries and M the maximum. Also let us write » for »A . We

have An v = »n v, or written out

(An )ij vj = »n vi .

j

Hence

(An )ij ¤ »n M.

m

j

Summing over i gives

m#(Wn (YG )) ¤ rM »n

where r is the size of the matrix A. Hence

log2 m + log2 #(Wn (YG )) ¤ log2 (M r) + nlog2 ».