38.02.03 · dynamics / symbolic-dynamics

Perron-Frobenius Theory, SFT Growth Rate, and Subshift Entropy

shipped3 tiersLean: none

Anchor (Master): Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 4 and §4.3-§4.5 (the Perron number characterisation of SFT entropies, the spectral radius as growth rate); Walters 1982 *An Introduction to Ergodic Theory* (Springer GTM 79) §7.2-§7.3 (topological entropy, the variational principle, entropy of subshifts); Seneta 1981 *Non-negative Matrices and Markov Chains* (Springer) Ch. 1-2 (Perron-Frobenius, the Birkhoff-Hilbert projective metric contraction proof)

Intuition Beginner

Take the little graph of allowed letter-pairs from the previous unit, the one whose square table of zeros and ones records which steps a walk may take. A natural question is how rich the system is: how fast does the number of allowed words of length $n$ grow as $n$ climbs? If the count roughly doubles each time you add a letter, the system is twice as rich per step as a system whose count merely grows by a fixed amount. That per-step multiplier is the single most important number attached to the graph, and the whole point of this unit is that one number can be read straight off the table.

The mechanism is the eigenvalue. When you multiply a vector by the table again and again, the vector swings around and then settles into pointing along one favoured direction, stretching by the same factor every step. That stretch factor is the largest eigenvalue, and for a table of non-negative numbers whose graph is all one connected piece it is a single positive number that beats every other in size. The Perron-Frobenius theorem is the guarantee that this favoured direction and this dominant multiplier always exist and are unique. Because the word counts are built by repeatedly applying the table, they end up growing at exactly that rate.

So the growth rate of allowed words is the dominant eigenvalue, and its logarithm is what we call the entropy of the system: the amount of new information, measured per symbol, that the system can carry. For the golden-mean rule with its one forbidden pair, that dominant eigenvalue turns out to be the golden ratio itself, so the entropy is the logarithm of the golden ratio.

Visual Beginner

Picture a vector as an arrow, and the transition table as a machine that takes an arrow and returns a new one. Feed any starting arrow in, take the output, feed it back, and repeat. After a few rounds the arrow stops wobbling and lines up along one fixed heading, and from then on every round just makes it longer by the same factor. That fixed heading is the Perron eigenvector; that fixed stretch factor is the Perron eigenvalue.

The table below contrasts the question we ask with the answer the eigenvalue gives.

question about the system	answer from the dominant eigenvalue $λ$
how many allowed words of length $n$ ?	about $λ^{n}$ for large $n$
how many sequences repeat with period $n$ ?	about $λ^{n}$ (the matrix trace)
how much information per symbol?	the entropy, $lo g λ$
which direction does counting settle into?	the Perron eigenvector

Worked example Beginner

Take the golden-mean rule on letters $0$ and $1$ , forbidding only the pair $11$ . Its table, with rows and columns ordered $0$ then $1$ , is $$ A = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}. $$ We find its dominant eigenvalue and read off the growth rate of allowed words.

Step 1. Write the eigenvalue equation. An eigenvalue $λ$ makes $A$ shrink to a number along its favoured direction; the condition is that the table $A - λ I$ collapses, which happens exactly when $$ (1 - \lambda)(0 - \lambda) - (1)(1) = 0. $$

Step 2. Expand. This is $λ^{2} - λ - 1 = 0$ .

Step 3. Solve. The two roots are $λ = \frac{1 + 5}{2}$ and $λ = \frac{1 - 5}{2}$ . The first is about $1.618$ , the golden ratio $φ$ ; the second is about $- 0.618$ , smaller in size. The dominant one is $φ$ .

Step 4. Read the growth rate. The number of allowed words of length $n$ grows like $φ^{n}$ . Indeed those counts are the Fibonacci numbers $2, 3, 5, 8, 13, \dots$ , and each is about $φ$ times the one before. The entropy is $lo g φ \approx 0.481$ .

What this tells us: a single banned pair pins the per-symbol richness of an infinite family of sequences to one specific number, the golden ratio, and you obtain it by solving one quadratic. The forbidden pair sets the rule; the dominant eigenvalue measures how much room is left.

Check your understanding Beginner

Formal definition Intermediate+

Fix a non-negative real matrix $A = (A_{ij})$ indexed by a finite set. Recall from 38.02.02 that the support graph $G_{A}$ has an edge $i \to j$ iff $A_{ij} > 0$ , that $A$ is irreducible iff $G_{A}$ is strongly connected (for every $i, j$ some $(A^{n})_{ij} > 0$ ), and that $A$ is primitive iff $A^{n} > 0$ entrywise for some single $n$ (irreducible and aperiodic). Write $ρ (A) = max_{i} ∣ λ_{i} ∣$ for the spectral radius, the maximum modulus of an eigenvalue.

Definition (Perron root and Perron eigenvectors). For an irreducible non-negative matrix $A$ , the Perron root (or Perron-Frobenius eigenvalue) is the spectral radius $λ = ρ (A)$ . A right Perron eigenvector is a vector $v > 0$ (entrywise positive) with $A v = λ v$ ; a left Perron eigenvector is $w > 0$ with $w^{⊤} A = λ w^{⊤}$ . The theorem below asserts these exist and are unique up to scale.

Definition (period of an irreducible matrix). The period $d = d (A)$ is $g cd {n \geq 1 : (A^{n})_{ii} > 0}$ , independent of $i$ by 38.02.02. $A$ is aperiodic (equivalently primitive) iff $d = 1$ .

