POSITIVE K-THEORY AND SYMBOLIC DYNAMICS

MIKE BOYLE

Abstract. This article is an exposition of the positive K-theory approach to classification problems in symbolic dynamics.

Contents

1. Introduction 2 2. Subshift definitions 2 3. Presentations of SFTs 3 3.1. Vertex Shifts and 0-1 matrices 3 3.2. Edge Shifts and ℤ_{+} matrices 3 3.3. Edges shifts and polynomial matrices 4 3.4. Path shifts 4 4. Elementary isomorphisms and path shifts 5 4.1. Elementary isomorphism 5 4.2. NZC and A^{♯} 5 4.3. Path shifts 6 5. Strong shift equivalence theory 7 5.1. Definition 7 5.2. Shifts of finite type 7 5.3. Cocycles 8 5.4. Markov chains 9 5.5. Other classifications with SSE 9 5.6. Wagoner’s SSE theory 9 6. Algebraic invariants of strong shift equivalence 10 6.1. SSE over a ring as a stabilized similarity 10 6.2. Periodic points and det(·) 10 6.3. Flow equivalence 10 6.4. Shift equivalence 11 7. Positive K-theory 11 7.1. Definitions 11 7.2. From SSE to positive K theory 12 7.3. Algebraic invariants from I − A 12 7.4. Using K_{2} 13 8. Flow equivalence 13 9. Good finitary isomorphism for Markov chains 14 References 16

Date: June 22, 2001.

2000 Mathematics Subject Classification. 37B10.

1. Introduction

The ideas around shift equivalence and strong shift equivalence provide fundamental tools for the study not only of shifts of finite type but also of various other symbolic dynamical systems. Recently there has emerged another such general framework, dubbed “positive K-theory” by Wagoner. This paper is an exposition of the positive K-theory approach to classification problems in symbolic dynamics, which has its successes and appeal, but which is also still a work in progress. The organization of the paper should be apparent from the table of contents.

I thank Jack Wagoner for very helpful feedback on this article (not to mention his essential role in creating the theory), and I thank Bill Parry for the material on strong shift equivalence of cocycles in Section 5.3.

2. Subshift definitions

For completeness we recall some elementary background definitions for subshifts. A reader familiar with these can skip this section.

The system which is the full shift on n symbols (also called the n-shift) is defined as follows. We give a finite set of n elements — say, {0, 1, ..., n − 1} — the discrete topology. (This finite set is often called the alphabet.) We let X be the product of countably many copies of this set, with the copies indexed by ℤ. We think of an element x of X as a doubly infinite sequence

x = ...x_{−1}x_{0}x_{1}...

where each x_{i} is one of the n elements. X is given the product topology and thus becomes a compact metrizable space. A metric compatible with the topology is given by defining, when x is not equal to y,

dist(x, y) = 2^{−k}, where k = min{|i| : x_{i} ≠ y_{i}}.

That is, two sequences are close if they agree in a large stretch of coordinates around the zero coordinate.

A finite sequence of elements of the alphabet is called a word. If W is a word of length j − i + 1, then the set of sequences x such that x_{i}...x_{j} = W is called a cylinder set. The cylinder sets are closed and open, and they give a basis for the product topology on X. Thus X is zero dimensional.

There is a natural shift map homeomorphism S sending X into X, defined by shifting the index set by one: (Sx)_{i} = x_{i+1}. The full shift on n symbols is the system (X, S).

A subshift is a subsystem of some full shift (X, T) on n symbols. This means that it is a homeomorphism obtained by restriction of T to some compact subset Y invariant under the shift and its inverse. The complement of Y is open and is thus a union of cylinder sets. Because Y is shift invariant, it follows that there is a (countable) list of words such that Y is precisely the set of all sequences y such that for every word W on the list, for every i ≤ j, W is not equal to y_{i}...y_{j}. That is, Y is the subset of all sequences which avoid the forbidden words.

A subshift is a shift of finite type (SFT) if there exists a finite alphabet and a positive integer N such that there is a list of words of length N on this alphabet such that a doubly infinite sequence x is in the subshift if and only if for every i ∈ ℤ the word x_{i} ⋯ x_{i+N−1} is on the list.

An SFT is also called a topological Markov shift, or topological Markov chain. This terminology is appropriate because an SFT can be viewed as the topological support of a finite-state stochastic Markov process, and also as the topological analogue of such a process [Pa1]. For more on SFTs and their uses, see [DGS, Ki, LM] and their references.

3. Presentations of SFTs

3.1. Vertex Shifts and 0-1 matrices. We now define vertex shifts, which are examples of shifts of finite type. Notation: throughout these notes, “graph” means “directed graph”.

For some n, let A be an n×n zero-one matrix. Regard A as the adjacency matrix of a graph with n vertices; the vertices index the rows and the columns, and A(i, j) is the number of edges from vertex i to vertex j. Let Y be the space of doubly infinite sequences y such that for every k in Z, A(y_{k}, y_{k+1}) = 1. We think of Y as the space of doubly infinite walks through the graph, where the walks/itineraries are presented by recording the vertices traversed. The restriction of the shift to Y is a shift of finite type: a sufficient list of forbidden words is the set of words ij such that there is no arc from i to j. It is not difficult to check that every shift of finite type is isomorphic (topologically conjugate) to a vertex shift.

3.2. Edge Shifts and ℤ_{+} matrices. Again let A be an adjacency matrix for a directed graph, but now allow multiple edges: so, the entries of A are nonnegative integers. Let the set of edges be the alphabet. Let Σ_{A} be the set of sequences y such that for all k, the terminal vertex of y_{k} is the initial vertex of y_{k+1}. Again, we can think of Σ_{A} as the space of doubly infinite walks through the graph, now presented by the edges traversed. The shift map restricted to Σ_{A} is an edge shift and it is a shift of finite type: a sufficient list of forbidden words is the set of edge pairs ij which do not satisfy the head-to-tail rule.

In the sequel, unless otherwise indicated an SFT defined by a nonnegative integral matrix A is intended to be the edge shift defined by A. We denote this SFT by σ_{A}. Any SFT is isomorphic to an edge shift, because the two-block presentation of a vertex shift is an edge shift.

The edge shift presentation is very useful. One reason is conciseness: an edge shift presented by a small matrix with large entries is presented as a vertex shift by a large matrix with a block pattern of zeros and ones which is awkward (e.g. [AW]).

Another reason is functoriality. Working only with zero-one matrices rules out some useful matrix operations (such as taking powers) and interpretations. For one of these, first a little preparation.

If S is a subshift, then we let S^{n} denote the homeomorphism obtained by iterating S n times. The homeomorphism S^{n} is isomorphic to a subshift S^{[n]} whose alphabet is the set of S-words of length n. An isomorphism from S^{n} to S^{[n]} is given by the map f which sends a point x to the point y such that for all k in ℤ,

y_{k} = [x_{kn}...x_{(k+1)n−1}].

Claim. Suppose an edge shift S is defined by a matrix A. Then the subshift S^{[n]}, after a renaming of symbols, is the edge shift defined by A^{n}.

Proof. Let G be the graph with adjacency matrix A and let G^{[n]} be the graph with adjacency matrix A^{n}. Let these graphs have the same vertex set, so that A(i, j) is the number of edges from i to j in G and A^{n}(i, j) is the number of edges from i to j in G^{[n]}.

