EQUIVARIANT FLOW EQUIVALENCE FOR SHIFTS OF FINITE TYPE, BY MATRIX EQUIVALENCE OVER

GROUP RINGS

MIKE BOYLE AND MICHAEL C. SULLIVAN

Abstract. Let G be a finite group. We classify G-equivariant flow equivalence of nontrivial irreducible shifts of finite type in terms of (i) elementary equivalence of matrices over ℤG and (ii) the conjugacy class in ℤG of the group of G-weights of cycles based at a fixed vertex. In the case G = ℤ/2, we have the classification for twistwise flow equivalence. We include some algebraic results and examples related to the determination of E(ℤG) equivalence, which involves K_{1}(ℤG).

Contents

1. Introduction 1 2. G-flow equivalence and SFTs 3 3. Positive equivalence 9 4. The weight class 12 5. Equivalence through very positive matrices 15 6. The main results 21 7. Twistwise flow equivalence 25 8. E(ℤG)-equivalence 27 9. E(ℤG)-equivalence of injective matrices 32 References 36

1. Introduction

Let G denote a finite group. In this paper, by a G shift of finite type (G-SFT) we will mean an SFT together with a continuous Gaction which commutes with the shift, where in addition the action is

Date: December 1, 2004. 2000 Mathematics Subject Classification. Primary: 37B10; Secondary: 15A21,

15A23, 15A33, 15A48, 19B28, 19M05, 20C05, 37D20, 37C80.

Key words and phrases. flow equivalence, shift of finite type, skew product, equivariant, K-theory, matrix equivalence, group ring, Smale flows, Markov.

free and the SFT is irreducible and is nontrivial (contains more than one orbit). We will classify these systems up to G-flow equivalence. This equivalence relation can be described in terms of G-SFTs, skew products or suspension flows (Sec 2). For example, two G-SFTs are G-flow equivalent if and only if there exists an orientation preserving homeomorphism between their mapping tori which commutes with the induced G actions.

A G-SFT can be presented by a finite square matrix A over ℤ_{+}G, the positive cone of the integral group ring ℤG [30]. Let (I − A)_{∞} denote the ℕ × ℕ matrix whose upper left corner is I − A and which otherwise equals the infinite identity matrix. Let E(ℤG) be the group of ℕ × ℕ matrices generated by basic elementary matrices (those which differ from I in at most one entry, which must be off-diagonal) over ℤG. Let W (A) denote the weight class of A (4.1): the conjugacy class in G of the group of weights of loops based at a fixed vertex. We show the weight class is an invariant of G-flow equivalence. When W (A) = W (B) = G, we will show that G-SFTs presented by matrices A and B are G-flow equivalent if and only if there are matrices U, V in E(ℤG) such that U(I − A)_{∞}V = (I − B)_{∞} (Thm. 6.1). The complete classification up to G-flow equivalence, which allows the possibility W (A) ⫋ G, has a more complicated statement (Thm. 6.4).

In the case that G is trivial, our classification reduces to the familiar classification of Franks [15] by cokernel group and determinant. When G is nontrivial, the classification up to E(ℤG) is much more difficult and interesting, and remains an open problem. We consider these algebraic issues in Sections 8 and 9. In Section 8, we give the modest requisite K-theory terminology and background, and for the case G = ℤ/2 we give a constructive partial result (Theorem 8.1) and some very concrete illustrative examples (8.6, 8.7) which indicate how the ℤG equivalence problem becomes more difficult when G is nontrivial (i.e. ℤG ≠ ℤ). In Section 9, we consider E(ℤG) equivalence of injective matrices. In this case, GL(ℤG) equivalence amounts to isomorphism of cokernel modules, and the refinement to E(ℤG) equivalence is classified by K_{1}(ℤG)/H for an associated subgroup H of SK_{1}(ℤG). As one consequence, if G is abelian and det(I − A) is not a zero divisor in ℤG, then det(I − A) determines the G-flow equivalence class up to finitely many possibilities (Theorem 6.5). Some of the algebra here works more generally and in particular has a consequence for invariants of SFTs with Markov measures (9.10,9.11).

Algebraic invariants over ℤ for isomorphism and flow equivalence of SFTs are paralleled by the algebraic invariants over ℤG for Gequivariant isomorphism and flow equivalence of G-SFTs. The first key step, classification of G-SFTs by strong shift equivalence over ℤ_{+}G of defining matrices, is due to Parry (Prop. 2.7.1). We use a systematic conversion [9, Thm. 7.2] from the realm of strong shift equivalence to the realm of “positive K-theory” to establish necessary matrix conditions for G-flow equivalence. We generalize existing positive Ktheory constructions [7] to establish sufficient conditions in the case W (A) = W (B) = G. To understand the reduction to this case, we draw on ideas of Holt, Parry and Schmidt [29, 31, 36].

Among motivations for studying G-SFTs, we mention three. First, there are two systematic frameworks for classifying systems related to SFTs: the ideas around strong shift equivalence growing out of Williams paper [42], and the ideas of positive K-theory growing out of the Kim-Roush-Wagoner papers [22]. (See [5, 6, 9].) The G-FE classification fills in another piece of both frameworks. Second, in the study of “symmetric chaos” [12], G-SFTs arise as important tools for the study of equivariant basic sets [11, 13], and can equal such sets. (We emphasize that we are not addressing the important but quite different case of nonfree actions.) Finally (and in fact our initial motivation), we are interested in twistwise flow equivalence, which arose [37, 38, 39] in the study of basic sets of Smale flows on 3-manifolds. Twistwise flow equivalence amounts to equivariant flow equivalence of G-SFTs with G = ℤ/2, so our results include a classification up to twistwise flow equivalence, along with constructive techniques resolving some open questions (Sec. 7).

We thank Bob Guralnick, Bob Fitzgerald, Bill Parry (especially, see 2.7.1 and 9.10), Jonathan Rosenberg (especially, see 9.7) and Klaus Schmidt for extremely helpful discussions. We are also grateful to the anonymous referee for many detailed comments which improved the exposition.

2. G-flow equivalence and SFTs

In this section we give background for flow equivalence, G-flows and G-SFTs.

2.1. Notational conventions. Except in part of Section 9, G denotes a finite group. All our G actions are assumed to be continuous (each g acts by a homeomorphism), from the right ((x, g) ↦ xg), and free (if g fixes any x then g is the identity in G). Here are other notations.

• Let x = ∑_{g∈G} n_{g}g be an element of ℤG. We define π_{h}(x) = x_{h} = n_{h} for each h ∈ G. If x_{g} > 0, we say g is a summand of x.

• For a and b in ℤG we say a ≫ b if π_{g}(a) > π_{g}(b) for each g ∈ G, and a > b if π_{g}(a) ≥ π_{g}(b) for each g ∈ G and π_{g}(a) > π_{g}(b) for at least one g ∈ G. We define ≪ and < similarly and extend these notations to matrices if they hold entry-by-entry.

• Let A be matrix over ℤG. We say A is very positive if A ≫ 0 and A is strictly positive if A > 0.

• The augmentation map α: ℤG → ℤ sends an element ∑ n_{g}g to ∑ n_{g}. Applying α entry-wise to a matrix A with entries in ℤG produces a matrix α(A) with entries in ℤ.

• In this paper, a ring means a ring with 1. Let R be a ring. Then E(R) has already been defined; E(n, R) is defined likewise, for n × n rather than ℕ × ℕ matrices. See the beginning of Section 8 for more.

2.2. Flows and sections. Let Y be a compact metrizable space. In this paper, a flow on Y will be an ℝ-action on Y, given by a continuous map γ: ℝ × Y → Y, where γ is locally injective (the flow has no rest points). Two flows are topologically conjugate, or conjugate, if there is a homeomorphism intertwining their ℝ-actions. Two flows are equivalent if there is a homeomorphism between their domains taking ℝ-orbits to ℝ-orbits and preserving orientation (i.e. respecting the direction of the flow).

A compact subset C of Y is a cross section of the flow if the restriction of γ to ℝ × C is a surjective local homeomorphism. (In this case, the return map to C is a well defined homeomorphism R : C → C; the return time r is a continuous function on C; and the given flow is topologically conjugate to the “flow under the function” built from R and r.) We say that R is a section to the flow. Two homeomorphisms are flow equivalent if they are topologically conjugate to sections of a common flow. (Homeomorphisms f, g are topologically conjugate if there is a homeomorphism h such that hf = gh.) Sections of two flows are flow equivalent if and only if the flows are equivalent.

In the case that T_{1} and T_{2} are homeomorphisms of zero dimensional compact metrizable spaces, Parry and Sullivan [32] showed that T_{1} and T_{2} are flow equivalent if and only if there is a third homeomorphism T such that there are discrete towers T′_{1} and T′_{2} over T which are topologically conjugate respectively to T_{1} and T_{2}. (A discrete tower is a homeomorphism (X′, T′) built from (X, T) by partitioning X into finitely many closed open sets C_{i}, picking for each i a positive integer n_{i}, making X′ the disjoint union of the sets C_{i} × {j}, 1 ≤ j ≤ n_{i}, and for x ∈ C_{i} setting T′(x, k) = (x, k + 1) when k < n_{i}, and T′(x, n_{i}) = (T x, 1). Here (X, T) is called the base of the tower.)

2.3. G-flows and G-sections. By a G-flow we mean a flow together with a continuous free right G-action which commutes with the flow (t(yg) = (ty)g). By a G-homeomorphism we mean a homeomorphism together with a continuous free right G-action with which it commutes. Two G-flows are G-conjugate if the flows are topologically conjugate by a map which intertwines the G-actions. Two G-flows are G-equivalent if the flows are equivalent by a map which intertwines the G-actions (f(xg) = (fx)g). A G-cross section to a G-flow is a cross section C which is G-invariant. Then there is an induced Gaction on C with which R becomes a G-homeomorphism, and we say the G-homeomorphism R is a G-section to the G-flow. A discrete G-tower (X′, T′) over a G-homeomorphism (X, T) is a discrete tower over (X, T), together with a G-action (x, j) ↦ (xg, j) (in the notation above) induced by the G action x ↦ xg for (X, T).

The standard theory carries over to the G setting. We call two Ghomeomorphisms G-flow equivalent if they are conjugate to G-sections of the same G-flow. G-sections of two G-flows are G-flow equivalent if and only if the flows are G-equivalent. In the case that T_{1} and T_{2} are G-homeomorphisms of zero dimensional compact metrizable spaces, T_{1} and T_{2} are G-flow equivalent if and only if there is a third Ghomeomorphism T such that there are discrete G-towers T′_{1} and T′_{2} over T which are G-conjugate respectively to T_{1} and T_{2}.

2.4. Skew products. Let T : X → X be a homeomorphism, with X zero dimensional. Let τ be a continuous map from X into the finite group G. Define a homeomorphism S: X × G → X × G by the rule (x, h) ↦ (T (x), τ(x)h). With the natural right G-action on X × G, g : (x, h) ↦ (x, hg), S is a G-homeomorphism. S is T ⋉_{τ} G, the skew product over T built from the skewing function τ.

Conversely, suppose S : X → X is a G-homeomorphism, with X zero dimensional. Let q : X → \overline{X} be the map onto the quotient space of G-orbits, and let T be the homeomorphism induced by S on \overline{X}. Because X is zero dimensional and the G action is free, we can find a closed open subset C of X such that {Cg: g ∈ G} is a partition of X. Using the homeomorphism q|C, identify \overline{X} with C. Using the maps Cg → C × G (xg ↦ (x, g)), identify X with C × G. In this notation, q is the standard projection C × G → C, and the G action on C × G is h: (x, g) ↦ (x, gh). To display the skew product structure, define τ: C → G by setting τ(x) = g if S(x) ∈ Cg. It follows for x ∈ C that S: (x, e) ↦ (T (x), τ(x)e). Because S commutes with the G action, we conclude that for any (x, g) we have S: (x, g) → (T (x), τ(x)g). So, up to G-conjugacy, every G-homeomorphism of a zero dimensional space is a skew product.

Finally, suppose we have a G-homeomorphism T. The given G-action induces a natural G action on the mapping torus Y of T, with respect to which the natural flow on Y is a G-flow, and T is conjugate to the obvious G-section of this flow.

2.5. Cocycles. Let T : X → X be a homeomorphism. We may regard a continuous skewing function τ: X → G as defining a cocycle for T. We say two such skewing functions τ and ρ are cohomologous if there is another continuous function h from X into G such that for all x in X, τ(x) = [h(x)]^{−1}ρ(x)h(T x). Such a function h is called a transfer function. It is an easy exercise to verify that two skew products T_{1} ⋉_{τ} G and T_{2} ⋉_{ρ} G are G-conjugate if and only if there is a topological conjugacy ϕ of T_{1} and T_{2} such that τ ∘ ϕ is cohomologous to ρ.

