POSITIVE ALGEBRAIC K-THEORY AND SHIFTS OF FINITE TYPE

M. BOYLE AND J.B.WAGONER

Abstract. This paper discusses classification of shifts of finite type using positive algebraic K-theory.

1. Introduction

Since R.F. Williams’ work in the early 1970’s, one of the main themes in studying shifts of finite type and their isomorphisms has been strong shift equivalence theory. See the overviews [B1,KR2,W5]. On the other hand, an important technique in coding theorems and concrete applications involving shifts of finite type has been state splitting and merging. See [LM, M]. The purpose of this article is to place state splitting and merging into an algebraic setting directly related to algebraic K-theory and to show how this is related to strong shift equivalence theory. We discuss how to associate a shift of finite type (X(A), σ(A)) to a matrix A which has nonnegative integral polynomial entries and which satisfies the no Z-cycles condition (NZC) in (2.1). In addition, we show how positive row and column operations over Z^{+}[t] on I − A as in (3.2) give rise to conjugacies of shifts of finite type. Fix a pair of indices (k, l) where k ≠ l. Let b be an integral polynomial satisfying 0 ≤ b ≤ A_{kl}. A positive row operation adds b times the l^{th} row to the k^{th} row of I − A, and a positive column operation adds b times the k^{th} column to the l^{th} column of I − A. The resulting matrix is of the form I − B where B has nonnegative integral polynomial entries and satisfies NZC too. Corresponding respectively to these row and column operations there are topological conjugacies L_{kl}(b) and R_{kl}(b) from (X(A), σ(A)) to (X(B), σ(B)). This generalizes the material in [KRW] and gives geometric content to the polynomial strong shift equivalence equations (PSSE) in Section 4. The construction of shifts of finite type in the presence of NZC, and various results of this paper including Theorem 7.2, are also known independently to K.H.Kim and F.W.Roush.

Assume A and B are nonnegative polynomial matrices satisfying NZC. The main results are

Classification Theorem (X(A), σ(A)) and (X(B), σ(B)) are topologically conjugate iff there is a sequence of positive row and column operations over Z^{+}[t] connecting I − A and I − B.

Conjugacy Theorem Every topological conjugacy from (X(A), σ(A)) to (X(B), σ(B)) arises from some sequence of positive row and column operations over Z^{+}[t] connecting I − A and I − B.

These theorems require the introduction of NZC. See Remark 6.4.

The matrices I − A and I − B are the same in the algebraic K-theory group K_{1}(Q(t)) iff they are connected by a sequence of row and column operations over the field of rational functions Q(t). The Classification Theorem gives geometric meaning to positive row and column operations over Z^{+}[t]. The Conjugacy Theorem is really part of the Classification Theorem. But we state it explicitly, because it is the first step in describing the group of automorphisms Aut(σ(A)) of (X(A), σ(A)) as some kind of positive algebraic K-theory group K_{2}(Z^{+}[t]). A sequence of row and column operations over Q(t) from I − A to itself gives rise to an element in K_{2}(Q(t)). Analogously, the Conjugacy Theorem says that any element of Aut(σ(A)) arises from positive row and column operations over Z^{+}[t] from I−A to itself. To construct the positive algebraic K-theory group K_{2}(Z^{+}[t]), it remains to specify what natural relations are satisfied.

2000 Mathematics Subject Classification. Primary 37B10; Secondary 19M05, 06F99 .

Key words and phrases. positive algebraic K-theory, positive row and column operations, shifts of finite type.

The first author was supported in part by NSF Grant DMS 9971501

The second was supported in part by NSF Grant DMS 9706852.

Section 2 describes the basic construction of the shift of finite type (X(A), σ(A)). Section 3 discusses positive row and column operations L_{kl}(b) and R_{kl}(b) and shows how they are related to the conjugacies c(R, S) arising from strong shift equivalence theory. Section 4 proves the Conjugacy Theorem. Section 5 discusses zeta functions and dimension modules from the nonnegative polynomial matrix viewpoint. Section 6 proves the Classification Theorem. Section 7 describes the generalization to matrices over integral group rings. Finally, the Appendix gives background on strong shift equivalence theory necessary for this paper.

We thank the referee for helpful comments which improved the exposition.

2. Nonnegative Polynomial Matrices

Matrices with nonnegative polynomial entries provide a very compact, efficient, and powerful way of representing shifts of finite type. Perhaps the first appearance of this idea is in Shannon’s work [Sh] on information theory. In [KRW] and [KOR] the polynomial matrix technique is indispensible in studying automorphisms of shift spaces on the one hand and characterizing the nonzero spectra of primitive, nonnegative integral matrices on the other. Polynomial matrix methods are used in [BL] to get small presentations of shifts of finite type, and in [KR1] to construct group extensions of shifts of finite type.

Consider a nonnegative polynomial matrix A = {A_{ij}} where A_{ij} = A_{ij}(t) lies in Z^{+}[t], the set of polynomials in t with nonnegative integer coefficients. The indices i and j will range through the positive integers, and we will assume that A has finite support, i.e., A_{ij} ≠ 0 for at most finitely many pairs of indices (i, j). We will generally let I denote the identity matrix of infinite size. For matrices appearing in the form I ± U , we will always assume U has finite support. This section describes how to construct a shift of finite type (X(A), σ(A)) under the no Z-cycles condition (NZC)

(2.1)  The nonnegative integer matrix A(0) = {A_{ij}(0)} has no periodic cycles.

This construction generalizes the one in [KRW] where it was assumed that A(0) = 0, i.e., each polynomial A_{ij} is divisible by t. From the viewpoint of this paper, a compelling reason to construct (X(A), σ(A)) in the presence of NZC is to give geometric meaning in the context of symbolic dynamics to the Polynomial Strong Shift Equivalence equations (PSSE) in Section 4. These are similar to equations found in algebraic K-theory.

The first step is to construct the directed graph A^{♭} as follows: The indices i and j will be called the primary vertices. Suppose

A_{ij} = a_{0} + a_{1}t + a_{2}t^{2} + … + a_{n}t^{n} .

Corresponding to the constant term a_{0} in A_{ij} draw a_{0} arcs from i to j. These will be called constant term routes. Corresponding to the power term a_{k}t^{k} in A_{ij} where k > 0 draw a_{k} simple paths of length k from i to j, each having k edges and k − 1 secondary vertices. These paths from i to j will be called power term routes. In particular, each route intersects the set of primary vertices only in its starting vertex and its ending vertex. For example, the matrix

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

gives rise to the graph A^{♭}

[figure: 1; 2]

where the constant term route is shown as a dotted arrow and the power term routes are shown as solid arrows. The nonnegative polynomial matrix A and the graph A^{♭} are essentially identical ways of presenting the same data, and we will consider them as being the same.