An element [e_{1}e_{2} … e_{n}] in the alphabet of S^{n} is a path in G of n edges from some vertex i to some vertex j. The number of such paths from i to j is A^{n}(i, j). So there is a bijection from the alphabet of S^{[n]} to the alphabet of σ_{A^{n}} (i.e., the edge set of G^{[n]}) which respects initial and terminal vertex. This renaming of symbols defines a one-block isomorphism from S^{[n]} to σ_{A^{n}}.

3.3. Edges shifts and polynomial matrices. The presentation of an SFT as a vertex shift allows one to extract algebraic invariants from a defining zero-one matrix. Defining edge shifts with nonnegative integral matrices, one makes a significant advance in conciseness and functoriality of presentation.

There is another advance in conciseness and functoriality gained by presenting SFT’s with polynomial matrices with entries in ℤ_{+}. Here is an example illustrating the general situation. Let B be the polynomial matrix

B = ( \begin{matrix}2t & t^{3} + t \\ 3t^{2} & 0 \end{matrix} ) .

To this (2 × 2) matrix, we associate a graph G with two distinguished vertices, say 1 and 2. A term t^{k} in B corresponds to a path of length k in G. From the term 2t, G acquires two edges from 1 to 1. From the term t^{3}, G acquires a path of three edges from 1 to 2. On this path are two new, intermediate vertices which have no further adjoining edges. Similarly G acquires an edge from 1 to 2 and three paths of length two from 2 to 1. In addition to the two distinguished vertices, for each term t^{k}, the graph G gains k − 1 vertices. In this example, altogether the graph has 7 vertices.

We will let B^{♯} denote the adjacency matrix of a graph G derived by this procedure from a polynomial matrix B over tℤ_{+}[t].

Clearly we can describe some very complicated graphs with polynomial matrices of small size. Just as ℤ_{+} matrices allow much more concise presentations than 0−1 matrices, so also do polynomial matrices allow much more concise presentations than ℤ_{+} matrices. For example, if C is a nonnegative integral matrix, then there is a 2 × 2 polynomial matrix A such that the spectral radius of A^{♯} equals the spectral radius of C [Pe]; moreover, if the matrix C is primitive, then the matrix A^{♯} can be chosen primitive [BL]. (So, 2 × 2 polynomial matrices are rich enough to present mixing SFTs of all possible entropies.) The matrix A can be chosen 1 × 1 if and only if the spectral radius of C (which is an algebraic integer) has no conjugates over ℚ which are positive real numbers [Ha]. For more on polynomial matrices and their history, see [B1].

The polynomial matrices also allow one to introduce analytic methods in the construction of matrices A over ℤ_{+} with prescribed properties, such as the nonzero spectrum of A^{♯}. This was the setting in which Kim, Ormes and Roush characterized the nonzero spectra of nonnegative matrices with integer entries [KOR].

3.4. Path shifts. The path shifts are a class of model SFTs better suited to the polynomial matrix presentation than edge shifts. They are developed in the next section.

4. Elementary isomorphisms and path shifts

4.1. Elementary isomorphism. To an n × n matrix A over tℤ_{+}[t] we have associated a directed graph G with adjacency matrix A^{♯} and a set V′ (a rome) of n primary vertices in the graph. Let a route be a finite path of edges e_{1} … e_{k} in the graph which hits the rome V′ exactly twice, at the initial vertex of e_{1} and the terminal vertex of e_{k}. Because V′ is a rome, any point x in the sequence space Σ_{A} can be written as a concatenation of routes.

By a basic elementary matrix we will mean a matrix E which is equal to the identity matrix except in at most one entry, say E(i, j), which must be an offdiagonal entry. Suppose A and B are n × n matrices over tℤ_{+}[t], E is basic elementary with E(i, j) = t^{k}, and E(I − A) = (I − B). Then B is obtained by applying the following operations to A: subtract t^{k} from A(i, j), and add t^{k}(row j of A) to row i of A. (It follows that if A(i, j) = ∑ n_{r}t^{r}, then n_{k} > 0.)

For an example, set i, j, k = 1, 2, 3 and

A = (\begin{matrix}t & t^{2} + t^{3} \\ t^{4} & t^{5} \end{matrix}) , B = (\begin{matrix}t + t^{7} & t^{2} + t^{8} \\ t^{4} & t^{5} \end{matrix})

and then we have

E(I − A) = (\begin{matrix}1 & t^{3} \\ 0 & 1 \end{matrix}) (\begin{matrix}1 − t & −t^{2} − t^{3} \\ −t^{4} & 1 − t^{5} \end{matrix}) = (\begin{matrix}1 − t − t^{7} & −t^{2} − t^{8} \\ −t^{4} & 1 − t^{5} \end{matrix}) = (I − B) .

Now choose a route r′ of length k from i to j in G_{A}. Define a set R′ of paths in G_{A} as follows:

R′ = (R_{A} \ {r′}) ∪ {r′r: r ∈ R_{A} and r′r is a path in G_{A}} .

Every point in Σ_{A} has a unique decomposition as a concatenation of paths in R′. Also, clearly there is a bijection β: R′ → R_{B} which respects length, initial vertex and terminal vertex. (Often the choice of β is unique.) The chosen bijection induces a toplogical conjugacy σ_{A} → σ_{B}. We likewise construct a family of conjugacies induced by right multiplications (I − A)E = (I − B), in this case setting R′ = (R_{A} \ {r′}) ∪ {r′r}.

4.2. NZC and A^{♯}. The construction of the last subsection, due to Kim, Roush and Wagoner, gives an important method for constructing conjugacies of SFTs [KRW1, KRW2, KRW3] and leads to a new framework for classification problems in symbolic dynamics, in which topological conjugacies are given by compositions of elementary conjugacies [BW]. For this framework, first, we regard our polynomial matrices A as ℕ × ℕ matrices, by embedding the finite matrix as the upper left corner of an otherwise zero matrix. Similarly, we use ℕ × ℕ elementary matrices E (which agree with the infinite identity matrix except perhaps for one offdiagonal entry). This is not enough, because there are matrices which define conjugate SFTs and which cannot be related by moves with the elementary matrices over tℤ_{+}[t]

described so far. For an example, consider the matrices A = (2t) and B = (\begin{matrix}t & t \\ t & t \end{matrix}).

To arrange that all topological conjugacies arise as compositions of conjugacies arising from elementary matrix multiplications, it suffices to slightly enlarge the class of presenting polynomial matrices, to the class of matrices A = A(t) over ℤ_{+}[t] which satisfy the no-zero-length-cycles condition NZC: the matrix A(0) over ℤ_{+} defined by setting t equal to 0 satisfies tr(A^{n}) = 0 for all positive integers n. For example, below C and D satisfy the NZC condition and F does not:

C = (\begin{matrix}t^{3} & 4 + t^{5} \\ t & 0 \end{matrix})  D = (\begin{matrix}t^{3} + 4t & t^{5} \\ t & 0 \end{matrix})  F = (\begin{matrix}t^{3} & 4 + t \\ 1 & 0 \end{matrix}) .