2.6. Shifts of finite type and matrices over ℤ_{+}. Here we give minimal background for shifts of finite type (SFTs). See the texts [23, 24] for an introduction to SFTs.

In this subsection, all matrices will be ℕ × ℕ with entries in ℤ_{+} and (except for the identity matrix I) with all but finitely many entries equal to zero. (In particular, det (I − A) is well defined as a limit of the determinants of the principal {1, 2, …, n}×{1, 2, …, n} submatrices.) Given such a matrix A, let G_{A} be the directed graph with vertex set ℕ and with exactly A(i, j) edges from i to j. Let E be the edge set and define Σ_{A} to be the subset of ℤ^{E} realized by bi-infinite paths in G_{A}. With the natural topology, Σ_{A} is a zero dimensional compact metrizable space. Let σ_{A} : Σ_{A} → Σ_{A} be the shift map, (σ_{A}(s))_{i} = s_{i+1}. The homeomorphism σ_{A} is the edge SFT induced by A. Every SFT is topologically conjugate to some edge SFT.

Matrices A and B over a semiring R are strong shift equivalent (SSE) over R if they are connected by a string of elementary moves of the following sort: there are R and S over R such that A = RS and B = SR. A fundamental result in symbolic dynamics is that σ_{A} is topologically conjugate to σ_{B} if and only if A is SSE over ℤ_{+} to B [42]. Refined computable invariants of SSE are known, but it is still not known even if SSE over ℤ_{+} is decidable.

If A = (A_{ij}) and

B = ( \begin{matrix}0 & A_{11} & ⋯ & A_{1n} \\ 1 & 0 & ⋯ & 0 \\ 0 & A_{21} & ⋯ & A_{2n} \\ ⋮ & ⋮ & & ⋮ \\ 0 & A_{n1} & ⋯ & A_{nn} \end{matrix} ) ,

then we say A and B are connected by a Parry-Sullivan move or a PS move.

It follows from the Parry-Sullivan result described above that SFTs σ_{A} and σ_{B} are flow equivalent if and only if the matrices A and B can be connected by SSE and Parry-Sullivan moves [32]. (The Parry-Sullivan moves allow for building the discrete towers.)

An SFT σ_{A} is irreducible if for any edges e and f which appear in points of Σ_{A}, there is a path in G_{A} beginning with e and ending with f. When σ_{A} and σ_{B} are irreducible and nontrivial (not just a single periodic orbit), they are flow equivalent if and only if the matrices I − A and I − B are SL(ℤ)-equivalent. This equivalence is determined by two simple invariants: the Parry-Sullivan number det(I − A) and the isomorphism class of the Bowen-Franks group cok(I −A) [32, 4, 15]. The Huang classification of reducible SFTs up to flow equivalence is much more complicated. (Huang’s original arguments are developed in [17, 18, 19, 20] and an almost complete unpublished manuscript, “The K-web invariant and flow equivalence of reducible shifts of finite type.” A complete alternate development is contained in [6, 8].) In this paper, we only address G-flow equivalence of irreducible SFTs.

2.7. Skew products, G-SFTs and matrices over ℤ_{+}G. By a G-SFT we mean an SFT together with a free G-action with which it commutes. (Usually “G-SFT” is not restricted to free actions [11, 12, 13]; we adopt the restriction only for this paper, where we only consider free actions.) In this subsection, we’ll consider presentations of G-SFTs.

Let A be an ℕ×ℕ matrix with entries in ℤ_{+}G and with all but finitely many entries equal to zero. Such a matrix A determines a weighted directed graph G_{A} as follows. As an unweighted graph, it is the graph G_{α(A)}. Recall α is the augmentation map (2.1). If A(i, j) = ∑ n_{g}g then exactly n_{g} of the edges from i to j are weighted g. Let ℓ(e) denote the weight on an edge e. Define a locally constant function τ_{A}: Σ_{α(A)} → G by the rule x ↦ ℓ(x_{0}). This function then defines a skew product over σ_{α(A)}. This skew product can be presented as an edge SFT with the graph G constructed as follows. Let the vertex set of G be the product of G and the vertex set of G_{α(A)}. For each edge e from i to j in G_{α(A)}, for each g in G draw an edge from (g, i) to (ℓ(e)g, j). We write S_{A} = σ_{α(A)} ⋉ τ_{A}. To make S_{A} a G-SFT, for each pair of vertices v, v′ of G, we choose an ordering of the edges from v to v′, and then let g in G act by the one block map given by the unique automorphism of G which acts on the vertex set G by (h, j) ↦ (hg, j) and which is order-preserving on edges.

It is not difficult to see that for any locally constant function into G from a SFT σ, there is a matrix A over ℤ_{+}G and a topological conjugacy from σ to σ_{α(A)} which takes the given function to τ_{A}, and therefore any G skew product over an SFT can be presented as some S_{A}. Moreover, a G-SFT can be presented as a skew product (Sec. 2.4– our assumption of freeness is necessary for this), and it is not difficult to see that the base map for this skew product must be SFT in order for the skew product to be SFT. Thus all G-SFTs are G-conjugate to those arising by this construction of S_{A}.

Proposition 2.7.1. [30] Let G be a finite group. The following are equivalent for matrices A and B over ℤ_{+}G and their associated skew product systems S_{A} and S_{B}.

(1) A and B are SSE over ℤ_{+}G.

(2) There is a topological conjugacy φ: σ_{α(A)} → σ_{α(B)} such that τ_{A} ∼ τ_{B} ∘ φ.

(3) The G-SFTs S_{A} and S_{B} are G-conjugate.

Proof. We will prove (2) ⟹ (1). As shown by Parry [28], the given conjugacy φ can be given as a string of state splittings from α(A) to some C followed by the reversal of a string of state splittings from α(B) to C. The SSE’s over ℤ_{+} which give the splittings are easily adapted to SSE’s over ℤ_{+}G which reflect the corresponding lifting of edge labelings (we give an example following the proof). In this way, we produce ℤ_{+}G matrices A′, B′ such that α(A′) = C = α(B′), the skewing functions derived from A′ and B′ are the functions lifted from the skewing functions defined from A and B, and they are cohomologous. If h is a continuous transfer function giving the cohomology of these functions, then in fact h(x) is determined by the initial vertex of x_{0} ([29, Lemma 9.1] proves this for irreducible SFTs, and the essential ideas of that proof can be extracted to prove the general case). Therefore there is a diagonal matrix D with D(i, i) = g_{i} ∈ G, such that DA′D^{−1} = B′. The ℤ_{+}G strong shift equivalence from A′ to DA′D^{−1} is given by the pair (A′D^{−1}, D). □

Above, in restricting to ℤG with G finite, we have not given the most general statement of Parry’s results.

Example 2.7.2. Here is the example promised in the preceding proof.

Let A = (\begin{matrix}g & h \\ j & k + ℓ \end{matrix}) over some ℤ_{+}G. Consider the row splitting of α(A) defined by the elementary SSE

α(A) = (\begin{matrix}1 & 1 \\ 1 & 2 \end{matrix}) = (\begin{matrix}1 & 0 & 1 \\ 0 & 1 & 2 \end{matrix}) (\begin{matrix}1 & 0 \\ 1 & 0 \\ 0 & 1 \end{matrix}) ,

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

Then the ℤ_{+}G SSE which captures the label lifting is simply

A = (\begin{matrix}g & h \\ j & k + ℓ \end{matrix}) = (\begin{matrix}g & 0 & h \\ 0 & j & k + ℓ \end{matrix}) (\begin{matrix}1 & 0 \\ 1 & 0 \\ 0 & 1 \end{matrix}) ,

(\begin{matrix}g & 0 & h \\ g & 0 & h \\ 0 & j & k + ℓ \end{matrix}) = (\begin{matrix}1 & 0 \\ 1 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix}g & 0 & h \\ 0 & j & k + ℓ \end{matrix}) .

Remark 2.7.3. The equivalence of (1) and (2) in Prop. 2.7.1, established by Parry following the related innovation of Parry and Tuncel for Markov chains [28, 33], is a key step to a proper algebraic approach to G-SFTs. Otherwise, the facts and constructions above are at most minor variations of well known results (see e.g. [13, Sec. 3.2],[11, 1, 28, 29]). We also remark that [21] gives a realization result for G-SFTs which employs the positive K-theory technique introduced in [22].

3. Positive equivalence

Below, we allow a square matrix to be n × n or ℕ × ℕ. Infinite matrices A, B are nonzero in only finitely many entries. Thus infinite matrices I −A, I −B equal the infinite identity matrix except in finitely many entries.

Definition 3.1. A square matrix M over ℤ or ℤG is irreducible if its entries are nonnegative (i.e. in ℤ_{+} or ℤ_{+}G) and for each index pair (i, j) there is an k > 0 with M^{k}(i, j) > 0. The matrix M is essentially irreducible if it has a unique principal submatrix that is irreducible and that is contained in no larger irreducible principal submatrix. Such a submatrix is called the irreducible core of M.

We consider matrices over ℤG. A basic elementary matrix is a matrix of the form E_{ij}(x), which denotes a matrix equal to the identity except for perhaps the off-diagonal ij entry (so, i ≠ j), which is equal to x. Suppose g ∈ G, E = E_{ij}(g) and A is a square matrix over ℤ_{+}G such that g is a summand of A(i, j). Then we say that each of the equivalences

(E, I): (I − A) → E(I − A) , (E^{−1}, I): E(I − A) → (I − A) ,
(I, E): (I − A) → (I − A)E , (I, E^{−1}): (I − A)E → (I − A)

is a basic positive equivalence over ℤG. Here the equivalences (E, I) and (I, E) are forward basic equivalences while (E^{−1}, I) and (I, E^{−1}) are backward basic equivalences.

Definition 3.2. An equivalence (U, V) : (I − A) → (I − B) is a positive equivalence if it is a composition of basic positive equivalences. When there exists a positive equivalence from I − A to I − B, we write

I − A ∼^{+} I − B.

The effect of a basic positive equivalence on the induced graph is discussed in detail in [7, page 278] when G is trivial. Our situation is entirely analogous. Suppose (E, I): (I − A) → (I − A′) is a basic forward positive equivalence, E = E_{ij}(g). Then A and A′ agree except perhaps in row i, where

A′(i, k) = A(i, k) + gA(j, k) if k ≠ j ,  and
A′(i, j) = A(i, j) + gA(j, j) − g .

Consequently the weighted graph G′ associated to A′ is constructed from the weighted graph G for A as follows. An edge e from i to j with weight g is deleted from G. For each G-edge f beginning at j, add an additional edge (called [ef]) from i to k with weight gh (where h is the weight of f and k is the terminal vertex of f). See Figure 1. (There, G-labels are suppressed for simplicity. If the labels of the edges e, f′, f′′ are g, h′, h′′, then the labels of the new edges [ef′], [ef′′] are gh′, gh′′.)

[figure: k; i; e; j; f′′; f′; k; i; [ef′]; [ef′′]; j; f′′; f′]

Figure 1. A basic positive equivalence.

The correspondence of the graphs G, G′ induces a bijection of σ_{A}- orbits and σ_{A′}-orbits,

… befcegfeffd … ↔ … b[ef]cegf[ef]fd …

This bijection of orbits does not arise from a bijection of points for the SFTs, but it does correspond to a homeomorphism of their mapping tori (after changing time by a factor of 2 over the clopen sets {x : x_{0} = [ef]}, the new flow is conjugate to the old one), which lifts to a G-equivariant equivalence of the mapping tori flows for the respective skew products.

The bijection of orbits above respects finiteness of orbits and the induced homeomorphism of mapping tori above respects respects density of orbits. Consequently, positive equivalence respects essential irreducibility and nontriviality (infinite number of orbits). Positive equivalence need not respect the size of the irreducible core of a presenting matrix.

Theorem 3.3. Let G be a finite group, and let A and B be square matrices over ℤ_{+}G. Then I − A ∼^{+} I − B if and only if S_{A} and S_{B} are G-flow equivalent.

Proof. We explained above that I − A ∼^{+} I − B implies the G-flow equivalence of S_{A} and S_{B}. Now suppose S_{A} and S_{B} are G-flow equivalent.

First suppose S_{A} and S_{B} are G-conjugate. Then by Proposition 2.7.1, B and A are SSE over ℤ_{+}G. In the polynomial setting of [9], the G-weighted SFTs defined by A, B can be presented by polynomial matrices I − tA, I − tB, and any SSE over ℤ_{+}G from A to B gives rise to a composition of polynomial positive equivalences via the polynomial strong shift equivalence equations [9, Theorem 7.2]. These equivalences, after setting the variable t equal to 1, produce a positive equivalence from I − A to I − B.

In the polynomial setting of [9], a matrix I − tA as above can be positively equivalent to a matrix I − B(t), where the entries of B(t) may involve higher powers of the variable t. A matrix B(t) over tℤ_{+}G[t] presents a discrete G-tower whose base is obtained by setting every t^{m} to t, and up to G-conjugacy every discrete G-tower over a G-SFT arises in this way. Changing t^{n} to t^{m} does not change the image under t ↦ 1. □

