CHAPTER 4 - ENTROPY

Summary

Entropy measures the complexity of mappings. For shifts, it also measures their “information capacity,” or ability to transmit messages. The entropy of a shift is an important number, for it is invariant under conjugacy, can be computed for a wide class of shifts, and behaves well under standard operations like factor codes and products. In this chapter we first introduce entropy and develop its basic properties. In order to compute entropy for irreducible shifts of finite type and sofic shifts in §4.3, we describe the Perron–Frobenius theory of nonnegative matrices in §4.2. In §4.4 we show how general shifts of finite type can be decomposed into irreducible pieces and compute entropy for general shifts of finite type and sofic shifts. In §4.5 we describe the structure of the irreducible pieces in terms of cyclically moving states.

Definition and Basic Properties

Before we get under way, we review some terminology and notation from linear algebra.

Recall that the characteristic polynomial of a matrix A is defined to be χA^(t) = det(tId – A), where Id is the identity matrix. The eigenvalues of A are the roots of χA^(t). An eigenvector of A corresponding to eigenvalue λ is a vector v, not identically 0, such that Av = λv.

We say that a (possibly rectangular) matrix A is (strictly) positive if each of its entries is positive. In this case we write A > 0.