To a matrix A over ℤ_{+}[t] satisfying NZC we will associate a matrix A^{♯} over ℤ_{+}. To begin the construction of A^{♯}, let B = A(0) − I; so, the nonzero entries of B are the nonzero offdiagonal entries of A. Say i(0)i(1) … i(k) is a B-path if B_{i(0)i(1)}B_{i(1)i(2)} ⋯ B_{i(k−1)i(k)} ≠ 0. Set M_{ij} = ∑ B_{i(0)i(1)}B_{i(1)i(2)} ⋯ B_{i(k−1)i(k)}, where the sum is over all B-paths such that

• i = i(0) and j = i(k),

• column i of A has an entry of positive degree, and

• row j of A has an entry of positive degree. (The empty sum is zero.) Then define a matrix A′′ by setting

A′′_{i,j} = A_{ij} − B_{ij} + ∑_{k} M_{ij}(A_{jk} − B_{jk}) .

Now A′′ is a matrix over tℤ_{+}[t]. The basic idea is that biinfinite A-paths can be factored uniquely as concatenations of A-paths which are positive length A-routes preceded by some (possibly empty) concatenation of zero-length A-routes; and there is a bijection (respecting length, initial vertex and terminal vertex) from these Apaths to the routes of A′′. We define A^{♯} to be (A′′)^{♯} (the ^{♯} construction was defined earlier for matrices over tℤ_{+}[t]). For example, in the previously displayed example we have C^{♯} = D^{♯}.

We will associate to A the topological conjugacy class of the edge SFT defined by A^{♯}. However, to associate definite elementary conjugacies of the corresponding edge SFTs to equations like E(I − A) = (I − B) for NZC matrices A and B, we would have to work through a somewhat complicated and unnatural analysis of cases. So, we will instead associate to an NZC matrix A a path SFT P_{A} on which our elementary conjugacies will be induced in an obvious and natural way. Roughly, a point in P_{A} will correspond to a concatenation of routes as before, but with some routes (corresponding to degree zero terms) traversed in “zero time”. In this setting, an equation E(I − A) = (I − B) or (I − A)E = (I − B) will induce a topological conjugacy P_{A} → P_{B} just as in the previous description, by a bijection R′_{A} → R_{B}. The price for this simplicity is that we must write down some technical definitions to make the intuition precise. We do this next.

4.3. Path shifts. Let A be an ℕ × ℕ matrix over ℤ_{+}[t] which satisfies NZC and has only finitely many nonzero entries. For each nonzero entry A_{ij}, write A_{ij} = t^{ℓ(1)} +⋯+t^{ℓ(n)}, where n = A_{ij}(1). Let R_{ij} = {(i, j, k, ℓ): 1 ≤ k ≤ n, ℓ = ℓ(k)}. We think of (i, j, k, ℓ) as representing a route r from i to j, with length (time-to-traverse) equal to ℓ. Let R = ∪_{ij}R_{ij} and define an alphabet A = {(i, j, k, ℓ, t): (i, j, k, ℓ) ∈ R, t ∈ ℤ} and an associated bisequence space

Σ = { … s_{−1}s_{0}s_{1} ⋯ ∈ A^{ℤ}: ∀n, if s_{n} = (i, j, k, ℓ, t) and s_{n+1} = (i′, j′, k′, ℓ′, t′),
then j = i′ and t′ = t + ℓ} .

Informally, we think of an element of Σ as representing an infinite itinerary through a graph whose edges are routes. A symbol (i, j, k, ℓ, t) indicates that at time t, the traveller is at vertex i and is about to travel along route (i, j, k, ℓ) to vertex j.

Finally, we say two elements s, s′ of Σ are equivalent (s ∼ s′) if there exists M in ℤ such that s_{n+M} = s′_{n} for all n. We give A the discrete topology, A^{ℤ} the product topology, Σ the relative topology and Σ/∼ the quotient topology. Let L be the maximum length of a route in R. Then the restriction of h to the compact set of bisequences s for which s_{0} = (i, j, k, ℓ, t) with 0 ≤ t ≤ L is still surjective, so Σ/∼ is compact. The shift action on Σ/∼ is induced by replacing each symbol s_{n} = (i, j, k, ℓ, t) with (i, j, k, ℓ, t − 1). The path shift P_{A} is Σ/∼ with this shift action.

To check that P_{A} as a topological dynamical system is SFT, we define a topological conjugacy to the edge SFT defined from A^{♯}. Let W be the set of words w with the following properties: w = s_{1} ⋯ s_{r} for some s in Σ such that s_{0} has positive length (i.e. s_{0} = (i_{0}, j_{0}, k_{0}, ℓ_{0}, t_{0}) with ℓ_{0} > 0), s_{r} has positive length, and s_{i} has zero length if 0 < i < r. Let \overline{W} be the set of words obtained from W by dropping the time coordinate (applying symbolwise the map (i, j, k, ℓ, t) ↦ (i, j, k, ℓ)). Because A satisfies the NZC condition, the set \overline{W} is finite. The alphabet of the target subshift will be \overline{W} and an additional symbol zero. The map h: s ↦ \overline{s} from Σ is defined as follows: if s_{n+1} … s_{n+r} ∈ W and s_{n+r} = (i, j, k, ℓ, t), then \overline{s}[t, t + ℓ] is the symbol \overline{W} followed by ℓ − 1 zeros. The map h defines a continuous map from Σ onto its image \overline{Σ}; and \overline{Σ} with the shift map is topologically conjugate to the edge SFT associated to A^{♯}. The map Σ → Σ/∼ is open, so h induces a continuous map \overline{h}: Σ/∼ → \overline{Σ}. A continuous bijective map from a compact space to a compact Hausdorff space is a homeomorphism. Finally, the shift action on \overline{Σ} is intertwined with a shift action on Σ/∼.

The path space presentation is the topological space P_{A} together with its shift action. Now equations E(I −A) = (I −B) and (I −A)E = (I −B) (with A, B NZC matrices over ℤ_{+}[t] and E basic elementary as before with E(i, j) = t^{k}) induce elementary topological conjugacies P_{A} → P_{B} by the correspondence of routes already described in the previous subsection. More generally, we allow that nonzero entry E(i, j) to be any element of ℤ_{+}[t]: we can still make the natural correspondence of routes (which amounts to the correspondence one would obtain by composing the conjugacies induced by matrices E_{s} such that E_{s}(i, j) = t^{k(s)} and ∑_{s} E_{s}(i, j) = E(i, j)).

It is proved in [BW] that every conjugacy of path SFTs is a composition of such elementary conjugacies.

5. Strong shift equivalence theory

5.1. Definition. Let S be a semiring with additive and multiplicative identities 0 and 1. An elementary strong shift equivalence over S from A to B is a triple (A, (U, V), B) such that A, U, V, B are finite matrices over S satisfying A = UV and B = V U. (The matrices A and B must be square but may have different size.) A strong shift equivlance over S is a concatenation of elementary strong shift equivalences. We use sse to abbreviate strong shift equivalence or strong shift equivalent. Two matrices are sse over S if there exists a concatenation of elementary sse’s over S between them.

5.2. Shifts of finite type. Strong shift equivalence was introduced by Williams [Wi] who proved the central result that A and B are sse over ℤ_{+} if and only if they define topologically conjugate (edge) SFTs. In fact, one can associate a definite topological conjugacy to an elementary strong shift equivalence, and show that any topological conjugacy of edge SFTs is a composition of conjugacies induced by elementary strong shift equivalences [Wi, W2].