Remark 3.4. There is a more complicated way to handle the preceding proof, along the lines of [7, pp. 296-297] (which was the case ℤG = ℤ). One can provide a decomposition of a state-splitting SSE move into positive equivalences, and provide a separate decomposition for an SSE which for some i corresponds to multiplying row i by g and column i by g^{−1}. Such moves generate SSE over ℤ_{+}G. Lastly one can decompose a PS move into a finite string of basic positive equivalences.

4. The weight class

Suppose A is a matrix over ℤ_{+}G, with τ_{A} the associated labeling of edges. The weight of a path e of edges e_{1}e_{2} ⋯ e_{k} from vertex i to j is defined to be τ(e) = τ_{A}(e_{1})τ_{A}(e_{2}) ⋯ τ_{A}(e_{k}). (So, g is the weight of some path from i to j if and only if π_{g}(A^{n}(i, j)) > 0 for some n ∈ ℕ.)

Definition 4.1. Suppose G is a finite group, A is an essentially irreducible matrix over ℤ_{+}G and i is a vertex indexing a row of the irreducible core of A. Then W_{i}(A) is the subgroup of G which is the set of weights of paths from i to i, and the weight class of A, W (A), is the conjugacy class of W_{i}(A) in G. A member of W (A) is a weights group for A; if W (A) contains one element, then it is the weights group for A.

Let us verify two implicit claims of the definition. First, W_{i}(A) is a group because it is a semigroup and G is finite. Second, we check given i ≠ j that W_{i} and W_{j} are conjugate subgroups in G. Appealing to irreducibility, let x be the weight of some path from i to j and let y be the weight of some path from j to i. Because G is finite, we may assume y = x^{−1} (if necessary after replacing y with y(xy)^{k} for suitable k). Then xW_{j}x^{−1} = W_{i}, because

W_{i} ⊃ xW_{j}x^{−1} ⊃ x(x^{−1}W_{i}x)x^{−1} = W_{i} .

If G is abelian, then there is only one group in the weight class of A, and it is the union of the W_{i}(A). If G is not abelian, then ∪_{i}W_{i}(A) can generate a group strictly containing each W_{i}(A), and this larger group will not be the right group for our analysis.

Proposition 4.2. Suppose A is an irreducible matrix over ℤ_{+}G, and there is a positive ℤ_{+}G equivalence from I −A to I −B. Then W (A) = W (B).

Proof. From the description in Section 3, it is clear that when there is a basic positive equivalence from I − A to I − B, there must be a vertex i, indexing a row in the irreducible core of A and also in the irreducible core of B, such that W_{i}(A) and W_{i}(B) are equal. □

Example 4.3. Suppose G is any nontrivial finite group. Let g be an element of G not equal to the identity e. In the ring ℤG, the formal element e is the multiplicative identity 1. Consider the matrices over ℤ_{+}G,

A = (\begin{matrix}g & 1 \\ 1 & 1 \end{matrix}) and B = (\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}) .

The weight class W (B) is trivial while W (A) is not, so by Proposition 4.2 there cannot be a positive ℤG-equivalence from I − A to I − B. However, there is an E(ℤG)-equivalence:

(\begin{matrix}1 & −g \\ 0 & 1 \end{matrix}) (I−A) = (\begin{matrix}1 & −g \\ 0 & 1 \end{matrix}) (\begin{matrix}1 − g & −1 \\ −1 & 0 \end{matrix}) = (\begin{matrix}1 & −1 \\ −1 & 0 \end{matrix}) = I−B . □

Example 4.3 shows that positive ℤG-equivalence of nontrivial irreducible S_{A} does not follow from E(ℤG)-equivalence. This issue is clarified in the positive K-theory framework [6, Sec. 8].

We will use the next lemma to pass from a matrix A over ℤ_{+}G to a matrix over ℤ_{+}H, when H is in the weight class. The lemma is modeled on the Parry-Schmidt argument [31] for presentations of Markov chains. Recall α denotes the augmentation map (2.1). Proposition 4.4. Suppose A is an irreducible matrix over ℤ_{+}G, and H is a group in the weight class of A. Then there is a diagonal matrix D over ℤ_{+}G with each diagonal entry in G (i.e., α(D) = Id) such that every entry of DAD^{−1} lies in ℤ_{+}H. Proof. First consider H = W_{ℓ}(A), where ℓ is some vertex of A. For each j pick a path from ℓ to j and let the j-th diagonal element d_{j} of D be the G-weight of this path. Let b_{j} be the G-weight of a path from j back to ℓ. Now, if A(i, j) has h as a summand, then d_{i}hd_{j}^{−1} is the corresponding summand in DAD^{−1}(i, j). Write

(4.5)  d_{i}hd_{j}^{−1} = (d_{i}hb_{j})(d_{j}b_{j})^{−1}.

Let k be the order of d_{j}b_{j} in G. Then the right hand side of (4.5) is (d_{i}hb_{j})(d_{j}b_{j})^{k−1}, a product of weights from ℓ to ℓ.

Finally, if H = gW_{ℓ}(A)g^{−1}, then replace D above with gD. □

The following example is extracted from an example of Derek Holt analyzed by Parry [29, Sec. 10], and shows that cohomology over G does not imply cohomology over a group in the weight class. Example 4.6. Let G = S_{4}, the group of permutations of {1, 2, 3, 4}. Define permutations a = (12)(34), b = (13)(24), c = (14)(23). Let H be the subgroup {e, a, b, c} ≅ ℤ/2 ⊕ ℤ/2. Consider two 1 × 1 matrices over ℤ_{+}H, A = (a+b) and B = (a+c). Let d be the transposition (12), so dad^{−1} = a and dbd^{−1} = c. Then dAd^{−1} = B and there is a positive ℤG equivalence from I −A to I −B. On the other hand, if we consider A and B as matrices over ℤ_{+}G, we see that {H} is the weight class of A and B (H is a normal subgroup of G), but the matrices I − A and I − B are not even SL(ℤH) equivalent: the determinant is defined for matrices over the commutative ring ℤH, and det(I − A) ≠ det(I − B). □

Fortunately, the passage from G to the weight class is no worse than indicated by the previous example.

Theorem 4.7. Let A and B be essentially irreducible matrices over ℤ_{+}H, such that H is a weights group for A and B, and H is a subgroup of the finite group G. Then there is a positive ℤ_{+}G equivalence from I − A to I − B if and only if there exists an element γ of G such that

• γHγ^{−1} = H, and

• there is a positive ℤ_{+}H equivalence from I − A to I − γ^{−1}Bγ.

Proof. We will prove the nontrivial direction (“only if”). The assumed positive ℤG-equivalence from I − A to I − B involves time changes as well as conjugacies, and we refine the discussion of the proof of Proposition 2.7.1 to incorporate these time changes; they can be captured by including with the splittings from A to C a set of Parry-Sullivan moves, which can like the splittings be mirrored in the positive equivalence framework using only matrices over ℤ_{+}H. Thus, as in the proof of Proposition 2.7.1, we end up with α(A′) = C = α(B′); a diagonal D with D(i, i) = g_{i} ∈ G such that DA′D^{−1} = B′; a positive ℤ_{+}H equivalence from I − A to I − A′; and another from I − B to I − B′.

Let τ_{A} and τ_{B} denote the edge-labeling functions defined by A′ and B′. Then for any path e = e_{1}e_{2} ⋯ e_{k} of edges from vertex i to vertex j, we have

g_{i}τ_{A}(e)(g_{j})^{−1} = τ_{B}(e) . (4.8)

Because H is a weights group for A and B and all entries of A and B are in ℤ_{+}H, it holds for each pair of vertices i, j in the irreducible core that every element of H arises as τ_{A}(e) for some path e from i to j. Because the right side of (4.8) lies in H, we have g_{i}H(g_{j})^{−1} ⊂ H. We conclude for every i, j that g_{i}H(g_{j})^{−1} = H. Let γ = g_{1}. For each j,

H = g_{j}Hγ^{−1} = g_{j}γ^{−1}(γHγ^{−1}) = g_{j}γ^{−1}H

and therefore for some h_{j} ∈ H we have g_{j} = h_{j}γ. Now D = (D′)γI, where D′(j, j) = h_{j}, and therefore

γ^{−1}B′γ = (γ^{−1}D′γ)A′(γ^{−1}D′γ)^{−1} .

The entries of γ^{−1}D′γ lie in ℤ_{+}H. We have now a ℤ_{+}H SSE from A′ to γ^{−1}B′γ. The ℤ_{+}H SSE from B′ to B yields a ℤ_{+}H SSE from γ^{−1}B′γ to γ^{−1}Bγ, by replacement of each elementary SSE (R, S) with γ^{−1}Rγ, γ^{−1}Sγ. Thus we have a ℤ_{+}H SSE from A′ to γ^{−1}Bγ, and there is a positive ℤ_{+}H equivalence from I − A′ to I − γ^{−1}Bγ, and by composition from I − A to I − γ^{−1}Bγ. □

Theorem 4.7 is reminiscent of a similar reduction of Parry and Schmidt in their extension of Livšic theory to nonabelian cocycles [29, Theorems 6.4, 9.5], [36]. They were particularly concerned with deducing cohomology of certain G-valued functions given conjugate weights on each periodic orbit. This is a much stronger assumption than we use, and yields a correspondingly stronger conclusion.

5. Equivalence through very positive matrices

In this section we give the heart of the proofs of our main results. Throughout this section k denotes a positive integer greater than 1 and all matrices will be k × k. Let 𝔐_{+} denote the set of k × k very positive matrices over ℤG (“very positive” was defined in (2.1)). We say an equivalence (U, V) is a basic elementary equivalence if one of U, V is I and the other has the form E_{ij}(g) or E_{ij}(−g).

Definition 5.1. An equivalence (U, V) : B → B′ is a positive equivalence through 𝔐_{+} if it can be given as a composition of basic elementary equivalences over ℤG,

B = B_{0} → B_{1} → B_{2} ⋯ → B_{n} = B′ ,

such that every B_{i} is in 𝔐_{+}.

Lemma 5.2. Suppose (U, V) : A − I → A′ − I is a positive equivalence through 𝔐_{+}. Then (U, V) : I − A → I − A′ is a positive equivalence.

Proof. It suffices to consider the case that (U, V) is a basic elementary equivalence, and this case is clear. □

The lemma explains our interest in the following theorem.

Theorem 5.3. Suppose U and V are in E(k, ℤG) and UBV = B′, with B and B′ matrices in 𝔐_{+}. Suppose also that there are matrices X and Y in E(k, ℤG) such that XBY = D, where D has block diagonal form I_{2} ⊕ F.

Then (U, V) : B → B′ is a positive equivalence through 𝔐_{+}.

The rest of this section is devoted to the proof of Theorem 5.3, which generalizes the arguments of [7, Sec. 5]. We begin with a definition.

Definition 5.4. A signed transposition matrix is the matrix of a transposition, but with one of the off-diagonal 1’s replaced by −1. A signed permutation matrix is any product of signed transposition matrices.

It is not difficult to verify that the matrix of any even permutation is a signed permutation matrix.

Recall that α(A) is the matrix obtained by applying the augmentation map α to A entrywise.

Lemma 5.5. Suppose B ∈ 𝔐_{+} and E = E_{ij}(g) or E = E_{ij}(−g) where g ∈ G. Suppose the ith row of α(EB) is not the zero row. Then in E(k, ℤG) there is a nonnegative matrix Q and a signed permutation matrix S such that (SE, Q): B → SEBQ is a positive equivalence through 𝔐_{+}.

Proof. If E(i, j) = g, then let Q = I = S. Now, suppose E(i, j) = −g. Select l such that α(B(i, l) − gB(j, l)) ≠ 0, and set x = B(i, l) − gB(j, l), that is x = (EB)(i, l). Let y = ∑_{h∈G} h ∈ ℤG. Then xy = ∑(∑ x_{f})h, where x = ∑ x_{f}f, with all sums over G. Thus all coefficients (xy)_{h} of xy are the same nonzero number.

Case I: xy ≫ 0. Here we may repeatedly add y times column l of B to the other columns, until we have a matrix B′ with B′(i, m) ≫ B′(j, m) for all m = 1, …, k. This B′ is BQ for some Q which is a product of nonnegative basic elementary matrices, and (E, Q): B → EBQ is the composition of positive equivalences through 𝔐_{+}, (I, Q): B → BQ followed by (E, I): BQ → EBQ. Let S = I.

