38.02.02 · dynamics / symbolic-dynamics

Shifts of Finite Type, Transition Matrices, and Coding

shipped3 tiersLean: none

Anchor (Master): Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 2-7 (edge shifts, the conjugacy problem, state splitting, strong shift equivalence, the Decomposition and Classification theorems, sofic shifts); Kitchens 1998 *Symbolic Dynamics* (Springer Universitext) Ch. 2; Williams 1973 *Classification of subshifts of finite type* (Annals of Mathematics 98) — the origin of strong shift equivalence; Bowen-Lanford 1970 *Zeta functions of restrictions of the shift transformation* (Proc. Symp. Pure Math. 14) — the rationality of the SFT zeta function

Intuition Beginner

A subshift is the set of all sequences that avoid some list of forbidden patterns. The friendliest case is when the only patterns you forbid are pairs of adjacent letters: you draw a small map of dots, one dot per letter, and an arrow from letter $a$ to letter $b$ exactly when the pair $ab$ is allowed. An allowed sequence is then nothing more than an endless walk that always travels along arrows of your map. The whole system is captured by a tiny picture, and the messy question "which infinite strings are legal?" becomes the concrete question "which walks does this graph permit?"

The map can be packaged as a square table of zeros and ones: put a $1$ in row $a$ , column $b$ when there is an arrow from $a$ to $b$ , and a $0$ when there is none. This table is the transition matrix. It looks just like the probability table of a random walk, but it has thrown the probabilities away and kept only the bare fact of which steps are possible. That single change — from "how likely" to "is it allowed" — is the whole difference between the random world and the symbolic one, and it is why the same little graph governs both.

The surprise is how much the table remembers. Multiply the table by itself $n$ times and the entries count the walks of length $n$ . The diagonal then counts the loops — the walks that return to where they started — which are exactly the sequences that repeat with period $n$ . So a question about repeating patterns in infinite strings becomes a question you answer by multiplying a small matrix.

Visual Beginner

Picture three dots labelled $a$ , $b$ , $c$ , with arrows showing which letter may follow which. Say $a$ may go to $a$ or $b$ , $b$ may go only to $c$ , and $c$ may go to $a$ . An allowed sequence is any endless trip that always follows an arrow: you can sit at $a$ for a while, then hop to $b$ , then you are forced to $c$ , then back to $a$ , and so on.

Beside the picture sits its table. Reading row $a$ : a $1$ under $a$ and under $b$ , a $0$ under $c$ , because $a$ may go to $a$ or $b$ but not straight to $c$ . The table below contrasts the two ways of describing the same allowed sequences.

description	the graph picture	the matrix picture
what a letter is	a dot	a row-and-column index
what "allowed pair" means	an arrow $a \to b$	a $1$ in row $a$ , column $b$
an allowed sequence	an endless walk along arrows	a sequence of indices with each step a $1$
how many length- $n$ walks	count paths by hand	add up the entries of the table multiplied $n$ times
sequences repeating with period $n$	closed loops of length $n$	the diagonal sum of that $n$ -th power

Worked example Beginner

Take the golden-mean rule on two letters $0$ and $1$ : the only forbidden pair is $11$ . The graph has an arrow $0 \to 0$ , an arrow $0 \to 1$ , and an arrow $1 \to 0$ , but no arrow $1 \to 1$ . Its transition matrix, with rows and columns ordered $0$ then $1$ , is $$ A = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}. $$ We will count the sequences that repeat with period $n$ by computing the diagonal sum of powers of $A$ .

Step 1. Square the matrix. Multiplying $A$ by itself, $$ A^2 = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 \ 1 & 1 \end{pmatrix}. $$ The diagonal entries are $2$ and $1$ , and they add to $3$ . So there are $3$ closed walks of length $2$ .

Step 2. Multiply once more. From $A^{2}$ and $A$ , $$ A^3 = \begin{pmatrix} 2 & 1 \ 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 2 \ 2 & 1 \end{pmatrix}. $$ The diagonal entries are $3$ and $1$ , adding to $4$ . So there are $4$ closed walks of length $3$ .

Step 3. Read off the diagonal sums. The diagonal sum of $A^{1}$ is $1 + 0 = 1$ ; of $A^{2}$ it is $3$ ; of $A^{3}$ it is $4$ . These count the period- $1$ , period- $2$ , and period- $3$ repeating sequences allowed by the golden-mean rule (counting each by the length of its repeating block).

Step 4. Notice the Fibonacci flavour. The numbers $1, 3, 4, 7, 11, \dots$ that come out are the Lucas numbers, the close cousins of the Fibonacci counts of allowed words. Both grow at the same rate, set by the golden ratio.

What this tells us: the single banned pair $11$ is enough to fix the count of every repeating sequence, and you recover those counts by the purely mechanical act of multiplying a two-by-two table and adding its diagonal. The graph forbids one arrow; the matrix does all the bookkeeping.

Check your understanding Beginner

Formal definition Intermediate+