5.3. Cocycles. Let G be a group, which for simplicity we will assume is abelian. Let ℤG be its integral group ring, with positive set ℤ_{+}G. An element of ℤG is a formal sum ∑_{g} n_{g}[g] with the g in G and the n_{g} in ℤ and all but finitely many n_{g} zero. Addition is given by ∑_{g} n_{g}[g]+∑_{g} m_{g}[g] = ∑_{g}(n_{g}+m_{g})[g] and multiplication is given by ∑_{g} n_{g}[g] ∑_{h} n_{h}[h] = ∑_{(g,h)}(n_{g}n_{h})[g + h] where g + h is computed in G. ℤ_{+}G is the set of elements ∑_{g} n_{g}[g] with each n_{g} ≥ 0.

Suppose A is a matrix with entries in ℤ_{+}G. Replacing an entry ∑_{g} n_{g}[g] with ∑ n_{g} produces a nonnegative integral matrix, which in this section we will denote A(0), and its associated edge SFT σ_{A(0)}, which we will also denote by σ_{A}. We view an entry n_{g}[g] as defining a labeling of edges by elements of G and then defining the locally constant function f_{A} from the SFT into G which sends a point x to the label of the edge which is its zero coordinate symbol x_{0}.

The function f_{A} can be used to define a skew product system. This is the map σ_{A} ⋉f on Σ_{A} ×G defined by the rule (x, g) ↦ (σ_{A}x, g +f_{A}(x)). Two skew products σ_{A} ⋉f and σ_{B} ⋉g are called isomorphic if there is a topological conjugacy σ_{A} ⋉f → σ_{B} ⋉ g of the form (x, g) ↦ (φ(x), g + r(x)). (In other words, the topological conjugacy commutes with the action of G given by g: (x, h) ↦ (x, h + g).)

We say two locally constant functions f, f′ from an SFT σ_{A} into G are cohomologous if there is a locally constant function h into G such that f = f′ + h − h ∘ σ_{A}. We write f ∼ f′ if f and f′ are cohomologous. In the case that the SFT σ_{A} is irreducible, the cohomology class of the locally constant function f is determined by the map on finite σ_{A}-orbits O defined by

O ↦ ∑_{x∈O} f(x).

Proposition [Pa2] The following are equivalent for matrices A, B over ℤ_{+}G and their associated skew product systems σ_{A} ⋉ f_{A}, σ_{B} ⋉ f_{B}.

• A and B are sse over ℤ_{+}G.

• There is a topological conjugacy φ: σ_{A} → σ_{B} such that f_{A} ∼ f_{B} ∘ φ.

• The skew product systems σ_{A} ⋉ f_{A} and σ_{B} ⋉ f_{B} are isomorphic. □ We won’t prove the proposition here, but the proof is a natural outgrowth of the

ℤ_{+} sse theory developed by Williams, Parry and others. In particular, there are related proofs in Appendix 2 of [BHa], which considers strong shift equivalence for “labeled” SFTs.

The classification of the skew products σ_{A} ⋉ f with a fixed base SFT σ_{A} is a difficult and very open problem. In this regard, a fundamental open question of Parry is the following:

Question [Pa2] Let G be a finite abelian group. Is it possible for there to exist infinitely many matrices A_{1}, A_{2}, … over ℤ_{+}G[t] satisfying the following conditions:

• for all i, j, the edge SFTs defined by A_{i}(0) and A_{j}(0) are topologically conjugate irreducible SFTs;

• for all distinct i, j, the skew product systems defined by A_{i} and A_{j} are not isomorphic (i.e. the matrices A_{i}, A_{j} are not sse over ℤ_{+}G); and

• there is a polynomial p(t) in ℤG[t] such that for all i, det(I − tA_{i}) = p(t) ?

The discussion of this subsection was based on communications from Bill Parry [Pa2]. Strong shift equivalence over ℤ_{+}G has also been used by Michael Sullivan in his study of twistwise flow equivalence, with special emphasis on the case G = ℤ/2ℤ, and there are related ideas in his papers [Su1, Su2, Su3].

5.4. Markov chains. Let ℝ_{+}^{∗} be the group of positive real numbers under multiplication; then ℤℝ_{+}^{∗} is the associated integral semigroup ring, with positive cone ℤ_{+}ℝ_{+}^{∗} as in the previous subsection. Parry and Tuncel [PT] developed a classification scheme for irreducible Markov chains. In their setup, an irreducible matrix A over ℤ_{+}ℝ_{+}^{∗} determines a shift of finite type σ_{A} with a shift-invariant Markov measure μ_{A} (actually, they worked not with ℤ_{+}ℝ_{+}^{∗} but with an isomorphic semiring, ℤ_{+}[exp]). For example, if P is an irreducible stochastic matrix P of transition probabilities for a Markov chain, and A is the matrix over ℤ_{+}ℝ_{+}^{∗} defined by A(i, j) = [P (i, j)], then A defines the Markov measure μ_{A} one would normally associate with P.

Parry and Tuncel (building on earlier work of Williams and Parry [PW]) showed two such matrices A, B are strong shift equivalent over ℤ_{+}ℝ_{+}^{∗} if and only if there is a topological conjugacy σ_{A} → σ_{B} which sends μ_{A} to μ_{B}, and developed the other natural generalizations of the ℤ theory. Subsequently Parry and Schmidt [PS] showed how to reduce the classification problem in a canonical way to the strong shift equivalence problem over ℤ_{+}G for canonically associated finitely generated groups G (the ratio and weights groups). This Markov chain sse theory was the first satisfactory extension of Williams’ sse theory to a further dynamical classification problem, but we see that at the level of strong shift equivalence it is a special case of the cocycle classification discussed in the previous subsection.

For a clear introduction to this theory for Markov chains, we recommend [MT] (also see [Tu1] and its references for later developments).

5.5. Other classifications with SSE. There are also rather satisfactory shift equivalence theories for the classification of sofic systems up to topological conjugacy [N1, N2, HN, BK, KR1] and the classification of locally compact countable state Markov chains up to uniformly continuous topological conjugacy [W1]. In both these cases, the defining relation of strong shift equivalence is applied not to finite matrices but to morphisms in another category. In the sofic case, the morphisms are elements of a complicated ring (the integral semigroup ring of the semigroup of finitely supported ℕ × ℕ zero-one matrices with all row sums at most 1). In the other case the morphisms are infinite matrices over ℤ_{+} with all row and column sums finite. There is also a far-reaching generalization of the shift equivalence theory to arbitrary subshifts due to Matsumoto [Ma].

We mention these theories for context; we do not now know a generalized positive K-theory framework into which any of these theories might be integrated.