Case II: xy ≪ 0. For concreteness of notation, let (i, j) = (1, 2). Let M_{l} denote (in this proof only) row l of a matrix M. We can choose a suitable Q, in the manner of Case I, to obtain Q nonnegative such that (BQ)_{2} ≫ (BQ)_{1} and (gBQ)_{2} ≫ (BQ)_{1} and (I, Q): B → BQ is a positive equivalence in 𝔐_{+}. For simplicity of notation, we now write BQ as B and we restrict what we write to rows 1 and 2, e.g.

E = (\begin{matrix}1 & −g \\ 0 & 1 \end{matrix}) and B = (\begin{matrix}B_{1} \\ B_{2} \end{matrix}) .

Let S = (\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix}). Then

(SE)B = (\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix}) (\begin{matrix}1 & −g \\ 0 & 1 \end{matrix}) (\begin{matrix}B_{1} \\ B_{2} \end{matrix})

= (\begin{matrix}0 & 1 \\ −1 & g \end{matrix}) (\begin{matrix}B_{1} \\ B_{2} \end{matrix}) = (\begin{matrix}B_{2} \\ gB_{2} − B_{1} \end{matrix}) ≫ 0 .

Write SE as the product

SE = E_{1}E_{2}E_{3}E_{4} = (\begin{matrix}1 & 0 \\ −1 & 1 \end{matrix}) (\begin{matrix}1 & 0 \\ g & 1 \end{matrix}) (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 \\ −1 & 1 \end{matrix}) .

Write the equivalence SE : B → SEB as the composition of left multiplications by E_{1}, E_{2}, E_{3}, E_{4}:

(\begin{matrix}B_{1} \\ B_{2} \end{matrix}) → (\begin{matrix}B_{1} \\ B_{2} − B_{1} \end{matrix}) → (\begin{matrix}B_{2} \\ B_{2} − B_{1} \end{matrix}) → (\begin{matrix}B_{2} \\ B_{2} − B_{1} + gB_{2} \end{matrix}) → (\begin{matrix}B_{2} \\ gB_{2} − B_{1} \end{matrix}) .

This finishes the proof. □

Lemma 5.6. Suppose B is a k × k matrix over ℤG and α(B) has rank at least 2. Suppose U ∈ E(k, ℤG), and no row of α(B) or α(UB) is the zero row. Then U is the product of basic elementary matrices, U = E_{n} ⋯ E_{1}, such that for 1 ≤ j ≤ n the matrix α(E_{j}E_{j−1} ⋯ E_{1}B) does not have a zero row.

Proof. Without loss of generality, assume U ≠ I. The proof is clear for k = 2, since α(B) will have full rank. Let k ≥ 3. (The reader may wish to work through the proof for k = 3 on a first reading.)

Let E(i) denote the set of ℤG matrices which equal I both on the diagonal and outside of row i. Let U be the set of factorizations U = U_{n} ⋯ U_{1} such that for 1 ≤ h ≤ n, the matrix U_{h} is not the identity and there is an index i_{h} such that U_{h} ∈ E(i_{h}). Given such a factorization U = U_{n} ⋯ U_{1}, let

z = #{h: 1 ≤ h ≤ n and row i_{h} of α(U_{h} ⋯ U_{1}B) is the zero row}.

Step 1. We will produce an element of U for which z = 0.

By induction, it suffices to begin with a factorization U = U_{n} ⋯ U_{1} from U for which z > 0, and produce another factorization from U with reduced z. Pick s minimal such that row i_{s} of α(U_{s} ⋯ U_{1}B) is zero, and let t be minimal such that t > s and i_{t} = i_{s}. (This t exists because row i_{s} of α(UB) is nonzero.) We will change the factorization by replacing the subword U_{t} ⋯ U_{s} with a suitable word U′_{T} ⋯ U′_{s}, to be defined recursively; T will either be t or t − 1.

First pick j_{s} ≠ i_{s} such that row j_{s} of α(U_{s−1} ⋯ U_{1}B) is nonzero (U_{s−1} ⋯ U_{1}B just denotes B in the case that s = 1). Choose F_{s} an elementary matrix which acts to add a multiple of row j_{s} to row i_{s}, such that (to avoid re-indexing) F_{s}^{−1}U_{s} ≠ I. Define U′_{s} = F_{s}^{−1}U_{s} ∈ E(i_{s}). Now U_{t} ⋯ U_{s} = U_{t} ⋯ U_{s+1}F_{s}U′_{s} and row i_{s} of α(U′_{s}U_{s−1} ⋯ U_{1}B) is not zero.

Now we give the recursive step. Suppose s < m = r + 1 ≤ t and we have produced U_{t} ⋯ U_{r+1}F_{m−1}U′_{r} ⋯ U′_{s} = U_{t} ⋯ U_{s} (and consequently, F_{m−1}U′_{r} ⋯ U′_{s} = U_{m−1} ⋯ U_{s}) such that there is a nonzero integer c_{m−1} and an index j_{m−1} ≠ i_{s}, such that F_{m−1}(i_{s}, j_{m−1}) = c_{m−1} and otherwise F_{m−1} = I. We will replace U_{m}F_{m−1} with new terms. There are three cases.

Case 1: m < t and j_{m−1} ≠ i_{m}. Set F_{m} = F_{m−1} and U′_{r+1} = F_{m}^{−1}U_{m}F_{m}. For example, if k = 3 and (i_{s}, i_{m}, j_{m−1}) = (1, 2, 3), then we would have for some a, b, c that

U′_{r+1} = F_{m}^{−1}U_{m}F_{m} = (\begin{matrix}1 & 0 & −c \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ a & 1 & b \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & c \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})

= (\begin{matrix}1 & 0 & −c \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & c \\ a & 1 & ac + b \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix}1 & 0 & 0 \\ a & 1 & ac + b \\ 0 & 0 & 1 \end{matrix}) .

Now U′_{r+1} ∈ E(i_{m}), and F_{m}U′_{r+1} = U_{m}F_{m−1}, and row i_{m} of U_{m} ⋯ U_{1}B equals row i_{m} of U′_{r+1}U′_{r} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B.

Case 2: m < t and j_{m−1} = i_{m}. Choose an index j_{m} such that j_{m} ∉ {i_{m}, i_{s}} and row j_{m} of α(U′_{r} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B) is not zero. This is possible because rows i_{s} and j_{m−1} of α(U′_{r} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B) are linearly dependent, (since row i_{s} of F_{m}U′_{r} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B equals row i_{s} of U_{m} ⋯ U_{1}B which is the zero row under α) and rank(α(B)) ≥ 2. Pick F_{m} with F_{m}(i_{s}, j_{m}) = 1 and otherwise F_{m} = I. Set U′_{r+1} = F_{m}^{−1}F_{m−1} and U′_{r+2} = F_{m}^{−1}U_{m}F_{m}. Now

• F_{m}U′_{r+2}U′_{r+1} = F_{m}(F_{m}^{−1}U_{m}F_{m})(F_{m}^{−1}F_{m−1}) = U_{m}F_{m−1},

• U′_{r+1} ∈ E(i_{s}) and row i_{s} of α(U′_{r+1} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B) is not zero,

• U′_{r+2} ∈ E(i_{m}) and row i_{m} of U′_{r+2} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B equals row i_{m} of U_{m} ⋯ U_{1}B.

Case 3: m = t. If U_{t}F_{t−1} ≠ I, then set U′_{T} = U′_{r+1} = U_{t}F_{t−1} ∈ E(i_{s}): row i_{s} is the same in the matrices U′_{T} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B and U_{m} ⋯ U_{1}B. If U_{t}F_{t−1} = I, then simply delete U_{t}F_{t−1}, so U′_{T} = U′_{r}.

The new factorization has z reduced. This concludes Step 1.

Step 2. Suppose we have the factorization from U with z = 0, U = U_{n} ⋯ U_{1}, with U_{h} ∈ E(i_{h}). For 1 ≤ h ≤ n, we will replace U_{h} with a suitable product of elementary matrices in E(i_{h}). The argument will be clear from the case h = 1. For notational simplicity, suppose i_{1} = 1. Write U_{1} as a product U_{1} = E_{k_{1}} ⋯ E_{1} of basic elementary matrices which agree with I outside row 1. Now, choose a row l > 1 of B such that row l of α(B) is not a rational multiple of row 1 of α(U_{1}B) (such a row l exists because rank(α(B)) > 1). Let E_{0} be the elementary matrix which adds row l to row 1: if s > 0, then α((E_{0})^{s}B) has row 1 not zero. Choose a nonnegative integer m large enough that for 1 ≤ j ≤ k_{1}, row 1 of α([E_{j} ⋯ E_{1}(E_{0})^{m}]B) is nonzero. Then for 0 ≤ s ≤ m,

[E_{0}^{−s}][E_{k} ⋯ E_{1}(E_{0})^{m}]B = [E_{0}^{m−s}][E_{k} ⋯ E_{1}]B
= [E_{0}^{m−s}]U_{1}B

and therefore row 1 of α([E_{0}^{−s}][E_{k_{1}} ⋯ E_{1}(E_{0})^{m}]B) cannot be zero. (Since each E_{i}, for i = 0, …, k_{1}, affects only row 1, they all commute with each other.) Thus the factorization U_{1} = (E_{0})^{−m}E_{k_{1}} ⋯ E_{1}(E_{0})^{m} has the required properties. □

Lemma 5.7. Suppose B and B′ are in 𝔐_{+}; α(B) and α(B′) have rank ≥ 2; U and W are in E(k, ℤG); the matrix α(UB) has at least one strictly positive entry; and UB = B′W. Then the equivalence (U, W^{−1}): B → B′ is a positive equivalence through 𝔐_{+}.

Proof. We divide the proof into four steps.

Step 1: Reduction to the case α(UB) has all entries positive. Consider an entry α((UB)(i, j)) > 0. We can repeatedly add column j to other columns until row i of α(UB) has all entries strictly positive. This corresponds to multiplying from the right by a nonnegative matrix Q in E(k, ℤ) ⊂ E(k, ℤG), giving UBQ = B′W Q. Then we can repeatedly add row i of UBQ to other rows until all entries of α(UBQ) are positive. This corresponds to multiplying from the left by a matrix P in E(k, ℤ), resulting in a matrix (P U)(BQ) = (P B′)(W Q) whose augmentation has all entries positive. Also, there are positive equivalences in 𝔐_{+} given by

(I, Q): B → BQ , (P, I): B′ → P B′ .

Therefore, after replacing (U, B, B′, W) with (P U, BQ, P B′, W Q), we may assume without loss of generality that α(UB) has all entries positive.

Step 2: Factoring U and B → SUBQ through 𝔐_{+}. By Lemma 5.6, we can write U as a product of basic elementary matrices, U = E_{l} ⋯ E_{1}, such that for 1 ≤ j ≤ l, the matrix α(E_{j} ⋯ E_{1}B) has no zero row. By Lemma 5.5 and Step 1, given the pair (E_{1}, B), there is a nonnegative Q_{1} in E(k, ℤG) and a signed permutation matrix S_{1} such that

(S_{1}E_{1}, Q_{1}): B → S_{1}E_{1}BQ_{1}

is a positive equivalence in 𝔐_{+}. We observe that

UBQ_{1} = S_{1}^{−1}[S_{1}E_{l}S_{1}^{−1}] ⋯ [S_{1}E_{2}S_{1}^{−1}][S_{1}E_{1}]BQ_{1} .

Now, for 2 ≤ j ≤ l, the matrix S_{1}E_{j}S_{1}^{−1} is again a basic elementary matrix E′_{j}, and the matrix α(E′_{j} ⋯ E′_{2}(S_{1}E_{1}BQ_{1})) has no zero rows.

Again using Lemma 5.5, for the pair ([S_{1}E_{2}S_{1}^{−1}], [S_{1}E_{1}BQ_{1}]) choose a signed permutation matrix S_{2} and nonnegative Q_{2} producing a positive equivalence in 𝔐_{+}

(S_{2}[S_{1}E_{2}S_{1}^{−1}], Q_{2}): S_{1}E_{1}BQ_{1} → S_{2}[S_{1}E_{2}S_{1}^{−1}]S_{1}E_{1}BQ_{1}Q_{2}

so that we get a positive equivalence in 𝔐_{+}

([S_{2}S_{1}E_{2}S_{1}^{−1}][S_{1}E_{1}], Q_{1}Q_{2}): B → [S_{2}S_{1}E_{2}E_{1}BQ_{1}Q_{2}]

and we observe that

UBQ_{1}Q_{2} = S_{1}^{−1}S_{2}^{−1}[S_{2}S_{1}E_{l}S_{1}^{−1}S_{2}^{−1}] ⋯ [S_{2}S_{1}E_{3}S_{1}^{−1}S_{2}^{−1}][S_{2}S_{1}E_{2}S_{1}^{−1}][S_{1}E_{1}]BQ_{1}Q_{2} .

Continue this, to obtain a signed permutation matrix S = S_{l} ⋯ S_{1} and nonnegative Q = Q_{1} ⋯ Q_{l} such that