Fix a finite alphabet $A$ and recall from 38.02.01 that a subshift is a closed, shift-invariant subset of the full shift $A^{Z}$ , and that a subshift defined by a finite set of forbidden words is a subshift of finite type (SFT). When the forbidden words all have length $2$ , the SFT is a topological Markov chain: it is described by a $0/1$ transition matrix $A = (A_{ab})_{a, b \in A}$ indexed by the alphabet $A$ , with $A_{ab} = 1$ iff the block $ab$ is allowed. Then $$ \mathsf{X}A = { x \in \mathcal{A}^{\mathbb{Z}} : A{x_n x_{n+1}} = 1 \text{ for all } n \in \mathbb{Z} }. $$ This $0/1$ matrix is the topological analogue of the stochastic transition matrix of a Markov chain 37.05.02: where the stochastic matrix records the probability of $a \to b$ , the transition matrix records merely whether $a \to b$ is permitted. The two share the same support graph $G_{A}$ (vertices $A$ , an edge $a \to b$ iff $A_{ab} = 1$ ), and every combinatorial notion below is read off $G_{A}$ alone.

Definition (vertex and edge shifts). Let $G$ be a finite directed graph with vertex set $V$ and edge set $E$ . The vertex shift $\hat{X}_{G} \subseteq V^{Z}$ is the set of bi-infinite vertex sequences $(v_{n})$ with $v_{n} \to v_{n + 1}$ an edge for every $n$ ; this is $X_{A}$ for $A$ the vertex adjacency matrix. The edge shift $X_{G} \subseteq E^{Z}$ is the set of bi-infinite edge sequences $(e_{n})$ with $terminal (e_{n}) = initial (e_{n + 1})$ ; this is the vertex shift of the line graph of $G$ , and it is the SFT defined by the edge adjacency. Multiple edges between two vertices are allowed, so the edge adjacency matrix is a general non-negative integer matrix, not merely $0/1$ .

Definition (higher-block presentation). For $N \geq 1$ , the $N$ -th higher-block code $β_{N} : X_{A} \to (L_{N})^{Z}$ sends $x$ to the sequence whose $n$ -th symbol is the block $x_{n} x_{n + 1} \dots x_{n + N - 1}$ , an element of the allowed- $N$ -block alphabet $L_{N} = L_{N} (X_{A})$ . It is an invertible sliding-block code onto its image, the higher-block presentation $X_{A}^{[N]}$ .

Definition (irreducible, primitive, period). The matrix $A$ (equivalently the graph $G_{A}$ ) is irreducible if for every pair $a, b$ there is $n \geq 1$ with $(A^{n})_{ab} > 0$ — the graph is strongly connected. It is primitive if there is a single $n$ with $A^{n} > 0$ entrywise. The period of an irreducible $A$ is $d (A) = g cd {n \geq 1 : (A^{n})_{aa} > 0}$ , the gcd of the lengths of closed walks; the value is independent of the vertex $a$ . An irreducible matrix is primitive iff $d (A) = 1$ (aperiodic). These are exactly the irreducibility/period notions of 37.05.02, now read off the support graph.

Definition (conjugacy and the conjugacy problem). Two subshifts $X, Y$ are topologically conjugate, written $X ≅ Y$ , if there is a shift-commuting homeomorphism $X \to Y$ ; by the Curtis-Hedlund-Lyndon theorem 38.02.01 this is an invertible sliding-block code. The conjugacy problem for SFTs asks for a decidable invariant complete for $≅$ .

Counterexamples to common slips

Irreducible is not the same as primitive. The matrix $A = (0110)$ is irreducible (its graph is the $2$ -cycle, strongly connected) but not primitive: $A^{n}$ is never strictly positive, because it alternates between $A$ and $I$ . Its period is $2$ . Primitivity demands aperiodicity on top of strong connectedness.
The transition matrix need not be symmetric, and direction matters. $A_{ab} = 1$ means $ab$ is allowed; this says nothing about $ba$ . The golden-mean matrix is symmetric by accident; a one-way rule like "allow $ab$ but forbid $ba$ " gives an asymmetric $A$ with a different support graph.
Conjugacy is finer than equal entropy. Two irreducible SFTs can have the same Perron eigenvalue (hence equal topological entropy) yet fail to be conjugate. Entropy is a conjugacy invariant, not a complete one; the complete invariant is strong shift equivalence (Master tier), and even the weaker shift equivalence does not suffice in general.
Higher-block presentations change the alphabet but not the system. Passing from $X_{A}$ to $X_{A}^{[N]}$ replaces letters by overlapping $N$ -blocks; the two are conjugate by construction. An " $N$ -step SFT" (forbidden words of length $\leq N$ ) is therefore a $1$ -step SFT in disguise, after recoding.

Key theorem with proof Intermediate+

Theorem (the topological Markov dictionary, periodic-point count, and zeta function). Let $A$ be a $0/1$ transition matrix with subshift $X_{A}$ and support graph $G_{A}$ .

(a) Recoding. Every SFT is topologically conjugate to a $1$ -step SFT, and every $1$ -step vertex SFT is conjugate to an edge shift; thus every SFT is conjugate to the edge shift of a finite graph.