5.6. Wagoner’s SSE theory. Let S_{+} be a semiring with 0 and 1. Beginning with the case S_{+} = ℤ_{+}, Wagoner took the following approach to studying SSE over S_{+}. He built a CW complex SSE(S_{+}) whose 0-cells are matrices over S_{+} and whose 1-cells are elementary strong shift equivalences over S_{+}. The 2-cells were defined by the “Triangle Identities”, natural identities chosen so that in the case S = ℤ_{+} homotopy classes of paths from A to B correspond bijectively to topological conjugacies from σ_{A} to σ_{B}. A meaningful exposition of this theory is beyond the scope of this paper; we refer to the survey [W2] and its references, and the recent note [BaW]. However, the development of this complex, and the extension by Wagoner and Kim and Roush of existing theory into this framework, is the essence of recent progress on the classification of shifts of finite type such as the refutation by Kim and Roush of the Williams’ conjecture [KRW1, KR2, KR3].

6. Algebraic invariants of strong shift equivalence

To appreciate the appeal of the “positive K-theory” framework we will say (just) a little bit about the algebraic and dynamical structure around strong shift equivalence. For a more thorough exposition of the algebra around strong shift equivalence, we refer to [B2] or [B1].

6.1. SSE over a ring as a stabilized similarity. In this subsection, we assume that S is a ring and following [MS] we show that sse over S is then a stabilized version of similarity over S.

Suppose A is a square matrix. Refer to square matrices with a block form

(\begin{matrix}A & X \\ 0 & 0 \end{matrix})  or  (\begin{matrix}0 & X \\ 0 & A \end{matrix})

as nilpotent extensions of A. Note A is sse over S to its nilpotent extensions, for example

(\begin{matrix}A & X \\ 0 & 0 \end{matrix}) = (\begin{matrix}I \\ 0 \end{matrix}) (A X)  and  A = (A X) (\begin{matrix}I \\ 0 \end{matrix}) .

If U is invertible over S and B = U^{−1}AU, then A is sse over S to B via A = (AU)U^{−1}, B = U^{−1}(AU). On the other hand, if A = UV and B = V U, then A and B have nilpotent extensions which are similar over S, since

(\begin{matrix}I & 0 \\ V & I \end{matrix}) (\begin{matrix}A & U \\ 0 & 0 \end{matrix}) = (\begin{matrix}0 & U \\ 0 & B \end{matrix}) (\begin{matrix}I & 0 \\ V & I \end{matrix})

So, sse over S is the equivalence relation generated by nilpotent extension and similarity over S.

6.2. Periodic points and det(·). Suppose T is a self homeomorphism of a space and for all n, there are only finitely many T orbits of cardinality n. These counts are generally recorded with the (Artin-Mazur) zeta function of T,

ζ_{T} (t) = exp ∑_{n=1}^{∞} \frac{|Fix(T^{n})|}{n}t^{n}.

For T = σ_{A}, with A a matrix over ℤ_{+},

ζ_{T} (t) = exp ∑_{n=1}^{∞} \frac{tr(A^{n})}{n}t^{n} = [det(I − tA)]^{−1} .

6.3. Flow equivalence. Two homeomorphisms are flow equivalent if they are cross sections of a common flow. Two irreducible matrices A, B over ℤ_{+} which are nontrivial (determine SFTs with more than one orbit) define flow equivalent SFTs if and only if (i) det(I − A) = det(I − B) and (ii) the cokernel groups cok(I − A) and cok(I − B) are isomorphic [F, PSu].

6.4. Shift equivalence. Let S be a semiring with 0 and 1. Two matrices A and B are shift equivalent over S if there are matrices U, V over S and a positive integer ℓ (called the lag) such that the following equations hold.

\begin{aligned}A^{ℓ} & = UV , & B^{ℓ} & = V U \\ AU & = UB , & BV & = V A. \end{aligned}

These equations define an equivalence relation whereas the relation UV ∼ V U merely generates one. If A and B are shift equivalent over S, then for all but finitely many positive integers n, A^{n} and B^{n} are strong shift equivalent over S. When S is a PID or even a Dedekind domain, matrices are shift equivalent over S iff they are strong shift equivalent over S; and primitive matrices over ℤ_{+} are shift equivalent over ℤ_{+} if and only if they are shift equivalent over ℤ. Shift equivalence is a very strong invariant of strong shift equivalence, and it also has a rich and useful algebraic structure.

However, irreducible matrices over ℤ_{+} can be shift equivalent over ℤ_{+} but not strong shift equivalent over ℤ_{+} [KR1, KR2], and this fundamental gap in the classification problem is still very poorly understood.

7. Positive K-theory

7.1. Definitions. Let S be a ring containing a semiring S_{+} which contains the additive and multiplicative identities 0 and 1. Let E(S_{+}) be the set of ℕ × ℕ matrices E which agree with the identity matrix I in all except at most one entry E(i, j), with i ≠ j and E(i, j) ∈ S_{+}.

Let M be a collection of ℕ × ℕ matrices over S which differ from the identity matrix in at most finitely many entries. We will define a category ℭ(M, S_{+}) whose objects are M. In this category, we define a forward elementary positive equivalence to be a triple (C, (U, V), D) such that

• C and D are in M;

• UCV = D;

• one of U and V is I;

• U and V are in E(S_{+})

A backward elementary positive equivalence is a triple (D, (U^{−1}, V^{−1}), C) such that (C, (U, V), D) is a forward elementary isomorphism. An elementary positive equivalence is a forward or backward elementary positive equivalence. A positive equivalence is a concatenation of elementary positive equivalences. We may also use “S_{+}-positive equivalence” in place of “positive equivalence” for emphasis or clarity.

The S_{+}-positive equivalences are the morphisms of the category ℭ(M, S_{+}). We let K_{1}^{+}(M, S_{+}) denote the set of equivalence classes of ℭ(M, S_{+}) (where two elements of M are equivalent if there is a positive equivalence between them).

Definition NZC(S_{+}[t]) is the set of ℕ × ℕ matrices with entries in S_{+}[t] of the form I − A, where

• all but finitely many entries of A are zero

• if A(0) denotes the matrix over S_{+} obtained by setting t = 0, then there exists a permutation matrix P such that P^{−1}A(0)P has only zero entries on or below the diagonal.

(For the examples of interest to us, the second condition above is equivalent to trace(A(0)^{n}) = 0 for all nonnegative integers n.) When M = NZC(S_{+}[t]), we use ℭ(S_{+}[t]) to denote ℭ(M, S_{+}[t]), and we use K_{1}^{+}(S_{+}[t]) to denote K_{1}^{+}(M, S_{+}[t]).

The notation K_{1}^{+} above is chosen by analogy. The K_{1} group of a ring R is the abelianization of its stabilized general linear group GL(R), the ℕ×ℕ matrices which agree with the identity in all but finitely many entries and which are invertible over R. For the ring S[t], the group K_{1}(S[t]) is equal as a set to K_{1}^{+}(GL(S[t]), S_{+}[t]), if we choose the semiring S_{+} to be all of S. For an arbitrary K_{1}^{+}(M, S_{+}), we are considering a class of matrices M which need not be invertible, and we are generating equivalence from a restricted class of elementary equivalences.

7.2. From SSE to positive K theory.

Proposition [BW] Let ℤG denote the integral group ring of a group G. Then the following are equivalent for matrices A, B in NZC(ℤ_{+}G[t]):

• There is a ℤ_{+}G[t]-positive equivalence from A to B.

• The matrices A^{♯}, B^{♯} are strong shift equivalent over ℤ_{+}G. □ The correspondence established in [BW] is more detailed than this: for matrices