UBQ = S^{−1}[S_{l} ⋯ S_{1}E_{l}S_{1}^{−1} ⋯ S_{l−1}^{−1}] ⋯ [S_{2}S_{1}E_{2}S_{1}^{−1}][S_{1}E_{1}]BQ
= S^{−1}(SUBQ)

and (SU, Q): B → SUBQ is a positive equivalence in 𝔐_{+}.

Step 3: Realizing the permutation. We continue from Step 2. It remains to show that

(S, I): UBQ → SUBQ

is a positive equivalence in 𝔐_{+}. Since S is a product of signed transposition matrices, it may be described as a permutation matrix in which some rows have been multiplied by −1. Since UBQ and SUBQ are strictly positive, it must be that S is a permutation matrix. Also, det(S) = 1, so if S ≠ I then S is the matrix of a permutation which is a product of 3-cycles. So it is enough to realize the positive equivalence in 𝔐_{+} in the case that S is the matrix of a 3-cycle. For this we write the matrix

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

as the following product C_{0}C_{1} ⋯ C_{5}:

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

For 0 ≤ i ≤ 5, the matrix C_{i}C_{i+1} ⋯ C_{5} is nonnegative. Therefore the equivalence (C, I): A → CA is a positive equivalence through 𝔐_{+} whenever A ∈ 𝔐_{+}.

Step 4. Conclusion. We now have several positive equivalences through 𝔐_{+}, namely (SU, Q) : B → SUBQ, (S^{−1}, I) : SUBQ → UBQ, and (I, Q^{−1}) : UBQ → UB. By composition, (U, I) is a positive equivalence through 𝔐_{+} from B to UB = B′W. By a similar argument (invoking corollaries to Lemmas 5.5 and 5.6 for multiplications on the right), we can show (I, W) is a positive equivalence through 𝔐_{+} from B to B′W. This proves Lemma 5.7. □

Proof of Theorem 5.3. We will use Lemma 5.7 twice: first to give a positive equivalence from B to itself, and then to give another from B to B′. The inverse of the first followed by the second will equal (U, V) and thus establish that (U, V) is a positive equivalence.

Notation: For a 2 × 2 matrix H and m ∈ ℕ let L = L_{m}(H) =

(\begin{matrix}m & −1 \\ 1 & 0 \end{matrix}) H ⊕I_{k−2}. For a matrix Q let Q\{12; ∗\} denote the submatrix

consisting of the first two rows of Q.

By assumption, there are matrices X and Y in E(k, ℤG) such that XBY = D, where D has block diagonal form I_{2} ⊕ F.

Step 1. We will show that for a suitable 2 × 2 matrix H and integer m large enough the self equivalence (X^{−1}LX, Y L^{−1}Y^{−1}) : B → B is a positive equivalence. The matrix α(XBY){12; ∗} = α(D){12; ∗} has rank two, so α(XB){12; ∗} has rank two, and thus there exists an H ∈ SL(2, ℤ) such that the first row R of H[α(XB){12; ∗}] has both a positive and a negative entry.

Let C be the first column of α(X^{−1}) = α(X)^{−1}. Since C is not the zero vector the k × k matrix CR has a positive and a negative entry.

Now, if m is sufficiently large, then the corresponding entries of α(X^{−1}LXB) and CR will have the same sign provided the corresponding entry of CR is not zero.

We now apply Lemma 5.7 to see that (X^{−1}LX, Y L^{−1}Y^{−1}) is a positive equivalence from B to itself.

Step 2. For large enough m the entries of α(UX^{−1}LXB) agree in sign with the corresponding nonzero entries of α(U)CR. Since α(U) is nonsingular, the matrix α(U)CR is nonzero and so contains positive and negative entries, because R does. Thus, by Lemma 5.7 (UX^{−1}LX, Y L^{−1}Y^{−1}V) is a positive equivalence form B to B′. This concludes the proof. □

6. The main results

Given an n × n matrix A, we define (I − A)_{∞} to be the ℕ × ℕ matrix equal to I − A in its n × n upper left-hand corner and equal to the infinite identity outside this block. The next theorem is our central result.

Theorem 6.1. Let G be a finite group, and let A and B be nontrivial essentially irreducible matrices over ℤ_{+}G such that W (A) = W (B) = G. If (U, V) : (I − A)_{∞} → (I − B)_{∞} is an E(ℤG)-equivalence, then it is a positive ℤG equivalence.

Proof. First, we may assume that that A and B have a common size k with only zero entries outside the upper left k − 2 × k − 2 corner (expanding a matrix A to a larger matrix with zero entries does not affect (I − A)_{∞}), and consequently the 2 × 2 identity matrix is a summand of I − A and of I − B. By Lemma 6.6 (which we defer to the end of this section), after replacing I − A and I − B with matrices positively equivalent over ℤG, we may assume that A − I is very positive and likewise that B − I ≫ 0. By Lemma 5.2, (U, V) : I − A → I − B is a positive equivalence if (U, V) : A − I → B − I is a positive equivalence through 𝔐_{+} (Definition 5.1). By Theorem 5.3, (U, V) : A − I → B − I is indeed a positive equivalence through 𝔐_{+}. □

Remark 6.2. Note, in Theorem 6.1 we not only showed a positive equivalence exists, in addition we showed every equivalence is a positive equivalence. In the case G is trivial, this additional information proves [7, Sec. 7] surjectivity of a certain homomorphism to Aut(cok(I − A)) from the mapping class group of the mapping torus of an irreducible nontrivial SFT S_{A}. (For this homomorphism, the action of a basic flow equivalence is multiplication by the corresponding basic elementary matrix.) In the case G is nontrivial, our map goes from an equivariant mapping class group to the ℤG module cok(I − A), and from Theorem 6.1 we similarly know the range in Aut(cok(I − A)) is the set of automorphisms induced by E(ℤG) self equivalences of (I − A).

Remark 6.3. Suppose in Theorem 6.1 that (I − A)_{∞}, (I − B)_{∞}, U and V equal I outside their upper left n × n corners. Then the proof of Theorem 6.1 shows that the factorization of (U, V) into basic positive equivalences can be achieved using only matrices which equal I outside their upper left (n + 2) × (n + 2) corners.

Theorem 6.4 (Classification Theorem). Let G be a finite group, and let A and B be essentially irreducible nontrivial matrices over ℤ_{+}G. For S_{A} and S_{B} to be G-flow equivalent, it is necessary that W (A) = W (B). Now suppose W (A) = W (B) and H is a group in this weight class. Let \overline{A} and \overline{B} be matrices over ℤH which are positively ℤG equivalent to A and B, respectively. ( \overline{A} and \overline{B} exist by Proposition 4.4). Then the following are equivalent:

(1) S_{A} and S_{B} are G-flow equivalent.

(2) There exists γ ∈ G such that γHγ^{−1} = H and there is an E(ℤH) equivalence from (I − \overline{A})_{∞} to (I − γ\overline{B}γ^{−1})_{∞}.

Proof. The necessity of W (A) = W (B) was Proposition 4.2. The implication (1) ⟹ (2) follows from Theorems 3.3 and 4.7. The implication (2) ⟹ (1) follows from Theorem 6.1. □

Theorem 6.4 reduces the G-flow equivalence classification to the problem of classifying matrices up to E(ℤG) equivalence, which we discuss in Sections 8 and 9. The positivity constraints on the matrices I − A we study does not lead to a smaller E(ℤG) equivalence problem, because for any finitely supported B over ℤG there is an E(ℤG) equivalence from I − B to a matrix I − A where A is essentially irreducible and nontrivial with weight class {G} (Proposition 8.8). We extract now one consequence of Theorem 6.4 and the algebra. SK_{1}(ℤG) is discussed in Section 8.

Theorem 6.5. Suppose G is a finite abelian group and A is a square irreducible matrix over ℤ_{+}G such that I −A is injective (i.e. det(I −A) is not a zero divisor in ℤG). Then the following hold.

(1) The number of distinct G-flow equivalence classes defined by matrices B such that det(I − B) = det(I − A) is finite.

(2) If SK_{1}(ℤG) is trivial and det(I − B) = det(I − A), then A and B determine the same G-flow equivalence class if and only if they have the same weight class and the ℤG modules cok(I −A) and cok(I − B) are isomorphic.

Proof. (1) When I − A is injective, cok(I − A) is finite. Therefore (crudely) only finitely many isomorphism classes of cokernel module are possible. The conclusion now follows from the Classification Theorem 6.4, Corollary 9.9, and the finiteness of SK_{1}(ℤG) [27]. (2) This follows from the Classification Theorem 6.4 and Proposition 9.5. □

We finish this section with the (somewhat tedious) proof for the reduction to very positive matrices.

Lemma 6.6 (Very Positive Presentation). Let A be an essentially irreducible m × m matrix over ℤ_{+}G, m ≥ 2, such that W_{i}(A) = G for 1 ≤ i ≤ m and α(A) has more than one cycle. Then there is a positive equivalence over ℤG from I − A to a matrix I − B such that π_{g}((B − I)(i, j)) > 0 for every g in G and every entry index (i, j), i.e., B − I ≫ 0.

Proof. We sequentially adjust the matrix A without renaming it each time. Let A be n × n, where n changes as A does. We relabel so that the irreducible core submatrix is in the upper left-hand corner.

Step 0: Diagonalizing cycles. First we describe a certain cycleshortening construction. Let i = i_{0}, i_{1}, …, i_{k} = i be a finite sequence of indices corresponding to a cycle (cyclic path of edges) C = e_{1}e_{2} ⋯ e_{k} with weight g, where e_{t} runs from i_{t−1} to i_{t} and has weight g_{t} (so g_{1}g_{2} ⋯ g_{k} = g). We require that some intermediate index i_{r} is not i.

We will construct a positive equivalence (I − A) → (I − B) for which we claim A(i, i) ≥ B(i, i) + g and also A(t, t) ≥ B(t, t) for all t. The latter part of this claim will be clear because the construction will be a composition of forward basic positive equivalences.

First suppose the path length k satisfies k > 2. Let e denote the edge e_{r}.

(1) If r < k − 1, then produce a new matrix I − A′ by applying the basic positive equivalence (E_{i_{r},i_{r+1}}(g_{r+1}), I). The A-cycle C gives rise to an A′-cycle C′, which looks like C except that any e_{s}e_{s+1} for which e_{s} = e is replaced by an edge from i_{s−1} = i_{r} to i_{s+1} with weight g_{s}g_{s+1}. The cycle C′ is still a cycle from i to i, it still passes through an index other than i, and it has the same weight as C.

(2) If we do not have r < k − 1, then r = k − 1 ≥ 2, and we may similarly apply the basic positive equivalence (I, E_{i_{r−1},i_{r}}(g_{r})) to shorten the cycle.

Repeating the moves above, we reach the case of path length k = 2. Apply the basic positive equivalence (E_{i_{0},i_{1}}(g_{1}), I). We have shortened the cycle to a cycle from i to i with the same weight. This completes the proof of the claim.

Given A, let A′′ denote the irreducible core of A, its maximal irreducible principal submatrix.

Step 1: Nonzero trace. If A has zero trace, then diagonalize a cycle as in the previous step to achieve nonzero trace.

Step 2: Trim. Suppose row j of A is zero and some entry A(i, j) ≠ 0. Let A(i, j) = g_{1} + ⋯ + g_{k} and set E = E_{ij}(g_{1} + ⋯ + g_{k}), so E = E_{ij}(g_{1}) ⋯ E_{ij}(g_{k}). Then E(I − A) = (I − B) where B = A except for the entry B(i, j) = 0, and (E, I) : (I − A) → (I − B) is a positive equivalence. After if necessary applying such positive equivalences, and analogous equivalences (E, I), we may assume that A(i, j) = 0 unless both i and j are indices for A′′.

Step 3: Core at least 2 × 2. Suppose the irreducible core A′′ is 1×1, say A′′ = (A(1, 1)). Because there is more than one cycle, we can write A(1, 1) = g + b where g ∈ G and 0 ≠ b ∈ ℤ_{+}G. Subtract g times row 2 of (I − A) from row 1; then subtract column 2 from column 1.

The result of these two positive equivalences is a matrix with (\begin{matrix}b & g \\ 1 & 0 \end{matrix})

as the irreducible core.

Step 4: Very positive core diagonal. At this point we have A′′ at least 2 × 2 in size and with an index i such that A′′(i, i) ≠ 0. Pick an index j ≠ i for A′′. Every element of G is the weight of some cycle from i to i, so it follows by irreducibility of A′′ that every element of G is the weight of some cycle from j to j which runs through i. This statement remains true after we diagonalize a cycle from j to j as in Step 0, because i and j must remain in the irreducible core, because the ii and jj entries are nonzero and do not decrease. Consequently we can diagonalize cycles until A′′(t, t) ≫ 0 for every diagonal entry of A′′.