(b) Dictionary. $A$ irreducible (i.e. $G_{A}$ strongly connected) iff $X_{A}$ is topologically transitive; $A$ primitive (strongly connected and aperiodic) iff $X_{A}$ is topologically mixing.

(c) Periodic points and zeta. The number of points of period $n$ is $# Fix (σ^{n}) = tr (A^{n})$ , and the Artin-Mazur zeta function is rational: $$ \zeta_\sigma(t) = \exp!\Big( \sum_{n \ge 1} \frac{#\mathrm{Fix}(\sigma^n)}{n}, t^n \Big) = \det(I - tA)^{-1}. $$

(See ^{[Lind-Marcus 1995 Ch. 2-4]}, ^{[Brin-Stuck 2002 §3.3-§3.5]}, ^{[Bowen-Lanford 1970]}.)

Proof. Part (a). If $X$ is an SFT with forbidden words of length $\leq N$ , its higher-block presentation $X^{[N - 1]}$ (with alphabet the allowed $(N - 1)$ -blocks) has forbidden words of length $2$ only: a pair of overlapping $(N - 1)$ -blocks is allowed iff their overlap is consistent and the combined $N$ -block is allowed. Thus $X^{[N - 1]}$ is a $1$ -step SFT conjugate to $X$ via the invertible higher-block code $β_{N - 1}$ . A $1$ -step vertex SFT $X_{A}$ becomes an edge shift by taking the graph $G$ whose vertices are the letters and drawing one edge $a \to b$ for each allowed pair: the map sending a vertex sequence to its sequence of traversed edges is a conjugacy onto the edge shift $X_{G}$ .

Part (b). Topological transitivity means a dense orbit, equivalently that for any two allowed blocks $u, v$ there is an allowed block $w$ with $u w v$ allowed. Given letters $a =$ last symbol of $u$ and $b =$ first symbol of $v$ , such a $w$ exists iff there is a walk $a \to \dots \to b$ in $G_{A}$ , i.e. iff $(A^{k})_{ab} > 0$ for some $k$ — exactly strong connectedness of $G_{A}$ , i.e. irreducibility of $A$ . Topological mixing means that for all $u, v$ there is $K$ with an allowed connecting block of every length $k \geq K$ ; the connecting blocks of length $k$ correspond to walks $a \to b$ of length $k$ , and walks of all large lengths exist between every ordered pair iff $A^{k} > 0$ for all large $k$ , i.e. iff $A$ is primitive. (For an irreducible $A$ with period $d > 1$ , walk lengths $a \to b$ are confined to a fixed residue class mod $d$ , so mixing fails; this is the cyclic structure of 37.05.02.)

Part (c). A point $x$ with $σ^{n} x = x$ is a bi-infinite sequence of period $n$ , determined by one period $x_{0} x_{1} \dots x_{n - 1}$ with $A_{x_{i} x_{i + 1}} = 1$ for all $i$ taken mod $n$ ; this is precisely a closed walk of length $n$ in $G_{A}$ . The number of closed walks of length $n$ based at vertex $a$ is $(A^{n})_{aa}$ , so the total is $\sum_{a} (A^{n})_{aa} = tr (A^{n})$ . For the zeta function, write the eigenvalues of $A$ as $λ_{1}, \dots, λ_{r}$ (with multiplicity), so $tr (A^{n}) = \sum_{i} λ_{i}^{n}$ . Then $$ \sum_{n \ge 1} \frac{\operatorname{tr}(A^n)}{n} t^n = \sum_i \sum_{n \ge 1} \frac{(\lambda_i t)^n}{n} = -\sum_i \log(1 - \lambda_i t) = -\log \prod_i (1 - \lambda_i t) = -\log\det(I - tA), $$ using $det (I - t A) = \prod_{i} (1 - λ_{i} t)$ . Exponentiating gives $ζ_{σ} (t) = det (I - t A)^{- 1}$ , a rational function. $□$

Bridge. This theorem builds toward the entire conjugacy theory of symbolic systems and appears again in every entropy and classification computation, because it reduces three apparently different questions — recoding, mixing, and counting — to linear algebra on one non-negative matrix. The foundational reason the same matrix answers all three is that an allowed sequence is a walk and a periodic point is a closed walk, so combinatorics on $G_{A}$ and spectral data of $A$ are two readings of one object; this is exactly the principle that makes the trace count loops and the determinant package them into a zeta function. The dictionary half is dual to the probabilistic dictionary of 37.05.02: irreducibility and period are graph properties shared by the $0/1$ matrix and the stochastic matrix on the same support, and the central insight is that topological transitivity here plays the role of irreducibility there while topological mixing plays the role of aperiodicity. Putting these together, the recoding statement promotes every finite-type system to an edge shift, so the conjugacy problem of the next unit becomes a problem about non-negative integer matrices up to a graph-rewriting equivalence — the bridge from forbidden words to matrices that the Master tier turns into strong shift equivalence.

Exercises Intermediate+

Exercise 5 (medium, short-answer).

Show that an SFT with forbidden words of length $\leq 3$ on alphabet $A$ is conjugate to a $1$ -step SFT, and identify the alphabet of the new presentation.

Hint