C, D over ℤ_{+}G, there is an explicit rule which associates to a strong shift equivalence over ℤ_{+}G from C to D a positive equivalence from I − tC to I − tD. (These postive equivalences then induce topological conjugacies of associated path space SFTs, which in the cocycle and Markov chain cases have the appropriate additional structure, which is respected by the conjugacy.) In fact, the objects of our category ℭ(M, S_{+}) become the 0-cells of a CW complex, in which the elementary forward positive equivalences are the oriented 1-cells, and the 2-dimensional cells can be defined from a positive version of the Steinberg relations for the algebraic K-theory group K_{2} (compare [W3]). The aim is to carry over the success of the Wagoner theory into this positive K framework, where we hope to obtain new insight. This effort is still in its early stages.

7.3. Algebraic invariants from I −A. We’ll give without proof the presentation of the algebraic invariants above in terms of the I − A presentation (for A in NZC(ℤ_{+}[t])). For a more thorough discussion of all this, see [B1].

First, the reciprocal of the zeta function of the SFT σ_{A} is equal to det(I − A). Next, we prepare to describe shift equivalence. For a ring R, let L(R) denote the

Laurent ring of polynomials in t, t^{−1} with coefficients in R. Let L(R)^{ℕ} denote the (countably generated free ) L(R)-module consisting of 1 × ℕ column vectors over L(R) with all but finitely many entries zero. For a matrix I − A in NZC(S_{+}[t]), let cok(I − A) denote the cokernel L(S)-module L(S)^{ℕ}/(I − A)L(S)^{ℕ}.

Now let I − A and I − B be matrices in NZC(S_{+}[t]). Then the matrices A^{♯} and B^{♯} are shift equivalent over S if and only cok(I − A) and cok(I − B) are isomorphism L(S)-modules. Shift-equivalence-over-S_{+} can be characterized as the isomorphism of ordered L(S)-modules (after putting an appropriate order structure on the cokernel module).

Finally, the flow equivalence invariants arise in this setting by “setting t equal to 1”. For emphasis we write A as A(t). The Parry-Sullivan invariant is det(I −A(1)). The Bowen-Franks group is the ℤ-module cok(I −A(1)), which is obtained from the ℤ[t, t^{−1}]-module cok(I − A(t)) by setting t equal to 1 (more formally, by applying the coinvariants functor). In the next section we will understand more precisely how flow equivalence arises naturaly in the positive K-theory setting.

Why should I−A give strong information about the associated SFT so naturally? This is probably a question too ill posed to have an answer, still we want to repeat a remark of Tuncel [Tu2] which may make “I−A” more plausible: we have (I−A)^{−1} = I + A + A^{2} + … (this is well defined by the NZC condition), so we can regard an entry (I − A)^{−1}(i, j) as recording the number of finite paths from i to j of length k, for all k.

7.4. Using K_{2}. There is an example (currently the only example) of a serious application of algebraic K-theory in the positive K-theory. Wagoner [W3] used the positive K-theory setup to define for any positive integer m a homomorphism

π_{1}( SSE(ℤ) , SSE_{2m}(ℤ_{+}) ) → K_{2}( ℤ[t]/(t^{2m}) , (t) )

and used this with van der Kallen’s computation [vdK] of the range group to generate new counterexamples to Williams’ conjecture that matrices shift equivalent over ℤ_{+} must be strong shift equivalent over ℤ_{+}. In this equation, the left hand side denotes the homotopy classes of paths in SSE(ℤ_{+}) with endpoints in SSE_{2m}(ℤ_{+}); SSE_{2m}(ℤ_{+}) is the subcomplex of SSE(ℤ_{+}) consisting of the connected components containing 0-cells A with trace(A^{k}) = 0 for 1 ≤ k ≤ 2m; and the relative K_{2} group which is the the right hand side is the kernel of the split surjective homomorphism

K_{2}( ℤ[t]/(t^{2m}) ) → K_{2}(ℤ)

which comes from setting t equal to zero. For an explanation of how all this works, we refer to [W3].

8. Flow equivalence

One of the appealing aspects of the “positive K-theory” setup is that flow equivalence and conjugacy appear naturally in the same framework.

Let ℤ[t^{∗}] be the commutative ring of elements m + nt^{∗} with • m and n in ℤ,

• (m_{1} + n_{1}t^{∗}) + (m_{2} + n_{2}t^{∗}) = (m_{1} + m_{2}) + (n_{1} + n_{2})t^{∗} ,

• (m_{1} + n_{1}t^{∗}) · (m_{2} + n_{2}t^{∗}) = (m_{1}m_{2}) + (m_{1}n_{2} + n_{1}m_{2} + n_{1}n_{2})t^{∗} . In other words, ℤ[t^{∗}] is a presentation of the integral semigroup ring ℤB of the Boolean semigroup B = {0, +}, just as ℤ[t] is a presentation of ℤℤ_{+}. There is an obvious homomorphism ℤ[t] → ℤ[t^{∗}] (sending t to t^{∗}) and we’ll use ^{∗} to denote any map induced by this homomorphism. We define NZC(ℤ_{+}[t^{∗}]) as we defined NZC(ℤ_{+}[t]) in (7.1), except that we set t^{∗} = 0 rather than setting t = 0 in the second condition. Then as in the polynomial case we use K_{1}^{+}(S_{+}[t^{∗}]) to denote K_{1}^{+}(NZC(S_{+}[t^{∗}]), S_{+}[t^{∗}]).

Now consider for example the matrices (t^{3} + t) and (2t). They present flow equivalent SFTs because there is an obvious continuous time change sending the mapping torus of one to the other. The equivalence relation of flow equivalence of SFTs is generated by topological conjugacies and such time changes. This has the following consequence: if I − A and I − B are in NZC(ℤ_{+}[t]), then A and B define flow equivalent SFTs if and only if I − A^{∗} and I − B^{∗} lie in the same element of K_{1}^{+}(ℤ_{+}[t^{∗}]). In other words, for SFTs the consolidation of topological conjugacy classes into flow equivalence classes is exactly described by the surjection

K_{1}^{+}(ℤ_{+}[t]) → K_{1}^{+}(ℤ_{+}[t^{∗}]) .

There is no analogue to this in the pure SSE theory.

Let Mℤ denote the ℕ × ℕ matrices over ℤ with all but finitely many entries agreeing with the identity. To obtain computable invariants we consider the map ℤ_{+}[t^{∗}] → ℤ induced by sending t^{∗} to 1. The corresponding map K_{1}^{+}(ℤ_{+}[t^{∗}]) → K_{1}^{+}(Mℤ, ℤ_{+}) is not injective: for an example (with only upper left corners given and with the matrices elsewhere agreeing with I), take

I − A^{∗} = (\begin{matrix}1 & 0 \\ −t^{∗} & 1 − t^{∗} \end{matrix}) → (\begin{matrix}1 & 0 \\ −1 & 0 \end{matrix}) ,
I − B^{∗} = (\begin{matrix}1 − 2t^{∗} & 0 \\ −t^{∗} & 1 − t^{∗} \end{matrix}) → (\begin{matrix}−1 & 0 \\ −1 & 0 \end{matrix}) ,
(\begin{matrix}1 & 2 \\ 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 \\ −1 & 0 \end{matrix}) = (\begin{matrix}−1 & 0 \\ −1 & 0 \end{matrix}) .