Step 5: A=core. If 1 ≤ t ≤ m and t is not an index for A′′: pick an index s for A′′; subtract row t of A from row s; then subtract column t from column s. This positive equivalence I − A → I − C produces C whose irreducible core has an index set enlarged by {t}. Apply Step 4 again to the tt and ss entries as needed to get all diagonal entries of C′′ ≫ 0. Repeat until A = A′′ with very positive diagonal.

Step 6: Very positive A. Suppose i ≠ j, g ∈ G and A′′(i, j) − g ≥ 0. Following Step 3, (E_{ij}(g), I) : (I − A) → (I − C) is a basic positive equivalence; C(i, j) ≫ 0; and C ≥ A. So, we may apply basic positive equivalences to arrive at A′′ on an unchanged index set with A′′ ≫ 0.

□

7. Twistwise flow equivalence

As noted in the Introduction, when G = ℤ/2 the equivalence relation of G-flow equivalence is called twistwise flow equivalence. Let t denote the generator of ℤ/2, so t^{2} = 1. We write A(t) for a matrix over ℤ_{+}G and let A(1) and A(−1) denote the matrices over ℤ obtained from setting t to 1 and −1.

Suppose A(t) is given. We define the ribbon set R to be a flow on a fiber bundle with fiber (−1, 1) over the one-dimension suspension flow (B, ϕ) of A(1), associated to A(t) as follows. We can pass to a higher block presentation so that we may assume A(t) has only 1’s, 0’s and t’s as entries. Then there is an oriented Markov partition D = {D_{1}, …, D_{k}} on a cross section of F that induces A(1). Let B_{ij} = {x ∈ B | x ∈ ϕ_{t}(y), y ∈ D_{i}, and ϕ_{τ(y)}(y) ∈ D_{j} for 0 ≤ t ≤ τ(y)}, where τ is the first return time map for D. Let R_{ij} = B_{ij} × (−1, 1). Attach the nonempty R_{ij}’s so that the core is F and the gluing of the edge fibers (end points of the B_{ij} crossed with the fiber (−1, 1)) are the identity if A_{ij} = 1 and multiplication by −1 if A_{ij} = t. Call this set R. We place a flow on R that agrees with ϕ on the core B and so that all other orbits are forward asymptotic to B and exit R in reverse time. Two matrices are twistwise flow equivalent if and only if they have topologically equivalent ribbon sets. Ribbon sets are realized naturally as stable bundles of basic sets of Smale flows [37].

We now define the invariants of twistwise flow equivalence established

in [37, 38, 39]. Let T = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}). If A(t) is k × k define A(T) to

be the 2k × 2k matrix over ℤ_{+} obtained by converting each a + bt

entry of A(t) to the block aI + bT = (\begin{matrix}a & b \\ b & a \end{matrix}). The determinants of

the three matrices I − A(1), I − A(−1), I − A(T) were established as invariants of twistwise flow equivalence, as were the isomorphism classes of their cokernel groups. (We remark that the group cok(I − A(T)) is isomorphic to the group obtained from the ℤℤ/2 module cok(I − A(t)) by forgetting the module structure.) The orientability of the ribbon set was determined by checking the diagonal entries of A^{i}(t) for i = 1, …, k for t’s. The ribbon set is orientable if t appears in none of these entries, and is nonorientable otherwise. Orientability is an invariant independent of the others; in the setting of this paper, orientability is triviality of the weight class.

From the results of this paper, it is easy to see that the previously known invariants were not complete. For example, none of those invariants distinguish a matrix and its transpose, so Example 8.6 and Proposition 8.8 can be used to produce a pair which agree on the previously known invariants but are not twistwise flow equivalent. The methods and results of this paper are also useful for establishing twistwise flow equivalence when it holds.

Example 7.1. Let A = (\begin{matrix}0 & t \\ 1 & 1 \end{matrix}), B = (\begin{matrix}1 & t \\ 1 & 1 \end{matrix}), and E = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}).

Then E(I − A) = I − B, so by Theorem 6.4, A and B are twistwise flow equivalent. This answers a question in [39, page 9]. Here E does not give a basic positive equivalence. However, following the philosophy

of the proof of Theorem 6.1, if we let Q_{1} = (\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}) and Q_{2} = (\begin{matrix}1 & t \\ 0 & 1 \end{matrix})

then (I, Q_{1}), (I, Q_{2}), (E, I), (I, Q_{2}^{−1}), (I, Q_{1}^{−1}) is a sequence of basic positive equivalences taking I − A to I − B. □

In [38] Table 2 lists some 3 × 3 matrices. Several pairs have identical invariants: counting down, 1 & 5, 2 & 7, 4 & 13, and 17 & 18. It was unknown if they were twistwise flow equivalent. We can now report that simple hand calculations show that the matrices corresponding to these pairs are twistwise flow equivalent. Section 8 includes some additional results on twistwise flow equivalence.

8. E(ℤG)-equivalence

In this section, we’ll give some general background on E(ℤG)-equivalence, with some results and examples for the case G = ℤ/2. Recall our convention (2.1) that in this paper a ring means a ring with 1.

Let R be a ring. E(n, R) denotes the group of n × n elementary matrices over R, the subgroup of GL(n, R) generated by basic elementary matrices. Similarly, we let E(R) denote the subgroup of GL(R) generated by the basic elementary matrices. The group GL(R)/E(R) is the abelian group K_{1}(R) studied in algebraic K-theory [34]. When R is commutative (so SL(R) can be defined as the group of invertible matrices with determinant 1), the quotient group SL(R)/E(R) is denoted SK_{1}(R). If G is a finite group, then SK_{1}(ℤG) denotes the kernel of the map K_{1}(ℤG) → K_{1}(ℚG) (the definitions agree if G is abelian). If G is finite, then SK_{1}(ℤG) is finite. If R is ℤ, or R = ℤG with G = ℤ/2, then every element of SL(R) is a product of basic elementary matrices, and SK_{1}(R) is trivial. In general, though, SK_{1}(ℤG) is not trivial when G is a finite group. For example, SK_{1}(ℤG) is not trivial if G = (ℤ/p)^{n} with p an odd prime and n ≥ 3. See [27] for the characterization of the finite abelian G with trivial SK_{1}(ℤG) and other background on SK_{1}(ℤG).

We will say an n×n matrix D over ℤ is a Smith normal form if D is a diagonal matrix diag(d_{1}, d_{2}, …, d_{n}) satisfying the following conditions: d_{i+1} divides d_{i} whenever 1 < i ≤ n and d_{i+1} ≠ 0; d_{i+1} = 0 implies d_{i} = 0; and d_{i} ≥ 0 if i > 1.(Our notation here is slightly unconventional.) It is well known that any n × n matrix over ℤ is SL(n, ℤ) equivalent to a unique Smith normal form. Because E(n, ℤ) = SL(n, ℤ), the Smith normal form also gives a complete invariant of E(n, ℤ)-equivalence.

This classification extends to ℕ × ℕ matrices. We will say a Smith normal form is a matrix whose upper left corner is a finite Smith normal form and which otherwise equals the infinite identity matrix. If A is an n × n square matrix over ℤ, then (I − A)_{∞} is E(ℤ)-equivalent to a unique Smith normal form, and this form is the matrix whose upper left corner is the Smith normal form of I_{n} − A, and which equals I elsewhere. (It is to make this last statement that we reversed the usual order of diagonal elements in our definition of Smith normal form.) So in the ℤ case, we have everything: a good normal form; a good algorithm for generating it; a decision procedure for determining whether two matrices are equivalent; an equivalence classification given by the classification of the cokernel group (ℤ-module) with a little more information (sign of the determinant) to reflect the refinement of GL(ℤ) equivalence by E(ℤ) equivalence; and immediate stabilization (i.e., if A and B are n × n and (I − A)_{∞} and (I − B)_{∞} are E(ℤ) equivalent, then (I − A) and (I − B) are E(n, ℤ) equivalent).

Given G a finite group, the results of this paper obviously lead one to ask similarly for a classification of matrices over ℤG up to E(ℤG)- equivalence, when the matrices are n × n, or equal I except in finitely many entries. This very natural algebraic problem is far more difficult than in the ℤ case. In particular, there is nothing so nice as the Smith normal form; even for G = ℤ/2, a matrix might not be equivalent over GL(ℤG) to any triangular matrix (8.7), or to its transpose (8.6). The problem even of GL(ℤG) equivalence seems not to have been addressed directly in the algebra literature, although there are powerful results [16] in a more general setting which point the way to substantial progress. In the rest of this section, we make no attempt to address the general problem, but we do give some illustrative concrete results and examples in the case G = ℤ/2.

From here until Proposition 8.8, G = ℤ/2. We write elements of ℤG in the form a + tb, where a, b are integers and t^{2} = 1. We will use the well known [34, Sec. 2.4] embedding of ℤG into ℤ^{2}, δ : a + tb ↦ (a + b, a−b). One easily checks that δ is a ring monomorphism whose image is {(c, d) : c ≡ d mod 2}. If we write a matrix over ℤG in the form A+tB (A and B over ℤ), then applying δ entrywise gives an embedding of matrix rings (also called δ), A + tB ↦ (A + B, A − B). Under this embedding, the image of SL(ℤG) is {(C, D) ∈ SL(ℤ) × SL(ℤ) : C ≡ D mod 2}. We will say that a matrix M over ℤG is a Smith normal form if δ(M) = (C, D) where C and D are Smith normal forms for ℤ. In this case, M is diagonal over ℤG and its diagonal entries satisfy the divisibility and zero conditions we gave above for the ℤ form; the nonnegativity condition is replaced by the corresponding nonnegativity of the image under δ. Clearly, M can be E(ℤG) equivalent to at most one Smith normal form.

Theorem 8.1 (Normal Form). Let G = ℤ/2. Let M be an n × n matrix over ℤG. Write M = A + Bt with A and B n × n matrices over ℤ. If det(A + B) is odd, then M is E(ℤG)-equivalent to a Smith normal form. This is the form corresponding to (C, D), where C and D are the Smith normal forms for A + B and A − B.

The theorem follows immediately from a more general lemma.

Lemma 8.2. Let G = ℤ/2. Let M be an n × n matrix over ℤG and let (C, D) = δ(M). Suppose the mod-2 rank of C is k. Then M is E(n, ℤG)-equivalent to a matrix M′ such that δ(M′) = (C′, D′) where the bottom right k × k corners of C′ and D′ are Smith normal forms (equal to the bottom right corners of the Smith normal forms for C and D) and the other entries in the last k rows and columns are zero.

Proof. Multiplication of M by a matrix in E(n, ℤG) corresponds to multiplication of (C, D) from the same side by a pair of matrices in E(n, ℤ) × E(n, ℤ) which are equal mod 2. So, an equivalence M → UMV corresponds to an E(n, ℤ) = SL(n, ℤ) equivalence (C, D) → (U_{1}CV_{1}, U_{2}DV_{2}) where U_{1} − U_{2} and V_{1} − V_{2} are zero mod 2. We will act on the given pair (C, D) with such equivalences. Note the condition C ≡ D mod 2 persists under this action.

Let (U_{1}, V_{1}) be an E(n, ℤ) equivalence putting C into the Smith normal form for ℤ. Apply this along with (U_{2}, V_{2}) = (U_{1}, V_{1}). The mod-2 rank assumption tells us that the last k diagonal entries of C are now odd and the other entries of C are even. The same is true of D. From here we will use equivalences with (U_{1}, V_{1}) = (I, V_{1}), to achieve the required form for D without disturbing the form for C. That is, we will act on D with the even elementary matrices: matrices in E(n, ℤ) equal mod 2 to the identity. In particular we may freely add even multiples of rows and columns to other rows and columns.

We claim that such even elementary operations may be used to put D into a form such that the all entries of the last row and column are zero except for the diagonal entry, which is the gcd of the entries of D. Without loss of generality, we suppose n > 1.

Step 1. Consider the bottom row of C, row n. The last entry is odd and the rest are even. Pick j such that D(n, j) = a is a nonzero entry of smallest magnitude in row n. Add even multiples of column j to other columns to produce the condition that every entry in row n lies in the interval [−|a|, |a|]. If any nonzero entry b of row n now satisfies |b| < |a|, then again add even multiples of columns to others until all entries lie in [−|b|, |b|]. Continue until there is some nonzero entry a such that all entries of row n lie in the set {−|a|, 0, |a|}. This number |a| must be the gcd of the original entries of row n. Consequently |a| is odd. Since the entries of row 1 were never changed mod n, the diagonal entry of row n must be a and the others then must be 0.

Step 2. Apply the Step 1 idea to column n, putting it into the form [0 ⋯ 0a]^{t} (a may have decreased).

If row n is no longer in the form [0 ⋯ 0a], then re-apply Step 1. Repeat Steps 1 and 2 as needed until both row 1 and column 1 are zero except for the odd entry on the diagonal. Call this “the process”.