Recode using overlapping $2$ -blocks; a pair of $2$ -blocks is allowed exactly when they overlap consistently and the combined $3$ -block is allowed.

Answer

Use the higher-block code $β_{2}$ , whose new alphabet is the set $L_{2}$ of allowed $2$ -blocks $ab$ . A point $x$ maps to the sequence of overlapping pairs $(x_{n} x_{n + 1})_{n}$ . Two pairs $ab$ and $c d$ may sit adjacent in the image iff $b = c$ (consistent overlap) and the $3$ -block $ab d$ is allowed; this is a length- $2$ condition on the new alphabet, so the image is a $1$ -step SFT. The map $β_{2}$ is an invertible sliding-block code (its inverse reads off the first symbol of each pair), hence a conjugacy. The new alphabet is $L_{2} (X)$ , the allowed $2$ -blocks. Rubric: full credit for the overlap condition and naming $L_{2}$ as the new alphabet.

Exercise 6 (medium, short-answer).

Prove that for an irreducible matrix $A$ , the period $d (A) = g cd {n : (A^{n})_{aa} > 0}$ does not depend on the vertex $a$ .

Hint

For vertices $a, b$ , irreducibility gives walks $a \to b$ of length $p$ and $b \to a$ of length $q$ ; relate return times at $a$ and $b$ using $p + q$ .

Answer

Let $d_{a} = g cd {n : (A^{n})_{aa} > 0}$ and $d_{b}$ likewise. By irreducibility pick walks $a \to b$ of length $p$ and $b \to a$ of length $q$ ; then $p + q$ is a closed walk at $a$ , so $d_{a} ∣ (p + q)$ , and likewise $d_{b} ∣ (p + q)$ . For any closed walk at $b$ of length $m$ , the concatenation $a \to b \to (loop) \to a$ has length $p + m + q$ , a return time at $a$ , so $d_{a} ∣ (p + q + m)$ ; combined with $d_{a} ∣ (p + q)$ this gives $d_{a} ∣ m$ . Hence $d_{a}$ divides every return time at $b$ , so $d_{a} ∣ d_{b}$ . By symmetry $d_{b} ∣ d_{a}$ , so $d_{a} = d_{b}$ . Rubric: full credit for the $p + q$ bridging argument and the two-sided divisibility.

Exercise 7 (hard, short-answer).

Let $A = (1011)$ . Show that $X_{A}$ contains exactly two points and explain why this matrix, although it has a positive entry pattern that is "upper triangular", gives a reducible system.

Hint

Read off the allowed pairs from the $1$ -entries: $00, 01, 11$ allowed, $10$ forbidden. Which bi-infinite sequences survive?

Answer

Order the alphabet $0, 1$ . The $1$ -entries are $A_{00}, A_{01}, A_{11}$ , so the allowed pairs are $00, 01, 11$ and the only forbidden pair is $10$ : a $1$ may never be followed by a $0$ . A bi-infinite sequence avoiding $10$ can never go from $1$ back to $0$ , so once it shows a $1$ it is all $1$ s forward and, looking backward, it must be all $0$ s before any $1$ — but a bi-infinite sequence has no first symbol, so the only sequences with no $10$ are the constant $\overline{0}$ and the constant $\overline{1}$ (a sequence $\dots 0001111 \dots$ would contain the boundary pair $01$ , which is allowed, yet such a sequence is not shift-periodic and in fact the orbit closure forces the two fixed points; the only shift-invariant survivors with no $10$ anywhere and consistent at every index are the two constants). The graph has edges $0 \to 0$ , $0 \to 1$ , $1 \to 1$ but no $1 \to 0$ , so it is not strongly connected: there is no walk from $1$ back to $0$ . Hence $A$ is reducible despite every diagonal entry being positive; strong connectedness, not positivity of the diagonal, is what irreducibility demands. Rubric: full credit for identifying $\overline{0}, \overline{1}$ as the only points and for the no-return-walk reducibility argument.

Exercise 8 (hard, short-answer).

Two edge shifts have transition matrices $A = (1111)$ and $B = (2)$ (the $1 \times 1$ matrix). Show they are topologically conjugate, exhibiting the conjugacy, even though $A$ and $B$ are not similar matrices.

Hint

$A$ is the full $2$ -shift recoded: count edges. $B$ is the full shift on $2$ symbols. Build an invertible sliding-block code, or use the periodic-point counts $tr (A^{n}) = tr (B^{n})$ .

Answer

The matrix $A$ has all entries $1$ , so $X_{A}$ allows every pair on a $2$ -letter alphabet: it is the full $2$ -shift. The matrix $B = (2)$ is the edge shift of a single vertex with two loops, whose edge sequences are arbitrary sequences of two edge-labels: again the full $2$ -shift. Relabelling the two edges of $B$ as the two letters of $A$ is a $0$ -block (memoryless) sliding-block code, invertible, hence a conjugacy $X_{B} ≅ X_{A}$ . Consistency check by counting: $tr (A^{n}) = tr (1111)^{n} = tr (2^{n - 1} A) = 2^{n} = tr (B^{n})$ , matching all periodic-point counts. The matrices are not similar — they have different sizes — yet the edge shifts coincide, which is the first sign that conjugacy of edge shifts is governed by something coarser than matrix similarity: strong shift equivalence, with $A$ and $B$ elementarily equivalent via the rectangular pair $R = (11)$ , $S = (11)$ ( $A = R S$ , $B = S R$ ). Rubric: full credit for recognising both as the full $2$ -shift, the relabelling conjugacy, and the $R, S$ elementary equivalence.