Definition (language growth and topological entropy of a subshift). For a subshift $X$ over a finite alphabet, let $L_{n} (X)$ be its set of admissible words of length $n$ and $p_{n} = ∣ L_{n} (X) ∣$ the complexity function. The topological entropy is $$ h(\mathsf{X}) = \lim_{n \to \infty} \frac{1}{n} \log p_n = \inf_{n \ge 1} \frac{1}{n} \log p_n, $$ the limit existing because $lo g p_{n}$ is subadditive ( $p_{m + n} \leq p_{m} p_{n}$ , Fekete's lemma). This agrees with the open-cover and separated-set definitions of topological entropy ^{[Walters 1982 §7.1-§7.3]} applied to the shift map $σ$ on $X$ .

Definition (zeta function). With $# Fix (σ^{n}) = tr (A^{n})$ from 38.02.02, the Artin-Mazur zeta function is $ζ_{σ} (t) = exp \sum_{n \geq 1} \frac{tr ( A ^{n} )}{n} t^{n} = det (I - t A)^{- 1}$ ; its smallest pole sits at $t = 1/ λ$ , the reciprocal of the Perron root.

Counterexamples to common slips

The spectral radius need not be an eigenvalue with a positive eigenvector when $A$ is reducible. The matrix $(1011)$ has $ρ = 1$ , but $1$ is a defective eigenvalue and there is no strictly positive eigenvector; irreducibility is what forces a positive Perron eigenvector and simplicity of the root.
Primitive is strictly stronger than irreducible, and only primitivity makes $λ$ the unique eigenvalue of maximum modulus. For the $2$ -cycle $(0110)$ the eigenvalues are $\pm 1$ , both of modulus $1$ : the matrix is irreducible but period $2$ , so its dominant modulus is achieved twice. Aperiodicity is exactly what removes the rival peripheral eigenvalues.
Entropy is a coarse invariant. Two non-conjugate irreducible SFTs can share a Perron root, hence equal entropy; entropy distinguishes systems but does not classify them (38.02.02, strong shift equivalence).
Growth rate is not the alphabet size. The full $k$ -shift has $λ = k$ and entropy $lo g k$ , but a proper SFT on $k$ letters has $λ < k$ ; the forbidden words strictly lower the Perron root.

Key theorem with proof Intermediate+

Theorem (Perron-Frobenius and the entropy of an SFT). Let $A$ be an irreducible non-negative matrix with spectral radius $λ = ρ (A)$ .

(a) Perron-Frobenius. $λ > 0$ is an eigenvalue of $A$ ; it is algebraically simple; and it has strictly positive right and left eigenvectors $v, w > 0$ , unique up to positive scalar. No eigenvalue exceeds $λ$ in modulus. If moreover $A$ is primitive, then $λ$ is the unique eigenvalue of maximum modulus: every other eigenvalue $μ$ satisfies $∣ μ ∣ < λ$ .

(b) Growth rate. If $A$ is a $0/1$ transition matrix of an SFT $X_{A}$ , then $p_{n} = ∣ L_{n} (X_{A}) ∣$ satisfies $c_{1} λ^{n} \leq p_{n} \leq c_{2} n^{r} λ^{n}$ for constants $c_{1}, c_{2} > 0$ (with $r$ at most the size of $A$ ), so $$ h(\mathsf{X}A) = \lim{n \to \infty} \frac{1}{n} \log p_n = \log \lambda(A). $$

(See ^{[Brin-Stuck 2002 §3.3-§3.5]}, ^{[Lind-Marcus 1995 Ch. 4]}, ^{[Seneta 1981 Ch. 1]}.)

Proof. Part (a). We give the cone-contraction argument. Let $C = {x \in R^{N} : x \geq 0} ∖ {0}$ and consider the map on the simplex $Δ = {x \geq 0 : \sum_{i} x_{i} = 1}$ given by $T (x) = A x /∥ A x ∥_{1}$ . Irreducibility ensures $A x \neq = 0$ for $x \in Δ$ , so $T$ is a continuous self-map of the compact convex set $Δ$ ; by the Brouwer fixed-point theorem $T$ has a fixed point $v \in Δ$ , giving $A v = λ v$ with $λ = ∥ A v ∥_{1} > 0$ and $v \geq 0$ . Irreducibility upgrades $v \geq 0$ to $v > 0$ : from $A v = λ v$ and $v \neq = 0$ , applying $(I + A)^{N - 1}$ (which is entrywise positive on the support of a strongly connected graph) gives $(I + A)^{N - 1} v = (1 + λ)^{N - 1} v > 0$ , so every coordinate of $v$ is positive.

That $λ = ρ (A)$ : any eigenvalue $μ$ with eigenvector $u$ satisfies $∣ μ ∣ ∣ u_{i} ∣ = ∣ \sum_{j} A_{ij} u_{j} ∣ \leq \sum_{j} A_{ij} ∣ u_{j} ∣$ , so the vector $∣ u ∣$ obeys $A ∣ u ∣ \geq ∣ μ ∣ ∣ u ∣$ entrywise. Pairing with the positive left eigenvector $w$ (obtained by the same argument applied to $A^{⊤}$ ) gives $λ (w \cdot ∣ u ∣) = w^{⊤} A ∣ u ∣ \geq ∣ μ ∣ (w \cdot ∣ u ∣)$ , and $w \cdot ∣ u ∣ > 0$ , hence $∣ μ ∣ \leq λ$ . So $λ$ is the spectral radius.

Simplicity: suppose $A u = λ u$ for some real $u$ not proportional to $v$ . For small $t$ the vector $v - t u$ is still positive; increasing $t$ to the first value $t_{0}$ where a coordinate hits $0$ gives $z = v - t_{0} u \geq 0$ , $z \neq = 0$ , $z$ has a zero coordinate, and $A z = λ z$ . But $(I + A)^{N - 1} z = (1 + λ)^{N - 1} z$ must be strictly positive by the irreducibility argument, contradicting the zero coordinate of $z$ . So the $λ$ -eigenspace is one-dimensional; a short additional argument with the left eigenvector $w$ (the geometric and algebraic multiplicities coincide because $w^{⊤} v > 0$ shows $λ$ is not a defective eigenvalue) gives algebraic simplicity.

Uniqueness of maximal modulus under primitivity: let $μ$ be an eigenvalue with $∣ μ ∣ = λ$ and eigenvector $u$ . Then $A ∣ u ∣ \geq λ ∣ u ∣$ as above, and pairing with $w$ forces equality $A ∣ u ∣ = λ ∣ u ∣$ , so $∣ u ∣$ is a positive Perron eigenvector, hence $∣ u ∣ = v$ up to scale, so $∣ u_{i} ∣ = v_{i} > 0$ for all $i$ . Equality in the triangle inequality $∣ \sum_{j} A_{ij} u_{j} ∣ = \sum_{j} A_{ij} ∣ u_{j} ∣$ at each $i$ forces all $u_{j}$ (over $j$ with $A_{ij} > 0$ ) to share a common phase $e^{i θ_{i}}$ ; writing $u_{j} = v_{j} e^{i ϕ_{j}}$ , primitivity (some $A^{m} > 0$ ) propagates a single global phase relation $μ = λ e^{i ψ}$ with $e^{i ψ} = 1$ , forcing $μ = λ$ . (For merely irreducible $A$ of period $d$ , the same analysis yields exactly $d$ peripheral eigenvalues $λ e^{2 π ik / d}$ .)

Part (b). Order the alphabet and recall $∣ L_{n} (X_{A}) ∣ = \sum_{i, j} (A^{n - 1})_{ij}$ , the total number of admissible words of length $n$ (each word is a walk of $n - 1$ steps). Let $1$ be the all-ones vector. Then $p_{n} = 1^{⊤} A^{n - 1} 1$ . Using the positive Perron eigenvectors $v, w$ normalised so $w^{⊤} v = 1$ , write $A^{m} = λ^{m} v w^{⊤} + R^{m}$ where $R$ is the action of $A$ on the complementary spectral subspace, with spectral radius $ρ (R) < λ$ when $A$ is primitive and $ρ (R) \leq λ$ in general. The lower bound: $p_{n} \geq (1^{⊤} v) (w^{⊤} 1) λ^{n - 1} - C ρ (R)^{n - 1} \geq c_{1} λ^{n}$ for large $n$ , where $(1^{⊤} v) (w^{⊤} 1) > 0$ . The upper bound: each entry of $A^{n - 1}$ is at most a polynomial-in- $n$ multiple of $λ^{n - 1}$ (the Jordan form has its largest block on the eigenvalue $λ$ , which is simple, so in fact the $λ$ -part contributes no polynomial factor and the subdominant Jordan blocks contribute at most $n^{r} ρ (R)^{n} \leq n^{r} λ^{n}$ ). Taking logarithms and dividing by $n$ , both bounds give $\frac{1}{n} lo g p_{n} \to lo g λ$ . Hence $h (X_{A}) = lo g λ (A)$ . $□$

Bridge. This theorem builds toward the whole entropy theory of dynamical systems and appears again in the variational principle and in thermodynamic formalism, because it pins the topological entropy of a finite-type system to one algebraic number read off a matrix. The foundational reason the spectral radius governs the count is that the word totals are $p_{n} = 1^{⊤} A^{n - 1} 1$ , a fixed linear functional of the matrix powers, so their growth is set by the dominant eigenvalue exactly as the periodic-point count $tr (A^{n}) \sim λ^{n}$ of 38.02.02 was; this is exactly the principle that the trace, the word count, and the zeta-function pole all locate the same number $λ$ . The Perron-Frobenius half is dual to the stochastic Perron-Frobenius of 37.05.02: there the irreducible non-negative matrix is row-stochastic with Perron root $1$ and positive Perron eigenvector the stationary distribution, here the Perron root is $λ > 1$ and its logarithm is the entropy, but the existence-uniqueness-positivity package and the primitivity-gives-a-spectral-gap statement are the same theorem. Putting these together, entropy generalises from this combinatorial growth rate to the measure-theoretic and topological entropies that organise all of ergodic theory, and the bridge is the variational principle linking $lo g λ$ to the supremum of measure-theoretic entropies over invariant measures.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Show that for any irreducible $A$ with right Perron eigenvector $v > 0$ and Perron root $λ$ , the entropy satisfies $lo g (min_{i} \frac{( A v ) _{i}}{v _{i}}) \leq lo g λ \leq lo g (max_{i} \frac{( A v ) _{i}}{v _{i}})$ , and deduce that for the genuine Perron eigenvector both bounds collapse to $lo g λ$ .

Hint

This is the Collatz-Wielandt characterisation: $λ = max_{x > 0} min_{i} (A x)_{i} / x_{i}$ .

Answer

For any $x > 0$ let $m = min_{i} (A x)_{i} / x_{i}$ and $M = max_{i} (A x)_{i} / x_{i}$ , so $m x \leq A x \leq M x$ entrywise. Pairing $A x \geq m x$ with the positive left eigenvector $w$ gives $λ (w \cdot x) = w^{⊤} A x \geq m (w \cdot x)$ , hence $m \leq λ$ ; pairing $A x \leq M x$ gives $λ \leq M$ . Thus $m \leq λ \leq M$ , the Collatz-Wielandt bounds. When $x = v$ is the Perron eigenvector, $A v = λ v$ makes every ratio $(A v)_{i} / v_{i} = λ$ , so $m = M = λ$ and both bounds are exactly $lo g λ$ . Rubric: full credit for the $w$ -pairing argument and the collapse at $x = v$ .

Exercise 7 (hard, short-answer).

Prove that the topological entropy of an irreducible SFT equals the exponential growth rate of periodic points: $lim_{n} \frac{1}{n} lo g # Fix (σ^{n}) = lo g λ$ . Why does this match the word-count growth rate?

Hint

$# Fix (σ^{n}) = tr (A^{n}) = \sum_{i} μ_{i}^{n}$ over eigenvalues $μ_{i}$ ; the dominant term is $λ^{n}$ along the period.

Answer

By 38.02.02, $# Fix (σ^{n}) = tr (A^{n}) = \sum_{i} μ_{i}^{n}$ summed over eigenvalues $μ_{i}$ with multiplicity. The Perron root $λ$ is simple and dominates all moduli, so $tr (A^{n}) = λ^{n} + O (ρ (R)^{n} \cdot poly (n))$ with $ρ (R) \leq λ$ ; for primitive $A$ the error is $o (λ^{n})$ and $tr (A^{n}) \sim λ^{n}$ . For imprimitive irreducible $A$ of period $d$ , the peripheral eigenvalues $λ e^{2 π ik / d}$ make $tr (A^{n})$ oscillate but along $n$ divisible by $d$ it equals $d λ^{n} (1 + o (1))$ , so $lim sup$ and the $d$ -periodic $lim inf$ both give growth rate $lo g λ$ . Either way $\frac{1}{n} lo g # Fix (σ^{n}) \to lo g λ$ . This equals the word-count rate because both quantities are linear functionals of $A^{n}$ ( $tr (A^{n})$ versus $1^{⊤} A^{n} 1$ ) and the dominant eigenvalue controls the asymptotics of every such functional with a positive component on the Perron eigenspace. Rubric: full credit for the eigenvalue-sum argument, handling the periodic case, and the shared-dominant-eigenvalue explanation.

Exercise 8 (hard, short-answer).

Let $A$ be primitive with Perron data $λ, v, w$ normalised so $w^{⊤} v = 1$ . Prove the rank-one limit $λ^{- n} A^{n} \to v w^{⊤}$ , and use it to give the sharp asymptotic $p_{n} \sim (1^{⊤} v) (w^{⊤} 1) λ^{n - 1}$ for the word counts.

Hint

Write $A = λ v w^{⊤} + R$ with $v w^{⊤} R = R v w^{⊤} = 0$ and $ρ (R) < λ$ ; then $A^{n} = λ^{n} v w^{⊤} + R^{n}$ .

Answer

Since $λ$ is simple, $R^{N} = ⟨ v ⟩ \oplus H$ where $H = {x : w^{⊤} x = 0}$ is $A$ -invariant; let $P = v w^{⊤}$ be the spectral projection onto $⟨ v ⟩$ (idempotent since $w^{⊤} v = 1$ ), and $R = A (I - P) = A - λ P$ . Then $P R = R P = 0$ and $R$ restricted to $H$ has spectral radius $ρ (R) < λ$ by primitivity (no peripheral eigenvalue besides $λ$ ). Hence $A^{n} = λ^{n} P + R^{n}$ , and $λ^{- n} A^{n} = P + (R / λ)^{n} \to P = v w^{⊤}$ because $ρ (R / λ) < 1$ . Consequently $p_{n} = 1^{⊤} A^{n - 1} 1 = λ^{n - 1} (1^{⊤} v) (w^{⊤} 1) + 1^{⊤} R^{n - 1} 1$ , and the remainder is $O (ρ (R)^{n - 1}) = o (λ^{n - 1})$ , giving $p_{n} \sim (1^{⊤} v) (w^{⊤} 1) λ^{n - 1}$ . Rubric: full credit for the spectral-projection decomposition, the $ρ (R) < λ$ step, and the leading asymptotic constant.

Advanced results Master

Theorem (the Birkhoff-Hilbert metric contraction proof). Let $A$ be a primitive non-negative matrix and equip the open positive cone $\overset{˚}{C} = {x : x > 0}$ with the Hilbert projective metric $θ (x, y) = lo g \frac{m a x _{i} ( x _{i} / y _{i} )}{m i n _{i} ( x _{i} / y _{i} )}$ . Then $A$ acts as a contraction of $(\overset{˚}{C} / \sim, θ)$ with Birkhoff contraction ratio $τ (A) = tanh (\frac{1}{4} Δ (A)) < 1$ , where $Δ (A) = sup_{i, j, k, l} lo g \frac{A _{ik} A _{j l}}{A _{j k} A _{i l}}$ is the projective diameter of the image. The unique fixed ray is the Perron eigenvector $v$ , and $λ^{- n} A^{n} \to v w^{⊤}$ geometrically at rate $τ (A)$ . (See ^{[Seneta 1981 Ch. 1-2]}.)

The Hilbert metric collapses the scaling freedom: two positive vectors are at distance $0$ iff proportional, and $A$ — by Birkhoff's theorem — strictly shrinks this metric whenever its image has finite projective diameter, which a primitive matrix achieves after finitely many steps. The Banach fixed-point theorem then delivers the Perron eigenvector as the unique attracting ray and quantifies the spectral gap as the contraction ratio $τ (A) < 1$ , so the subdominant modulus obeys $ρ (R) / λ \leq τ (A)$ . This is the analytic engine behind the cleaner existence proof: Brouwer gives a fixed point, but Birkhoff-Hilbert gives uniqueness, simplicity, and an exponential convergence rate in one stroke, and it is the form that survives to infinite-dimensional Perron-Frobenius (Ruelle's transfer operators in thermodynamic formalism).