To produce in our framework the full Huang [H1, H2, H3, H4] flow equivalence classification by ℤ invariants (and obtain further information), we use the structure A acquires through its irreducible components [B3, BH]. This becomes complicated, so we will only state a result for the irreducible case (which is the central result of the theory). Let M_{irr} denote the set of matrices I − A in NZC(ℤ_{+}[t]) such that A has a unique maximal irreducible submatrix and this submatrix is nontrivial. (“Nontrivial” here means that the associated SFT is not a single finite orbit.)

For a matrix A over ℤ[t] or ℤ[t^{∗}], let A_{1} denote the matrix over ℤ induced by t ↦ t^{∗} ↦ 1. The central result is the following: for every I − A and I − B in M_{irr}, every SL(ℤ) equivalence U(I − A_{1})V = I − B_{1} lifts to a positive ℤ_{+}[t^{∗}]- equivalence from I − A^{∗} to I − B^{∗}. (The content of this result is contained in [B3], without explicit reference to matrices over ℤ[t^{∗}].) With an appropriate definition for a flow equivalence, one can restate this as follows: for matrices derived from M_{irr}, every SL(ℤ) equivalence lifts to a flow equivalence. This result lets one recover (and perhaps “explain”) the Franks classification [F] of flow equivalence of nontrivial irreducible SFTs, because cok and det are complete invariants of SL(ℤ) equivalence.

To express this classification in our framework, let Mℤ denote the ℕ×ℕ matrices over ℤ with all but finitely many entries agreeing with the identity. Then for irreducible nontrivial SFTs the consolidation of conjugacy classes into flow equivalence classes is exactly described by the map

K_{1}^{+}(M_{irr}, ℤ_{+}[t]) → K_{1}^{+}(Mℤ, ℤ)

and this map is well known to be surjective. The lifting result also provides new topological information about the mapping class group of the mapping torus of an irreducible SFT [B3].

9. Good finitary isomorphism for Markov chains

In this section we describe the bare bones of the Gomez positive K-theory classification scheme [G] for good finitary isomorphism of positive recurrent irreducible countable state Markov shifts.

A countable state Markov chain is defined just as we defined a shift of finite type, but using a countable alphabet rather than a finite alphabet. The Markov measure is likewise defined as in the finite state case, but with the countable alphabet.

A finitary isomorphism of Markov shifts is a measure preserving map φ intertwining the shifts such that φ and φ^{−1} are continuous on the complements of null sets. A magic word for φ is a word W such that for any word U, there is a word \overline{U} with length equal to the length of U such that almost surely, if x is in the domain of φ with x_{−n} ⋯ x_{−1} = W, x_{0} ⋯ x_{k} = U and x_{k+1} ⋯ x_{k+n} = W, then (φx)_{0} ⋯ (φx)_{k} = \overline{U}. The map φ is a magic word isomorphism if φ and φ^{−1} have magic words. The appropriateness of this class and its context in the study of Markov chains is discussed in [G].

We regard an element of the integral group semiring ℤ_{+}ℝ_{+}^{∗} as a formal sum

∑_{α∈ℝ_{+}} n_{α}[α]; n_{α} ∈ ℤ_{+}, α ∈ ℝ_{+}; n_{α} = 0 for all but finitely many α .

Let ℤ_{+}[[ℝ_{+}^{∗}]] be the semiring defined in the same way, except that n_{α} may be nonzero for countably many α. Then let ℤ_{+}[[ℝ_{+}^{∗}]][[t]] denote the semiring of formal power series

∑_{k=0}^{∞} a_{k}t^{k} , a_{k} ∈ ℤ_{+}[[ℝ_{+}^{∗}]] .

Now recall how a matrix I − A in NZC(ℤ_{+}[ℝ_{+}^{∗}]) presented a finite state Markov chain. In the most direct case, in which A has a unique irreducible component and the derived real matrix is stochastic, a summand [α]t^{k} of A_{ij} represents a path with transition time k and transition probability α. In the countable state case, A_{ij} is allowed to be a sum of countably many terms [α]t^{k}, and we simply regard A as a matrix over ℤ_{+}[[ℝ_{+}^{∗}]][[t]].

For A over ℤ_{+}[[ℝ_{+}^{∗}]][[t]], we let A′ denote the matrix over ℝ_{+}[[t]] obtained by applying entrywise the coefficients map ℤ_{+}[[ℝ_{+}^{∗}]] → [0, +∞] induced by ∑ n_{α}[α] ↦ ∑ n_{α}α. Let A′(1) denote the evaluation of A′ at t = 1. For the rest of this section, let M denote the set of matrices I − A such that

• A ∈ NZC(ℤ_{+}[[ℝ_{+}^{∗}]][[t]]),

• the chains corresponding to the irreducible components of A′(1) are positive recurrent, and

• there is a unique irreducible component with the maximum Perron value. In the presence of the first two conditions the last condition is equivalent to the smallest positive root of the power series det(I − A′) being a simple root. Call this unique irreducible component the maximum component. Let A_{max} denote the matrix which agrees with A in entries of this component and is zero elsewhere. The Markov shift σ_{A} associated to A in M is by definition the Markov shift associated to A_{max}. We can regard this shift as a path shift with a certain measure, or as a standard countable state Markov shift. For any irreducible countable state positive recurrent Markov chain, there is a magic word isomorphism to such a chain. We omit the details of these constructions.

Next we define the category \overline{C}(M, ℤ_{+}[[ℝ_{+}^{∗}]][[t]]). This is the category obtained by adding into C(M, ℤ_{+}[[ℝ_{+}^{∗}]][[t]]) one more generating positive equivalence: I − A is equivalent to I − A_{max}.

Gomez associated to each elementary positive equivalence a magic word isomorphism of the associated Markov shifts, and he showed that for I −A and I −B in M, every magic word isomorphism from σ_{A} to σ_{B} is induced by a positive equivalence from I − A to I − B in \overline{C}(M, ℤ_{+}[[ℝ_{+}^{∗}]][[t]]).

References

[AW] R. Adler and B. Weiss, Similarity of automorphisms of the torus, Memoirs A.M.S 98 (1970).

[BaW] L. Badoian and J.B.Wagoner, Simple connectivity of the Markov partition space, Pacific J. Math., to appear.

[B1] M. Boyle, Symbolic Dynamics and Matrices, in Combinatorial and Graph-Theoretical Problems in Linear Algebra, IMA Volumes in Math. and its Applications 50 (1993), 1-38.

[B2] M. Boyle, Algebraic aspects of symbolic dynamics, in Topics in symbolic dynamics and applications (Temuco, 1997), London Math. Soc. Lecture Note Ser.279 (2000), 57-88, Cambridge Univ. Press, Cambridge.

[B3] M. Boyle, Flow equivalence of reducible shifts of finite type by positive factorizations of elementary matrices, Pacific J. Math, to appear.

[BHa] M. Boyle and D. Handelman, The spectra of nonnegative matrices via symbolic dynamics, Annals of Math. 133 (1991) 249–316.

[BH] M. Boyle and D. Huang, Poset block equivalence of integral matrices, preprint (2000).