Advanced results Master

Theorem (state splitting and the Decomposition Theorem; Williams). Every topological conjugacy between edge shifts is a composition of in-splittings, out-splittings, and their inverses (amalgamations). Two edge shifts $X_{A}, X_{B}$ are topologically conjugate iff the non-negative integer matrices $A$ and $B$ are strong shift equivalent: there are non-negative integer rectangular matrices $(R_{i}, S_{i})$ and a chain $A = A_{0}, A_{1}, \dots, A_{k} = B$ with $A_{i - 1} = R_{i} S_{i}$ , $A_{i} = S_{i} R_{i}$ (each step an elementary equivalence). (See ^{[Williams 1973]}, ^{[Lind-Marcus 1995 Ch. 7]}.)

Strong shift equivalence is the exact algebraic shadow of conjugacy. A single elementary equivalence $A = R S$ , $B = S R$ realises one round of state splitting: $R$ records how each state of $A$ splits into states of $B$ and $S$ records the reassembly, and $R S = A$ , $S R = B$ encode that the two graphs present the same bi-infinite walk set. The Decomposition Theorem says these elementary moves generate all of conjugacy, so the conjugacy problem for SFTs is the decidability problem for strong shift equivalence — a problem whose general decidability remained open for decades and whose subtlety is the reason the coarser shift equivalence ( $A^{ℓ} = R S$ , $B^{ℓ} = S R$ for some $ℓ$ , with $A R = R B$ , $S A = B S$ ) was introduced as a computable approximation. Kim and Roush showed shift equivalence is decidable; whether it equals strong shift equivalence (Williams' conjecture) is false in general, settled by Kim-Roush in the 1990s with reducible counterexamples.

Theorem (entropy, the Perron eigenvalue, and Lind's theorem). For an irreducible SFT with transition matrix $A$ , the topological entropy is $h (X_{A}) = lo g λ_{A}$ , where $λ_{A}$ is the Perron-Frobenius eigenvalue (spectral radius) of $A$ . A real number $λ \geq 1$ is the entropy-exponential $e^{h}$ of some irreducible SFT iff $λ$ is a Perron number (an algebraic integer strictly dominating its other conjugates in modulus). (Lind-Marcus 1995 ^{[Lind-Marcus 1995 Ch. 4]}.)

The entropy formula is Perron-Frobenius applied to the word-count growth $# L_{n} ≍ λ_{A}^{n}$ , and it shows entropy to be a conjugacy invariant taking values in ${lo g λ : λ Perron}$ . This is the topological counterpart of the Perron eigenvalue governing the convergence rate of the stochastic chain in 37.05.02: there the eigenvalue $1$ carries the stationary distribution and the spectral gap controls mixing, here the eigenvalue $λ_{A}$ carries the entropy and the rest of the spectrum carries the zeta-function poles. Lind's characterisation closes the realisation question — every Perron number, and no other, is an SFT growth rate — exhibiting the spectral radius as the bridge from combinatorial complexity to algebraic number theory.

Theorem (sofic shifts as factors of SFTs; the Krieger and Fischer covers). A subshift is sofic iff it is a sliding-block factor of an SFT, iff it is the set of label-sequences of a finite labelled graph, iff its language is regular. Every irreducible sofic shift has a unique minimal right-resolving presentation, the Fischer cover, and a canonical Krieger cover; sofic-but-not-SFT shifts exist, the even shift being canonical. (Lind-Marcus 1995 ^{[Lind-Marcus 1995 Ch. 3]}.)

Sofic shifts sit one level above finite type: an SFT records a language defined by finitely many forbidden factors, while a sofic shift records an arbitrary regular language, presented by a finite automaton whose underlying edge shift is an SFT and whose label map is the factor code. The Fischer cover is the minimal such automaton among irreducible right-resolving presentations, playing the role for sofic shifts that the transition matrix plays for SFTs, and it makes entropy and zeta-function computations for sofic shifts reduce to matrix computations on the cover. The even shift's failure to be finite type — no bounded memory can enforce a global parity constraint — is exactly the gap between regular languages and the bounded-factor languages of SFTs.

Synthesis. These results are one architecture seen at four resolutions, and putting these together the entire finite-type theory becomes linear algebra on non-negative integer matrices up to strong shift equivalence. The central insight is that an SFT is its transition matrix modulo state splitting: the Decomposition Theorem makes conjugacy a chain of elementary equivalences $A = R S \leftrightarrow S R = B$ , so the foundational reason entropy, periodic-point counts, and the zeta function are conjugacy invariants is that each is a strong-shift-equivalence invariant of the matrix — the trace data $tr (A^{n})$ , the determinant $det (I - t A)$ , and the spectral radius $λ_{A}$ all survive the move $R S \mapsto S R$ because $R S$ and $S R$ share their nonzero spectrum. This is exactly the principle that the periodic-point count is the matrix trace and the zeta function is its determinant package, now promoted to a classification statement. The dictionary half is dual to the probabilistic theory of 37.05.02: the $0/1$ matrix is the support shadow of the stochastic matrix, irreducibility and period are shared by both on the common support graph, and the Perron eigenvalue that controls mixing there controls entropy here — topological and measured Markov dynamics share one combinatorial skeleton. The bridge onward is that sofic shifts generalise SFTs to regular languages, embedding symbolic dynamics in automata theory, so the classification of finite-state symbolic systems is the classification of non-negative integer matrices up to strong shift equivalence, the central problem this unit hands to the conjugacy theory downstream.

Full proof set Master

Proposition 1 (periodic points are closed walks). For a $0/1$ transition matrix $A$ , $# Fix (σ^{n}) = tr (A^{n})$ .

Proof. A point $x \in X_{A}$ with $σ^{n} x = x$ satisfies $x_{k + n} = x_{k}$ for all $k$ , so it is the bi-infinite repetition of the word $x_{0} x_{1} \dots x_{n - 1}$ , subject to $A_{x_{i} x_{i + 1}} = 1$ for $i = 0, \dots, n - 1$ with $x_{n} := x_{0}$ . This is exactly a closed walk $x_{0} \to x_{1} \to \dots \to x_{n - 1} \to x_{0}$ of length $n$ in $G_{A}$ . The number of closed walks of length $n$ based at $a$ is $(A^{n})_{aa}$ — by the standard induction $(A^{n})_{ab} =$ number of length- $n$ walks $a \to b$ , since $(A^{n})_{ab} = \sum_{c} (A^{n - 1})_{a c} A_{c b}$ counts walks by their penultimate vertex. Summing the diagonal over base vertices gives $\sum_{a} (A^{n})_{aa} = tr (A^{n})$ . $□$

Proposition 2 (rationality of the zeta function). $ζ_{σ} (t) = det (I - t A)^{- 1}$ .

Proof. Let $λ_{1}, \dots, λ_{r}$ be the eigenvalues of $A$ with algebraic multiplicity, so $tr (A^{n}) = \sum_{i} λ_{i}^{n}$ (Newton; the trace of a power is the power sum of eigenvalues). Then for $∣ t ∣$ small, $$ \sum_{n \ge 1} \frac{\operatorname{tr}(A^n)}{n} t^n = \sum_i \sum_{n \ge 1} \frac{(\lambda_i t)^n}{n} = -\sum_i \log(1 - \lambda_i t). $$ Exponentiating, $ζ_{σ} (t) = \prod_{i} (1 - λ_{i} t)^{- 1} = det (I - t A)^{- 1}$ , since $det (I - t A) = \prod_{i} (1 - λ_{i} t)$ . The right side is rational in $t$ . $□$

Proposition 3 (irreducible $\Leftrightarrow$ transitive). $X_{A}$ is topologically transitive iff $A$ is irreducible.

Proof. Transitivity is equivalent to: for all allowed blocks $u, v$ there is a block $w$ with $u w v$ allowed (this builds a dense orbit by concatenating an enumeration of block pairs, and conversely a dense orbit realises every such junction). Writing $a$ for the last letter of $u$ and $b$ for the first of $v$ , the existence of $w$ is the existence of a walk $a \to b$ in $G_{A}$ , i.e. $(A^{k})_{ab} > 0$ for some $k \geq 1$ . Quantifying over all $a, b$ , this is strong connectedness of $G_{A}$ , which is irreducibility of $A$ . $□$

Proposition 4 (primitive $\Leftrightarrow$ mixing). $X_{A}$ is topologically mixing iff $A$ is primitive.

Proof. Mixing means: for all allowed $u, v$ there is $K$ such that for every $k \geq K$ a connecting block of length $k$ exists with $u (\cdot) v$ allowed and the gap equal to $k$ . With $a, b$ as before, connecting blocks of length $k$ correspond to walks $a \to b$ of length $k$ , counted by $(A^{k})_{ab}$ . Thus mixing says $(A^{k})_{ab} > 0$ for all $a, b$ and all large $k$ , i.e. $A^{k} > 0$ entrywise for all large $k$ . A non-negative matrix with $A^{k} > 0$ for some $k$ has $A^{m} > 0$ for all $m \geq k$ when it is irreducible with a self-loop somewhere; in general $A^{k} > 0$ for all large $k$ is precisely primitivity (irreducible and aperiodic, by Perron-Frobenius). Conversely a primitive matrix has $A^{k} > 0$ for all $k \geq$ some $k_{0}$ , giving mixing. $□$

Proposition 5 (higher-block conjugacy). The higher-block code $β_{N} : X_{A} \to X_{A}^{[N]}$ is a topological conjugacy, and $X_{A}^{[N]}$ is a $1$ -step SFT for $N$ at least the longest forbidden-word length minus one.

Proof. $β_{N}$ is a sliding-block code with window $[0, N - 1]$ and block map $Φ (x_{0} \dots x_{N - 1}) = x_{0} \dots x_{N - 1} \in L_{N}$ , hence continuous and shift-commuting 38.02.01. Its inverse is the $0$ -block code reading the first symbol of each $N$ -block, $ψ (y)_{n} = (y_{n})_{0}$ , also a sliding-block code; $ψ \circ β_{N} = id$ and $β_{N} \circ ψ = id$ on the image, so $β_{N}$ is an invertible sliding-block code, a conjugacy onto $X_{A}^{[N]}$ . In the image alphabet $L_{N}$ , two consecutive symbols $y_{n} = u$ , $y_{n + 1} = u^{'}$ are compatible iff $u, u^{'}$ overlap in their length- $(N - 1)$ inner block and the merged $(N + 1)$ -block is allowed; this is a length- $2$ constraint, so the image is $1$ -step. For $N$ one less than the longest forbidden word, every forbidden constraint becomes a length- $2$ constraint on $L_{N}$ , so $X_{A}^{[N]}$ is a $1$ -step SFT. $□$

Proposition 6 (elementary equivalence preserves the nonzero spectrum, hence entropy and zeta). If $A = R S$ and $B = S R$ with $R, S$ non-negative integer matrices, then $A$ and $B$ have the same nonzero eigenvalues with multiplicity; consequently $tr (A^{n}) = tr (B^{n})$ for all $n \geq 1$ , $λ_{A} = λ_{B}$ , and $ζ_{σ_{A}} = ζ_{σ_{B}}$ up to the factor $det (I - t A) / det (I - tB) =$ a power of $(1 - t)^{\pm 0}$ accounting for zero eigenvalues.

Proof. For any (possibly rectangular) $R, S$ with $R S, S R$ defined, $R S$ and $S R$ have equal nonzero eigenvalues with multiplicity: if $R S v = λ v$ with $λ \neq = 0$ , then $S v \neq = 0$ and $S R (S v) = S (R S) v = λ (S v)$ , so $S v$ is a $λ$ -eigenvector of $S R$ ; the map $v \mapsto S v$ is injective on the $λ$ -eigenspace for $λ \neq = 0$ (as $R S v = λ v \neq = 0$ forces $S v \neq = 0$ ), and symmetrically, giving equal multiplicities. Hence the power sums $tr ((R S)^{n}) = \sum_{λ \neq = 0} λ^{n} = tr ((S R)^{n})$ agree for $n \geq 1$ , the spectral radii agree ( $λ_{A} = λ_{B}$ ), and $det (I - tR S)$ and $det (I - tS R)$ differ only by the unit factor $(1 - 0 \cdot t)^{d i m A - d i m B}$ from the differing counts of zero eigenvalues, which is $1$ . Therefore strong shift equivalence — a chain of such elementary moves — preserves entropy and the zeta function, confirming they are conjugacy invariants. $□$

Connections Master

Shift spaces and subshifts 38.02.01. This unit specialises the general theory of that prerequisite to the finite-type case: the forbidden-word characterisation and the Curtis-Hedlund-Lyndon theorem proved there are the tools that turn an SFT into an edge shift and a conjugacy into an invertible sliding-block code, and the golden-mean and even shifts introduced there are the running examples whose transition matrix, entropy, and sofic-vs-SFT status are computed here. The upstream unit owns the definition of subshift and code; this unit owns the matrix theory and the conjugacy classification.
Class structure, irreducibility, and periodicity of Markov chains 37.05.02. The $0/1$ transition matrix here is the topological shadow of the stochastic transition matrix there: communication classes, irreducibility, and the gcd-of-cycle-lengths period transfer verbatim from the stochastic matrix to its support graph, with topological transitivity replacing irreducibility and topological mixing replacing aperiodicity. Where the probabilistic theory weights walks by probability and extracts a stationary distribution from the Perron eigenvalue $1$ , the symbolic theory counts walks and extracts entropy from the Perron eigenvalue $λ_{A}$ ; both read off the same directed graph, and this unit's hooks_out records the link.
Dynamical systems, orbits, and limit sets 38.01.01. The chaotic systems catalogued abstractly there — the doubling map, the Smale horseshoe, the hyperbolic toral automorphism — are each conjugate, via a Markov partition, to a subshift of finite type studied here, so the transition matrix of the present unit is the concrete combinatorial model of the recurrence, topological transitivity, and mixing defined there. The periodic-point count $tr (A^{n})$ computes the periodic orbits of those smooth systems through their symbolic codings.

Historical & philosophical context Master

Subshifts of finite type appear implicitly in the symbolic codings of Hadamard (1898) and of Morse and Hedlund (1938), but their systematic theory as topological Markov chains was developed in the 1960s and 1970s alongside the smooth-ergodic-theory program of Anosov, Sinai, and Bowen, who used Markov partitions to code Axiom A diffeomorphisms by SFTs. The rationality of the Artin-Mazur zeta function $ζ_{σ} (t) = det (I - t A)^{- 1}$ for a subshift of finite type was established by Rufus Bowen and Oscar Lanford in their 1970 note Zeta functions of restrictions of the shift transformation (Proc. Symp. Pure Math. 14) ^{[Bowen-Lanford 1970]}, adapting the Artin-Mazur definition of a dynamical zeta function to the symbolic setting.

The conjugacy problem for SFTs was reframed as an algebraic problem by Robert Williams in his 1973 paper Classification of subshifts of finite type (Annals of Mathematics 98) ^{[Williams 1973]}, which introduced strong shift equivalence and shift equivalence of non-negative integer matrices and proved the Decomposition Theorem that every conjugacy of edge shifts factors through state splittings. Williams conjectured that shift equivalence and strong shift equivalence coincide; the question stood for two decades until Ki Hang Kim and Fred Roush constructed reducible counterexamples in the early 1990s, with the irreducible case resolved later, leaving the general decidability of strong shift equivalence — and hence of SFT conjugacy — among the central open problems of the field. The textbook synthesis is Douglas Lind and Brian Marcus' 1995 An Introduction to Symbolic Dynamics and Coding (Cambridge) ^{[Lind-Marcus 1995]}, which organises the subject around edge shifts, the transition matrix, entropy and the Perron number characterisation due to Lind, sofic shifts, and the Williams classification.

Bibliography Master

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

@book{BrinStuck2002sft,
  author    = {Brin, Michael and Stuck, Garrett},
  title     = {Introduction to Dynamical Systems},
  publisher = {Cambridge University Press},
  year      = {2002}
}

@article{Williams1973,
  author  = {Williams, Robert F.},
  title   = {Classification of subshifts of finite type},
  journal = {Annals of Mathematics},
  volume  = {98},
  year    = {1973},
  pages   = {120--153}
}

@incollection{BowenLanford1970,
  author    = {Bowen, Rufus and Lanford, Oscar E.},
  title     = {Zeta functions of restrictions of the shift transformation},
  booktitle = {Global Analysis (Proc. Sympos. Pure Math., Vol. XIV)},
  publisher = {American Mathematical Society},
  year      = {1970},
  pages     = {43--49}
}

@book{Kitchens1998sft,
  author    = {Kitchens, Bruce P.},
  title     = {Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts},
  publisher = {Springer-Verlag},
  series    = {Universitext},
  year      = {1998}
}

@article{KimRoush1999,
  author  = {Kim, Ki Hang and Roush, Fred W.},
  title   = {The Williams conjecture is false for irreducible subshifts},
  journal = {Annals of Mathematics},
  volume  = {149},
  year    = {1999},
  pages   = {545--558}
}

Prerequisites

38.02.01

Tier anchors

beginner: Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 2 (graphs, edge shifts, the golden-mean picture) and §6.1 (state splitting drawn on small graphs); 3Blue1Brown *Chaos* visual essays for the walk-on-a-graph intuition behind allowed sequences
intermediate: Brin-Stuck 2002 *Introduction to Dynamical Systems* (Cambridge University Press) Ch. 3 §3.3-§3.5 (topological Markov chains, transition matrices, irreducibility and mixing, counting periodic points and the zeta function); Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge) Ch. 2-4 and §2.3 (higher-block presentations)
master: Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 2-7 (edge shifts, the conjugacy problem, state splitting, strong shift equivalence, the Decomposition and Classification theorems, sofic shifts); Kitchens 1998 *Symbolic Dynamics* (Springer Universitext) Ch. 2; Williams 1973 *Classification of subshifts of finite type* (Annals of Mathematics 98) — the origin of strong shift equivalence; Bowen-Lanford 1970 *Zeta functions of restrictions of the shift transformation* (Proc. Symp. Pure Math. 14) — the rationality of the SFT zeta function

References

Lind, Marcus 1995 — An Introduction to Symbolic Dynamics and Coding · Ch. 2 (graphs, edge shifts, transition matrices), Ch. 3 (sofic shifts), Ch. 4 (entropy and the Perron eigenvalue), Ch. 6-7 (state splitting, strong shift equivalence, the conjugacy theory); Cambridge University Press 1995
Brin, Stuck 2002 — Introduction to Dynamical Systems · Ch. 3 §3.3-§3.5 (topological Markov chains, the transition matrix, irreducibility, topological transitivity and mixing, #Fix(σ^n)=tr A^n, the zeta function); Cambridge University Press 2002
Williams 1973 — Classification of subshifts of finite type · Annals of Mathematics 98 (1973) 120-153; correction ibid. 99 (1974) 380-381; introduces elementary and strong shift equivalence of non-negative integer matrices and proves conjugacy of edge shifts equals strong shift equivalence of their matrices
Bowen, Lanford 1970 — Zeta functions of restrictions of the shift transformation · Proceedings of Symposia in Pure Mathematics 14 (1970) 43-49; the rationality ζ_σ(t) = det(I - tA)^{-1} of the Artin-Mazur zeta function of a subshift of finite type
Kitchens 1998 — Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts · Springer Universitext 1998, Ch. 2 (subshifts of finite type, transition matrices, the spectral theory of non-negative matrices, periodic-point counts)

Estimated time

beginner: 18m
intermediate: 48m
master: 86m