If |a| is not the gcd of all the matrix entries, then there is some higher row i containing an element not divisible by a. Add twice row i to row n. Now row n has a gcd smaller than |a|. Apply “the process” again. The one nonzero entry in row n or column n, on the diagonal, has decreased in magnitude. Finitely many iterations therefore produce the diagonal entry a such that |a| is the gcd of the matrix entries. Finally, if necessary after multiplying the last row and a higher row both by −1 (this corresponds to multiplying by a determinant 1 matrix which equals I mod 2), we can assume a > 0. This finishes the proof of the claim.

Repeat this procedure on successive submatrices until a matrix is produced which satisfies the statement of the theorem. If k = n, then at the final step there will not be a “higher row” and there will not be freedom to adjust the sign of the diagonal entry—it must equal the sign of the determinant. □

Remark 8.3. The lemma shows that Theorem 8.1 is true under the weaker assumption that at most one entry of the Smith form for A + B is even, because in this case the algorithm of the lemma produces a matrix which is equivalent to A−B and which must be a Smith normal form.

Corollary 8.4. Let G = ℤ/2. If M = A+tB where A and B are square integral matrices with det(A + B) odd, then M is E(ℤG)-equivalent to its transpose.

Remark 8.5. Equivalence to the transpose gives rise to an interpretation of G-flow equivalence to the time-reversed flow as in [15]. Because irreducible matrices over ℤ are equivalent to diagonal matrices, Franks could include that the mapping torus flows of irreducible shifts of finite type are flow equivalent to their time-reversed flows. For G-flow equivalence with G nontrivial, this holds in some cases (e.g. Cor. 8.4) but not in general, as the next example shows.

Example 8.6. For G = ℤ/2, there is a matrix M over ℤG which is not GL(ℤG)-equivalent to its transpose.

Proof. We will give a 2 × 2 example M. (It is not difficult to verify for this example that M ⊕ I, where I is the infinite identity matrix, is also not equivalent GL(ℤG)-equivalent to its transpose.) Define M, and consequently δ(M) = 2(C, D), as follows:

M = (\begin{matrix}1 & 1 \\ 0 & 2 \end{matrix}) + t (\begin{matrix}1 & −1 \\ 0 & 2 \end{matrix}) ,  C = (\begin{matrix}1 & 0 \\ 0 & 2 \end{matrix}) ,  D = (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix}) .

To show M is not equivalent to its transpose, we suppose there are GL(ℤ) matrices U_{1}, U_{2}, V_{1}, V_{2} such that U_{1} ≡ U_{2} mod 2, V_{1} ≡ V_{2} mod 2, U_{1}CV_{1} = C and U_{2}DV_{2} = D^{t}, and then find a contradiction. First consider the equivalence C = U_{1}CV_{1}:

(\begin{matrix}1 & 0 \\ 0 & 2 \end{matrix}) = (\begin{matrix}a & b \\ c & d \end{matrix}) (\begin{matrix}1 & 0 \\ 0 & 2 \end{matrix}) (\begin{matrix}α & β \\ γ & δ \end{matrix}) = (\begin{matrix}aα + 2bγ & aβ + 2bδ \\ cα + 2dγ & cβ + 2dδ \end{matrix}) .

We see that a and α must be odd, and then also that c and β must be even, and then because the determinants of U_{1} and V_{1} are odd that d and δ must be odd. So we have

U_{1} = (\begin{matrix}1 & ∗ \\ 0 & 1 \end{matrix}) mod 2  and  V_{1} = (\begin{matrix}1 & 0 \\ ∗ & 1 \end{matrix}) mod 2 ,

with ∗ indicating an entry which is not specified mod 2. Consequently, mod 2 we have

U_{2}DV_{2} = U_{1}DV_{1} = (\begin{matrix}1 & ∗ \\ 0 & 1 \end{matrix}) (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix}) (\begin{matrix}1 & 0 \\ ∗ & 1 \end{matrix}) = (\begin{matrix}∗ & 1 \\ 0 & 0 \end{matrix}) ≠ D^{t} .

This contradiction finishes the proof. □

Example 8.7. Let G = ℤ/2. There is a matrix M over ℤG such that M is not GL(ℤG)-equivalent to a triangular matrix. In particular, M is not equivalent to a Smith normal form.

Proof. We will give a 2 × 2 example M. (It is not difficult to verify for this example that M ⊕ I, where I is the infinite identity matrix, is also not equivalent to a triangular matrix.) Set

M = (\begin{matrix}1 & 1 \\ 1 & 2 \end{matrix}) + t (\begin{matrix}1 & −1 \\ −1 & 0 \end{matrix})

so that δ(M) = 2(I, D) where D = (\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}) . Suppose M′ is upper

triangular and GL(ℤG)-equivalent to M. Then δ(M′) = 2(C′, D′) for some matrices C′, D′ over ℤ which are upper triangular. Here C′ must be GL(ℤ)-equivalent to I, so its diagonal entries must be ±1. Let U be a matrix which acts to add a multiple of row 2 to row 1, such that UC′ is diagonal. Let W be a diagonal matrix with diagonal entries from {1, −1} such that W UC′ = I. Note W UD′ is upper triangular. Replace (C′, D′) with (W UC′, W UD′). At this point we have 2(I, D) equivalent to some 2(I, D′′) where D′′ is upper triangular. So, there are GL(2, ℤ) matrices U_{1} ≡ U_{2} mod 2 and V_{1} ≡ V_{2} mod 2 such that U_{1}(2I)V_{1} = 2I and U_{2}(2D′′)V_{2} = 2D. Now V_{1} must equal (U_{1})^{−1} and therefore mod 2 we have D similar to a triangular matrix. This is impossible because the characteristic polynomial of D considered over the field ℤ/2 is irreducible. □

We finish with the proposition mentioned in Section 6.

Proposition 8.8. Suppose G is a finite group, and B is a finitely supported ℕ × ℕ matrix over ℤG. Then I − B is E(ℤG) equivalent to some matrix (I − A)_{∞} over ℤ_{+}G, where A has weight class {G} and A ≫ 0.

Proof. Suppose B is zero outside its upper left n × n corner. Let y denote the sum of all elements in G and let m be a positive integer. Subtract my times row n + 1 from the rows 1, 2, …, n. Then add column n + 1 to the columns 1, 2, …, n. Finally, add row 1 to row n + 1. If m is sufficiently large, we get a matrix I − C for which C is zero except in the upper left (n+1)×(n+1) corner, where every entry of C is greater than y. Let A be the upper left (n + 1) × (n + 1) corner of C. □

9. E(ℤG)-equivalence of injective matrices

Recall, if C is an n × n matrix, then C_{∞} denotes the ℕ × ℕ matrix whose upper left corner is C and which otherwise is equal to the infinite identity matrix. We begin with an easy application of a theorem of Fitting [14]. Recall our convention (2.1) that in this paper a ring means a ring with 1.

Lemma 9.1. Suppose R is a ring, and C and D are injective square matrices over R. Then the following are equivalent.

(1) There exist V ∈ E(R) and U ∈ GL(R) such that UC_{∞}V = D_{∞}.

(2) The R-modules cok(C) and cok(D) are isomorphic.

Proof. We will prove the nontrivial implication, which is (2) ⟹ (1). Let matrices act on row vectors. Suppose C and D are m×m and n×n, respectively. Let e.g. I_{n} denote the n × n identity matrix. Because C and D have isomorphic cokernels, there is an invertible matrix V_{1} such that the matrices

(9.2)  (\begin{matrix}C & 0 \\ 0 & I_{m} \end{matrix}) V_{1} and (\begin{matrix}I_{n} & 0 \\ 0 & D \end{matrix})

have the same image. For this claim we refer to Warfield’s modern (and English) presentation [41, p.1816] of Fitting’s result; it is evident from the proof that the matrix V_{1} can be chosen from E(m + n, R).

Because the displayed matrices are injective with equal image, obviously [14, 41] there exists an invertible matrix U_{1} such that

U_{1} (\begin{matrix}C & 0 \\ 0 & I_{m} \end{matrix}) V_{1} = (\begin{matrix}I_{n} & 0 \\ 0 & D \end{matrix}) .

Finally, let E be a matrix in E(m + n, R) such that

E^{−1} (\begin{matrix}I_{n} & 0 \\ 0 & D \end{matrix}) E = (\begin{matrix}D & 0 \\ 0 & I_{n} \end{matrix})

and set U = (EU_{1})_{∞} and V = (V_{1}E^{−1})_{∞}. □

Remark 9.3. [41, p.1823] For a certain finite group G (the generalized quaternion group of order 32), Swan [40, p.57] found an ideal P, not free as a ℤG module, but still with module isomorphisms ℤG ⊕ ℤG ≅ P ⊕ P ≅ ℤG ⊕ P. This yields 2 × 2 matrices over ℤG with isomorphic cokernels but nonisomorphic kernels. Therefore Lemma 9.1 would be false without the hypothesis of injectivity.

Remark 9.4. An imperfection of Fitting’s general result is that the size of the identity summands in (9.2) depends on the matrices C, D. However, if d is a positive integer in the stable range (defined below) of the ring R, then those summands I_{m}, I_{n} can be chosen with m = n = d, and under some additional conditions on R (for example if R is commutative) this bound can be lowered to d − 1 [41, pp.1822-1823]. When G is a finite group, the Krull dimension (see [26, Ch. 6] for the definition for a not necessarily commutative ring) of the Noetherian ring ℤG is 1 [26, Prop. 6.5.5, p. 211], and consequently 2 is in (and is then easily seen to be the minimum integer in) the stable range of ℤG [26, Thm. 6.7.3, p. 220].

To define stable range, say a row vector (a_{1}, …, a_{n}) over R is a right unimodular row if there are elements x_{i} ∈ R, 1 ≤ i ≤ n, with ∑_{i} a_{i}x_{i} = 1. The stable range of R is the set of positive integers d such that for any right unimodular row (a_{1}, …, a_{n}) with n > d, there exist elements b_{i} ∈ R, 1 ≤ i ≤ n − 1, such that the row (a_{1} + a_{n}b_{1}, …, a_{n−1} + a_{n}b_{n−1}) is again right unimodular.

We pause to isolate for later use a particularly simple statement.

Proposition 9.5. Suppose R is a commutative ring; SK_{1}(R) is trivial; C and D are finite square matrices over R; and C is injective. Then the following are equivalent.

(1) There exist U, V in E(R) such that UC_{∞}V = D_{∞}.

(2) det(C) = det(D) and the R-modules cok(C) and cok(D) are isomorphic.

Proof. We check the nontrivial implication, (2) ⟹ (1). By Lemma 9.1, we have matrices U, V such that UC_{∞}V = D_{∞} with V ∈ E(R). Because det(V) = 1 and det(D) = det(C) ≠ 0, we have also det(U) = 1. Because SK_{1}(R) is trivial, it follows that U and V are in E(R). □

Now we want to observe that injective matrices with a given cokernel isomorphism class are classified up to elementary equivalence by a quotient of K_{1}.

Proposition 9.6. Let R be a ring. Let C be the set of all square injective matrices over R with cokernel module isomorphic to that of a given square injective matrix over R. Let E(C) be the partition of C such that C and D are in the same element of E(C) if C_{∞} and D_{∞} are E(R) equivalent. Then there is a subgroup H of K_{1}(R) such that the following hold.

(1) For any C and D in C, if (U, V) is a GL(R) equivalence from C_{∞} to D_{∞}, i.e. UC_{∞}V = D_{∞}, then there exists an elementary equivalence from C_{∞} to D_{∞} if and only if [UV] ∈ H.

(2) For any C ∈ C, the map GL(R) → C defined by U ↦ UC_{∞} induces a well defined bijection (K_{1}(R))/H → E(C).

(3) If R is commutative, or if R = ℤG with G finite, then H ⊂ SK_{1}(R)

Proof. We write C ∼ D if there is an elementary equivalence from C to D. If U is in GL(n, R), then it is well known that the matrix

(\begin{matrix}U & 0 \\ 0 & U^{−1} \end{matrix}) is in E(2n, R), and therefore that for any n × n matrix C

over R

(\begin{matrix}UC & 0 \\ 0 & I \end{matrix}) ∼ (\begin{matrix}U^{−1} & 0 \\ 0 & U \end{matrix}) (\begin{matrix}UC & 0 \\ 0 & I \end{matrix}) (\begin{matrix}U & 0 \\ 0 & U^{−1} \end{matrix}) ∼ (\begin{matrix}CU & 0 \\ 0 & I \end{matrix}) .

We will use this simple fact repeatedly. From here, we suppress the subscript ∞ and consider all matrices infinite. U and V will denote elements of GL(R). Note, if C ∼ D, then CU ∼ DU and UC ∼ UD, and in particular U(CV) ∼ U(V C). Also, U(V C) ∼ U(CV) = (UC)V ∼ V (UC). Thus UV C ∼ V UC and similarly CUV ∼ CV U.