[BK] M. Boyle and W. Krieger, Almost Markov and shift equivalent sofic systems, Proceedings of Maryland Special Year in Dynamics 1986-87, Springer Lecture Notes in Math. 1342 (1988), 33–93, Springer, Berlin.

[BL] M. Boyle and D. Lind, Small polynomial matrix presentations of nonnegative matrices, preprint (2001).

[BW] M. Boyle and J.B. Wagoner, Nonnegative algebraic K-theory and subshifts of finite type, in preparation.

[DGS] M. Denker, C. Grillenberger, K. Sigmund, Ergodic Theory on Compact Spaces, Springer Lec. Notes in Math 527 (1970).

[E] E.G. Effros, Dimensions and C^{∗}-algebras, CBMS Reg. Conf. Series in Math 46 (1981).

[F] J. Franks, Flow equivalence of subshifts of finite type, Ergod. Th. & Dynam. Sys. 4(1984), 53-66.

[G] R. Gomez, Finitary isomorphisms of Markov chains via positive K-theory, Ph.D. thesis, University of Maryland, College Park (2000), and preprint (2001).

[HN] T. Hamachi and M. Nasu, Topological conjugacy for 1-block factor maps of subshifts and sofic covers, Proceedings of Maryland Special Year in Dynamics 1986-87, Springer Lecture Notes in Math. 1342 (1988), 251-260, Springer-Verlag.

[Ha] D. Handelman, Spectral radii of primitive integral companion matrices and log concave polynomials, in Symbolic dynamics and its applications, Contemp. Math. 135 (1992), 231–237, Amer. Math. Soc., Providence, RI.

[H1] D. Huang, Flow equivalence of reducible shifts of finite type, Ergod. Th. & Dynam. Sys. 14 (1994), 695-720.

[H2] D. Huang, Flow equivalence of reducible shifts of finite type and Cuntz-Krieger algebra, J. Reine. Angew. Math. 462 (1995), 185-217.

[H3] D. Huang, Automorphisms of Bowen-Franks groups for shifts of finite type, Ergod. Th. & Dynam. Sys., to appear.

[H4] D. Huang, The K-web invariant and flow equivalence of reducible shifts of finite type, in preparation.

[KR1] K. H. Kim and F.W. Roush, An algorithm for sofic shift equivalence, Ergodic Theory Dynam. Systems 10 (1990), 381–393.

[KR2] K.H. Kim and F.W. Roush, The Williams conjecture is false for irreducible subshifts, Electron. Res. Announc. Amer. Math. Soc. 3 (1997),105-109 (electronic).

[KR3] K.H. Kim and F.W. Roush, The Williams conjecture is false for irreducible subshifts, Annals of Math. 149 (1999), 545–558.

[KOR] K.H.Kim, N.Ormes and F.W. Roush, The spectra of nonnegative integer matrices via formal power series, J. Amer. Math. Soc. 13 (2000), 773–806.

[KRW1] K.H. Kim, F.W. Roush and J.B. Wagoner, Automorphisms of the dimension group and gyration numbers of automorphisms of a shift, J. Amer. Math. Soc. 5 (1992), 191-212.

[KRW2] K.H. Kim, F.W. Roush and J.B. Wagoner, Inert actions on periodic points, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 55-62 (electronic).

[KRW3] K.H. Kim, F.W. Roush and J.B. Wagoner, Characterization of inert actions on periodic points I, Forum Math. 12 (2000), 565-602.

[KRW4] K.H. Kim, F.W. Roush, and J.B. Wagoner, Characterization of inert actions on periodic points II, Forum Math. 12 , 671-712.

[Ki] B.P. Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts, Springer-Verlag (1998).

[LM] D. Lind and B. Marcus, An introduction to Symbolic Dynamics and Coding, Cambridge University Press (1995).

[MS] M. Maller and M. Shub, The integral homology of Smale diffeomorphisms, Topology 24 (1985), 153-164.

[MT] B. Marcus and S. Tuncel, The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains, Ergodic Theory Dynam. Systems 11 (1991), 129–180.

[Ma] K. Matsumoto, Presentations of subshifts and their topological conjugacy invariants, Documenta Math. 4 (1999), 285-340.

[N1] M. Nasu, Topological conjugacy for sofic systems, Ergodic Theory Dynam. Systems 6 (1986), 265-280.

[N2] M. Nasu, Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological Markov shifts, Proceedings of Maryland Special Year in Dynamics 1986-87, Springer Lecture Notes in Math. 1342 (1988), 564-607,Springer-Verlag.

[Pa1] W. Parry, Intrinsic Markov chains, Trans. AMS 112 (1964), 55-66.

[Pa2] W. Parry, personal communication.

[PS] W. Parry and K. Schmidt. Natural coefficients and invariants for Markov shifts, Inventiones Math. 76 (1984), 15-32.

[PSu] W. Parry and D. Sullivan, A topological invariant for flows on one-dimensional spaces, Topology 14(1975), 297-299.

[PT] W. Parry and S. Tuncel, On the stochastic and topological structure of Markov chains, Bull. London Math. Soc. 14 (1982), 16–27.

[PW] W. Parry and R.F. Williams, Block coding and a zeta function for Markov chains, Proc. London Math. Soc. 35 (1977), 483-495.

[Pe] D. Perrin, On positive matrices, Theoret. Comput. Sci. 94 (1992), no. 2, 357–366.

[R] J. Rosenberg, Algebraic K-theory and its applications, Graduate Texts in Mathematics 147, Springer-Verlag (1994).

[S] K. Schmidt, Dynamical systems of algebraic origin, Progress in Mathematics 128, Birkhauser Verlag (1995).

[Su1] M. Sullivan, An invariant of basic sets of Smale flows, Ergodic Theory Dynam. Systems 17 (1997), 1437–1448; Errata, Ergodic Theory Dynam. Systems 18 (1998), 1047.

[Su2] M. Sullivan, Invariants of twist-wise flow equivalence, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 126–130 (electronic).

[Su3] M. Sullivan, Invariants of twist-wise flow equivalence, Discrete Contin. Dynam.Systems 4 (1998), 475–484.

[Tu1] S. Tuncel, Coefficient rings for beta function classes of Markov chains, Ergodic Theory Dynam. Systems 20 (2000), 1477–1493.

[Tu2] S. Tuncel, personal communication.

[vdK] W. van der Kallen, Le K_{2} des nombres duaux, C.R. Acad. Sc. Paris (A) 273 (1971), 1204-1207.

[W1] J.B. Wagoner, Topological Markov chains, C^{∗}-algebras, and K_{2}, Adv. in Math. 71 (1988), 133–185.

[W2] J. B. Wagoner, Strong shift equivalence theory and the shift equivalence problem, Bull. Amer. Math. Soc. (N.S.) 36 (1999), no. 3, 271–296.

[W3] J. B. Wagoner, Strong shift equivalence and K_{2} of the dual numbers, J. Reine Angew. Math. 521 (2000), 119-160.

[Wi] R.F. Williams, Classification of subshifts of finite type, Annals of Math. 98 (1973), 120-153; Errata, Annals of Math. 99 (1974), 380-381.

Department of Mathematics, University of Maryland, College Park, MD 20742-4015, U.S.A.

   E-mail address: mmb@math.umd.edu  Home page:  www.math.umd.edu/∼mmb