Theorem (Lind's characterisation of SFT entropies). A real number $β \geq 1$ equals $e^{h (X)}$ for some irreducible SFT $X$ iff $β$ is a Perron number: a real algebraic integer $β \geq 1$ that strictly exceeds the modulus of each of its Galois conjugates. Equivalently, the set of SFT growth rates is exactly ${λ (A) : A an irreducible non-negative integer matrix}$ , the Perron numbers. (See ^{[Lind-Marcus 1995 Ch. 4]}.)

That the spectral radius of an irreducible non-negative integer matrix is a Perron number is immediate from Perron-Frobenius: $λ$ is a simple root of the integer characteristic polynomial, hence an algebraic integer strictly dominating its conjugates in modulus. The depth is the converse: every Perron number is realised as some $λ (A)$ , proved by Lind via an explicit companion-type construction that builds an integer matrix whose Perron root is the prescribed algebraic integer. The characterisation closes the realisation question and identifies the entropies of finite-type symbolic systems with a clean number-theoretic class, placing topological entropy at the interface of dynamics and algebraic number theory; it is the spectral-radius counterpart of the rationality of the zeta function, both turning combinatorial data into algebraic invariants.

Theorem (variational principle for SFTs and the measure of maximal entropy). For an irreducible SFT $X_{A}$ , the topological entropy $lo g λ (A)$ equals $sup_{μ} h_{μ} (σ)$ over $σ$ -invariant Borel probability measures $μ$ , and the supremum is attained by a unique measure, the Parry measure, whose transition probabilities are $P_{ij} = \frac{A _{ij} v _{j}}{λ v _{i}}$ with stationary distribution $π_{i} = w_{i} v_{i}$ built from the left and right Perron eigenvectors. (See ^{[Walters 1982 §7.2-§7.3]}.)

The variational principle identifies the topological entropy of an SFT with the largest measure-theoretic entropy any invariant measure can carry, and the maximiser is constructed directly from Perron-Frobenius data: rescaling the $0/1$ (or non-negative integer) matrix by the right Perron eigenvector $v$ and the eigenvalue $λ$ produces a stochastic matrix $P$ — this is exactly the diagonal similarity $P = λ^{- 1} D^{- 1} A D$ with $D = diag (v)$ — whose stationary chain is the unique measure of maximal entropy. This is the precise junction with 37.05.02: the Parry measure is the Markov measure whose stochastic transition matrix is the Perron-rescaled topological matrix, so the topological Perron root $λ$ and the stochastic Perron eigenvalue $1$ of 37.05.02 are two views of one diagonal change of variables.

Synthesis. Putting these together, the entire entropy theory of finite-type symbolic dynamics is the spectral theory of one non-negative matrix, and the central insight is that the Perron root $λ$ is simultaneously the word-growth rate, the periodic-point growth rate, the smallest zeta-pole reciprocal, and the maximal measure-theoretic entropy. The foundational reason these coincide is that each is a linear functional of the matrix powers $A^{n}$ with a positive component along the simple dominant eigenspace, so the Perron-Frobenius theorem forces them all to grow at rate $λ$ ; this is exactly the principle that the trace counts loops, the determinant packages them, and the dominant eigenvalue measures the richness. The construction is dual to the stochastic Perron-Frobenius of 37.05.02: the Parry measure is built by the diagonal similarity $P = λ^{- 1} diag (v)^{- 1} A diag (v)$ that turns the topological matrix with Perron root $λ$ into a stochastic matrix with Perron root $1$ , so the stationary distribution there and the measure of maximal entropy here are the same object seen through one rescaling, and the central insight generalises: entropy is the logarithm of a spectral radius. The bridge onward is that the variational principle promotes this identity to all dynamical systems through thermodynamic formalism, where the Perron-Frobenius theorem becomes the Ruelle-Perron-Frobenius theorem for transfer operators and the Perron root becomes the pressure, so this unit's finite matrix is the first nontrivial instance of the operator that organises equilibrium statistical mechanics on shift spaces.

Full proof set Master

Proposition 1 (Perron root is the spectral radius and is positive). For an irreducible non-negative $A$ , $ρ (A) > 0$ is an eigenvalue with a strictly positive eigenvector.

Proof. Apply $T (x) = A x /∥ A x ∥_{1}$ to the simplex $Δ$ ; irreducibility makes $A x \neq = 0$ for $x \geq 0$ , $x \neq = 0$ (some row reaches a nonzero coordinate), so $T : Δ \to Δ$ is continuous on the compact convex $Δ$ and Brouwer gives a fixed point $v$ with $A v = λ v$ , $λ = ∥ A v ∥_{1} > 0$ , $v \geq 0$ . Positivity: $(I + A)^{N - 1}$ is entrywise positive because for a strongly connected graph on $N$ vertices every ordered pair is joined by a walk of length $\leq N - 1$ , so $(I + A)^{N - 1} v = (1 + λ)^{N - 1} v$ is strictly positive, forcing $v > 0$ . That $λ = ρ (A)$ : for any eigenpair $(μ, u)$ , $∣ μ ∣ ∣ u ∣ \leq A ∣ u ∣$ entrywise; pairing with the positive left eigenvector $w$ gives $∣ μ ∣ (w \cdot ∣ u ∣) \leq λ (w \cdot ∣ u ∣)$ with $w \cdot ∣ u ∣ > 0$ , so $∣ μ ∣ \leq λ$ . $□$

Proposition 2 (simplicity of the Perron root). The eigenvalue $λ = ρ (A)$ of an irreducible non-negative matrix is algebraically simple.

Proof. Geometric simplicity first. Suppose $A u = λ u$ with $u$ real and independent of $v$ . Choose $t_{0} = min_{i} v_{i} / u_{i}$ over indices with $u_{i} > 0$ (or use $- u$ if needed) so that $z = v - t_{0} u \geq 0$ has at least one zero coordinate and $z \neq = 0$ (independence). Then $A z = λ z$ , and $(I + A)^{N - 1} z = (1 + λ)^{N - 1} z$ is strictly positive by the walk argument of Proposition 1, contradicting the zero coordinate. So the $λ$ -eigenspace is one-dimensional. Algebraic simplicity: let $w > 0$ be the left Perron eigenvector. If $λ$ were a defective eigenvalue there would be a generalized eigenvector $u_{1}$ with $(A - λ) u_{1} = v$ . Then $w^{⊤} (A - λ) u_{1} = (w^{⊤} A - λ w^{⊤}) u_{1} = 0$ , but the left side is $w^{⊤} v > 0$ , a contradiction. Hence the Jordan block at $λ$ is $1 \times 1$ and $λ$ is algebraically simple. $□$

Proposition 3 (primitive ⇔ unique eigenvalue of maximal modulus). An irreducible non-negative matrix $A$ is primitive iff $λ = ρ (A)$ strictly exceeds the modulus of every other eigenvalue.

Proof. ( $\Rightarrow$ ) Let $∣ μ ∣ = λ$ with eigenvector $u$ . From $∣ μ ∣∣ u ∣ \leq A ∣ u ∣$ and equality after pairing with $w$ , we get $A ∣ u ∣ = λ ∣ u ∣$ , so $∣ u ∣$ is a positive Perron eigenvector, $∣ u ∣ = v$ up to scale. Equality in $∣ \sum_{j} A_{ij} u_{j} ∣ = \sum_{j} A_{ij} ∣ u_{j} ∣$ forces, for each $i$ , all $u_{j}$ with $A_{ij} > 0$ to have a common argument; writing $u = D v$ with $D = diag (e^{i ϕ_{k}})$ unitary, the relation becomes $A D = (μ / λ) D A$ on the support, and iterating, $A^{m} D = (μ / λ)^{m} D A^{m}$ . Primitivity gives $A^{m} > 0$ for some $m$ , and a strictly positive matrix equation $A^{m} D = (μ / λ)^{m} D A^{m}$ with $D$ diagonal unitary forces $(μ / λ)^{m} = 1$ and $D$ scalar, so $u ∥ v$ and $μ = λ$ . ( $\Leftarrow$ ) If $λ$ is the strict-maximum-modulus simple eigenvalue, then $λ^{- n} A^{n} \to v w^{⊤} > 0$ (Proposition 5 below), so $A^{n} > 0$ for large $n$ : $A$ is primitive. $□$

Proposition 4 (entropy equals log Perron root). For an irreducible $0/1$ transition matrix $A$ , $h (X_{A}) = lo g λ (A)$ .

Proof. $p_{n} = ∣ L_{n} (X_{A}) ∣ = 1^{⊤} A^{n - 1} 1$ . Lower bound: with $v, w > 0$ Perron eigenvectors normalised $w^{⊤} v = 1$ and spectral decomposition $A^{m} = λ^{m} v w^{⊤} + R^{m}$ ( $ρ (R) \leq λ$ , and $v w^{⊤}$ the spectral projection), $p_{n} \geq λ^{n - 1} (1^{⊤} v) (w^{⊤} 1) - ∥ 1^{⊤} R^{n - 1} 1 ∥$ . The constant $(1^{⊤} v) (w^{⊤} 1) > 0$ since $v, w > 0$ , and the remainder is $O (n^{r} ρ (R)^{n - 1})$ ; dividing $lo g p_{n}$ by $n$ gives $lim inf \geq lo g λ$ . Upper bound: every entry of $A^{n - 1}$ is bounded by $\sum_{i} μ_{i}$ -type Jordan estimates by $C n^{r} λ^{n - 1}$ since $λ = ρ (A)$ and $λ$ is the largest modulus, so $p_{n} \leq N^{2} C n^{r} λ^{n - 1}$ and $lim sup \frac{1}{n} lo g p_{n} \leq lo g λ$ . The two bounds meet; the limit exists by subadditivity (Fekete) and equals $lo g λ$ . $□$

Proposition 5 (rank-one power limit, primitive case). For primitive $A$ with $w^{⊤} v = 1$ , $λ^{- n} A^{n} \to v w^{⊤}$ .

Proof. Simplicity of $λ$ (Proposition 2) splits $R^{N} = ⟨ v ⟩ \oplus H$ , $H = ker w^{⊤}$ , both $A$ -invariant. Let $P = v w^{⊤}$ (idempotent, $P A = A P = λ P$ ) and $R = A - λ P$ , so $A^{n} = λ^{n} P + R^{n}$ and $R$ acts on $H$ with eigenvalues the non- $λ$ eigenvalues of $A$ , all of modulus $< λ$ by Proposition 3. Hence $∥ (R / λ)^{n} ∥ \to 0$ and $λ^{- n} A^{n} = P + (R / λ)^{n} \to P = v w^{⊤}$ . $□$

Proposition 6 (the Parry measure attains the entropy). For an irreducible $0/1$ matrix $A$ with Perron data $λ, v, w$ , the stochastic matrix $P_{ij} = A_{ij} v_{j} / (λ v_{i})$ is well-defined and stochastic, its stationary distribution is $π_{i} = w_{i} v_{i}$ (normalised), and the associated Markov measure $μ$ has $h_{μ} (σ) = lo g λ = h (X_{A})$ , the maximum over invariant measures.

Proof. Stochastic: $\sum_{j} P_{ij} = \frac{1}{λ v _{i}} \sum_{j} A_{ij} v_{j} = \frac{( A v ) _{i}}{λ v _{i}} = \frac{λ v _{i}}{λ v _{i}} = 1$ , and $P_{ij} \geq 0$ . Stationarity: $\sum_{i} π_{i} P_{ij} = \sum_{i} w_{i} v_{i} \frac{A _{ij} v _{j}}{λ v _{i}} = \frac{v _{j}}{λ} \sum_{i} w_{i} A_{ij} = \frac{v _{j}}{λ} (w^{⊤} A)_{j} = \frac{v _{j}}{λ} λ w_{j} = v_{j} w_{j} = π_{j}$ , so $π P = π$ (after normalising $\sum_{i} w_{i} v_{i} = 1$ ). Entropy of the Markov measure: $h_{μ} (σ) = - \sum_{i, j} π_{i} P_{ij} lo g P_{ij}$ . Substituting $lo g P_{ij} = lo g A_{ij} + lo g v_{j} - lo g λ - lo g v_{i}$ and using $A_{ij} \in {0, 1}$ (so $lo g A_{ij} = 0$ on the support), the $lo g v_{j}$ and $lo g v_{i}$ contributions telescope under stationarity ( $\sum_{i, j} π_{i} P_{ij} lo g v_{j} = \sum_{j} π_{j} lo g v_{j} = \sum_{i} π_{i} lo g v_{i}$ cancels), leaving $h_{μ} (σ) = lo g λ \sum_{i, j} π_{i} P_{ij} = lo g λ$ . By the variational principle $h_{μ} \leq h (X_{A}) = lo g λ$ for every invariant $μ$ , and equality holds here, so $μ$ is a measure of maximal entropy; uniqueness follows from strict concavity of entropy on the simplex of Markov measures with full support. $□$

Connections Master

Shifts of finite type, transition matrices, and coding 38.02.02. This unit supplies the spectral half of that prerequisite's combinatorial theory: the periodic-point count $tr (A^{n}) \sim λ^{n}$ and the zeta-pole at $1/ λ$ established there are governed by the Perron root analysed here, and the entropy $lo g λ$ becomes the conjugacy invariant that strong shift equivalence preserves. The upstream unit owns the matrix and its trace; this unit owns the dominant eigenvalue and the entropy it computes.
Class structure, irreducibility, and periodicity of Markov chains 37.05.02. The Perron-Frobenius theorem proved here is the topological twin of the stochastic Perron-Frobenius there: an irreducible non-negative matrix has a simple positive dominant eigenvalue with positive eigenvectors, equal to $1$ for a row-stochastic chain (carrying the stationary distribution) and to $λ > 1$ for a counting matrix (carrying the entropy). The Parry measure of maximal entropy is exactly the Markov chain of 37.05.02 obtained by the diagonal Perron rescaling, so this unit's hooks_out records the link.
Topological transitivity, topological mixing, and Devaney chaos 38.01.03. The irreducible/primitive dichotomy that makes the Perron root simple or strictly dominant is precisely the transitive/mixing dichotomy of that unit read on the transition matrix: irreducibility gives a simple Perron root and topological transitivity, while primitivity gives a strict spectral gap and topological mixing. The positive entropy $lo g λ > 0$ for any non-degenerate SFT certifies the exponential orbit complexity that the chaos definitions there describe qualitatively.

Historical & philosophical context Master

The dominant-eigenvalue theory originates with Oskar Perron, who proved in his 1907 paper Zur Theorie der Matrices (Mathematische Annalen 64, 248-263) ^{[Perron 1907]} that a strictly positive square matrix has a positive eigenvalue of maximal modulus, simple and with a positive eigenvector. Georg Frobenius extended this to non-negative matrices in a sequence of Berlin Academy papers culminating in Über Matrizen aus nicht negativen Elementen (Sitzungsberichte der Preußischen Akademie, 1912), isolating irreducibility as the hypothesis that preserves simplicity and positivity, and developing the imprimitivity (period) theory that pins the peripheral eigenvalues to the roots of unity $λ e^{2 π ik / d}$ . The Birkhoff projective-metric proof, which recasts Perron-Frobenius as a contraction in Hilbert's metric on the positive cone, is due to Garrett Birkhoff (1957), building on Hilbert's 1895 projective metric; it is the form that generalises to the Ruelle-Perron-Frobenius transfer operators of thermodynamic formalism.

The application to symbolic dynamics — that the topological entropy of a subshift of finite type is $lo g λ (A)$ — was crystallised in the ergodic-theory program of the 1960s and 1970s, with William Parry's 1964 construction of the measure of maximal entropy (the Parry measure) from the Perron eigenvectors and the variational principle for topological entropy established by Goodman, Goodwyn, and Dinaburg. The number-theoretic characterisation of the achievable growth rates was completed by Douglas Lind, The entropies of topological Markov shifts and a related class of algebraic integers (Ergodic Theory and Dynamical Systems 4, 1984, 283-300), which proved that the SFT entropies are exactly the logarithms of Perron numbers. The textbook synthesis is Lind and Marcus' 1995 An Introduction to Symbolic Dynamics and Coding (Cambridge) ^{[Lind-Marcus 1995]}, organising entropy around the Perron eigenvalue, with Seneta's Non-negative Matrices and Markov Chains ^{[Seneta 1981]} the standard reference for the matrix theory.

Bibliography Master

@article{Perron1907,
  author  = {Perron, Oskar},
  title   = {Zur Theorie der Matrices},
  journal = {Mathematische Annalen},
  volume  = {64},
  year    = {1907},
  pages   = {248--263}
}

@article{Frobenius1912,
  author  = {Frobenius, Georg},
  title   = {{\"U}ber Matrizen aus nicht negativen Elementen},
  journal = {Sitzungsberichte der K{\"o}niglich Preu{\ss}ischen Akademie der Wissenschaften},
  year    = {1912},
  pages   = {456--477}
}

@article{Lind1984,
  author  = {Lind, Douglas A.},
  title   = {The entropies of topological Markov shifts and a related class of algebraic integers},
  journal = {Ergodic Theory and Dynamical Systems},
  volume  = {4},
  year    = {1984},
  pages   = {283--300}
}

@article{Parry1964,
  author  = {Parry, William},
  title   = {Intrinsic Markov chains},
  journal = {Transactions of the American Mathematical Society},
  volume  = {112},
  year    = {1964},
  pages   = {55--66}
}

@book{LindMarcus1995pf,
  author    = {Lind, Douglas and Marcus, Brian},
  title     = {An Introduction to Symbolic Dynamics and Coding},
  publisher = {Cambridge University Press},
  year      = {1995}
}

@book{Seneta1981,
  author    = {Seneta, Eugene},
  title     = {Non-negative Matrices and Markov Chains},
  publisher = {Springer-Verlag},
  series    = {Springer Series in Statistics},
  year      = {1981}
}

@book{Walters1982,
  author    = {Walters, Peter},
  title     = {An Introduction to Ergodic Theory},
  publisher = {Springer-Verlag},
  series    = {Graduate Texts in Mathematics},
  volume    = {79},
  year      = {1982}
}

@article{Birkhoff1957,
  author  = {Birkhoff, Garrett},
  title   = {Extensions of Jentzsch's theorem},
  journal = {Transactions of the American Mathematical Society},
  volume  = {85},
  year    = {1957},
  pages   = {219--227}
}

Prerequisites

38.02.02
38.01.03

Tier anchors

beginner: Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 4 (entropy and the Perron eigenvalue, the golden-mean growth rate); 3Blue1Brown *Eigenvalues and eigenvectors* for the visual of a vector pulled toward a dominant direction under repeated matrix application
intermediate: Brin-Stuck 2002 *Introduction to Dynamical Systems* (Cambridge University Press) Ch. 3 §3.3-§3.5 (Perron-Frobenius for topological Markov chains, the spectral radius, entropy as log of the Perron root); Seneta 1981 *Non-negative Matrices and Markov Chains* (Springer) Ch. 1 (the Perron-Frobenius theorem for irreducible and primitive matrices)
master: Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 4 and §4.3-§4.5 (the Perron number characterisation of SFT entropies, the spectral radius as growth rate); Walters 1982 *An Introduction to Ergodic Theory* (Springer GTM 79) §7.2-§7.3 (topological entropy, the variational principle, entropy of subshifts); Seneta 1981 *Non-negative Matrices and Markov Chains* (Springer) Ch. 1-2 (Perron-Frobenius, the Birkhoff-Hilbert projective metric contraction proof)

References

Brin, Stuck 2002 — Introduction to Dynamical Systems · Ch. 3 §3.3-§3.5 (the Perron-Frobenius theorem for non-negative matrices, the spectral radius of an irreducible matrix, topological entropy of a topological Markov chain = log of the Perron root, the zeta function); Cambridge University Press 2002
Lind, Marcus 1995 — An Introduction to Symbolic Dynamics and Coding · Ch. 4 (entropy, the Perron-Frobenius eigenvalue, #words of length n ~ lambda^n, the Perron-number characterisation of SFT growth rates); Cambridge University Press 1995
Seneta 1981 — Non-negative Matrices and Markov Chains · Ch. 1-2 (the Perron-Frobenius theorem for irreducible and primitive non-negative matrices, simplicity of the Perron root, strict positivity of the eigenvectors, the spectral-gap/aperiodicity characterisation of the dominant eigenvalue; the projective-metric contraction argument); Springer Series in Statistics 1981
Walters 1982 — An Introduction to Ergodic Theory · Springer GTM 79, §7.1-§7.3 (topological entropy via open covers and via separated/spanning sets, entropy of subshifts, the variational principle)
Perron 1907 — Zur Theorie der Matrices · Mathematische Annalen 64 (1907) 248-263 (the dominant positive eigenvalue of a strictly positive matrix); Frobenius 1912 — Über Matrizen aus nicht negativen Elementen, Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften (1912) 456-477 (extension to irreducible non-negative matrices, the period/imprimitivity theory)

Estimated time

beginner: 18m
intermediate: 50m
master: 88m