Choose a matrix C in C and define H_{C} to be the set of U in GL(R) such that UC ∼ C (or equivalently CU ∼ C). If UC ∼ C and V C ∼ C then U(V C) ∼ U(C) ∼ C, and similarly U^{−1}(C) ∼ U^{−1}(UC) = C. Therefore H_{C} is a group. We claim UCV ∼ C if and only if UV ∈ H_{C}. If UV ∈ H_{C}, then UCV ∼ UV C ∼ C. Conversely, if UCV ∼ C, then C ∼ UCV ∼ UV C and thus UV ∈ H_{C}.

Next suppose that D is another element of C. We claim H_{C} = H_{D}. Suppose UDV ∼ D. By Lemma 9.1 there are X, Y in GL(R) such that D = XCY. Thus XCY ∼ UXCY V ∼ XUCV Y, so UCV ∼ C and UV ∈ H_{C}. Similarly, UV ∈ H_{C} implies UDV ∼ D. Thus shows the group H_{C} does not depend on the choice of C from C.

Notice H_{C} contains the commutator of GL(R), since UV CU^{−1}V^{−1} ∼ V UCU^{−1}V^{−1} ∼ C. The commutator is the kernel of the map GL(R) → K_{1}(R). Define H as the image of H_{C} in K_{1}(R). It follows that [U] ∈ H ⟺ U ∈ H_{C}. This proves (1). It then follows that in (2) we have a well defined injection (K_{1}(R))/H → E(C), which is surjective by Lemma 9.1.

To prove (3), suppose [U] ∈ H. Perhaps after passing to another representative of [U], we have E ∈ E(R) such that UC = CE. If R is commutative, the injectivity of C forces det(U) = 1, i.e., [U] ∈ SK_{1}(R). Suppose now that R = ℤG with G finite. Let \overline{U}, \overline{C}, \overline{E} denote the images of U, C, E under the map induced by the inclusion ℤG → ℚG. The injectivity of C implies that \overline{C} is invertible. Now (\overline{C})^{−1}\overline{U}\overline{C} = \overline{E}, which implies that \overline{U} and \overline{E} are E(ℚG) equivalent. In other words,

[U] is in the kernel of the induced map K_{1}(ℤG) → K_{1}(ℚG), and [U] ∈ SK_{1}(R). □

Remark 9.7. In the case of ℤG with G not abelian, we thank Jonathan Rosenberg [35] for the statement and proof of part (3) of Proposition 9.6,

Remark 9.8. In Proposition 9.6, if C contains an element of GL(R), then clearly the group H is trivial. We do not know whether it is possible for H to be nontrivial.

Our main interest in the next result is the case R = ℤG, where G is finite (so, SK_{1}(ℤG) is finite [27]) and abelian. In this case, it is straightforward to check whether a square matrix C over ℤG is injective (examine the matrix for the regular representation or equivalently check whether det(C) is a zero divisor in ℤG). Also in this case, the ℤG module cok(C) is finite if and only if C is injective.

Corollary 9.9. Suppose R is a commutative ring and SK_{1}(R) is finite. Suppose D_{1}, …, D_{k} are finite square matrices over R such that

(1) The modules cok(D_{i}) are isomorphic;

(2) the determinants det(D_{i}) are equal and are not equal to a zero divisor in R; and

(3) for i ≠ j, there is no E(R) equivalence from (D_{i})_{∞} to (D_{j})_{∞}. Then k ≤ |SK_{1}(R)|. □

Remark 9.10. Let G be a subgroup of the positive reals under multiplication, and let A be a finite square matrix A with entries in ℤ_{+}G, with α(A) irreducible. Then A presents the shift of finite type σ_{α(A)} together with an invariant Markov measure, μ_{A} [25, 33]. Let B be another such matrix, and (after the normalizations described in [25]), suppose that I − A and I − B have equal determinant, and that G is the common group of weights over periodic cycles for μ_{A} and μ_{B}. Then [25, 31, 33] there is a measure preserving topological conjugacy (σ_{α(A)}, μ_{A}) → (σ_{α(B)}, μ_{B}) if and only if A and B are strong shift equivalent over ℤ_{+}G, if and only if (by [9, Theorem 7.2]) there is a positive equivalence of polynomial matrices from I − tA to I − tB. In this case (after setting t = 1), we get matrices U, V in E(ℤG) such that U(I − A)_{∞}V = (I − B)_{∞}. (In fact, this elementary equivalence class of I − A is also an invariant of stochastic flow equivalence [2].) Bill Parry [30] has asked if the cokernel module of (I − A) is a complete invariant of equivalence over ℤG when det(I − A) is nonzero. The next result, which follows immediately from Proposition 9.5, answers this question in the affirmative.

Proposition 9.11. Suppose R = ℤG where G ≅ ℤ^{n} and A, B are finite square matrices over R and det(I −A) is nonzero. The following are equivalent.

(1) There exist U, V in E(R) such that U(I − A)_{∞}V = (I − B)_{∞}.

(2) det(I − A) = det(I − B) and the R-modules cok(I − A) and cok(I − B) are isomorphic.

Proof. For any commutative ring R, the units group R^{∗} of R is a direct summand of K_{1}(R). The projection from K_{1}(R) to R^{∗} is given by det, and the complementary summand is SK_{1}(R). Let G = ℤ^{n}, and let U denote the set of “obvious” units of ℤG, U = {±g : g ∈ G}. Then the det map on K_{1}(ℤG) is an isomorphism to (ℤG)^{∗}, and moreover (ℤG)^{∗} = U [3]. (The statement of the relevant Corollary in [3, p. 63] shows K_{1}(ℤG) ≅ ℤ/2 ⊕ ℤ^{n}. Because U ≅ ℤ/2 ⊕ ℤ^{n}, it follows here that det is injective. That (ℤG)^{∗} = U follows from the construction of the isomorphism proving the Corollary.) Because SK_{1}(ℤG) is trivial, Prop. 9.11 follows from Prop. 9.5. □

References

[1] R. ADLER, B. KITCHENS and B. MARCUS, ‘Almost topological classification of finite-to-one factor maps between shifts of finite type’, Ergodic Theory Dynam. Systems (4) 5 (1985) 485–500.

[2] P. V. ARAUJO, ‘A stochastic analogue of a theorem of Boyle’s on almost flow equivalence’, Ergodic Theory Dynam. Systems (3) 13 (1993) 417–444.

[3] H. BASS, A. HELLER and R. G. SWAN, ‘The Whitehead group of a polynomial extension’, Pub. Math. IHES 22 (1964) 61-79.

[4] R. BOWEN and J. FRANKS, ‘Homology for zero-dimensional basic sets’, Ann. of Math. 106 (1977) 73-92.

[5] M. BOYLE, ‘Symbolic Dynamics and Matrices’, Combinatorical and Graph-Theoretical Problems in Linear Algebra (eds. R. A. Brualdi, S. Friedland and V. Klee), IMA Volumes in Mathematics and its Applications 50 (Springer-Verlag, New York, 1993), pp. 1-38.

[6] M. BOYLE, ‘Positive K-theory and symbolic dynamics’, Dynamics and Randomness (eds. A. Maass, S. Martinez and J. San Martin), Nonlinear Phenomena and Complex Systems 7 (Kluwer, 2002), pp. 31-52.

[7] M. BOYLE, ‘Flow equivalence of shifts of finite type via positive factorizations’, Pacific J. Math. (2) 204 (2002) 273-317.

[8] M. BOYLE and D. HUANG, ‘Poset block equivalence of integral matrices’, Trans. Amer. Math. Soc. 355 (2003) 3861-3886.

[9] M. BOYLE and J. B. WAGONER, ‘Positive algebraic K-theory and shifts of finite type’, Modern Dynamical Systems and Applications (eds. M. Brin, B. Hasselblatt and Y. Pesin, Cambridge University Press, 2004), pp. 45-66.

[10] U. FIEBIG, ‘Periodic points and finite group actions on shifts of finite type’, Ergodic Theory Dynam. Systems (3) 13 (1993) 485-514.

[11] M. FIELD, ‘Equivariant diffeomorphisms hyperbolic transverse to a Gaction’, J. London Math. Soc. (2) 27 (1983) 563-576.

[12] M. FIELD and M. GOLUBITSKY, Symmetry in chaos. A search for pattern in mathematics, art and nature. Corrected reprint of the 1992 original (Oxford University Press, 1995).

[13] M. FIELD and M. NICOL, ‘Ergodic Theory of Equivariant Diffeomorphisms: Markov Partitions and Stable Ergodicity’, Memoirs Amer. Math. Soc. 803 (2004).

[14] H. FITTING, ‘Uber den Zusammenhang zwischen dem Begriff der Gleichartigkeit zweier Ideale und dem Aquivalenz-begriff der Elementarteilertheorie’, Math. Annalen 112 (1936) 572-582.

[15] J. FRANKS, ‘Flow equivalence of subshifts of finite type’, Ergodic Theory Dynam. Systems 4 (1984) 53-66.

[16] R. GURALNICK and L. LEVY, ‘Presentations of modules when ideals need not be principal’, Illinois J. Math. (4) 32 (1988) 593-653.

[17] D. HUANG, ‘Flow equivalence of reducible shifts of finite type’, Ergodic Theory Dynam. Systems 14 (1994) 695-720.

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

[19] D. HUANG, ‘The classification of two-component Cuntz-Krieger algebras’, Proc. Amer. Math. Soc. (2) 124 (1996) 505-512.

[20] D. HUANG, ‘Automorphisms of Bowen-Franks groups for shifts of finite type’, Ergodic Theory Dynam. Systems 21 (2001) 1113-1137.

[21] K. H. KIM and F. W. ROUSH, ‘Free Z_{p} actions on subshifts’, Pure Math. Appl. (2-4) 8 (1997) 293-322.

[22] K. H. KIM, F. W. ROUSH and J. B. WAGONER, ‘Characterization of inert actions on periodic points, Part I and Part II’, Forum Math. 12 (2000), 565-602 and 671-712.

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

[24] D.LIND and B. MARCUS, An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, 1995).

[25] B. MARCUS and S. TUNCEL, ‘The weight-per-symbol polytope and embeddings of Markov chains’, Ergodic Theory Dynam. Systems 11 (1991) 129-180.

[26] J. C. MCCONNELL and J. C. ROBSON, Noncommutative Noetherian rings, Revised edition, Graduate Studies in Math. 30 (American Math. Soc., Providence, 2001).

[27] R. OLIVER, Whitehead groups of finite groups, London Math. Soc. Lecture Note Ser. 132 (Cambridge Univ. Press, 1988).

[28] W. PARRY, ‘Notes on coding problems for finite state processes’, Bull. London Math. Soc. (1) 23 (1991) 1-33.

[29] W. PARRY, ‘The Livšic periodic point theorem for non-abelian cocycles’, Ergodic Theory Dynam. Systems 19 (1999) 687-701.

[30] W. PARRY, personal communication (2001).

[31] W. PARRY and K. SCHMIDT ‘Natural coefficients and invariants for Markov-shifts’, Invent. Math. (1) 76 (1984) 15-32.

[32] W. PARRY and D. SULLIVAN, ‘A topological invariant for flows on onedimensional spaces’, Topology 14 (1975) 297-299.

[33] W. PARRY and S. TUNCEL, ‘On the stochastic and topological structure of Markov chains’, Bull. London Math. Soc. (1) 14 (1982) 16-27.

[34] J. ROSENBERG, Algebraic K-theory and Its Applications (Springer-Verlag, 1994).

[35] J. ROSENBERG, personal communication (2004).

[36] K. SCHMIDT, ‘Remarks on Livšic’ theory for nonabelian cocycles’, Ergodic Theory Dynam. Systems 19 (1999) 703-721.

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

[38] M. SULLIVAN, ‘Invariants of twist-wise flow equivalence’, Electron. Res. Announc. Amer. Math. Soc. 3 (1997) 126–130.

[39] M. SULLIVAN, ‘Invariants of twist-wise flow equivalence’, Discrete Contin. Dynam. Systems (3) 4 (1998) 475–484.

[40] R. G. SWAN, ‘Projective modules over group rings and maximal orders’, Ann. of Math. (2) 76 (1962) 55-61.

[41] R. B. WARFIELD, ‘Stable equivalence of matrices and resolutions’, Communications in Algebra (17) 6 (1978) 1811-1828.

[42] R. F. WILLIAMS, ‘Classification of subshifts of finite type’, Ann. of Math. 98 (1973) 120–153; Errata Ann. of Math 99 (1974), 380–381.

Department of Mathematics, University of Maryland, College Park, MD 20742-4015

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

Department of Mathematics, Southern Illinois University, Carbondale IL 62901-4408

 E-mail address: msulliva@math.siu.edu
 URL: www.math.siu.edu/sullivan