We will explain two equivalent methods for constructing shift spaces from A^{♭}. The first space (P (A), σ(A)) will use the path space construction which generalizes the well known edge path construction explained in [LM]. This will be useful in showing how certain elementary row and column operations on the matrix I − A give rise to topological conjugacies of shift spaces. The second space (X(A), σ(A)) will come from a zero-one matrix A^{#} of finite size. One of its uses is to show (P (A), σ(A)) is actually a shift of finite type.

The Path Space Construction

Consider the set P of all sequences E = {E_{n}} = {(r_{n}, t_{n})}, −∞ < n < ∞ , satisfying the conditions

(1) Each r_{n} is a route of A^{♭}, and the end vertex of r_{n} is the start vertex of r_{n+1}.

(2) Each t_{n} is an integer and t_{n+1} = t_{n} + |r_{n}|, where |r_{n}| is zero if r_{n} is a constant term route and is the number of arcs in r_{n} if r_{n} is a power term route.

The intuitive idea is that E is an infinite trip through A^{♭} where at time t_{n} the voyager is at the starting vertex of the route r_{n} and is about to traverse r_{n}. Let Ω denote the (infinite) alphabet consisting of all pairs (r, t) where r is a route of A^{♭} and t is an integer. We give Ω the discrete topology and endow P with the topology it inherits as a subset of the infinite product Ω^{Z}. We say E = {(r_{n}, t_{n})} is equivalent to E′ = {(r′_{n}, t′_{n})} and write E ∼ E′ provided there is some integer m so that r_{n+m} = r′_{n} and t_{n+m} = t′_{n} for all n. Use the quotient topology to define

(2.2)  P (A) = P modulo ∼ .

We remark that P (A) is compact. To see this, let L be the length of the longest route in A^{♭}. Let P_{L} denote the compact subspace of P consisting of those E satisfying 0 ≤ t_{0} ≤ L. Then the quotient map from P_{L} to P (A) is still onto, because the NZC implies that any E must have 0 ≤ t_{n} ≤ L for some n. Next define a shift map σ : P → P by the equation

(2.3)  σ(E)_{n} = (r_{n}, t_{n} − 1) .

This respects the equivalence relation ∼ and induces a continuous shift map

(2.4)  σ(A) : P (A) → P (A) .

The #-Construction

We will now construct a zero-one matrix A^{#} with finite support from the graph A^{♭}, and by definition, we will let

(2.5)  (X(A), σ(A)) = {X_{A^{#}}, σ_{A^{#}}}

where the bracket notation on the right denotes the standard “vertex shift” construction as explained in [LM,W5] and in the Appendix.

Special Case A(0) = 0

This is just the edge path construction for the graph A^{♭}. Namely, the set of states S^{#} is the set of arcs between primary and/or secondary vertices in A^{♭}, and A^{#}(α, β) = 1 iff the end vertex of α is the start vertex of β.

General Case

The first step is to define the set S^{#} of states of A^{#}. The states will be quintuples

(2.6)  α = (i, α′, j, α′′, k)

where

(1) Each of i, j, and k is a primary vertex.

(2) If i ≠ j, then α′ is a connected path of constant term routes from i to j and α′′ is a subarc of a power term route from j to k.

(3) If i = j, then there are no paths of constant term routes from i to j because of NZC. So we let α′ be the symbol ϕ, and we require α′′ to be a subarc of a power term route from j to k.

When i = j , the state α is really just the triple (j, α′′, k). So, for example, if A_{jk} = t, then α is identified with the power term arc from j to k. But we also write α as a quintuple as in (2.6) to preserve uniformity of notation. There are no states consisting only of a constant term path from one vertex to another.

The next step is to define the transition function

(2.7)  A^{#} : S^{#} × S^{#} → {0, 1} .

Let α = (i, α′, j, α′′, k) and β = (p, β′, q, β′′, r). Then

A^{#}(α, β) = 1 when the conditions in Case 1

or Case 2 below hold

A^{#}(α, β) = 0 otherwise .

Case 1. We have i = p, j = q, k = r, and α′ = β′. Both α′′ and β′′ are subarcs on the same power term route from j to k and the ending vertex of α′′ is the starting vertex of β′′.

Case 2. The subarc α′′ is the last one along a power term route from j to k and therefore the ending vertex of α′′ is k. We require k = p, and we require that the subarc β′′ is the first one along a power term route from q to r. In particular, the beginning vertex of β′′ is q.

The final step is to make A^{#} into an n^{#} × n^{#} matrix where n^{#} is the number of states. We do this by

(2.8)  choosing an ordering of the set S^{#} .

Two different choices of orderings of S^{#} will produce matrices A_{1}^{#} and A_{2}^{#} related by the equation

(2.9)  A_{2}^{#} = Q^{−1}A_{1}^{#}Q

where Q is a permutation matrix. Q induces a conjugacy from (X_{A_{1}^{#}}, σ_{A_{1}^{#}}) to (X_{A_{2}^{#}}, σ_{A_{2}^{#}}) .

Comment NZC implies that the number of paths consisting only of constant term routes is finite. Therefore S^{#} is a finite set, and {X_{A^{#}}, σ_{A^{#}}} will be a shift of finite type.

In the case where the constant term matrix A(0) = 0, there are no constant term routes and the matrix A^{#} is the same as the one constructed in [KRW]. If A is a matrix over Z^{+}, then {tA}^{♭} is the graph associated to the matrix A and {tA}^{#} is precisely the zero-one matrix describing the edge path presentation matrix A′ of the shift of finite type associated to A. In particular, we have

(2.10)  (X(tA), σ(tA)) = {X_{A′} , σ_{A′} } .

See [LM] and the Appendix.

Example 2.11 Consider the matrix

A = ( \begin{matrix}t & 1 \\ t & 0 \end{matrix} ) .

The graph A^{♭} is

[figure: 1; 2]

There are three states:

[figure: α_{1}; =; 1; α_{2}; =; 1; 2; 1; α_{3}; =; 2; 1]

The matrix A^{#} is

( \begin{matrix}1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{matrix} )

Hence

(X(A), σ(A)) = {X_{A^{#}}, σ_{A^{#}}} = the full Bernoulli 2-shift.

As discussed in the Appendix, we don’t require each row and each column of a matrix M to have a nonzero entry in forming {X_{M}, σ_{M}}.

Example 2.12 Consider the matrix

A = ( \begin{matrix}t & t \\ 1 & 0 \end{matrix} )

The graph A^{♭} is

[figure: 1; 2]

There are four states:

[figure: α_{1}; =; 1; α_{2}; =; 1; 2; α_{3}; =; 2; 1; α_{4}; =; 2; 1; 2]

The matrix A^{#} is

( \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{matrix} )

which is just the matrix for the edge path presentation, as discussed in [LM], of the shift of finite type associated to the graph

[figure: 1; 2]

Hence, we again have

(X(A), σ(A)) = {X_{A^{#}}, σ_{A^{#}}} = the full Bernoulli 2-shift .

Equivalency of the Path Construction and the #-Constuction

Theorem 2.13. There is a topological conjugacy Φ : (P (A), σ(A)) → (X(A), σ(A)).

Proof. Here is how Φ and its inverse Ψ : (X(A), σ(A)) → (P (A), σ(A)) are constructed.

Definition of Φ: Let E = {(r_{h}, t_{h})} represent an infinite path in P (A) where −∞ < h < ∞. We want to find an infinite allowable sequence Φ(E) = {Φ(E)_{n}} of states in S^{#}. The NZC condition (2.1) implies we can write the set of integers as the union of intervals [t_{p}, t_{p+1}, …, t_{p+q+1}] where t_{p−1} < t_{p} = … = t_{p+q} < t_{p+q+1} and the intervals overlap only at their endpoints. Let i be the start vertex of r_{p}, j be the start vertex of r_{p+q}, and k be the final vertex of r_{p+q}. If q = 0, let α′ = ϕ. If q > 0, let α′ be the path of constant term routes leading from i to j which is the concatenation of r_{p}, …, r_{p+q−1}. The power term route r_{p+q} is the concatenation of subarcs α′′_{1}, …, α′′_{ℓ} where t_{p+q+1} = t_{p+q} +ℓ. Then we let Φ(E)_{n} = (i, α′, j, α′′_{s}, k) where s = n+1−t_{p+q} for t_{p+q} ≤ n < t_{p+q+1}.

Definition of Ψ: Let x = {x_{p}} be in X(A) where x_{p} = (i_{p}, α′_{p}, j_{p}, α′′_{p}, k_{p}). We want to get Ψ(x) = {(r_{n}, t_{n})} in P (A). The constant term paths α′_{p} and the power term routes α′′_{p} fit together compatibly to produce a sequence of primary vertices {v_{n}} and a sequence of routes {r_{n}} where r_{n} goes from v_{n} to v_{n+1}. To establish the indexing of these routes which concatenate together, it suffices to specifiy that r_{0} is the power term route containing the arc α′′_{0}. To get the required sequence of times {t_{n}}, first let t_{0} = −(k − 1) = 1 − k where α′′_{0} is the k-th arc along r_{0} going from v_{0} to v_{1}. Then we recursively define t_{n} for n ≠ 0 by the condition t_{n+1} = t_{n} + |r_{n}|.

Verification that Φ and Ψ commute with σ(A) and that they are continuous inverses of each other is straightforward.

□

For future reference, we now generalize Nasu’s definition [N,W4] of simple automorphisms of a shift of finite type. His work has played an important role. An elementary simple automorphism of (X(A), σ(A)) is one coming from an automorphism of the graph A^{♭} which fixes the primary vertices. A simple automorphism of (X(A), σ(A)) is one of the form αΘα^{−1} where α : (X(A), σ(A)) → (X(B), σ(B)) is a topological conjugacy and Θ is an elementary simple automorphism of (X(B), σ(B)). Composition is read from left to right.

Definition 2.14. Simp(σ(A)) is the subgroup of Aut(σ(A)) generated by simple automorphisms.

We briefly discuss in (4.20) below why this yields the same group as Nasu’s original definition.

3. Positive Row and Column Operations

In this section we discuss how positive row and column operations on matrices give rise to conjugacies between shifts of finite type defined by matrices satisfying NZC. In this section, as elsewhere in this paper, composition is read from left to right. Also, we use the terms conjugacy and topological conjugacy interchangeably.

Let A = {A_{ij}} be a nonnegative polynomial matrix with finite support satisfying NZC (2.1). Fix an entry A_{kl} of A where k ≠ l, and let b denote a polynomial in Z[t]. Let T_{kl}(b) denote the matrix which has the entry b in the k^{th} row and l^{th} column and zeros elsewhere. Let I denote the infinite identity matrix. Define

(3.1)  E_{kl}(b) = I + T_{kl}(b)

E_{kl}(b) will be called a positive shear if b lies in Z^{+}[t]. Define a new matrix of finite support B by one of the equations

(3.2)  \begin{aligned}I − B & = & E_{kl}(b)(I − A) \\ I − B & = & (I − A)E_{kl}(b) \end{aligned}

We will say that E_{ij}(b) goes from I − A to I − B .

If a(t) = ∑_{r} a_{r}t^{r} and b(t) = ∑_{r} b_{r}t^{r} are polynomials, we define a ≤ b iff a_{r} ≤ b_{r} for each r. We also define ZO[t] to be the set of zero-one polynomials: those polynomials a(t) = ∑_{r} a_{r}t^{r} such that each coefficient a_{r} is equal to zero or one.

Positive Shear Lemma 3.3. Assume 0 ≤ b ≤ A_{kl}. Then B is nonnegative and satisfies NZC. Corresponding to the first and second equations in (3.2) respectively there are conjugacies

L_{kl}(b) : (P (A), σ(A)) → (P (B), σ(B))
R_{kl}(b) : (P (A), σ(A)) → (P (B), σ(B))

The conjugacies L_{kl}(b) and R_{kl}(b) are uniquely determined up to composition on the left by elements in Simp(σ(A)) and composition on the right by elements in Simp(σ(B)). If A and B have all entries in ZO[t], then the conjugacies L_{kl}(b) and R_{kl}(b) are uniquely determined.

Proof. For simplicity, let b = t^{p} be a single route from the primary vertex k to the primary vertex l of length p ≥ 0. The matrix B (i.e., the graph B^{♭}) is obtained from the matrix A by first deleting the route b between k and l and then inserting a route r′ of length |r′| = p + |r| from k to q for each route r starting at l and ending at q. Every infinite trip through A corresponds uniquely to a concatenation of routes in B and this determines L. More precisely, let E = {(r_{n}, t_{n})} be in P (A). Consider a part of E like

…, (r_{n}, t_{n}), (r_{n+1}, t_{n+1}), (r_{n+2}, t_{n+2}), …

where r_{n} = b and r_{n+1} = r as above. Delete (r_{n+1}, t_{n+1}) and replace (r_{n}, t_{n}) with (r′, t_{n}). Note that t_{n+2} = t_{n} + |r′|. The result is just a subsequence E′ of E where some of the items have been changed. Now renumber this subsequence in an increasing fashion so that it becomes a sequence E′ = {E′_{n}} where n runs through all the integers. The equivalence class modulo ∼ of E′ does not depend on this renumbering, so the rule E → E′ induces a map L : P (A) → P (B). This map L is bijective; L and L^{−1} are continuous; and Lσ = σL.

In the case that b is a sum of terms t^{p}, to define L we make the replacements above separately for each summand t^{p} of b. There is no contradiction of definitions because k ≠ l. The only freedom in the construction involves the choice of particular corresponding routes, in the case that an entry of A or B has the form ∑_{r} a_{r}t^{r} with some a_{r} > 1. Permutations of such routes are given by simple automorphisms.

□

We now discuss a generalization of the Positive Shear Lemma. If P = {P_{ij}} and Q = {Q_{ij}} are nonnegative polynomial matrices, we say P ≤ Q provided P_{ij} ≤ Q_{ij} for each pair of indices (i, j).

Assume X is the conjugate of an upper triangular matrix by a permutation. Define an invertible matrix

(3.4)  E(X) = I + X .

Let A be a nonnegative polynomial matrix satisfying NZC as in (2.1). Define a new matrix B by one of the equations

(3.5)  \begin{aligned}I − B & = & E(X)(I − A) \\ I − B & = & (I − A)E(X) \end{aligned}

Generalized Positive Shear Lemma 3.6. Assume 0 ≤ X ≤ A and X^{2} = 0. Then B is nonnegative and satisfies NZC . Corresponding to the first and second equations in (3.5) respectively there are conjugacies

L(X) : (P (A), σ(A)) → (P (B), σ(B))
R(X) : (P (A), σ(A)) → (P (B), σ(B)) .

If A, X and B have all entries in ZO[t], then the conjugacies L(X) and R(X) are uniquely determined. For the category of matrices over Z^{+}[t], L(X) and R(X) are well defined up to multiplication on the left by elements in Simp(σ(A)) and multiplication on the right by elements in Simp(σ(B)).

Proof. The proof is a straightforward generalization of the proof for the Positive Shear Lemma. The idea is that the condition X^{2} = 0 allows the construction in (3.3) to be done at various places in A simultanously in view of the following lemma. □

Lemma 3.7. Let X be a nonnegative polynomial matrix satisfying the condition X^{2} = 0. Then there are disjoint sets of indices I and J such that X_{ij} = 0 unless i is in I and j is in J.

Proof. Let I be the set of those indices i such that X_{ij} ≠ 0 for some j. Let J be the set of those indices j such that X_{ij} ≠ 0 for some i. Nonnegativity with X^{2} = 0 implies I ∩ J = 0. □

4. Conjugacies

The purpose of this section is to show that all conjugacies between shifts of finite type are generated by the positive row and column type conjugacies L_{kl}(b) and R_{kl}(b) of (3.3). Polynomial matrices A, B, etc. will have finite support. For each such matrix M satisfying NZC, we fix a topological conjugacy Φ_{M} : (P (A), σ(A)) → (X(A), σ(A)). To any conjugacy L from (P (A), σ(A)) to (P (B), σ(B)), we associate a conjugacy \overline{L} = (Φ_{A})^{−1}LΦ_{B} from (X(A), σ(A)) to (X(B), σ(B)).

Theorem 4.1. Let A and B be nonnegative polynomial matrices satisfying NZC. Any conjugacy Δ : (X(A), σ(A)) → (X(B), σ(B)) can be written as a composition

Δ = ∏_{i=1}^{n} \overline{C}_{k_{i}l_{i}}(b_{i})^{ϵ_{i}}

where A_{0} = A, A_{n} = B, and C_{k_{i}l_{i}}(b_{i}) is a positive row or column conjugacy L_{kl}(b) or R_{kl}(b) as in (3.3) which goes from I − A_{i−1} to I − A_{i} if ϵ_{i} = 1 and from I − A_{i} to I − A_{i−1} if ϵ_{i} = −1.

This will be a consequence of the next two results. The first is a special case of (4.1).

Proposition 4.2. Let A and B be zero-one matrices. Any conjugacy Δ : (X(tA), σ(tA)) → (X(tB), σ(tB)) can be written as a composition

Δ = ∏_{i=1}^{n} \overline{C}_{k_{i}l_{i}}(t)^{ϵ_{i}}

where A_{0} = tA, A_{n} = tB, and C_{k_{i}l_{i}}(t) is a positive row or column conjugacy as in (3.3) which goes from I − A_{i−1} to I − A_{i} if ϵ_{i} = 1 and from I − A_{i} to I − A_{i−1} if ϵ_{i} = −1. Moreover, each A_{i} = tD_{i} where D_{i} is a zero-one matrix.

Proposition 4.3. Let A be a nonnegative polynomial matrix satisfying NZC. There is a path of positive row and column operations over Z^{+}[t] connecting I − A and I − tA^{#}.

We first show how (4.1) follows from (4.2) and (4.3). Later we will prove (4.2) and (4.3).

Proof of (4.1). By Proposition 4.3 and the Positive Shear Lemma 3.3, there are conjugacies

ρ_{A} : (X(A), σ(A)) → (X(tA^{#}), σ(tA^{#})) ,
ρ_{B} : (X(B), σ(B)) → (X(tB^{#}), σ(tB^{#}))

which are compositions of positive row and column conjugacies. Reading composition from left to right, we define a conjugacy

γ = (ρ_{A})^{−1}Δρ_{B} : (X(tA^{#}), σ(tA^{#})) → (X(tB^{#}), σ(tB^{#})) .

By Proposition 4.2, γ is a composition of positive row and column conjugacies, and therefore so is ρ_{A}γ(ρ_{B})^{−1} = ρ_{A}[(ρ_{A})^{−1}Δρ_{B}](ρ_{B})^{−1} = Δ .

□

Given an infinite, finitely supported matrix M, we define its support to be the largest integer s = supp(M) such that M_{sk} ≠ 0 or M_{ks} ≠ 0 for some integer k. (If M is the zero matrix, we define supp(M) = 1.) Now suppose A, B, R, S are infinite finitely supported matrices over Z^{+} such that

(4.4)  A = RS and B = SR .

Pick an integer n greater than or equal to supp(A), supp(B), supp(R), and supp(S). Let I denote the n × n identity matrix. The following set of equations will be our key to transferring strong shift equivalence results into the polynomial setting.

Polynomial Strong Shift Equivalence Equations (PSSE)

(4.5)  ( \begin{matrix}I − tRS & 0 \\ −tS & I \end{matrix} ) ( \begin{matrix}I & 0 \\ tS & I \end{matrix} ) = ( \begin{matrix}I − tRS & 0 \\ 0 & I \end{matrix} )

(4.6)  ( \begin{matrix}I & R \\ 0 & I \end{matrix} ) ( \begin{matrix}I & −R \\ −tS & I \end{matrix} ) = ( \begin{matrix}I − tRS & 0 \\ −tS & I \end{matrix} )

(4.7)  ( \begin{matrix}I & −R \\ −tS & I \end{matrix} ) ( \begin{matrix}I & R \\ 0 & I \end{matrix} ) = ( \begin{matrix}I & 0 \\ −tS & I − tSR \end{matrix} )

(4.8)  ( \begin{matrix}I & 0 \\ tS & I \end{matrix} ) ( \begin{matrix}I & 0 \\ −tS & I − tSR \end{matrix} ) = ( \begin{matrix}I & 0 \\ 0 & I − tSR \end{matrix} )

For each matrix M in the PSSE, there is a 2 × 2 block structure, which we will use below to define associated conjugacies. For example R_{21}(tS) will denote a conjugacy associated by Lemma 3.6 to the equation (4.5). Recall, we read composition from left to right.

Lemma 4.9. Let A, R, S, B be matrices over Z^{+} satisfying (4.4) with n chosen as above for the PSSE. Then there is a conjugacy of path space shifts

f(R, S) : P ( \begin{matrix}tA & 0 \\ 0 & 0 \end{matrix} ) → P ( \begin{matrix}0 & 0 \\ 0 & tB \end{matrix} )

defined as a composition of maps from the PSSE equations (4.5),(4.6),(4.7),(4.8) as follows:

f(R, S) = R_{21}(tS)^{−1}L_{12}(R)^{−1}R_{12}(R)L_{12}(tS) = L_{12}(R)^{−1}R_{12}(R) .

The conjugacy f(R, S) is uniquely determined modulo composition with simple automorphisms, and it is uniquely determined if A, R, S and B are zero-one matrices.

Proof. The proof is a straightforward computation. The second equality displayed holds because R_{21}(tS) and R_{12}(R) are identity maps, which is possible because from the path space construction we have equalities of shifts of finite type

P ( \begin{matrix}tRS & 0 \\ 0 & 0 \end{matrix} ) = P ( \begin{matrix}tRS & 0 \\ tS & 0 \end{matrix} ) and P ( \begin{matrix}0 & 0 \\ tS & tSR \end{matrix} ) = P ( \begin{matrix}0 & 0 \\ 0 & tSR \end{matrix} )

□

Given the lemma we have the following definition.

Definition 4.10. Given A, R, S, B as in Lemma 4.9, let e(R, S) denote the conjugacy of path space shifts P (A) → P (B) defined as f(R, S)f(I, B)^{−1}.

Next we specify a definite choice of Φ_{tM} when M is zero-one, in which case X(A) = X_{(tM)^{#}} = X_{M′}. (The truth of Propositions 4.1 and 4.2 does not depend on the particular choice.)

Definition 4.11 (Definition of Φ_{tM}). If M is a zero-one matrix and x ∈ P (tM), let {(r_{k}, t_{k})} be a sequence representing x such that t_{0} = 0; then Φ_{tM}(x) is the point \overline{x} in X_{M′} such that \overline{x}_{k} is the unique edge from the initial vertex of r_{k} to the terminal vertex of r_{k}.

We can now turn to the proof of Proposition 4.2.

Proof of (4.2). The basic idea of the proof is simple: we’ve known since Williams [Wi] that any conjugacy of shifts of finite type defined by zero-one matrices arises from some strong shift equivalence using zero-one matrices, and the PSSE lets us transport this result to the polynomial matrix setting. The complication is now only in precisely tracking definitions.

By definition a conjugacy Δ from (X(tA), σ(tA)) to (X(tB), σ(tB)) is a conjugacy from (X_{{tA}^{#}}, σ_{{tA}^{#}}) to (X_{{tB}^{#}}, σ_{{tB}^{#}}). From (A.14) we know that Δ is the subdivision of a conjugacy from (X_{A}, σ_{A}) to (X_{B}, σ_{B}). This means that

(4.12)  Δ = ∏_{i} c(Ri^{′}, Si^{′})^{ϵ_{i}}

where (Ri^{′}, Si^{′}) is the subdivision of a strong shift equivalence (R_{i}, S_{i}) in the category of zero-one matrices.

Now \overline{e}(R, S) = (Φ_{tA})^{−1}e(R, S)Φ_{tB}, and it suffices to prove c(R′, S′) = \overline{e}(R, S) when the elementary strong shift equivalence (R, S) : A → B of (4.4) is a strong shift equivalence in the category of zero-one matrices.

We compute L_{12}(R) : z ↦ x and R_{12}(R) : z ↦ w where

z ∈ P ( \begin{matrix}0 & R \\ tS & 0 \end{matrix} ) ,
x ∈ P (tA) = P ( \begin{matrix}tA & 0 \\ 0 & 0 \end{matrix} ) = P ( \begin{matrix}tA & 0 \\ tS & 0 \end{matrix} ) , and
w ∈ P ( \begin{matrix}0 & 0 \\ tS & tB \end{matrix} ) = P (tC) , where C = ( \begin{matrix}0 & 0 \\ 0 & B \end{matrix} ) .

Consider the diagram

(4.13)  [figure: k_{i}; r_{i}; a_{i}t; k_{i+1}; r_{i+1}; a_{i+1}t; k_{i+2}; l_{i}; s_{i}t; c_{i}t; l_{i+1}; s_{i+1}t]

Here r_{i} is one of the R_{k_{i}l_{i}} constant term arcs from k_{i} to l_{i} and s_{i}t is one of the S_{l_{i}k_{i+1}} power term arcs of length one from l_{i} to k_{i+1}. We use the notation

z = {…, r_{−1}, ts_{−1}, |r_{0}, ts_{0}, …}

when the equivalence class z contains a sequence {…, (r_{−1}, t_{−2}), (ts_{−1}, t_{−1}), (r_{0}, t_{0}), (ts_{0}, t_{1}) …} with t_{0} = 0 (i.e., the vertical bar specifies that the route r_{0} “begins at time 0”). We have 1 ≤ k_{i} ≤ n and n + 1 ≤ l_{i} ≤ 2n. Because the matrices RS and SR are zero-one, z determines uniquely the additional routes/edges of P (A) and P (C), denoted a_{i}t and c_{i}t. Examination of L_{12}(R) and R_{12}(R) shows that

x = {…, a_{−1}t, |a_{0}t, …} and w = {…, c_{−1}t, |c_{0}t, …} .

and therefore w = f(R, S)(x). Let y = e(R, S)(x), i.e., f(I, B)(y) = (w). Then y is equal to w except for a permutation of indices: i.e., l_{i} = p_{i} + n. Examination of the proof of the construction of c(R′, S′) in [W4,Section 2] now shows that c(R′, S′) = \overline{e}(R, S) as required. □

Proof of (4.3). First suppose A(0) is nonzero. Then there exists some entry A_{kl}(t) such that • A_{kl}(0) ≠ 0 and

• row l of A(0) is zero. Let α = A_{kl}(0) and set E = E_{kl}(α). Define a matrix A′ by E(I −A) = I −A′; this gives a positive row operation taking I − A to I − A′, and the number of nonzero entries in A′(0) is one less than in A(0). After applying a finite sequence of such moves to remove all nonzero constant terms of A, we arrive at a matrix C(t) such that C(0) = 0.

We next produce a zero-one matrix D and a path of positive row and column operations from I − tD to I − C. Suppose t^{n} ≤ C_{pq} with n > 1; for concreteness, let n = 3 (which is essentially the general case). In the graph C^{♭}, there is a corresponding route

[figure: p; q]
t^{3}

Let r, s be distinct indices for which C has zero rows and zero columns. We will produce a path of positive row and column operations to C from a matrix C′′ whose graph (C′′)^{♭} agrees with the graph C^{♭} except that the route above is replaced by the path

[figure: p; t; r; t; s; t; q]

Claim 4.14. There is a matrix C′′ as described above and a path of positive row and column operations over Z^{+}[t] from I − C′′ to I − C.

Proof of (4.14). There are two cases depending on whether p ≠ q or p = q.

Case 1: p ≠ q . Write the vertices of C′′ in the order p, r, s, q followed by the other vertices. Then I − C′′ has the form

I − C′′ = ( \begin{matrix}1 − a(t) & −t & 0 & −b(t) & ∗ \\ 0 & 1 & −t & 0 & 0 \\ 0 & 0 & 1 & −t & 0 \\ −c(t) & 0 & 0 & 1 − d(t) & ∗ \\ ∗ & 0 & 0 & ∗ & ∗ \end{matrix} )

where the last row and column indicate the remaining portion of I − C′′ (which agrees with I − C). Then I − C has the form

I − C = ( \begin{matrix}1 − a(t) & 0 & 0 & −b(t) − t^{3} & ∗ \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ −c(t) & 0 & 0 & 1 − d(t) & ∗ \\ ∗ & 0 & 0 & ∗ & ∗ \end{matrix} ) .

A sequence of positive row and column operations from I − C′′ to I − C is (from left to right)

R_{sq}(t) , R_{rs}(t) , R_{rq}(t^{2}) , L_{pr}(t) , L_{ps}(t^{2}) .

Case 2: p = q . Write the vertices of C in the order p, r, s followed by the other vertices. We have the forms

I − C′′ = ( \begin{matrix}1 − a(t) & −t & 0 & ∗ \\ 0 & 1 & −t & 0 \\ −t & 0 & 1 & 0 \\ ∗ & 0 & 0 & ∗ \end{matrix} ) , I − C = ( \begin{matrix}1 − a(t) − t^{3} & 0 & 0 & ∗ \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ ∗ & 0 & 0 & ∗ \end{matrix} ) .

A sequence of positive row and column operations from I − C′ to I − C is (from left to right)

R_{rs}(t) , L_{pr}(t) , L_{ps}(t^{2}) , R_{sp}(t) .

This finishes the proof of the Claim 4.14. □

Iterating the move provided by the Claim, we produce the required path of positive row and column operations from I − C to I − tD with D a zero one matrix. Because A^{#} and D are zero-one matrices which define topologically conjugate shifts of finite type, it follows from Proposition 4.2 that there is a path of positive row and column operations between them. Concatenating paths gives the required path from I − A to I − tA^{#}. □

Discussion of simple automorphisms 4.15.

Here is an example illustrating why the definition of simple automorphisms in (2.14) yields the same group as Nasu’s original definition in [N]. Consider a portion of A^{♭} which has m power term routes of length two going from the primary vertex p to the primary vertex q as in the following diagram.

(4.16)  [figure: p; q]
mt^{2}

Any permutation α of these m routes determines a permutation β of the m routes of length one from the primary vertex r to the primary vertex q in the diagram below.

(4.17)  [figure: p; t; r; mt; q]

Observe that β gives a simple automorphism in the sense of [N]. Let B^{♭} be the graph obtained from A^{♭} by replacing (4.16) with (4.17). The conjugacy from (P (B), σ(B)) to (P (A), σ(A)) intertwining α and β is L_{pr}(t) followed by R_{rq}(mt). This procedure is called zipping.

5. Zeta Functions and Dimension Modules

This section generalizes the material in [KRW] on zeta functions and dimension modules to shifts of finite type built from nonnegative polynomial matrices A with finite support satisfying NZC.

The Zeta Function

We define the zeta function of (X(A), σ(A)) to be

(5.1)  ζ_{A}(t) = ζ_{A^{#}}(t) .

By Proposition 4.3 and the formulas in (3.2), we know that

(5.2)  det(I − tA^{#}) = det(I − A) .

Consequently

(5.3)  det(tI − A^{#}) = t^{v}det(I − A(t^{−1}))

where the matrix A^{#} is v × v and where A(t^{−1}) is obtained from A by substituting t^{−1} for t. The Bowen-Lanford formula [Sm] for the zeta function yields

(5.4)  ζ_{A}(t) = \frac{1}{det(I − A)}

and we also have

(5.5)  Entropy of (X(A), σ(A)) = log(λ_{A})

where λ_{A} is the largest root of t^{v}det(I − A(t^{−1})).

The Dimension Module

We will present the dimension module (G(A), G^{+}(A), s(A)) of (X(A), σ(A)) as an ordered Z[t, t^{−1}] module, and then show in (5.16) that this matches the usual definition of the dimension triple of {X_{A^{#}}, σ_{A^{#}}}. Let n denote a positive integer. Let F^{n} be the standard free, left Z[t]-module of rank n. Let F^{∞} denote the free, left Z[t]-module which is the direct sum of countably many copies of Z[t]. Elements of F^{n} and F^{∞} will be written as row vectors. Define

(5.6)  G(A) = Coker(I − A) = F^{∞}/Image(I − A) .

Let n ≥ supp(A). The inclusion F^{n} ⊂ F^{∞} induces an isomorphism

(5.7)  F^{n}/Image(I(n, n) − A(n, n)) = F^{∞}/Image(I − A)

where, as in the Appendix, I(n, n) and A(n, n) are the finite n×n-matrices obtained by considering just the first n rows and columns of I and A. Therefore, G(A) is a finitely generated Z[t]-module.

The action of t on G(A) is invertible. To see this, pick n large enough that (by the NZC condition) the matrix A^{n} has no constant term, and set C = (1/t)A^{n}; then for every [v] in Coker(I − A) we have

[v] − (t[v])C = [v(I − tC)] = [v(I − A^{n})] = [v(I − A)(I + A + ⋯ + A^{n−1})] = [0]

so C gives the required inverse. Consequently, we may (and from here do) regard G(A) as a Z[t, t^{−1}] module. Then we define

(5.8)  s(A) = the endomorphism of the Z[t, t^{−1}]-module G(A) coming from multiplication by t^{−1}.

Let F_{+}^{∞} denote the subset of F^{∞} consisting of elements that have all coordinates nonnegative. Define

(5.9)  G^{+}(A) = Image of F_{+}^{∞} in G(A) .

Let X be a polynomial matrix of finite support and assume there is a permutation matrix P such that P XP^{−1} is upper triangular with diagonal entries equal to zero. The matrix I + X is invertible over Z[t]. Let A be a polynomial matrix of finite support. As in (3.5), define the matrix B by one of the equations

(5.10)  \begin{aligned}I − B & = & (I + X)(I − A) \\ I − B & = & (I − A)(I + X) \end{aligned}

Corresponding to the first and second equations respectively, we have two commutative diagrams of exact sequences of left Z[t, t^{−1}]-modules which induce isomorphisms of Z[t, t^{−1}] modules. The first diagram is

(5.11)  \xymatrix{0 \ar[r] & F^{∞} \ar[r]_{I−A} & F^{∞} \ar[r]_{π_{A}} & G(A) \ar[r] & 0 \\ 0 \ar[r] & F^{∞} \ar[r]_{I−B} \ar[u]_{I+X} & F^{∞} \ar[r]_{π_{B}} \ar[u]^{I} & G(B) \ar[r] \ar[u]_{I} & 0}

In this case, G(A) = G(B) and the induced isomorphism of Z[t, t^{−1}] modules is the identity. The second diagram is

(5.12)  \xymatrix{0 \ar[r] & F^{∞} \ar[r]_{I−A} \ar[d]_{I} & F^{∞} \ar[r]_{π_{A}} \ar[d]_{I+X} & G(A) \ar[r] \ar[d]^{g(X)} & 0 \\ 0 \ar[r] & F^{∞} \ar[r]_{I−B} & F^{∞} \ar[r]_{π_{B}} & G(B) \ar[r] & 0}

which yields the isomorphism of Z[t, t^{−1}] modules

(5.13)  g(X) : G(A) → G(B)

Proposition 5.14. Assume A is a nonnegative polynomial matrix satisfying NZC. If 0 ≤ X ≤ A and X^{2} = 0, then

g(X) : (G(A), G^{+}(A), s(A)) → (G(B), G^{+}(B), s(B))

is an isomorphism of dimension modules.

Proof. Since X ≥ 0 we know that I + X takes F_{+}^{∞} into F_{+}^{∞}. Therefore, g(X) takes G^{+}(A) into G^{+}(B). It is injective, because g(X) is an isomorphism. It remains to verify that g(X) takes G^{+}(A) onto G^{+}(B). The condition X^{2} = 0 yields the matrix equation

I = (A − X)(I + X) + (I − A)(I + X) = (A − X)(I + X) + (I − B) .

So modulo Image(I − B) we see that any element w of G^{+}(B) is of the form

w = v(I + X)

where v = w(A − X) lies in F_{+}^{∞} because A − X ≥ 0.

□

Remark 5.15. We defined the dimension module of A as the ordered Z[t, t^{−1}] module coker(I−A) from the action of I − A on F^{∞}, where F = Z[t]. Using instead F = Z[t, t^{−1}] would produce an isomorphic module, with isomorphism induced by the inclusion Z[t] ↪ Z[t, t^{−1}].

If M is an n × n matrix over Z^{+}, let (G_{M}, G_{M}^{+}, s_{M}) denote the usual dimension group triple defined by direct limits. Recall, as a set G_{M} = {[(v, k)] : v ∈ Z^{n}, k ∈ N}, with [(v, i)] = [(w, j)] iff vA^{j+k} = wA^{i+k} for some k > 0; G_{M}^{+} = {[v] ∈ G_{M} : v ≥ 0}; and s_{M} : [v] ↦ [vM].

Proposition 5.16. Assume A is a nonnegative polynomial matrix satisfying NZC. There is an isomorphism of triples

(G(A), G^{+}(A), s(A)) = (G_{A^{#}}, G_{A^{#}}^{+}, s_{A^{#}}) .

Proof. As in [KRW] or [LM], the rule [t^{k}v] ↦ [(v, k)] defines an isomorphism

(G(tA^{#}), G^{+}(tA^{#}), s(tA^{#})) → (G_{A^{#}}, G_{A^{#}}^{+}, s_{A^{#}}) .

The result now follows from (5.14) and (4.3). □

An irreducible component of a directed graph G is a subgraph H such that any two vertices i and j in H may be joined by a directed path from i to j using edges in H and, moreover, H is contained in no larger subgraph with this property.

Corollary 5.17. Let A and B be nonnegative polynomial matrices satisfying NZC. Then the following conditions are equivalent:

(G): There is an isomorphism between the Z[t, t^{−1}]-modules G(A) and G(B).

(E): There is a sequence of row and column operations over Z[t] connecting I −A and I −B. If, in addition, the graphs A^{♭} and B^{♭} each have one just one irreducible component, and this component is primitive, then both (G) and (E) are equivalent to

(G^{+}): There is an isomorphism between the dimension module triples (G(A), G^{+}(A), s(A)) and (G(B), G^{+}(B), s(B)).

Proof. That condition (E) implies (G) comes from (5.13). We now show that (G) implies (E). From (5.16) we know that (G) implies there is an isomorphism (G_{A^{#}}, s_{A^{#}}) ≃ (G_{B^{#}}, s_{B^{#}}). The proof of Krieger’s result [LM,7.5.8] shows that A^{#} and B^{#} are shift equivalent over Z. Effros and Williams showed this implies A^{#} and B^{#} are strong shift equivalent over Z. See [W3]. The PSSE show that I − tA^{#} and I − tB^{#} are connected by row and column operations over Z[t]. Therefore, so are I − A and I − B by (4.3).

Clearly (G^{+}) implies (G). We want to show (G) implies (G^{+}) under the assumption that A^{♭} and B^{♭} each have just one irreducible component, which is primitive. This property is respected by positive elmentary row and column operations, so by Prop. 4.3 it is inherited by the graphs (A^{#})^{♭} and (B^{#})^{♭}. From (5.16) we know that there are isomorphisms of dimension module triples

(G(M), G^{+}(M), s(M)) ≃ (G_{M^{#}}, G_{M^{#}}^{+}, s_{M^{#}}) ≃ (G_{M_{nd}^{#}}, G_{M_{nd}^{#}}^{+}, s_{M_{nd}^{#}})

for M = A and M = B where, as in the Appendix, M_{nd}^{#} is a nondegenerate zero-one matrix connected to M^{#} by a path of strong shift equivalences in RS(ZO). Since A(0) = B(0) = 0, the graphs A^{#} and B^{#} come from A^{♭} and B^{♭} by considering all vertices to be primary. Therefore the graphs A_{nd}^{#} and B_{nd}^{#} are primitive. For primitive matrices P and Q, it is well known [LM] that isomorphism of (G_{P} , s_{P}) and (G_{Q}, s_{Q}) implies isomorphism of (G_{P} , G_{P}^{+}, s_{P}) and (G_{Q}, G_{Q}^{+}, s_{Q}).

□

6. Classification

This section summarizes the discussion of conjugacy and eventual conjugacy [LM] in terms of row and column operations on polynomial matrices of finite support.

Theorem 6.1. Let A and B be nonnegative polynomial matrices satisfying NZC. There is a conjugacy between (X(A), σ(A)) and (X(B), σ(B)) iff there is a path of positive row and column operations over Z^{+}[t] connecting I − A and I − B.

Theorem 6.2. Let A and B be nonnegative polynomial matrices satisfying NZC. Assume the graphs A^{♭} and B^{♭} each have just one irreducible component, which is primitive. There is an eventual conjugacy between (X(A), σ(A)) and (X(B), σ(B)) iff there is a path of row and column operations over Z[t] connecting I − A and I − B.

Examples 6.3. Here are examples of (6.1) for the matrices

A = ( \begin{matrix}t & 1 \\ t & 0 \end{matrix} ) , B = ( \begin{matrix}t & t \\ 1 & 0 \end{matrix} ) , C = ( \begin{matrix}2t & 0 \\ 0 & 0 \end{matrix} ) , D = ( \begin{matrix}t & t \\ t & t \end{matrix} ) .

All these give the shifts conjugate to (X_{2}, σ_{2}) which comes from the matrix C. The matrix I − C is obtained from I − A by first multiplying on the left by E_{12}(1) and then on the right by E_{21}(t). The matrix I − C is obtained from I − B by first multiplying on the left by E_{12}(t) and then on the right by E_{21}(1). The matrix I − D is obtained from I − A by multiplying on the right by E_{12}(1).

Remark 6.4. If we presented shifts of finite type only by matrices over tZ^{+}[t] (as in [KRW]), then it would be impossible to produce a path of elementary positive equivalences from I − C to I − D, with C, D as in (6.3) above. This motivates the presentation of shifts of finite type by matrices over Z^{+}[t] satisfying NZC.

Let A and B be nonnegative integral matrices of finite support. Recall from [LM] the following well known facts: (X_{A}, σ_{A}) and (X_{B}, σ_{B}) are conjugate iff A and B are strong shift equivalent over Z^{+}; (X_{A}, σ_{A}) and (X_{B}, σ_{B}) are eventually conjugate iff the matrices A and B are shift equivalent over Z^{+}; primitive matrices A and B are shift equivalent over Z^{+} iff they are strong shift equivalent over Z. Parallel to (6.1) and (6.2) we have the following results.

Theorem 6.5. Let A and B be nonnegative integral matrices. Then A and B are strong shift equivalent over Z^{+} iff there is a path of positive row and column operations over Z^{+}[t] connecting I − tA and I − tB.

Theorem 6.6. Assume A and B are integral matrices. Then A and B are strong shift equivalent over Z iff there is a path of row and column operations over Z[t] connecting I − tA and I − tB.

Proof of (6.1). This is really just a combination of the results (3.3) and (4.1). □

Proof of (6.2). If there is a path of row and column operations over Z[t] connecting I − A and I − B, then the dimension modules G(A) and G(B) are isomorphic. Acccording to (5.16) and (5.17) this implies there is an isomorphism between the dimension module triples (G_{A^{#}}, G_{A^{#}}^{+}, s_{A^{#}}) and (G_{B^{#}}, G_{B^{#}}^{+}, s_{B^{#}}). Therefore, we have an eventual conjugacy between (X(A), σ(A)) and (X(B), σ(B)). Conversely, if (X(A), σ(A)) and (X(B), σ(B)) are eventually conjugate, then there is an isomorphism of dimension module triples (G_{A^{#}}, G_{A^{#}}^{+}, s_{A^{#}}) and (G_{B^{#}}, G_{B^{#}}^{+}, s_{B^{#}}). Using (5.16) and (5.17) , we conclude there is a sequence of row and column operations over Z[t] connecting I − A and I − B. □

Proof of (6.5). This is a special case of (6.1), because {tA}^{#} = A′ and because there is the subdivision strong shift equivalence (R_{A}, S_{A}) : A → A′ as in (2.1) of [W4]. See the Appendix. □

Proof of (6.6). This just like the proof in (5.17). If I − tA and I − tB are connected by row and column operations, then (G(tA), s(tA)) = (G_{A}, s_{A}) and (G(tB), s(tB)) = (G_{B}, s_{B}) are isomorphic. Conversely if the dimension groups are isomorphic, A and B are strong shift equivalent over Z. The PSSE show that I − tA and I − tB are connected by row and column operations over Z[t]. □

7. The Integral Group Ring Setting

Much of the material in the previous sections can be developed when Z^{+} is replaced by Z^{+}[G] where G is a group. For simplicity we just state the Z^{+}[G] version of the main algebraic classification theorem. This has various applications and interpretations depending on the choice of G; for example, classifying free G actions on shifts of finite type when G is finite or classifying Markov chains when G is free abelian. See [B2, BS, MT, P].

Let Λ = Z[G]. Let μ = ∑ μ_{g}g and ν = ∑ ν_{g}g. Define μ ≤ ν iff μ_{g} ≤ ν_{g} for all g. Define Λ^{+} = Z^{+}[G] to be those μ = ∑ μ_{g}g where μ ≥ 0, i.e., μ_{g} ≥ 0 for all g. Let A = {A_{ij}} be a matrix of finite support with entries A_{ij} in Λ^{+}[t]. Assume A satisfies the no Z-cycles condition (NZC). This means that

(7.1)  The matrix |A| obtained by letting t = 0 and each g = 1 has no cycles.

The first step is to define the weighted graph A^{♭} . Consider the matrix entry A_{ij}. This is a sum of terms of the form gt^{p} where g is a group element in G and p ≥ 0. If p = 0, place a dotted arc from the primary vertex i to the primary vertex j and give it the weight g. If p ≥ 1, place a solid route from i to j consisting of p subarcs. Give the first arc the weight g and give the remaining arcs the weight e, the identity element in the group G. To obtain the matrix A^{#} with entries in Λ^{+}, we let the set S^{#} of states be quintuples

α = (i, α′, j, α′′, k)

as before in (2.6) , but now in addition the consecutive arcs α1^{′}, …, αr^{′}in α′ and the arc α′′ in A^{♭} have weights. Choose an ordering of S^{#}. Let β = (p, β′, q, β′′, r) be another state. We then define

A^{#} : S^{#} × S^{#} → G

as follows:

Case 1A. We have i = p, j = q, k = r, and α′ = β′. The arc α′′ is the first one along the power term route from j to k and β′′ is the second arc from j to k.

A^{#}(α, β) = {∏_{s} weight(αs^{′})}weight(α′′)

Case 1B. We have i = p, j = q, k = r, and α′ = β′. The arc α′′ is at least the second arc along the power term route from j to k and β′′ is the arc from j to k which follows α′′ .

A^{#}(α, β) = e

Case 2A. The subarc α′′ is the only arc along a power term route from j to k and has ending vertex k. We require k = p, and we require that the subarc β′′ be the first one along a power term route from q to r. In particular, the beginning vertex of β′′ is q.

A^{#}(α, β) = {∏_{s} weight(αs^{′})}weight(α′′)

Case 2B. The arc α′′ is the last one along a power term route from j to k which has length at least two, and the ending vertex of α′′ is k. We require k = p, and we require that the subarc β′′ be the first one along a power term route from q to r. In particular, the beginning vertex of β′′ is q.

A^{#}(α, β) = e

Case 3. Otherwise A^{#}(α, β) = 0.

Algebraic Classification Theorem 7.2. Assume A and B are matrices over Λ^{+}[t] with finite support which satisfy NZC. Then I − A and I − B can be connected by positive row and column operations over Λ^{+}[t] iff A^{#} and B^{#} are strong shift equivalent over Λ^{+}.

The proof that SSE implies I − A and I − B can be connected by positive row and column operations over Λ^{+}[t] comes directly from the PSSE. The proof in the opposite direction comes by showing that state splittings and mergings in the construction of L_{kl}(b) and R_{kl}(b) give rise to corresponding strong shift equivalences over Λ^{+}.

Appendix A. Appendix

The purpose of this section is to clarify a certain nondegeneracy condition which has appeared in earlier discussions of shifts of finite type and their automorphisms in the context of strong shift equivalence theory. The main reason for this is that relaxing the nondegeneracy condition gives algebraic flexibility which is necessary for relating strong shift equivalence theory to the positive row and column operation approach to shifts of finite type and their automorphisms which is developed in this paper.

Let P = (P_{ij}) be a zero-one matrix of finite support where the indices i and j run through the positive integers. This means that P_{ij} ≠ 0 for at most finitely many pairs of indices (i, j). The support of P is the least integer n = supp(P) such that P_{ij} = 0 if i > n or j > n. If P = 0, we let supp(P) = 1. Any finite n × n matrix will be considered as an infinite matrix of support less than or equal to n by appending identically zero rows and columns to it. As in [LM], construct the shift of finite type {X_{P} , σ_{P} } from P as follows:

(A.1)  X_{P}  =  \left\{{bi-infinite sequences x = \{x_{k}\} where \atop P (x_{k}, x_{k+1}) = 1 for −∞ < k < ∞.}\right\}

If i is a state ( i.e., a positive integer) such that the i^{th} row or the i^{th} column is zero, then i does not appear as a symbol x_{k} in any x in X_{P}. The shift map σ_{P} : X_{P} → X_{P} is defined by σ_{P} (x) = y where y_{k} = x_{k+1}. X_{P} has the product topology which makes it a Cantor set and σ_{P} is the shift homeomorphism. {X_{P} , σ_{P} } is the vertex shift associated to P. More generally, if P is a matrix over Z^{+}, then there is the edge path shift of finite type (X_{P} , σ_{P}) associated to P by the formula

(A.2)  (X_{P} , σ_{P}) = {X_{P′} , σ_{P′} }

where P′ is the zero-one matrix of the edge path presentation of the directed graph arising from P as in [LM]. Namely, the states are the arcs in the directed graph associated to P, and P′(α, β) = 1 iff the end vertex of α is the start vertex of β. Strictly speaking, an order of the arcs is chosen as well to get the matrix P′. If another order is chosen, corresponding new P′ will be conjugate to the first one by a permutation, and the resulting vertex shifts will be topologically conjugate. If P is a zero-one matrix, there is a topological conjugacy between {X_{P} , σ_{P} } and {X_{P′} , σ_{P′} }. See the discussion of subdivision below.

Let Q be a zero-one matrix of finite support. A strong shift equivalence (R, S) : P → Q in the category ZO of zero-one matrices with finite support is a zero-one matrix R of finite support and zero-one matrix S of finite support satisfying the strong shift equivalence equations

(A.3)  P = RS and Q = SR .

This data produces a conjugacy

(A.4)  c(R, S) : {X_{P} , σ_{P} } → {X_{Q}, σ_{Q}}

in the following way . Let x = {x_{k}} be in X_{P}, and let y = {y_{k}} in X_{Q} be the image of x under c(R, S). We know that

1 = A(x_{k}, x_{k+1}) = ∑_{p} R(x_{k}, p)S(p, x_{k+1}) .

Since the matrices A, R, and S are zero-one, there is exactly one p for which R(x_{k}, p)S(p, x_{k+1}) = 1. We set

(A.5)  y_{k} = p .

A strong shift equivalence (R, S) : P → Q of matrices with finite support over Z^{+} is defined similarly and induces a conjugacy

(A.6)  c(R, S) : (X_{P} , σ_{P}) → (X_{Q}, σ_{Q})

which is well defined up to simple automorphisms. See [W4, Section 2].

Now as in [W2,W4] construct the spaces RS(ZO) and RS(Z^{+}) of strong shift equivalences for zero-one or Z^{+} matrices with finite support. We then have the following two versions of R.F. Williams’ results in strong shift equivalence theory.

Theorem A.7. Up to topological conjugacy shifts of finite type are in one-to-one correspondence with the path components of π_{0}(RS(ZO)) of RS(ZO). The inclusion RS(ZO) ⊂ RS(Z^{+}) induces a bijection of path components π_{0}(RS(ZO)) = π_{0}(RS(Z^{+})).

Theorem A.8. Let A and B be zero-one matrices. Any topological conjugacy α : {X_{A}, σ_{A}} → {X_{B}, σ_{B}} can be written as a composition

α = ∏_{i} c(R_{i}, S_{i})^{ϵ_{i}}

corresponding to a path of strong shift equivalences connecting A and B in RS(ZO).

We will give proofs for these theorems below. The point of these theorems is to eliminate the following nondegeneracy condition which has often been tacitly and/or explicitly assumed in the literature. Let X = {X_{ij}} be a matrix with finite support. Let X(m, n) be the finite m × n matrix obtained by considering the first m rows and the first n columns of X. We say X is an m × n matrix provided

(A.9)  X_{ij} = 0 if i > m or j > n

and we say an m × n matrix X is nondegenerate provided

(A.10)  no row or column of X(m, n) is entirely zero.

Let RS_{nd}(ZO) and RS_{nd}(Z^{+}) denote the subspaces of RS(ZO) and RS(Z^{+}) formed by taking vertices to be nondegenerate m × m matrices P and edges (R, S) : P → Q between a nondegenerate m × m matrix P and a nondegenerate n × n matrix Q to be a nondegenerate m × n matrix R and a nondegenerate n × m matrix S satisfying the strong shift equivalence equations (A.3). The nondegeneracy condition we are referring to is that Theorem A.7 and Theorem A.8 are usually stated with RS_{nd}(ZO) and RS_{nd}(Z^{+}) instead of RS(ZO) and RS(Z^{+}). The technical reason for this is the requirement that all atoms of a Markov partition are assumed to be nonempty sets. See [W1,W2,W4,BW].

Proposition A.11. Let A ≠ 0 be a zero-one or Z^{+} matrix of finite support. Then there is a path in RS(ZO), respectively RS(Z^{+}), from A to some nondegenerate matrix A_{nd}.

The proof of Proposition A.11 follows immediately from repeated application of Lemma A.12, for which we need two definitions. If P is an m×m matrix such that P (m, m) is invertible, then we let P^{−1} denote the m × m matrix such that P^{−1}(m, m) = P (m, m)^{−1}. If X is an m × m matrix, then we say X is trimmable provided there is a row or column of X(m, m) which is entirely zero.

Lemma A.12. Assume X is a trimmable m × m zero-one or Z^{+} matrix which is not identically zero. There is an m × m permutation matrix P and a two step path of strong shift equivalences

\begin{matrix}(P, P^{−1}X) : X → P^{−1}XP \\ (R, S) : P^{−1}XP → Y \end{matrix}

in RS(ZO) or RS(Z^{+}) respectively where Y is an n × n matrix with n < m.

Proof of A.12. We give the proof for the case when X(m, m) has a zero column. The argument when it has a zero row is similar. Let P be an m × m matrix such that P (m, m) is a permutation matrix and the last column of P^{−1}XP is zero. Let n = m − 1 and write

P^{−1}XP = ( \begin{matrix}Y & 0 \\ U & 0 \end{matrix} )

where Y is a n × n matrix and U is a 1 × n matrix. Define the m × n matrix R and the n × m matrix S to be

R = ( \begin{matrix}Y \\ U \end{matrix} )  S = ( I 0 )

where I is the n × n identity matrix. Then we have the strong shift equivalence equations

P^{−1}XP = RS and Y = SR .
□

Proof of (A.7). One result in R.F.Williams’ paper [Wi] as formulated in [W2] is that the isomorphism classes of shifts of finite type are in one-to-one correspondence with the path components of π_{0}(RS_{nd}(ZO)). So the first step in proving (A.7) is to show that

π_{0}(RS_{nd}(ZO)) → π_{0}(RS(ZO))

is a bijection. Proposition A.11 shows this map is onto. To show this is one-to-one, suppose there is a path Γ of strong shift equivalences in RS(ZO) connecting the nondegenerate m × m matrix A to the nondegenerate n × n matrix B. The construction (A.4) above yields a topological conjugacy α : (X_{A}, σ_{A}) → (X_{B}, σ_{B}). Then Williams’ work as formulated in [W2] says that α arises from a path Γ_{nd} in RS_{nd}(ZO) connecting A and B. To verify the last statement of (A.7), observe that the proof in [W4] showing π_{0}(RS_{nd}(ZO)) = π_{0}(RS_{nd}(Z^{+})) also shows π_{0}(RS(ZO)) = π_{0}(RS(Z^{+})).

□

Proof of (A.8). Let α : {X_{A}, σ_{A}} → {X_{B}, σ_{B}} be an isomorphism where A and B are zero-one matrices with finite support. Use Proposition A.11 to find paths Γ_{A} and Γ_{B} in RS(ZO) from A and B to nondegenerate matrices A_{nd} and B_{nd} respectively. Let θ_{A} : {X_{A}, σ_{A}} → {X_{A_{nd}}, σ_{A_{nd}}} denote the conjugacy which is the product of the conjugacies c(R, S)^{±1} corresponding to the edges in Γ_{A}. Similarly, let θ_{B} : {X_{B}, σ_{B}} → {X_{B_{nd}}, σ_{B_{nd}}} denote the conjugacy which is the product of the conjugacies c(R, S)^{±1} corresponding to the edges in Γ_{B}. Then, reading composition from left to right,

α = θ_{A}(θ_{A}^{−1}αθ_{B})θ_{B}^{−1} .

By the version of (A.8) using RS_{nd}(ZO), we know that the isomorphism

θ_{A}^{−1}αθ_{B} : {X_{A_{nd}}, σ_{A_{nd}}} → {X_{B_{nd}}, σ_{B_{nd}}}

is a product of conjugacies c(R, S)^{±1} corresponding to the edges in a path from A_{nd} to B_{nd} in RS_{nd}(ZO). □

While the argument for (A.7) does produce some path Γ_{nd}, connecting A and B in RS_{nd}(ZO), we have not shown that Γ is homotopic keeping endpoints fixed to a path in RS_{nd}(ZO). As explained in [W5] we know that

\begin{matrix}Aut(σ_{A}) = π_{1}(RS_{nd}(ZO), A) \\ Aut(σ_{A})/Simp(σ_{A}) = π_{1}(RS_{nd}(Z^{+}), A) \end{matrix}

Question 1 Are the natural homomorphisms

\begin{matrix}π_{1}(RS_{nd}(ZO), A) → π_{1}(RS(ZO), A) \\ π_{1}(RS_{nd}(Z^{+}), A) → π_{1}(RS(Z^{+}), A) \end{matrix}

isomorphisms ?

Question 2 Are the inclusions RS_{nd}(ZO) ⊂ RS(ZO) and RS_{nd}(Z^{+}) ⊂ RS(Z^{+}) homotopy equivalences ?

We end this Appendix with a discussion of subdivision which is needed in this paper. Let A be a zero-one matrix. There are two ways to associate a shift of finite type to A. The first is the vertex shift {X_{A}, σ_{A}} as given above. The second is the edge path construction {X_{A′} , σ_{A′} } as in [LM,W4]. In (2.1) of [W4] there is the subdivision strong shift equivalence (R_{A}, S_{A}) : A → A′ which induces the subdivision conjugacy sd_{A} : {X_{A}, σ_{A}} → {X_{A′} , σ_{A′} }. If (R, S) : A → B is a strong shift equivalence of zero-one matrices, the diagram (2.1) of [W4] produces a commutative diagram of conjugacies

(A.13)  \xymatrix{\{X_{A}, σ_{A}\} \ar[r]_{c(R,S)} \ar[d]_{sd_{A}} & \{X_{B}, σ_{B}\} \ar[d]_{sd_{B}} \\ \{X_{A′} , σ_{A′} \} \ar[r]_{c(R′ ,S′)} & \{X_{B′} , σ_{B′} \}}

The conjugacy c(R′, S′) is called the subdivision of c(R, S). In the category of zero-one matrices there is no ambiguity in c(R′, S′) because there is only one choice to be made in (2.5) of [W4]. An easy consequence of (A.13) is

Proposition A.14. Any conjugacy β : {X_{A′} , σ_{A′} } → {X_{B′} , σ_{B′} } is the subdivision of the conjugacy α : {X_{A}, σ_{A}} → {X_{B}, σ_{B}} where α = sd_{A}βsd_{B}^{−1} (reading composition from left to right). This means that if we write α = ∏_{i} c(R_{i}, S_{i})^{ϵ_{i}}, then β = ∏_{i} c(Ri^{′}, Si^{′})^{ϵ_{i}}

References

[B1] M.Boyle, Symbolic dynamics and matrices, in Combinatorial and Graph-theoretic Problems in Linear Algebra, IMA Volumes in Mathematics and Its Applications 50 (1993), editors R.A. Brualdi, S. Friendlander, and V. Klee, 1-38.

[B2] M. Boyle, Positive K-theory in symbolic dynamics, Dynamics and Randomness, editors A. Maass, S. Martinez, and J. San Martin, Kluwer, 2002, 31-52.

[BL] M.Boyle and D.Lind, Small polynomial matrix presentations of nonnegative matrices , Linear Algebra Applications 355 (2002), 49-70.

[BS] M.Boyle and M. Sullivan, Equivariant flow equivalence for shifts of finite type, in preparation.

[BW] L. Badoian and J.B.Wagoner, Simple connectivity of the Markov partition space, Pac. Jour. Math. 193 (2000), No.1, 1-3.

[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), No.4, 773-806.

[KR1] K.H.Kim and F.W.Roush, Free Z_{p} actions on subshifts, Pure Math. Appl. 8 (1997), 293-322.

[KR2] K.H.Kim and F.W.Roush, Williams’ conjecture is false for irreducible subshifts, Annals of Math(2) 149 (1999), No.2, 545-558.

[KRW] K.H.Kim, F.W.Roush, and J.B.Wagoner, Characterization of inert actions on periodic points, Part I and Part II, Forum Mathematicum 12 (2000), 565-602 and 671-712.

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

[M] B. Marcus, R. Roth, and P. Siegel, Constrained systems and coding for recording channels, Chapter 20, Volume II of Handbook of Coding Theory (ed., V.S. Pless and W. C. Huffman), Elsevier Press, 1998.

[MT] B. Marcus & S. Tuncel, The weight-per-symbol polytope and embeddings of Markov chains, Ergod. Th. & Dyn. Syst. 11 (1991), 129-180.

[N] M. Nasu, Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological Markov shifts, Springer Lecture Notes in Math 1342, 1988.

[P] W. Parry, Notes on coding problems for finite state processes, Bull. London Math. Soc. 23 (1991), No. 1, 1-33.

[Sh] C.Shannon, A mathematical theory of communication, Bell Sys.Tech Jour., 27,1948, 379-423, reprinted by University of Illinois Press,1963.

[Sm] S.Smale, Differentiable Dynamical Systems, Bull. Amer. Math. Soc. 73 (1967), No.6, 747-847.

[W1] J.B.Wagoner, Markov partitions and K_{2}, Publ. Math. IHES, No. 65 (1987), 91-129.

[W2] J.B.Wagoner, Triangle inequalities and symmetries of a subshift of finite type, Pacific J. Math. 144 (1990), 331-350.

[W3] J.B.Wagoner, Higher dimensional shift equivalence is the same as strong shift equivalence over the integers, Proc. Amer. Math. Soc. 109 (1990), 527-536.

[W4] J.B.Wagoner, Eventual finite order generation for the kernel of the dimension group representation , Trans. Amer. Math. Soc. 317 (1990), 331-350.

[W5] J.B.Wagoner, Strong shift equivalence theory and the shift equivalence problem, Bull. Amer. Math. Soc. 36 (1999), No.3, 271-296.

[W6] J.B.Wagoner, Strong Shift Equivalence Theory, preprint from UC Berkeley, to appear in Symbolic Dynamics, AMS Proceedings of Symposia in Applied Mathematics.

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

Department of Mathematics, University of Maryland, College Park, MD 20742-4015 E-mail address: mmb@math.umd.edu Home page: www.math.umd.edu/∼ mmb

Department of Mathematics, University of California, Berkeley, CA 94720

E-mail address: wagoner@math.berkeley.edu