FLOW EQUIVALENCE OF SHIFTS OF FINITE TYPE VIA POSITIVE FACTORIZATIONS

MIKE BOYLE

Abstract. Together with [BH], this paper gives an alternate development of the Huang classification of shifts of finite type up to flow equivalence, and provides additional functorial information, used to analyze the action of the mapping class group of the mapping torus of a shift of finite type on the “isotopy futures” group, which is introduced here. For a shift of finite type σ_{A}, this group is isomorphic to the Bowen-Franks group cok(I−A). The action on the isotopy futures group of a subshift is the flow equivalence analogue of the dimension group representation.

Contents

1. Introduction 1 2. Definitions 4 2.1. Poset blocked matrices 4 2.2. Positive equivalence. 5 2.3. Cycle components. 7 3. Statement of results 8 4. Factorization: the proof 9 5. Factorization: the positive case 14 6. Flow equivalence 19 7. The mapping class group 22 Appendix A. Reduction to nondegenerate form 28 References 35

1. Introduction

Shifts of finite type (SFTs) are the fundamental building blocks of symbolic dynamics, with applications to hyperbolic dynamics, ergodic theory, topological dynamics, matrix theory and other areas [Bow, DGS, Ki, LM, Rob, S]. Any SFT is conjugate to an SFT σ_{A} defined by a matrix A with nonnegative integer entries. A fundamental question about SFTs, when are they flow equivalent, is important also for the study of certain C^{∗}-algebras [C, CK, H2, H3, R]. This question was solved in the irreducible case by Franks [F], extending earlier work of Parry and Sullivan [PS] and Bowen and Franks [BowF], and then in the general case by Huang [H4, H5], following earlier work on more tractable special cases [H1, H3]. Huang [H4, H5] developed complete algebraic invariants (defined in terms of the given matrix A) for flow equivalence of SFTs.

Date: November 27, 2000.

2000 Mathematics Subject Classification. Primary: 37B10; Secondary: 06A11, 15A21, 15A36, 37D20, 46L35.

Key words and phrases. block, equivalence, poset, integral matrix, shift of finite type, reducible, flow equivalence, Cuntz-Krieger, positive.

The research of the author was supported by NSF Grant DMS9706852.

This paper has three main features.

(1) Taken together with [BH], the paper gives a self-contained alternate development of the Huang classification of SFTs up to flow equivalence. This development separates algebraic and positivity issues, and provides additional functorial information.

(2) We introduce the isotopy futures group F_{S} of the mapping torus Y_{S} of a subshift S, and when S is an SFT σ_{A} we construct an isomorphism of F_{S} and the Bowen-Franks group cok(I − A), and analyze the induced action of the mapping class group of Y_{S} on F_{S}.

(3) We integrate the study of flow equivalence of SFTs into the “positive Ktheory” framework for classification problems in symbolic dynamics.

We now discuss these features in more detail.

1. To study reducible SFTs, we work with certain infinite block triangular integral matrices with block rows and columns indexed by a finite poset P: if i ⪯̸ j in P, then the ij block of the matrix must be zero. The elements of P, and their ordering, correspond to the irreducible components of the SFT, and their asymptotic transitions; the isomorphism class of the poset P is an invariant of flow equivalence. We say two such matrices B, B′ are SL_{P}(ℤ) equivalent if there are matrices U, V satisfying the same zero-subblock conditions, and with all diagonal blocks having determinant 1, such that UBV = B′. After fixing a choice of P, and allowing a permutation of P, we show that A, A′ define flow equivalent SFTs if and only if the matrices I−A and I−A′ are SL_{P}(ℤ) equivalent by an equivalence which is “positive on cycle components”(a technical condition which may be removed after reduction to a standard form, see Theorem 3.4). The key to this result is the Factorization Theorem 3.3, which gives necessary and sufficient conditions for an SL_{P}(ℤ) equivalence to be a composition of “positive” elementary equivalences (which induce flow equivalences). Complete algebraic invariants for SL_{P}(ℤ) equivalence are contained in the joint work [BH] with Danrun Huang. (The proofs in the current paper are very different from those of Huang [H4, H5], but the algebraic sequel [BH] depends completely on the ideas introduced by Huang in [H4, H5].)

In Huang’s development, the proofs involve creating positive matrix models realizing given isomorphisms of an associated “K-web” of exact sequences of associated groups; the difficult positivity and algebraic issues are intertwined. By interposing the SL_{P}(ℤ) equivalence relation between the SFTs and the complicated K-web algebraic invariants, we separate the positivity issues (which we address in this paper) from purely algebraic issues (which are addressed in [BH]). This clarifies the meaning of the invariants and the structure of the problem. It also facilitates the application of algebraic results.

2. The analysis of the induced action on cok(I − A) uses the Factorization Theorem 3.3 together with purely algebraic results from [BH] on SL_{P}(ℤ) equivalence. There is a plausible program (7.15) for extending these ideas to obtain more information.

It seems to be nontrivial to construct a functor which attaches isomorphisms of Bowen-Franks groups to isotopy classes of flow equivalences of SFTs. (For example, we do not know if it is possible to construct a homomorphism from Ȟ^{1}(Y_{σ_{A}}) onto the Bowen-Franks group cok(I − A) such that the natural action of the mapping class group on Ȟ^{1}(Y_{σ_{A}}) induces an automorphism of cok(I − A); and we suspect there is no such homomorphism.) An alternate approach using work of Badoian is discussed at the end of Section 7. Another possible approach would be to extend ideas of Bowen and Franks, who computed cok(I −A) as a relative homology group in the context of basic sets of Smale flows ([BowF, F]).

3. In the framework of positive K-theory (a term introduced by Wagoner), some class of matrices A presents some category of dynamical system, and multiplication of I − A by elementary matrices satisfying some positivity condition induces isomorphisms of the system presented by A. This framework was born in [KRW2, KRW3], where matrices over tℤ_{+}[t] presented SFTs, and multiplication of I − A by certain elementary matrices over ℤ[t] gave a completely new method of constructing topological conjugacies, which allowed the solution of a difficult and important open problem. This framework for SFT’s is developed or exploited further in [BW, B1, KR1, W2]; in the last reference [W2], the K-theory connection is more than a formal analogy and gives new counterexamples to Williams’ shift equivalence conjecture. In [G], the matrix entries lie in a certain ring of formal power series, and the elementary matrix multiplications induce good finitary isomorphisms of Markov chains. In this paper and in [Ba1], the matrices have integer (or zero-one) entries, and the elementary multiplications induce flow equivalences. There is a passage from the topological conjugacy case to the flow equivalence case by “setting t equal to 1” (applying the coinvariants functor), as described in [B1]. The positive K-theory approach gives a unified and useful framework for classification problems in symbolic dynamics, and we view this paper as a significant piece of the theory for the case of flow equivalence of SFTs. It is possible that the methods of this paper may be suggestive for the case of topological conjugacy of SFTs.

Some of our results on flow equivalence have alternate proofs based on the work of Leslie Badoian [Ba1], who develops for irreducible SFTs a flow equivalence theory analogous to the theory created by Wagoner for topological conjugacies of SFTs. At the end of Section 7, we summarize the main results of [Ba1], and discuss those alternate proofs.

Now some words on the structure of the paper. In Section 2 we give some definitions and technical results necessary for the statement of the main results in Section 3. The proof of the Factorization Theorem is carried out in Sections 4-5 and the Appendix. Shifts of finite type and the relation of flow equivalence to the matrix results are addressed in Section 6. The isotopy futures group and connections to flow equivalence are studied in Section 7. For the simple general statement of our Factorization Theorem for matrices, we need preliminary technical arguments to reduce our matrices to a nondegenerate form. These preliminaries are complicated, and we banish them to an appendix.

The basic approach of this paper, and the Factorization Theorem in the “no cycle components”case under additional technical assumptions since removed, were announced in [B1].

I thank Danrun Huang for many helpful comments, and for a very satisfying collaboration in our sequel paper [BH]. Also, without his earlier work, this paper would not exist.

2. Definitions

2.1. Poset blocked matrices. For the rest of the paper, we let P = {1, ..., N} denote a finite poset (partially ordered set). We describe the order with a relation ≺ satisfying the following conditions (in which < refers to the usual order on ℕ) for all i, j, k in P:

i ≺ j ⟹ i < j ,
i ≺ j ≺ k ⟹ i ≺ k

We write i ⪯ j to mean that i ≺ j or i = j. We can visualize the poset as an acyclic directed graph with vertex set {1, ..., N} and transitions i → j iff i ≺ j.

We say that a matrix (or a block in a matrix) is square if its rows and columns are indexed by the same set (which may be finite or countably infinite). Suppose that n_{1}, …, n_{N} lie in the set {1, 2, …, ∞}. Let n = (n_{1}, …, n_{N}). We say a square matrix M is “n-blocked” if it splits into blocks M_{ij}, 1 ≤ i, j ≤ N, where M_{ij} denotes the intersection of the ith block row and the jth block column, and has size n_{i} ×n_{j}. (We will also use the notation M{i, j} to denote M_{ij}.) Given an n-blocked matrix M, we let I_{j} denote the set of indices for rows/columns through the block M_{jj}.

Definition 2.1. 𝔐_{P}(n, ℤ) is the set of n-blocked matrices with entries in ℤ satisfying the following conditions:

(1) For 1 ≤ i ≤ N, the block M_{ii} equals the identity matrix in all but finitely many entries.

(2) For 1 ≤ i, j ≤ N and i ≠ j, the block M_{ij} is zero in all but finitely many entries.

(3) If i ⪯̸ j, then the block M_{ij} is zero.

The matrices in the semiring 𝔐_{P}(n, ℤ) are block upper triangular and in addition certain blocks above the diagonal must be zero. 𝔐_{P}(n, ℤ) is closed under addition and (because ≺ is transitive) under matrix multiplication.

A nonnegative matrix A is irreducible if it is square with all entries nonnegative, and for every (i, j) there exists n > 0 such that A^{n}(i, j) > 0. (In particular, for us a zero matrix is not irreducible.) A square matrix is essentially irreducible if it has a unique principal submatrix which is irreducible and which is contained in no larger irreducible principal submatrix.

Definition 2.2. 𝔐_{P,+}^{∘}(n, ℤ) is the set of n-blocked nonnegative integral matrices with only finitely many nonzero entries, satisfying the following conditions:

(1) Each diagonal block M_{ii} is essentially irreducible.

(2) If i ⪯̸ j, then the block M_{ij} is zero.

(3) If i ≺ j, then there is an index i′ occuring on a cycle of M_{ii} and an index j′ occuring on a cycle of M_{jj} and a positive integer n, such that A^{n}(i′, j′) > 0.

Definition 2.3. SL_{P}(n, ℤ) is the set of matrices M in 𝔐_{P}(n, ℤ) such that det(M_{ii}) = 1 for 1 ≤ i ≤ N.

Abbreviations 2.4. 𝔐_{P}(ℤ), 𝔐_{P,+}^{∘}(ℤ) and SL_{P}(ℤ) denote the sets 𝔐_{P}(n, ℤ), 𝔐_{P,+}^{∘}(n, ℤ) and SL_{P}(n, ℤ) for which n = (n_{1}, …, n_{N}) with every n_{i} = ∞. Whenever any such matrix family appears with no subscript P, it means that P = {1} (the block structure is trivial).

We say two matrices B, B′ in 𝔐_{P}(n, ℤ) are SL_{P}(n, ℤ)-equivalent in 𝔐_{P}(n, ℤ) if there are matrices U, V in SL_{P}(n, ℤ) such that UBV = B′, and we write this as (U, V): B → B′. We say a matrix is a basic elementary matrix if it equals the identity matrix except in at most one offdiagonal entry. It is not difficult to check that SL_{P}(n, ℤ) is a group under multiplication which is generated by basic elementary matrices [BH]. Given n ≤ r, we have natural truncation and embedding maps between n-blocked and r-blocked matrices,

tru_{n} : 𝔐_{P}(r, ℤ) → 𝔐_{P}(n, ℤ) ,
ι_{r} : 𝔐_{P}(n, ℤ) → 𝔐_{P}(r, ℤ) .

The truncation map replaces an ij block with its n_{i} × n_{j} upper left corner. The embedding map embeds an ij block as the upper left corner of an ij block. If i ≠ j, then the image ij block is zero outside this embedded left corner; if i = j, it is the identity outside this left corner. We will use A_{∞} to abbreviate ι_{n}(A) in the case that every n_{i} = ∞. We will also use tru_{n}, ι_{r} and A_{∞} for matrix families other than 𝔐_{P}. The only potentially ambiguous point, which should be clear from context, is whether the embedded block corners should be extended as above with 𝔐_{P} to match the identity matrix, or should be extended to match the zero matrix (e.g. when the range is 𝔐_{P,+}^{∘}).

2.2. Positive equivalence. Suppose for some (i, j) that E is a basic elementary matrix with offdiagonal entry E(i, j) = 1, A ∈ 𝔐_{P,+}^{∘}(n, ℤ), and A(i, j) > 0. 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 in I − 𝔐_{P,+}^{∘}(n, ℤ). Note, E ∈ SL_{P}(n, ℤ). We say that an SL_{P}(n, ℤ) equivalence is a positive equivalence in I − 𝔐_{P,+}^{∘}(n, ℤ) if it is a composition of basic positive equivalences in I − 𝔐_{P,+}^{∘}(n, ℤ).

To understand the meaning of a basic positive equivalence, suppose A ∈ 𝔐_{P,+}^{∘}(n, ℤ) with A(i, j) > 0 and E is basic elementary matrix with offdiagonal entry E(i, j) = 1. We first discuss the case (E, I): (I − A) → E(I − A). Define A′ by the requirement E(I − A) = (I − A′). Then A and A′ agree except perhaps in row i, where

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

View A as the adjacency matrix of a directed graph G_{A} with edge set E_{A} and vertex set given by the n_{1} + ⋯ + n_{N} indices for the rows/columns of A. (There can be edges joining only finitely many of those vertices.) We can describe a directed graph G_{A′} which has A′ as its adjacency matrix as follows. G_{A′} has the same vertex set as G_{A}. Now pick an edge e which runs from vertex i to vertex j in G_{A} (e exists because by assumption A(i, j) > 0). The edge set E_{A′} will be derived from E_{A} as follows: remove e from E_{A}; and then for every vertex k, for every edge f in E_{A} from j to k add in a new edge (named [ef]) from i to k. It is easy to verify that with this edge set E_{A′}, the directed graph G_{A′} has adjacency matrix A′.

With this notation, now define a map γ: E_{A′} → (E_{A})^{∗} by γ: f ↦ f and γ: [ef] ↦ ef. Then γ induces an injective map (also called γ), from the set Σ_{A′} of biinfinite paths through G_{A′} to the set Σ_{A} of biinfinite paths through G_{A}, sending x′ to x by the rule

γ: … x′_{−2}x′_{−1}|x′_{0}x′_{1} … ↦ … γ(x′_{−2})γ(x′_{−1})|γ(x′_{0})γ(x′_{1}) …

(in which the placement of the vertical bar indicates the indexing for x, e.g. x_{0}x_{1} ⋯ = γ(x′_{0})γ(x′_{1}) …). Briefly: we get x from x′ by replacing each A′ edge [ef] with ef.

The injective map γ: Σ_{A′} → Σ_{A} is not surjective precisely because the image will not contain points x for which x_{−1} = e (the image will contain the shifted point σ^{−1}x which is defined by (σ^{−1}x)_{i} = x_{i−1}). However, although γ is generally not a bijection, it does induce a bijection of orbits (under the shift) in Σ_{A} and Σ_{A′}. Also, γ induces a bijection of finite orbits: that is, γ induces a bijection (also called γ) of cycles in G_{A} and G_{A′} (which need not respect the cycle length). If 1 ≤ t ≤ N and c is a cycle for the block A_{tt}, then γ(c) is a cycle for A′_{tt}, because if i and j are not indices for the same component then γ is the identity on cycles. Also, if x in Σ_{A} is backwardly asymptotic (under the shift) to a cycle c and forwardly asymptotic to a cycle c̃, then γ(x) is backwardly asymptotic to γ(c) and forwardly asymptotic to γ(c̃). It follows that the matrix A′ satisfies the conditions of Definition 2.2 and lies in 𝔐_{P,+}^{∘}(n, ℤ) .

The discussion of the case (I, E): (I − A) → (I − A)E = (I − A′) is much the same. Let f be an A-edge from i to j. To form the A′ graph from the A graph in this case, delete f, and add a new edge [ef] for each edge e with terminal vertex i. Then define γ as before.

The following lemma, fundamental to the sequel, is implicit in Franks’ paper [F].

Lemma 2.5. Suppose A ∈ 𝔐_{P,+}^{∘}(n, ℤ), E is a basic elementary matrix in SL_{P}(n, ℤ) whose nonzero offdiagonal entry is E(i, j) = 1, and there is a positive integer k such that A^{k}(i, j) > 0.

(1) If (E(I − A))(i, j) ≤ 0, then (E, I): (I − A) → E(I − A) is a positive

equivalence in I − 𝔐_{P,+}^{∘}(n, ℤ) .

(2) If ((I − A)E)(i, j) ≤ 0, then (I, E): (I − A) → (I − A)E is a positive

equivalence in I − 𝔐_{P,+}^{∘}(n, ℤ) .

Proof. We will consider the claim for the first equivalence (E, I); the other case is similar. By assumption, there is a list i = i_{0}, i_{1}, ..., i_{k} = j (which we take to be of minimal length, so the indices i_{0}, i_{1}, ..., i_{k} are distinct) such that for 0 ≤ t < k we have A(i_{t}, i_{t+1}) > 0. If k = 1, then the equivalence is a basic positive equivalence (and we know a basic positive equivalence takes a matrix in I − 𝔐_{P,+}^{∘}(n, ℤ) to a matrix in I − 𝔐_{P,+}^{∘}(n, ℤ) ). So suppose k > 1. Let F_{t} be the elementary matrix whose which acts to add row i_{t} to row i. Let F = F_{k−1} … F_{1}. Then we have basic positive equivalences

(I − A) → F_{1}(I − A) → F_{2}F_{1}(I − A) → ⋯ → (F_{k−1} ⋯ F_{2}F_{1})(I − A)
= F (I − A) → EF (I − A) → (F_{k−1})^{−1}EF (I − A)
→ ⋯ → (F_{1})^{−1} ⋯ (F_{k−2})^{−1}(F_{k−1})^{−1}EF (I − A)
= F^{−1}EF (I − A) = E(I − A) .
□

2.3. Cycle components. The technical discussion of this subsection is only required for the case when the matrix A in 𝔐_{P,+}^{∘}(n, ℤ) has a diagonal block whose maximal irreducible submatrix is a permutation matrix.

Lemma 2.6. Suppose A is an S × S nonnegative integral matrix which has as its unique irreducible submatrix a cyclic permutation matrix. Then the cokernel group cok(I − A) = ℤ^{S}/(I − A)ℤ^{S} is isomorphic to ℤ. Let I denote the set of indices involved in the cyclic permutation. Then the canonical basis vectors satisfy the following conditions.

(1) [e_{i}] is a generator of cok(I − A) if i ∈ I.

(2) [e_{i}] = [e_{j}] if i and j are in I.
(3) [e_{i}] = 0 if i ∉ I.

Proof. (3) If i ∉ I, then for large n, A^{n}e_{i} = 0, and e_{i} = (I − A^{n})e_{i} = (I − A)(I + A + ⋯ + A^{n−1})e_{i}. Then [e_{i}] = 0 in cok(I − A).

(2) Let π denote the given permutation and suppose i and j are in I. Then there exists n > 0 such that A^{n}e_{i} = e_{j}, so in cok(I − A) we have [e_{i}] − [e_{j}] = [e_{i} − e_{j}] = [(I − A^{n})e_{i}] = 0.

(1) Clearly now, if i ∈ I, then [e_{i}] generates cok(I − A). Also, because det(I − A) = 0, ℤ is a subgroup of cok(I − A). Therefore cok(I − A) ≅ ℤ. □

For a matrix A satisfying the hypotheses of the lemma, we make cok(I − A) an ordered group by declaring its positive set to be the collection of those [w] such that (in the notation of the statement of the lemma) ∑_{i∈I} w_{i} ≥ 0. (This sum does not depend on the representative w of [w].) We say an isomorphism between two such cokernel groups is positive if it takes the positive set in the domain to the positive set in the range.

If A ∈ 𝔐_{P,+}^{∘}(n, ℤ), then for 1 ≤ i ≤ N the diagonal block A_{ii} contains a unique maximal irreducible principal submatrix. If this matrix is a permutation matrix, then we say that i is a cycle component of A. We let C_{A} denote the set of cycle components of A. For each i in C_{A}, we make the cokernel group

cok(I − A)_{ii} = ℤ^{n_{i}}/(I − A)_{ii}Z^{n_{i}} ≅ ℤ

an ordered group as described above. For A and A′ in 𝔐_{P,+}^{∘}(n, ℤ), if (U, V) is an SL_{P}(ℤ) equivalence from A to A′, then for 1 ≤ i ≤ N the equivalence (U, V) induces an SL(ℤ) equivalence (U_{ii}, V_{ii}) from A_{ii} to A′_{ii}, and this induces an isomorphism from cok(I − A)_{ii} to cok(I − A′)_{ii} by the rule [x] ↦ [U_{ii}x]. We say that the SL_{P}(ℤ) equivalence (U, V) is positive on cycle components if this induced isomorphism of the ith component cokernel groups is positive whenever i is a cycle component for both A and A′. For example, if

A_{ii} = A′_{ii} = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) and U_{ii} = V_{ii} = (\begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix}) ,

then (U, V) is not positive on cycle components.

Proposition 2.7. Suppose (U, V) is a positive SL_{P}(n, ℤ) equivalence from (I − A) to (I − A′) in I − 𝔐_{P,+}^{∘}(n, ℤ). Then

(1) A and A′ have the same cycle components, and

(2) (U, V) is positive on cycle components.

Proof. It suffices to consider the case (U, V) = (E, I) where E is a basic elementary matrix with offdiagonal entry E(i_{1}, j_{1}) = 1 such that i_{1} and j_{1} index rows through A_{ii} and i is a cycle component of A.

(1) It is clear from the earlier discussion on positive equivalence that the ith component of A has a unique cycle iff the ith component of A′ has a unique cycle.

(2) For any canonical basis vector e_{s}, the vector Ee_{s} is nonnegative because E is nonnegative. It follows that (E, I) must be positive on components. □

3. Statement of results

In this section we state the main results (Theorem 3.1 and Theorem 3.3) which do not involve the mapping class group. We also give Theorems 3.4 and 3.5, which clarify computational issues. The definition of flow equivalence is given in Section 6, and all discussion of the mapping class group results is deferred to Section 7.

We need a little more notation. Given P, we will use the same index set I^{P}, a disjoint union of countably infinite sets I_{p}^{P}, p ∈ P, for all matrices with P × P blocking into infinite subblocks. Given finite posets P, P′, let Iso[P, P′] be the set of poset isomorphisms from P to P′. For each ν in Iso[P, P′], fix an infinite permutation matrix P = P_{ν} such that

P (i, j) = 1 and j ∈ I_{p}^{P} ⇒ i ∈ I_{ν(p)}^{P′} .

Informally, a block P {p, q} is zero if q ≠ ν(p) and is the (infinite) identity matrix if q = ν(p).

Theorem 3.1 (Classification Theorem). Suppose A is in 𝔐_{P,+}^{∘}(ℤ) and A′ is in 𝔐_{P′,+}^{∘}(ℤ). The following are equivalent.

(1) The SFTs σ_{A} and σ_{A′} are flow equivalent.

(2) For some ν ∈ Iso[P, P′], with P = P_{ν}: there exists a positive SL_{P}(ℤ) equivalence from (I − A) to (I − P^{−1}A′P) in I − 𝔐_{P,+}^{∘}(ℤ).

(3) For some ν ∈ Iso[P, P′], with P = P_{ν}: A and P^{−1}A′P have the same cycle components, and there exists an SL_{P}(ℤ) equivalence from (I − A) to (I − P^{−1}A′P) which is positive on cycle components.

Remarks 3.2.

(1) There are only finitely many automorphisms ν: P → P′, and they are easily computed. So, we can decide (3) in Theorem 3.1 if we can decide it in the case where P = I and P = P′.

(2) The content of Theorem 3.1 is contained in [H4, H5]. We will prove the equivalence (1) ⟺ (2) in Section 6. The implication (2) ⟹ (3) is trivial. The implication (3) ⟹ (2) follows from the main contribution of this paper, which is the next theorem.

Theorem 3.3 (Factorization Theorem). Suppose A and A′ are in 𝔐_{P,+}^{∘}(ℤ), and (U, V): (I − A) → (I − A′) is an SL_{P}(ℤ) equivalence. The following are equivalent.

(1) (U, V): (I −A) → (I −A′) is a positive SL_{P}(ℤ) equivalence in I −𝔐_{P,+}^{∘}(ℤ).

(2) A and A′ have the same cycle components, and (U, V) is positive on cycle components.

Below, given a matrix A in any 𝔐_{P,+}^{∘}(n, ℤ), we let A_{∞} denote its embedding in 𝔐_{P,+}^{∘}(ℤ).

Theorem 3.4. Suppose A and A′ are in 𝔐_{P,+}^{∘}(n, ℤ), where n = (n_{1}, …, n_{N}) and the following hold for 1 ≤ i ≤ N:

• n_{i} = 1 ⇔ i is a cycle component of A ⇔ i is a cycle component of A′,

• n_{i} = 1 or n_{i} = ∞.

Then the following are equivalent.

(1) There exists a positive SL_{P}(ℤ) equivalence from (I − A_{∞}) to (I − A′_{∞}) in I − 𝔐_{P,+}^{∘}(ℤ).

(2) (I − A) and (I − A′) are SL_{P}(n, ℤ) equivalent.

Proof of Theorem 3.4. (2) ⟹ (1) Suppose (U, V) is the SL_{P}(n, ℤ) equivalence. If n_{i} = 1, then U_{ii} = V_{ii} = 1 because {U, V } ⊂ SL_{P}(n, ℤ). So, the embeddings of U and V in SL_{P}(ℤ) give an SL_{P}(ℤ) equivalence (I −A_{∞}) → (I −A′_{∞}) in I −𝔐_{P,+}^{∘}(ℤ) which is positive on cycle components.

(1) ⟹ (2) This follows from Lemmas A.3 and A.7. □

The point of Theorem 3.4 is to give a flow equivalence criterion in terms of just SL_{P}(n, ℤ) equivalence (which is characterized in [BH]), without a “positive on cycle components” condition. Given matrices A_{1} and A′_{1} in 𝔐_{P,+}^{∘}(n, ℤ), Lemmas A.1 and A.2 give us positive equivalences, from I − A_{1} to I − A and from I − A′_{1} to I − A′, such that A_{∞} and A′_{∞} are of the form described in Theorem 3.4.

Theorem 3.5. [BH] Suppose B and B′ are matrices in 𝔐_{P}(n, ℤ) such that for each diagonal block in B or B′, the greatest common divisor of the entries of the block is 1. Suppose n ≤ r, and let ι be the embedding of 𝔐_{P}(n, ℤ) into 𝔐_{P}(r, ℤ).

Then B is SL_{P}(n, ℤ) equivalent to B′ if and only if ιB is SL_{P}(r, ℤ) equivalent to ιB′.

Theorem 3.5, taken from the Stabilization result in [BH], reduces the problem of SL_{P}(ℤ) equivalence of the matrices (I − A) and (I − A′) in Theorem 3.4 to an equivalence problem for finite matrices.

4. Factorization: the proof

To begin, we describe a matrix class in which our positivity considerations will be simplified.

Definition 4.1. Given a subset C of {1, …, N}, and a vector n with positive integer entries such that n_{i} = 1 if i ∈ C, define 𝔐_{P}^{++}(C, n, ℤ) to be the set of n-blocked integral matrices M whose blocks M_{ij} satisfy the following conditions:

• M_{ii} = 0 if i ∈ C,
• M_{ij} = 0 if i ≠ j and i ⊀ j,
• M_{ij} > 0 otherwise.

(So, each block of M has all entries zero or all entries greater than zero, M_{ii} = 0 when i ∈ C, and otherwise M_{ij} > 0 if and only if i ⪯ j. If −M = I − A, then C is the set of cycle components of A.)

Definition 4.2. An elementary positive equivalence in 𝔐_{P}^{++}(C, n, ℤ) is an SL_{P}(n, ℤ) equivalence (U, V): B → B′ = UBV such that {B, B′} ⊂ 𝔐_{P}^{++}(C, n, ℤ); one of U, V equals Id; and the other is a basic elementary matrix. A positive equivalence in 𝔐_{P}^{++}(C, n, ℤ) is a composition of elementary positive equivalences in 𝔐_{P}^{++}(C, n, ℤ). For such an equivalence (U, V), we use notations such as

(U, V): B ⟶_{+} B′ or B ⟶_{+}^{(U,V)} B′ or B ⟶_{+} B′ .

Observation 4.3. Suppose B = (A − I), B′ = (A′ − I) and

(U, V): B ⟶_{+} B′ .

Then (U, V): (I − A) → (I − A′) is a positive equivalence in 𝔐_{P,+}^{∘}(n, ℤ).

Outline of the proof. Now we can give an outline of the proof of the Factorization Theorem (3.3), which we break into four steps.

Step 1 of the proof (“block positive reduction”) is to reduce it to proving the following theorem:

Theorem 4.4. Suppose B = A − I and B′ = A′ − I, satisfying

• B and B′ are in 𝔐_{P}^{++}(C, n, ℤ)
• (U, V): B → B′ is an SL(n, ℤ) equivalence
• if i ∉ C, then dim(ker(A_{ii})) ≥ 2.

Then

(U, V): B ⟶_{+} B′ .

Step 2 (“the positive case”) is to prove Theorem 4.4 in the case B and B′ are positive (i.e. P = {1} and C = ∅). This step is the heart of the proof and it is carried out in Section 5. This is the only step which uses the condition dim(ker(A_{ii})) ≥ 2.

Step 3 (“the unipotent case”) is to prove Theorem 4.4 in the case that U and V lie in U_{P}(n, ℤ), where U_{P}(n, ℤ) denotes the set of matrices M in SL_{P}(n, ℤ) such that M_{ii} = I for all i in P.

Step 4 (“the general case”) is to finish the proof of Theorem 4.4.

Step 1: Block positive reduction. We will accomplish this step by proving the following proposition. Let C_{A} = C denote the set of cycle components of A. For each cycle component i, let C_{i}^{sec} denote the set of indices for rows/columns through A_{ii} such that i does not lie on a cycle, and let C_{i}^{prim} denote the set of indices i for rows/columns through A_{ii} which lie on the unique cycle in A_{ii}. Let C^{prim} = ∪C_{i}^{prim} and C^{sec} = ∪C_{i}^{sec}.

Proposition 4.5. Suppose {A, A′} ⊂ 𝔐_{P,+}^{∘}(n, ℤ); C_{A} = C_{A′} = C; (U, V): (I − A) → (I − A′) is an SL_{P}(n, ℤ) equivalence which is positive on cycle components; and n = (n_{1}, … n_{N}) has positive integer entries. Then there is a commuting diagram of SL_{P}(n, ℤ) equivalences

(I − A) ⟶ (I − \overline{A})
(U,V)↓  ↓^{(\overline{U},\overline{V})}
(I − A′) ⟶ (I − \overline{A}′)

such that

(1) The horizontal arrows are positive SL_{P}(n, ℤ) equivalences in 𝔐_{P,+}^{∘}(n, ℤ).

(2) For both \overline{A} and \overline{A}′, the principal submatrix indexed by the complement of C^{sec} is strictly positive wherever the P ordering permits a nonzero entry, and in addition the diagonal blocks (\overline{A} − I)_{tt} and (\overline{A}′ − I)_{tt} are strictly positive whenever t ∉ C.

(3) For both \overline{A} and \overline{A}′, C^{prim} is the set of indices ℓ such that for some i ∈ C, (ℓ, ℓ) indexes the upper left corner of the ii block.

(4) \overline{A}(i, j) = \overline{A′}(i, j) = 0 whenever \{i, j\} ∩ C^{sec} ≠ ∅.

(5) \overline{U}(i, j) = \overline{V} (i, j) = δ_{ij} whenever \{i, j\} ∩ C^{sec} ≠ ∅.

For matrices \overline{A}, \overline{A}′ in 𝔐_{P,+}^{∘}(n, ℤ), we say an SL_{P}(n, ℤ) equivalence (\overline{U}, \overline{V}): (I − \overline{A}) → (I −\overline{A}′) is nondegenerate if it satisfies the conditions 2,3,4,5 of Proposition 4.5. Note condition 3 implies that \overline{A}(ℓ, ℓ) = 1 if ℓ ∈ C^{prim}.

Let us see that Proposition 4.5 reduces the proof of (2) ⟹ (1) in the Factorization Theorem 3.3 to the proof of Theorem 4.4. Given (I − A), (I − A′) and (U, V) satisfying (2) in the statement of Theorem 3.3, pick a vector n with positive integer entries large enough that

• for all i, j in P, the ij blocks of U, V, I − A and I − A′ agree with δ_{ij}I outside the upper left n_{i} × n_{j} corner, and

• if i ∉ C, then the upper left n_{i} × n_{i} corners of A_{ii} and A′_{ii} have kernels of dimension at least two.

Replace A, A′, U and V with their trunctations to n-blocked matrices. Then it suffices to prove that (U, V): (I − A) → (I − A′) is a positive SL(n, ℤ) equivalence in 𝔐_{P,+}^{∘}(n, ℤ). To do this, first apply Proposition 4.5 to the matrices U, V, A, A′. Then truncate the resulting \overline{U}, \overline{V} , \overline{A}, \overline{A′} by removing all rows and columns indexed by C^{sec}, and call the resulting matrices U, V, A, A′. To finish the proof of the Factorization Theorem 3.3, it suffices to show (U, V): (I − A) → (I − A′) is a positive equivalence, and this now follows by an application of Theorem 4.4 and Observation 4.3.

We want Proposition 4.5 in order to have a completely general result about factoring equivalences into positive equivalences, and in order to see the main arguments more clearly in the less technical setting of 𝔐_{P}^{++}(C, n, ℤ). Because the proof of Proposition 4.5 is tedious (almost entirely on account of technicalities involving cycle components), we relegate the proof of Proposition 4.5 to Appendix A.

Below, we use U_{P} to denote U_{P}(n, ℤ) and we use 𝔐_{P}^{++} to denote 𝔐_{P}^{++}(C, n, ℤ). For i, j in P and B a matrix with a P-indexed block structure, we let B{i, j} denote the ij block of B.

Step 2: the positive case. This is carried out in Section 5.

Step 3: the unipotent case.

Lemma 4.6. Suppose U and V are matrices in U_{P}, B and B′ are in 𝔐_{P}^{++}, and UBV = B′. Then

B ⟶_{+}^{(U,V)} B′ .

Proof. Write U as a product of matrices in U_{P}, U = U_{n} ⋯ U_{1}, where for each U_{t} there is an associated pair (i_{t}, j_{t}), such that the following hold:

• U_{t} = I, except in the block U_{t}{i_{t}, j_{t}}, and
• if s ≠ t, then (i_{s}, j_{s}) ≠ (i_{t}, j_{t}).

Note, whenever i_{s} is an immediate predecessor of j_{s} in P and B{i_{s}, i_{s}} = 0, these conditions imply

(4.7)  (U_{s}B){i_{s}, j_{s}} = B′{i_{s}, j_{s}} .

We claim there are nonnegative matrices Q_{1}, …, Q_{n} in U_{P} such that (with Q = Q_{1} ⋯ Q_{n})

(4.8)  B ⟶_{+}^{(U_{1},Q_{1})} · ⟶_{+}^{(U_{2},Q_{2})} ⋯ ⟶_{+}^{(U_{n},Q_{n})}U_{n} ⋯ U_{1}BQ_{1} ⋯ Q_{n} = UBQ .

To show (4.8), first we will produce Q_{1} such that

B ⟶_{+}^{(U_{1},Q_{1})} U_{1}BQ_{1} .

Denote (i_{1}, j_{1}) as (i, j). Factor U_{1} as U_{1} = U_{1}^{−}U_{1}^{+}, where U_{1}^{−} and U_{1}^{+} equal I outside the {i, j} block, U_{1}^{+}{i, j} is the nonnegative part of U_{1}{i, j}, and U_{1}^{−}{i, j} is the nonpositive part of U_{1}{i, j}. Clearly

(U_{1}^{+}, I): B ⟶_{+} U_{1}^{+}B .

For U_{1}^{−} there are two cases.

CASE I: B{i, i} > 0. We have U_{1}^{−}(U_{1}^{+}B) = U_{1}^{+}B outside blocks {i, k} such that i ≺ j ⪯ k. Because (U_{1}^{+}B){i, i} = B{i, i} > 0, we can pick Q_{1} in U_{P}, with sufficiently large nonnegative entries in such blocks {i, k}, to put U_{1}^{−}(U_{1}^{+}B)Q_{1} into 𝔐_{P}^{++}. Then

U_{1}^{+}B ⟶_{+}^{(I,Q_{1})} U_{1}^{+}BQ_{1} ⟶_{+}^{(U_{1}^{−},I)} U_{1}^{−}U_{1}^{+}BQ_{1} = U_{1}BQ_{1} .

CASE II: B{i, i} = 0. Again, U_{1}^{−}(U_{1}^{+}B) = U_{1}^{+}B outside blocks {i, k} such that i ≺ j ⪯ k. Because B{i, j} > 0, we can choose Q_{1} nonnegative in U_{P} such that for all k satisfying i ≺ j ≺ k, we have U_{1}^{−}(U_{1}^{+}B)Q_{1}{i, k} > 0. (A positive entry in the block Q{j, k} acts here to add a multiple of a column through the {i, j} block to a column in the {i, k} block.) If there is some h such that i ≺ h ≺ j, then suitable positive entries in Q_{1}{h, k} will also achieve U_{1}^{−}(U_{1}^{+}B)Q_{1}{i, j} > 0. If there is no such h, then i is an immediate predecessor of j in P, and by appeal to (4.7) we have

(U_{1}^{−}(U_{1}^{+}B)Q_{1}){i, j} = (U_{1}B){i, j}
= B′{i, j} > 0 .

Therefore

U_{1}^{+}B ⟶_{+}^{(I,Q_{1})} U_{1}^{+}BQ_{1} ⟶_{+}^{(U_{1}^{−},I)} U_{1}BQ_{1}

as required.

Thus in either case we have

B ⟶_{+}^{(U_{1},Q_{1})} U_{1}BQ_{1} ∈ 𝔐_{P}^{++} .

An easy induction on the argument gives (4.8), with

B ⟶_{+}^{(U,Q)} UBQ ∈ 𝔐_{P}^{++} ,

with Q a product of nonnegative elementary matrices in U_{P}. The transposed argument gives a matrix P in U_{P} such that P is a product of nonnegative elementary matrices such that

B′ ⟶_{+}^{(P,V^{−1})} P B′V^{−1} ∈ 𝔐_{P}^{++} .

Then

B ⟶_{+}^{(U,Q)} UBQ ⟶_{+}^{(P,I)} P UBQ = P B′V^{−1}Q ⟵_{+}^{(I,Q)} P B′V^{−1} ⟵_{+}^{(P,V^{−1})} B′

so

(P^{−1}P U, QQ^{−1}V) = (U, V): B ⟶_{+} B′

as required. □

Step 4: the general case.

Lemma 4.9. Suppose i ∉ C, E is a basic elementary matrix in SL_{P}(n, ℤ), E{j, k} = (Id){j, k} when (j, k) ≠ (i, i), {B, B′} ⊂ 𝔐_{P}^{++}(C, n, ℤ) and

(E{i, i}, Id): B{i, i} ⟶_{+} B′{i, i} .

Then there exists V in U_{P} such that

(E, V): B ⟶_{+} B′ .

Similarly, if

(Id, E{i, i}): B{i, i} ⟶_{+} B′{i, i}

then there exists U in U_{P} such that

(U, E): B ⟶_{+} B′ .

Proof. We will consider the equivalence (E, I), the other case is similar. Let E(s, t) be the nonzero offdiagonal entry of E. If E(s, t) = 1, then set V = Id. Now suppose E(s, t) = −1, so E acts from the the left to subtract row t from row s. Then possibly there are nonpositive entries in blocks (EB){i, j} where i ≺ j. To correct for this, pick r an index for a column through the ii block; note that B(s, r) > B(t, r) because (EB){i, i} > 0 by assumption; consider a positive integer M; and let V be the matrix in U_{P} which acts from the right to add column r to column q, M times, for every q indexing a column through an ij block for which i ≺ j. For these q,

(EBV)(s, q) = M(B(s, r) − B(t, r)) + B(s, q) − B(t, q) .

So, if M is large enough, then this gives

B ⟶_{+}^{(I,V)} BV ⟶_{+}^{(E,I)} EBV

as required. □

Proof of the general case. Now let (U, V): B → B′ be the SL_{P}(n, ℤ) equivalence, with {B, B′} ⊂ 𝔐_{P}^{++}(C, n, ℤ). By Step 2 (Theorem 5.1), for each i ∈ P \ C, we have

(U{i, i}, V {i, i}): B{i, i} ⟶_{+} B′{i, i} .

So, we may find a string of elementary equivalences, say (E_{1}, F_{1}), … (E_{t}, F_{t}), with every E_{t}{i, j} = F_{t}{i, j} = (Id){i, j} unless i = j ∉ C, which accomplishes the elementary positive equivalence decomposition inside the diagonal blocks. By Lemma 4.9, we may find (U_{1}, V_{1}), …, (U_{t}, V_{t}) with each U_{s} and V_{s} in U_{P}, such that

B ⟶_{+}^{(U_{1},F_{1})} · ⟶_{+}^{(E_{1},V_{1})} ⋯ ⟶_{+}^{(U_{t},F_{t})} · ⟶_{+}^{(E_{t},V_{t})} B′′ .

Let X = E_{t}U_{t} ⋯ E_{2}U_{2}E_{1}U_{1}. Let Y = F_{1}V_{1}F_{2}V_{2} ⋯ F_{t}V_{t}. Then for all i in P, X{i, i} = U{i, i} and Y {i, i} = V {i, i}, so UX^{−1} ∈ U_{P} and Y^{−1}V ∈ U_{P}. It follows from Step 3 (Lemma 4.6) that

B′′ ⟶_{+}^{(UX^{−1},Y^{−1}V)} B′ .

Thus (U, V): B → B′ is the composition

B ⟶_{+}^{(X,Y)} B′′ ⟶_{+}^{(UX^{−1},Y^{−1}V)} B′

and this finishes the proof. □

5. Factorization: the positive case

In this section, all matrices are K × K, where K is a positive integer and K > 1. We let 𝔐_{+} denote the set of K × K matrices with strictly positive integer entries.

We say an equivalence (U, V): B → B′ is a positive equivalence through 𝔐_{+} if it can be given as a chain of positive elementary equivalences

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

in which every B_{i} is in 𝔐_{+}.

The purpose of this section is to prove the following theorem.

Theorem 5.1. Suppose U and V are in SL(K, ℤ), and B and UBV are in 𝔐_{+}. Suppose also that B is SL(K, ℤ) equivalent to a diagonal matrix in which at least two entries equal 1.

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

Remark 5.2. The “two entries”technical assumption may be excessive, but is harmless for our applications. Except for the final argument which addresses the possibility that UB is nonpositive, we only use the weaker assumption that B has rank greater than one.

The proof of Theorem 5.1 rests on three lemmas. We begin the preparations. By a signed transposition matrix, we mean a matrix which is the matrix of a

transposition, but with one of the off-diagonal 1’s replaced by -1. By a signed permutation matrix we mean a product of signed transposition matrices. Since K > 1, any K × K permutation matrix with determinant 1 is a signed permutation matrix. A K × K matrix S is a signed permutation matrix if and only if detS = 1 and the matrix |S| is a permutation matrix (where |S|(i, j) := |S(i, j)|).

Lemma 5.3. Suppose B ∈ 𝔐_{+}, E is a basic elementary matrix with nonzero offdiagonal entry E(i, j), and the ith row of EB is not the zero row.

Then in SL(K, ℤ) there are 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) = 1, then let Q = I = S. Now suppose E(i, j) = −1, so E acts from the left by subtracting row j from row i, and the rows i and j of B are not equal.

Case I: For some k, B(i, k) > B(j, k).

Here we may repeatedly add column k of B to other columns, until we have a matrix B′ with B′(i, m) > B′(j, m) for all m. This B′ is BQ for some Q which is a product of nonnegative basic elementary matrices. Now (E, Q): B → EBQ is the composition of positive equivalences, (I, Q): B → BQ followed by (E, I): BQ → EBQ. Let S = I.

Case II: For every k, B(i, k) ≤ B(j, k).

Because the rows i and j of B are not equal, after multiplying from the right by a suitable Q we can assume in this Case that 0 < B(i, k) < B(j, k) for all k. Now (I, Q): B → BQ in 𝔐_{+}, so for notational simplicity from here we may assume Q = I.

For concreteness of notation, let (i, j) = (1, 2). For the rest of this Case, for simplicity we will restrict what we write to these two rows, e.g.

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

where B_{1} and B_{2} denote the first and second rows of B, and we have B_{1} < B_{2}. Let

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

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

and the latter matrix is positive. Let E′ = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) and let E′′ = (\begin{matrix}1 & 0 \\ −1 & 1 \end{matrix}), then

SE = (\begin{matrix}0 & 1 \\ −1 & 1 \end{matrix}) = E′E′′ .

Now (E′′, I): B → E′′B is a positive equivalence in 𝔐_{+}, since row 2 of B is positive and greater than row 1; and (E′, I): E′′B → E′E′′B is also a positive equivalence in 𝔐_{+}. □

Lemma 5.4. Suppose B is a K × K integral matrix of rank at least 2, and U is in SL(K, ℤ), and no row of B or UB is the zero row. Then U is the product of basic elementary matrices, U = E_{k} ⋯ E_{1}, such that for 1 ≤ j ≤ k the matrix E_{j}E_{j−1} ⋯ E_{1}B has no zero row.

Proof. Without loss of generality, assume K ≥ 3 and U is not the identity. Let E(i) denote the set of integral 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.

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 (for notational simplicity) 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 ≤ t and we have produced U_{t} ⋯ F_{m−1}U′_{r} ⋯ U′_{s} = U_{t} ⋯ 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 & 0 \\ 0 & 1 & 0 \\ −c & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ a & 1 & b \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ c & 0 & 1 \end{matrix})

= (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ −c & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ a + bc & 1 & b \\ c & 0 & 1 \end{matrix}) = (\begin{matrix}1 & 0 & 0 \\ a + bc & 1 & 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′_{r+1}U′_{r} ⋯ U′_{s}U_{s−1} ⋯ U_{1}B equals row i_{m} of U_{m} ⋯ 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) 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_{m} ⋯ U_{1}B and U′_{T} ⋯ U′_{s}U_{s−1} ⋯ 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} ⋯ E_{1} of basic elementary matrices which agree with I outside row 1. Now, choose a row m > 1 of B which is not a rational multiple of row 1 of U_{1}B (such a row m exists because rank(B) > 1). Let E_{0} be the elementary matrix which adds row m to row 1: if s > 0, then (E_{0})^{s}B has row 1 nonzero. Choose a nonnegative integer M large enough that for 1 ≤ j ≤ k, 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} ⋯ E_{1}(E_{0})^{M}]B cannot be zero. Thus the factorization U_{1} = (E_{0})^{−M}E_{k} ⋯ E_{1}(E_{0})^{M} has the required properties. □

Lemma 5.5 (Key Lemma). Suppose B and B′ are in 𝔐_{+}, U and W are in SL(K, ℤ), 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. Step 1: Reduction to the case UB > 0.

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 left by a nonnegative matrix Q in SL(K, ℤ), 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 SL(K, ℤ), giving

(P U)(BQ) = (P B′)(W Q) > 0

with 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 > 0.

Step 2: Reducing the length of an elementary factorization.

By lemma 5.4, we can write U has a product of basic elementary matrices, U = E_{k} ⋯ E_{1}, such that for 1 ≤ j ≤ k, the matrix B_{j} = E_{j} ⋯ E_{1}B has no zero row. By lemma 5.3, given the pair (E_{1}, B), there is a nonnegative Q_{1} in SL(K, ℤ) 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_{k}S_{1}^{−1}] ⋯ [S_{1}E_{2}S_{1}^{−1}][S_{1}E_{1}]BQ_{1} .

Now, for 2 ≤ j ≤ k, 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.3, 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_{k}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 permuation matrix S = S_{k} ⋯ S_{1} and nonnegative Q = Q_{1} ⋯ Q_{k} such that

UBQ = S^{−1}[S_{k} ⋯ S_{1}E_{k}S_{1}^{−1} ⋯ S_{k−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): B → CB is a positive equivalence through 𝔐_{+} whenever B ∈ 𝔐_{+}. □

We can now complete the proof of Theorem 5.1. It only remains to address the technical point that in the equivalence (U, V): B → B′, all the entries of UB might be nonpositive. (For example, with K even we could have (U, V) = (−I, −I).)

Proof of Theorem 5.1. By assumption there are X, Y in SL(K, ℤ) such that XBY =

D, where D is diagonal and has the block form D = (\begin{matrix}I & 0 \\ 0 & F \end{matrix} ), where I is 2 × 2. For

any H in SL(2, ℤ), the K × K matrix G = G_{H} = (\begin{matrix}H & 0 \\ 0 & I \end{matrix}) yields a self equivalence

(X^{−1}GX, Y G^{−1}Y^{−1}): B → B .

For a matrix Q, we let Q{12; ∗} denote the submatrix consisting of the first two rows. The matrix (XBY){12; ∗} = D{12; ∗} has rank two, so the matrix (XB){12; ∗} has rank two, and we may choose H′ ∈ SL(2, ℤ) such that the first row r of H′[(XB){12; ∗}] has both a positive entry and a negative entry. For

M ∈ ℕ, let H_{M} = (\begin{matrix}M & −1 \\ 1 & 0 \end{matrix}), H = H_{M}H′, and G = G_{H}. Let c denote the first

column of X^{−1}. Since c is not the zero vector, the K × K matrix cr has a positive entry and a negative entry.

If M is sufficiently large, then the entries of the two matrices X^{−1}GXB and Mcr will have the same sign wherever the entries of Mcr are nonzero, and X^{−1}GXB will have a positive entry. Then the Key Lemma 5.5 shows that (X^{−1}GX, Y G^{−1}Y^{−1}) gives a positive equivalence in 𝔐_{+} from B to B.

Similarly, for large enough M the entries of UX^{−1}GXB will agree in sign with the entries of UMcr wherever the entries of the latter matrix are nonzero. Because U is nonsingular, the matrix Ucr is nonzero, and then contains positive and negative entries because r does.

So, using M sufficiently large, we obtain (U, V): B → B′ as a positive equivalence in 𝔐_{+}, the inverse of (X^{−1}GX, Y G^{−1}Y^{−1}) followed by (UX^{−1}GX, Y G^{−1}Y^{−1}V).

□

6. Flow equivalence

The purpose of this section is to prove the claims of Theorem 3.1 involving flow equivalence. As sketched in [B1] (see also [Ba1]), the positive K-theory framework is most natural for this. Because a complete development of this connection has not yet appeared, for brevity we will make no direct use of it below.

We begin with some background. For S a selfhomeomorphism of a compact metric space X, the mapping torus Y_{S} of S is the quotient space (X × ℝ)/ ∼ where (x, n + t) ∼ (S^{n}x, t) if n ∈ ℤ. Y_{S} admits a natural flow,

Y_{S} × ℝ → Y_{S}
([(x, t)], s) ↦ [(x, s + t)] .

This flow has the copy X_{0} = {[(x, 0)]: x ∈ X} of X as a cross section, and the return map to X_{0} under the flow (given by [(x, 0)] ↦ [(Sx, 0)]) is obviously topologically conjugate to S. Let T be another selfhomeomorphism of a compact metric space. Then S and T are flow equivalent if and only if there is a homeomorphism Y_{S} → Y_{T} which takes flow lines onto flow lines and respects the direction of the associated flows. (Equivalently: S and T are conjugate to return maps of cross sections of a common flow.)

For example, consider S = σ_{A}, T = σ_{A′} and the map γ arising from a basic positive equivalence in Subsection 2.2. It is not difficult to see that γ is the restriction of a homeomorphism Y_{S} → Y_{T} which takes flow lines onto flow lines and respects the direction of the associated flows, and therefore σ_{A} and σ_{A′} are flow equivalent.

Now fix A in 𝔐_{P,+}^{∘}(ℤ) and A′ in 𝔐_{P′,+}^{∘}(ℤ). Let F and F′ be finite matrices such that F_{∞} = A and F′_{∞} = A′. Let σ_{A} = σ_{F} and σ_{A′} = σ_{F′} be the associated SFTs. (So, for example σ_{A} is the left shift on the path space Σ_{A}, which is given the natural zero dimensional metrizable topology.) Parry and Sullivan [PS] showed that σ_{F} and σ_{F′} are flow equivalent if and only if σ_{F} is topologically conjugate to some SFT which after a time change is topologically conjugate to σ_{F′}. It follows ([PS]) that σ_{F} and σ_{F′} are flow equivalent if and only if F′ can be obtained from F by a finite sequence of basic flow moves, which are state splittings and stretchings and their inverses. The inverse of a splitting is called an amalgamation. We will describe the splitting and stretching moves now.

Let B and B′ be finite square matrices. B′ is obtained from B by an elementary row amalgamation if there exist indices i_{1}, i_{2} and i such that the columns i_{1} and i_{2} of A′ are equal, and A is obtained from A′ as follows: add row i_{1} to row i_{2}, then remove the row and column indexed by i_{1}. The reverse move is that B is obtained from B′ by a row splitting. Analogously there are column splittings and amalgamations. By state splittings we mean row splittings and column splittings.

We say B′ is obtained from B by a state stretching if for some indices i, j the following hold: B′(i, j) = 1, the other entries of row i and column j are zero, and B is the matrix obtained from B′ by adding column i to column j and then removing row i and column i.

We are now ready for the proof. Suppose A is in 𝔐_{P,+}^{∘}(ℤ) and A′ is in 𝔐_{P′,+}^{∘}(ℤ). We will show the following are equivalent.

(1) σ_{A} and σ_{A′} are flow equivalent.

(2) There exists ν ∈ Iso[P, P′] such that for P = P_{ν}, there exists a positive SL_{P}(ℤ) equivalence from (I − A) to (I − P^{−1}A′P) in I − 𝔐_{P,+}^{∘}(ℤ).

Proof. Given (2), it follows from Lemma 2.5 that there is a chain of basic positive SL_{P}(ℤ) equivalences from (I −A) to (I −P^{−1}A′P). Each basic positive equivalence gives rise to a flow equivalence as discussed above. It follows that (2) implies (1).

Now we assume (1) and will deduce (2). Let F and F′ be finite matrices such that F_{∞} = A and F′_{∞} = A′. After using Lemmas A.1 and A.2 to pass to flow equivalent SFTs, we may assume that for each i ∈ P, the diagonal blocks F_{ii} and F′_{ii} are strictly positive.

From [PS] we are given a sequence of basic moves through finite matrices, F = F_{0} → F_{1} → ⋯ → F_{m} = F′. We may regard P and P′ as the posets of irreducible components of F and F′ respectively, where e.g. i ⪯ j in P when there exists a transition from i to j (by which we mean that there exists a point in the SFT Σ_{A} forwardly asymptotic to a cycle from component j and backwardly asymptotic to a cycle from component i). Each move F_{i} → F_{i+1} induces a bijection of irreducible components, respecting transitions, and thus the composition induces a poset isomorphism ν: P(A) → P(A′). After replacing A′ with P^{−1}A′P, where P = P_{ν}, we may assume P = P′ and ν = Id.

Next, for 1 ≤ i ≤ n, we will associate to F_{i} a matrix A_{i} in 𝔐_{P,+}^{∘}(ℤ) such that (modulo permutations of indices) tru(A_{i}) = F_{i}. We must take a little care with the indices, to be able to lift each of the moves F_{i} → F_{i+1} to a (positive) SL_{P}(ℤ) equivalence (I − A_{i}) → (I − A_{i+1}). Let Ind(B) denote the set indexing the rows and columns of a square matrix B. For each F_{j}, we will define an injection τ_{j}: Ind(F_{j}) → I^{P}, and then define A_{j} = ι(F_{j}) by setting

A_{j}(s, t) = F (s′, t′)  if (s, t) = (τ_{j}(s′), τ_{j}(t′))
= 0  otherwise.

The maps τ_{j} will be defined recursively. For j = 0, we set A_{0} = A and take τ_{j} to be compatible with the embedding of F as a principal submatrix of A. Now suppose 0 ≤ j < n and τ_{j} and A_{j} are given. The transition F_{j} → F_{j+1} is given by a basic flow move, and under such a move, every element of Ind(F_{j+1}) is naturally related to one or two elements of Ind(F_{j}). (An element i of Ind(F_{j+1}) is related to two elements i_{1}, i_{2} of Ind(F_{j}) when the move F_{j+1} → F_{j} is a splitting or stretching of the state i into the states i_{1}, i_{2}.) In any case, for each i in Ind(F_{j+1}), fix a related vertex rel(i) in Ind(F_{j}). Then choose any map τ_{j+1} : Ind(F_{j+1}) → I^{P} such that τ_{j}(rel(i)) and τ_{j+1}(i) lie in I_{p}^{P} for the same element p of P. (When i is related to two indices, this p may depend on the choice for rel(i).) This defines the matrices A = A_{0}, A_{1}, …, A_{m}.

Next we will show that each elementary flow move F_{j} → F_{j+1} gives rise to a positive SL_{P}(ℤ) equivalence (I − A_{j}) → (I − A_{j+1}). Each of the equivalences we give will be accomplished by elementary matrices which must lie in SL_{P}(ℤ) on account of our choices of indices.

First we show how an elementary row splitting gives rise to a positive SL_{P}(ℤ) equivalence. The general construction can be understood from the example

B = (\begin{matrix}a & b & 0 \\ c_{1} + c_{2} & d_{1} + d_{2} & 0 \\ 0 & 0 & 0 \end{matrix}) → (\begin{matrix}a & b & b \\ c_{1} & d_{1} & d_{1} \\ c_{2} & d_{2} & d_{2} \end{matrix}) = B′ .

Here the positive equivalence (I − B) → (I − B′) is accomplished as follows:

(I − B) = (\begin{matrix}1 − a & −b & 0 \\ −(c_{1} + c_{2}) & 1 − (d_{1} + d_{2}) & 0 \\ 0 & 0 & 1 \end{matrix})

→ (\begin{matrix}1 − a & −b & 0 \\ −(c_{1} + c_{2}) & 1 − (d_{1} + d_{2}) & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ −c_{2} & −d_{2} & 1 \end{matrix}) = (\begin{matrix}1 − a & −b & 0 \\ −(c_{1} + c_{2}) & 1 − (d_{1} + d_{2}) & 0 \\ −c_{2} & −d_{2} & 1 \end{matrix})

→ (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & −1 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 − a & −b & 0 \\ −(c_{1} + c_{2}) & 1 − (d_{1} + d_{2}) & 0 \\ −c_{2} & −d_{2} & 1 \end{matrix}) = (\begin{matrix}1 − a & −b & 0 \\ −c_{1} & 1 − d_{1} & −1 \\ −c_{2} & −d_{2} & 1 \end{matrix})

→ (\begin{matrix}1 − a & −b & 0 \\ −c_{1} & 1 − d_{1} & −1 \\ −c_{2} & −d_{2} & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix}1 − a & −b & −b \\ −c_{1} & 1 − d_{1} & −d_{1} \\ −c_{2} & −d_{2} & 1 − d_{2} \end{matrix}) .

The positive equivalence for a column splitting is constructed similarly.

Next we show that a state stretching gives rise to a positive equivalence. The general construction can be understood from the example

B = (\begin{matrix}0 & 0 & 0 \\ 0 & a & b \\ 0 & c & d \end{matrix}) → (\begin{matrix}0 & 1 & 0 \\ a & 0 & b \\ c & 0 & d \end{matrix}) = B′ .

Here the positive equivalence (I − B) → (I − B′) is accomplished as follows.

(I − B) = (\begin{matrix}1 & 0 & 0 \\ 0 & 1 − a & −b \\ 0 & −c & 1 − d \end{matrix})

→ (\begin{matrix}1 & 0 & 0 \\ −a & 1 & 0 \\ −c & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ 0 & 1 − a & −b \\ 0 & −c & 1 − d \end{matrix}) = (\begin{matrix}1 & 0 & 0 \\ −a & 1 − a & −b \\ −c & −c & 1 − d \end{matrix})

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

At this point we have a positive SL_{P}(ℤ) equivalence (I − A) → (I − A′_{n}), where there is a permutation matrix Q such that Q^{−1}A′_{n}Q = A′. Because A′ = F′_{∞} and F′ has all diagonal blocks positive, if A′(i, j) > 0 then i lies on an A′ cycle and j lies on an A′ cycle. Therefore the permutation given by Q can be chosen compatible with the poset isomorphism ν = Id, and the matrix Q is a block diagonal matrix in SL_{P}(ℤ). It remains to check that I − A′_{n} → Q^{−1}A′_{n}Q is accomplished by a positive SL_{P}(ℤ) equivalence. Because Q is block diagonal and we can use compositions, it is enough to give the equivalence in the case that Q is the transposition matrix for indices i, j which lie in some I_{p}^{P}. Choose indices α, β in I_{p}^{P} such that A′_{n} is identically zero in the rows and columns indexed by α and β. Let P be the permutation matrix for the product of transpositions (i, j)(α, β). Then P is in SL_{P}(ℤ) and P A′_{n}P = Q^{−1}A′_{n}Q. This finishes the proof. □

7. The mapping class group

In this section the symbols S, T denote subshifts (e.g., T is the restriction of some full shift σ_{[n]} to a closed shift-invariant subset, which we also call T). As in Section 6, let Y_{S} denote the mapping torus of S. We regard Y_{S} as an oriented space, in the sense that the associated flow gives an orientation to each of its orbits (i.e., to each connected component of Y_{S}). A flow equivalence from a subshift S to a subshift T is an orientation preserving homeomorphism φ: Y_{S} → Y_{T} (where “orientation preserving”means orientation preserving on each orbit). Two such homeomorphisms φ_{0}, φ_{1} are isotopic (φ_{0} ∼ φ_{1}) if there is a continuous map t ↦ φ_{t}, 0 ≤ t ≤ 1, which connects them in the metrizable space of homeomorphisms from Y_{S} to Y_{T}. Let Is(S, T) denote the set of isotopy classes of flow equivalences from S to T. We let Is(S, S) = Is(S) and call this the mapping class group of the oriented space Y_{S}.

The isotopy futures group of Y_{S}.

Given S, x ∈ S and n ∈ ℤ, define

r(x, n) = {[(w, 0)] ∈ Y_{S}: w ∈ S, w_{i} = x_{i} for i ≤ n} .

We call such a set a ray in Y_{S}. We say two sets E, E′ in Y_{S} are isotopic (E ∼ E′) if there is a homeomorphism φ: Y_{S} → Y_{S} such that φ(E) = E′ and φ is isotopic to the identity. An isotopy ray is a set isotopic to a ray. A beam is a disjoint union of finitely many rays. An isotopy beam is a set isotopic to a beam. Let B = B(S) denote the set of isotopy beams of Y_{S}.

We define F(S), the isotopy futures group of S, to be ℤB/K, where ℤB is the free abelian group with generating set B = B(S), and K = K(S) is the subgroup of ℤB generated by all elements of the following forms:

(7.1)  b − b′ ,  if {b, b′} ⊂ B and b ∼ b′ ,
(7.2)  b − ∑_{j=1}^{k} b_{j} ,  if {b, b_{1}, …, b_{k}} ⊂ B, k ∈ ℕ, and b = ˙∪_{j}b_{j} .

For S a subshift, let P_{n}(S) denote the partition of S into clopen sets of the form C(x, n) = {w ∈ S: w_{i} = x_{i} if |i| ≤ n}.

Lemma 7.3. Suppose S, T are subshifts and φ: Y_{S} → Y_{T} is an orientation preserving homeomorphism and b ∈ B(S). Then φ(b) ∈ B(T).

Proof. Exploiting the zero dimensionality of S as in [PS], after postcomposing φ with a suitable map isotopic to the identity we may assume that there is a positive integer M such that for any C in P_{M}(S) there is a constant h = h_{C} and a homeomorphism f = f_{C} from C to a clopen subset D of T such that φ([(x, 0)]) = [(f(x), h)], for all x in C.

Because φ respects disjoint union and pushes Is(S) forward to Is(T) (by the rule [h] ↦ [φhφ^{−1}]), it suffices to consider the case that b is a ray r(x, n) with n ≥ M. Let C′ = {w ∈ S: w_{i} = x_{i} if i ≤ n} ⊂ C ∈ P_{M}(S), with h = h_{C} and f = f_{C}. Choose k ∈ ℕ such that for all x in C, the sequence x(−∞, n] determines (fx)(−∞, n−k] and the sequence (fx)(−∞, n+k] determines x(−∞, n]. So, if w ∈ f(C′), then {z ∈ T: z_{i} = w_{i} if i ≤ n + k} ⊂ f(C′). Let W be the (finite) set of words {w[n − k, n + k]: w ∈ f(C′)}. Then φ(b) = φ(r(x, n)) = ∪_{W ∈W}{[(z, h)]: z(−∞, n − k − 1] = (fx)(−∞, n − k − 1] and z[n − k, n + k] = W }, so φ(b) is an isotopy beam. □

The following proposition follows easily from the lemma.

Proposition 7.4. Suppose S and T are subshifts and φ: Y_{S} → Y_{T} is an orientation preserving homeomorphism. Then the mapping of isotopy beams b ↦ φ(b) induces an isomorphism φ_{∗}: F(S) → F(T).

Let Iso(F(S), F(T)) denote the set of group isomorphisms from F(S) to F(T). Let Aut(F(S)) = Iso(F(S), F(S)). The next proposition is now obvious.

Proposition 7.5. The rule φ ↦ φ_{∗} induces a group homomorphism ρ: Is(S) → Aut(F(S)).

Remark 7.6. The construction of F_{S} is one of several variations on the dimension group construction introduced by Krieger [Kr1, Kr2]; our construction was influenced also by [LM] and [BFF]. The construction of F_{S} is a flow equivalence analogue of Krieger’s construction of a dimension group from a subshift S. The map ρ: Is(Y_{S}) → Aut(F_{S}) is the analogue for flow equivalence of the dimension representation of the automorphism group of a subshift.

The isomorphism β: F(σ_{A}) → cok(I − A).

Suppose A is a matrix in 𝔐_{P,+}^{∘}(ℤ). Let I denote the index set of the rows and columns of A. Let ℤ^{I} be the group of (infinite) row vectors indexed by I, with all but finitely many entries zero. For a symbol/edge x_{n} of σ_{A}, let τ(x_{n}) denote the terminal vertex of the edge x_{n} (so, τ(x_{n}) ∈ I).

The group cok(I −A) is the cokernel of the map ℤ^{I} → ℤ^{I} given by v ↦ v(I −A) (i.e., cok(I − A) = ℤ^{I}/image(I − A)). Given a ray r = r(x, n) with i = τ(x_{n}), let e_{i} be the ith canonical basis vector in ℤ^{I}, and define β(r) = [e_{i}] ∈ cok(I − A).

First note, given k ∈ ℤ and a ray r = r(x, n), if we set r′ equal to {[(w, k)]: [(w, 0)] ∈ r(x, n)}, then r′ is again a ray,

r′ = r(σ^{k}x, n − k) and β(r′) = β(r) . (7.7)

Here the equality of sets follow from the manipulations

{[(w, k)]: [(w, 0)] ∈ r(x, n)} = {[(σ^{k}w, 0)]: w(−∞, n] = x(−∞, n]}
= {[(z, 0)]: z(−∞, n − k] = x(−∞, n]} = {[(z, 0)]: z(−∞, n − k] = (σ^{k}x)(−∞, n − k]}

and then β(r) = β(r′) because the edges x_{n} and (σ^{k}x)_{n−k} are equal.

Next, given x ∈ σ_{A}, n ∈ ℤ and k ∈ ℕ, for each σ_{A}-word W = W_{1} ⋯ W_{k} which can follow x_{n}, choose a point y = y_{W} such that y(−∞, n] = x(−∞, n] and y[n + 1, n + k] = W. Then the equality

β(r(x, n]) = ∑_{W} β(r(y_{W} , n + k)) ∈ cok(I − A) (7.8)

follows for k = 1 by direct computation and for k > 1 by induction.

Given a beam b which is a disjoint union of finitely many rays r(x^{(i)}, n^{(i)}), we now define

β(b) = ∑_{i} β(r(x^{(i)}, n^{(i)})) .

(We will use the symbol β for various maps derived from the map β on rays.) To see that this definition is independent of the particular choice of rays, suppose b is also the union of rays r(w^{(j)}, m^{(j)}). Choose M ≥ max_{i,j}{n^{(i)}, m^{(j)}}. Then b is the disjoint union of rays r(z^{(k)}, M), each of the r(x^{(i)}, n^{(i)}) and r(w^{(j)}, m^{(j)}) is a union of some of the rays r(z^{(k)}, M), and by (7.8) we have

∑_{i} β(r(x^{(i)}, n^{(i)})) = ∑_{k} β(r(z^{(k)}, M)) = ∑_{j} β(r(w^{(j)}, m^{(j)})) .

Therefore β(b) is well defined.

We will write Y_{A} for the mapping torus of σ_{A}.

Lemma 7.9. If b and b′ are beams in Y_{A} such that b ∼ b′, then β(b) = β(b′).

Proof. Without loss of generality, choose M ∈ ℕ and a finite set E of Y_{A} such that b is the disjoint union of rays r(x, M), x ∈ E. Let {φ_{t}} be an isotopy such that φ_{0} = id and φ_{1}(b) = b′. Because φ_{1} ∼ id, there is a continuous function k(x) such that for all [(x, 0)] in b, φ_{1} : [(x, 0)] ↦ [(x, k(x))]. Because φ(b) is a beam, the function k is integer valued. Possibly after increasing our choice of M, we may assume that k is constant on each ray r(x, M). By (7.7), φ_{1} takes each ray r = r(x, M) onto a ray r′ such that β(r) = β(r′), b′ is the disjoint union of these rays r′, and

β(b) = ∑_{r} β(r) = ∑_{r′} β(r′) = β(b′) .

□

An isotopy beam b is isotopic to some beam b′. Define β(b) = β(b′). It follows from the lemma that β(b) does not depend on the choice of b′. Likewise we have a well defined homomorphism of groups

(7.10)  β: ℤB → cok(I − A) ,
∑ n_{i}b_{i} ↦ ∑ n_{i}β(b_{i}) .

Proposition 7.11. The kernel of the map β in (7.10) is the subgroup K with generators (7.1, 7.2). So, there is an induced isomorphism of groups

β_{A}: F(σ_{A}) → cok(I − A) .

Proof. First we show K ⊂ Kerβ by showing that β vanishes on the generators of K. For (7.1), suppose b ∼ b′; then β(b − b′) = 0 by Lemma 7.9. For (7.2), suppose b is an isotopy beam and b is the disjoint union of finitely many isotopy beams b_{i}. Without loss of generality, suppose b is a beam. The b_{i} are a finite collection of disjoint compact sets, so for sufficiently large m, for any C in P_{m}(S) such that b ∩ C ≠ ∅, the set (b ∩ C) will be contained in one of the b_{i}. If m is large enough, then b ∩ C if nonempty will be a ray. Thus, taking sums over C in P_{m}, and for notational convenience defining β to be zero on the empty set, we get

β(b) = ∑_{C} β(C ∩ b)

= ∑_{j} ∑_{C} β(C ∩ b_{j}) = ∑_{j} β(b_{j}) .

Now we show kerβ ⊂ K. Suppose g = ∑ n_{j}b_{j} ∈ kerβ. There exists M ≥ 0 such that for each j, there are rays r(x^{(jk)}, M) such that b_{j} − ∑_{k} r(x^{(jk)}, M) ∈ K. so g = ∑_{jk} n_{j}r(x^{(jk)}, M) (mod K). For any x, β(r(σ^{M}x, 0)) = β(r(x, M)); also, r(x, 0) − r(x′, 0) ∈ K if x_{0} and x′_{0} have the same terminal vertex i. So, we may choose for each i an element x^{(i)} such that (x^{(i)})_{0} has terminal vertex i, for each x^{(jk)} replace x^{(jk)} with the appropriate x^{(i)}, and after reindexing obtain integers m_{i} such that

g = ∑_{i} m_{i}r(x^{(i)}, 0) (mod K) .

Because β(g) = 0 and K ⊂ kerβ, there is an integral row vector w such that ∑_{i} m_{i}e_{i} = w(I − A), and therefore

g = ∑_{i} w_{i}([r(x^{(i)}, 0)] − ∑_{j} A_{ij}[r(x^{(j)}, 0)]) (mod K) .

For each i, we have r(σ_{A}x^{(i)}, −1) − r(x^{(i)}, 0) ∈ K, and also

r(σ_{A}x^{(i)}, −1) − ∑_{j} A_{ij}r(x^{(j)}, 0) ∈ K .

It follows that g = 0 (mod K). □

In our definition of F(S) and cok(I − A) we used sets r(x, n) and row vectors. (So, cok(I − A) = rowcok(I − A).) In the same way, using sets

r^{+}(x, n) := {[(w, 0)] ∈ Y_{S}: w ∈ S and w_{i} = x_{i} for i ≥ n}

we may define the pasts group P(S); and using column vectors, we obtain an isomorphism P(σ_{A}) → colcok(I − A). For a flow equivalence φ: Y_{A} → Y_{B}, the isomorphism φ_{∗}: F(σ_{A}) → F(σ_{B}) given by Proposition 7.4 induces the isomorphism

φ_{∗}^{row} := (β_{B})φ_{∗}(β_{A})^{−1} : rowcok(I − A) → rowcok(I − B) .

Likewise, the action of φ on P(σ_{A}) induces an isomorphism

φ_{∗}^{col} : colcok(I − A) → colcok(I − B) .

The action of Is(σ_{A}) on cok(I − A).

For a flow equivalence φ: Y_{A} → Y_{A}, we have group homomorphisms

Is(σ_{A}) → Aut(rowcok(I − A))  and  Is(σ_{A}) → Aut(colcok(I − A))
φ ↦ φ_{∗}^{row}  φ ↦ φ_{∗}^{col} .

As described in subsection 2.2, if (U, V) is a basic positive SL_{P}(n, ℤ) equivalence from (I − A) to (I − B) = U(I − A)V, and B plays the role of A′ in subsection 2.2, then there is an associated map γ from σ_{A} to σ_{B}, and it is easy to see that this map is the restriction (to the cross section σ_{A}) of an orientation preserving homeomorphism Y_{A} → Y_{B}. More generally, if (U, V) is the composition of basic positive SL_{P}(n, ℤ) equivalences (U_{i}, V_{i}), and φ is the corresponding composition of the flow equivalences associated to the (U_{i}, V_{i}), then we will write φ = φ_{(U,V)}. This is an abuse of notation in that we are not claiming that (U, V) determines φ (the map φ may depend on the particular factorization of (U, V)); we are only indicating that φ arises via some factorization of (U, V).

Proposition 7.12. Suppose A ∈ 𝔐_{P,+}^{∘}(ℤ). Suppose (U, V): (I − A) → (I − B) is a positive SL_{P} equivalence, and φ_{(U,V)} is an associated flow equivalence.

Then the induced map φ_{∗}^{row} : rowcok(I −A) → rowcok(I −B) is given by the rule [w] ↦ [wV], and the induced map φ_{∗}^{col} : colcok(I − A) → colcok(I − B) is given by the rule [w] ↦ [Uw].

Proof. We will check the proposition in the case that (U, V) = (E, I) and E is a basic elementary matrix with unique offdiagonal entry E(i, j) = 1. The argument for (I, E) is similar and then the proposition follows by composition. For concreteness,, suppose E(1, 2) = 1 (in other entries E = I). Let φ = φ_{(E,I)} be defined via the map γ and edge e described in subsection 2.2.

Suppose x ∈ σ_{A} and x_{−1} has terminal vertex i. Then the edge (γx)_{−1} has terminal vertex i and φ maps r(x, −1) onto r(γx, −1). It follows that the diagram

F(σ_{A})  ⟶^{φ_{∗}}  F(σ_{B})
β_{A}↓  ^{β_{B}} ↓
rowcok(I − A) ⟶^{Id} rowcok(I − B)

commutes; that is, φ_{∗}^{row} = Id.

If x ∈ σ_{B} and x_{0} has initial vertex not equal to 2, then φ maps r^{+}(x, 0) onto r^{+}(γx, 0). Thus the map (φ_{∗}^{col})^{−1} sends [e_{i}] in colcok(I −A) to [e_{i}] in colcok(I −B) whenever i ≠ 2. If the initial vertex of x_{0} is 2, then φ^{−1} sends r^{+}(x, 0) to the set of all points (w, 0) in r^{+}(γ^{−1}x, 0) such that w_{−1} ≠ e. Consequently, if y is a point in σ_{A} such that y_{i} = (γx)_{i} if i ≥ 0 and y_{−1} = e, then

φ^{−1}(r^{+}(x, 0)) = r^{+}(γ^{−1}x, 0) \ r^{+}(y, −1) .

We also have

β_{B}^{col}:  r^{+}(x, 0) ↦ [e_{2}] ∈ colcok(I − B) ,
β_{A}^{col}: r^{+}(γ^{−1}x, 0) ↦ [e_{2}] ∈ colcok(I − A) ,
β_{A}^{col}: r^{+}(y, −1) ↦ [e_{1}] ∈ colcok(I − A) .

Therefore (φ_{∗}^{col})^{−1} : [e_{2}] ↦ [e_{2}] − [e_{1}], hence for all integral column vectors v we have (φ_{∗}^{col})^{−1} : [v] ↦ [E^{−1}v] as required. □

Theorem 7.13. Suppose A ∈ 𝔐_{+}^{∘}(ℤ) and the mapping torus of σ_{A} is not a circle. Then the induced map Is(Y_{A}) → Aut(cok(I − A)) is surjective.

Remark 7.14. Of course, the theorem is true for colcok as well as for rowcok. In the case that the mapping torus of σ_{A} is a circle (i.e., A has a unique irreducible component, and this component is a permutation matrix), any orientation preserving homeomorphism from Y_{A} to Y_{A} is isotopic to the identity, but cok(I − A) ≅ ℤ and Aut(cok(I − A)) ≅ ℤ/2, so the map Is(Y_{A}) → Aut(cok(I − A) is not surjective. Theorem 7.13 says that apart from this case, every automorphism of the isotopy futures group of an irreducible shift of finite type is induced by a flow equivalence.

Proof of Theorem 7.13. It is proved in [BH] that any automorphism of rowcok(I − A) or colcok(I − A) is induced by an SL(ℤ) equivalence (by the rules described in the statement of Proposition 7.12). By the Factorization Theorem 3.3, such an equivalence is a positive equivalence. By Proposition 7.12, a flow equivalence associated to this positive equivalence has the desired action on the cokernel group.

□

From the view of symbolic dynamics, Theorem 7.13 stands in contrast to the Kim-Roush-Wagoner result [KRW1] that the dimension representation of a mixing shift of finite type is not in general surjective. (The contrast is meaningful because the invariants are related by “setting t equal to 1” [B1].)

When A ∈ 𝔐_{+}^{∘}(ℤ) (i.e. A is essentially irreducible) and σ_{A} is not a circle, the flow equivalence class of σ_{A} is given by the SL(ℤ) equivalence class of I − A, for which det(I − A) and cok(I − A) give complete invariants. When P is nontrivial and A ∈ 𝔐_{P,+}^{∘}(ℤ) (i.e. the SFT σ_{A} is reducible), the flow equivalence class of A (modulo a permutation of P) is given by its positive SL_{P}(ℤ) equivalence class, and the complete algebraic invariants (introduced by Huang) are more subtle, involving the “K-web” of the matrix I − A, denoted K(I − A). The K-web is a diagram of exact sequences of certain kernel and cokernel groups of submatrices of I − A. The K-web invariants are completely analyzed in [BH], which also characterizes the automorphisms of K(A) which can be induced by an SL_{P}(ℤ) equivalence. We believe that the type of analysis carried out to describe the action of Is(σ_{A}) on cok(I − A) in the irreducible case can be extended to describe the possible actions of Is(σ_{A}) on the more complicated algebraic structure of the K-web which classifies in the reducible case. Specifically, we expect that the following program can be carried out. Together with [BH], this program would give a complete description of the possible actions of Is(σ_{A}) on the K-web.

Program 7.15. For A, B in 𝔐_{P}(ℤ_{+}), we conjecture the following.

(1) The K-web data for I − A can be described in terms of isotopy beams of subsystems of Y_{A}, and the map on isotopy beams by an orientation preserving homeomorphism φ: Y_{A} → Y_{B} induces an isomorphism K(A) → K(B).

(2) For a positive SL_{P}(ℤ) equivalence (U, V) from A to B, the isomorphism K(A) → K(B) induced by φ_{(U,V)} is the natural isomorphism induced by (U, V) as described in [BH].

(3) If φ is an orientation preserving homeomorphism from Y_{A} to Y_{B}, then there is a positive SL_{P}(ℤ) equivalence (U, V) such that φ is isotopic to φ_{(U,V)}.

The most fundamental of the three steps above is the last one, and a version of this has already been carried out in the irreducible case (i.e. P = {1}) by Badoian [Ba1], as we discuss below.

The work of Badoian.

We’ll describe some of the work [Ba1] of Leslie Badoian, which gives alternate proofs of some of our results. The work [Ba1] is too extensive for a full summary here; roughly speaking, Badoian carries out for irreducible shifts of finite type a flow equivalence version of the strong shift equivalence theory Wagoner [W1] built on the foundation laid by Williams [Wi].

Badoian builds an infinite oriented CW complex, denoted F K. A zero-cell for F K is an equivalence class of infinite, essentially irreducible, finitely supported zeroone matrices, where two matrices are equivalent iff their unique maximal irreducible principal submatrices are equal. A one-cell [A] → [B] corresponds to an elementary equivalence (I − B) = U(I − A)V satisfying certain conditions. Two-cells are also defined, by certain matrix relations. The two main results of [Ba1] are the following.

• Classification Theorem. σ_{A} and σ_{B} are flow equivalent if and only if A and B lie in the same connected component of F K.

• Flow Equivalence Theorem. π_{1}(F K_{A}) ≅ Is(σ_{A}). (I.e., a path along onecells gives rise to a flow equivalence, and two paths give rise to isotopic flow equivalences if and only if the paths are homotopic in F K.)

The elementary equivalences of [Ba1] are not the same as our elementary positive equivalences, but Badoian has found short arguments [Ba2] which show directly that that her elementary equivalences and ours generate the same set of flow equivalences up to isotopy. With this fact and some technical remarks, the results of Section 6 for irreducible shifts of finite type follow directly from Badoian’s Classification Theorem (which in turn rests on Parry-Sullivan [PS] and Williams [Wi], as does our Section 6).

The Flow Equivalence Theorem gives an alternate route in the irreducible case to the representation Is(σ_{A}, σ_{B}) → Iso(cok(I − A), cok(I − B)): we could take the natural definition along an edge (given by the associated flow equivalence), compose along paths of edges, and consult the definition of two-cells in F K to verify that the definition only depends on the homotopy class of the path of edges. All of this is parallel to the development of the dimension representation in Wagoner’s strong shift equivalence theory [W1].

We have not relied in proofs on citation of [Ba1], for a few reasons. Although there should be no fundamental problem with extending Badoian’s approach to reducible shifts of finite type, the results in [Ba1] are only for irreducible shifts of finite type. We also wanted self-contained and reasonably brief arguments. (The long work [Ba1] deals with a fundamental difficult problem which we avoid: we do not try to understand when two paths give rise to the same flow equivalence up to isotopy.) Finally, although the CW complex approach has rather spectacularly proved its worth [KR2, KRW1, W1], the Krieger-style construction remains important, and its more earthy definition (by actions on sets) makes sense directly for general subshifts. Matsumoto [Ma] has a far reaching extension of Williams’ theory to general subshifts, and this offers hope for some analogue of Wagoner’s strong shift equivalence theory for general subshifts; but there is no such theory yet.

Appendix A. Reduction to nondegenerate form

This appendix is devoted to the proof of Proposition 4.5.

We will prove Proposition 4.5 by composition in a larger commuting diagram (to be assembled in three stages):

(I − A) ⟶ (I − \overline{A_{1}}) ⟶ (I − \overline{A_{2}}) ⟶ (I − \overline{A})
(U,V)↓  ^{(U_{1},V_{1})}↓  ^{(U_{2},V_{2})}↓  ↓^{(\overline{U},\overline{V})}
(I − A′) ⟶ (I − \overline{A′_{1}}) ⟶ (I − \overline{A′_{2}}) ⟶ (I − \overline{A′})

The horizontal arrows will be positive equivalences and the vertical equivalences to the right of (U, V) will be defined from them by composition (then the diagram will commute). Stage I will produce the left square with \overline{A_{1}} and \overline{A′_{1}} satisfying conditions 2,3 and 4 of Proposition 4.5. Stage II will produce the middle square, with (U_{2})_{ii} = (V_{2})_{ii} = Id for i ∈ C, and with \overline{A_{2}} and \overline{A′_{2}} still satisfying conditions 2,3 and 4 of Proposition 4.5. Stage III will produce the right square to finish the proof. The individual stages will follow from several lemmas.

Lemma A.1. Suppose A ∈ 𝔐_{P,+}^{∘}(n, ℤ). Then there is a positive SL_{P}(n, ℤ) equivalence in I − 𝔐_{P,+}^{∘}(n, ℤ) from I − A to a matrix I − C such that for all i ∈ C_{A} the following hold:

(1) The block C_{ii} has its upper left corner entry equal to 1, and C_{ii} has no other nonzero entry.

(2) Let (ℓ, ℓ) be the entry of C which is the upper left corner of C_{ii}. Then for j ≠ i, every row of a block C_{ij} other than row ℓ is zero, and every column of a block C_{ji} other than column ℓ is equal to zero.

Proof. Suppose i ∈ C_{A}. Let i_{1}, …, i_{k} be nonrepeated indices such that A_{ii}(i_{t}, i_{t+1}) = 1, 1 ≤ t < k, and A_{ii}(i_{k}, i_{1}) = 1.

Cycle-shortening construction. Suppose k > 1. Let A = A^{(0)}. For 1 ≤ j < k, define A^{(j)} by the equation I − A^{(j)} = E_{j}(I − A^{(j−1)}), where E_{j} denotes the basic elementary matrix which acts to add row i_{k−j+1} to row i_{k−j}. Each A^{(j)} is nonnegative. Then add the columns i_{2}, …, i_{k} of A^{(k)} to column i_{1} of A^{(k)}. By Lemma 2.5, each step in this process gives a positive equivalence in I −𝔐_{P,+}^{∘}(n, ℤ), and in the last matrix A′, the block A′_{ii} has as its unique cycle the 1-cycle (i_{1}). Below is an example of the process, with (i_{1}, i_{2}, i_{3}, i_{4}) = (1, 2, 3, 4), viewed in the principal submatrices on indices 1, 2, 3, 4:

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

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

Now without loss of generality, we suppose k = 1 with A(i_{1}, i_{1}) = 1. Because (i_{1}) is the unique A_{ii} cycle, if A_{ii} is nonzero at any entry other than (i_{1}, i_{1}), then it is nonzero at some entry (j, l) such that row l of A is zero or column j of A is zero. In the former case, let E be the elementary matrix which acts from the left to add row l to row j, then (E, I): (I −A) → E(I −A) = (I −A′′) is a positive equivalence in which A′′ = A except that A′(j, l) = 0. The latter case is treated similarly, by adding column j to column l. Iterating, we produce a positive equivalence in I −𝔐_{P,+}^{∘}(n, ℤ) from I −A to a matrix I −A′ such that A′(i_{1}, i_{1}) is the only nonzero entry of A′_{ii}.

Next, given i in C_{A′} with A′(i_{1}, i_{1}) = 1, we may for each j ≺ i add rows of I −A′ through the ii block to rows through the ji block (never adding row i_{1}) until every column of the block (I − A′)_{ji} except column i_{1} is zero. We do this for all the cycle components i, for i in decreasing order, so that no block zeroed out for some i is made nonzero by subsequent operations. Then similarly, taking i in C_{A} in increasing order, we add columns through the ii block to columns through the ji blocks with i ≺ j, to end with a matrix C′ which satisfies the statement of the lemma (with C′ in place of C), except that the distinguished indices i_{1} might not be the corner indices ℓ.

So, suppose i is a cycle component for which ℓ ≠ i_{1}. We apply four basic positive equivalences to give (I − C′) → (I − C′′), as viewed below in principal submatrices on indices {i_{1}, ℓ, k} (where k is any index not in {i_{1}, ℓ}). (In the very special case that C′ is 2 × 2, there can be no third index k and these principal submatrices should be restricted to indices {i_{1}, ℓ}.) For concreteness we use (ℓ, i_{1}, k) = (1, 2, 3):

(\begin{matrix}1 & 0 & 0 \\ 0 & 0 & x \\ 0 & y & z \end{matrix}) → (\begin{matrix}1 & 0 & 0 \\ −1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ 0 & 0 & x \\ 0 & y & z \end{matrix}) = (\begin{matrix}1 & 0 & 0 \\ −1 & 0 & x \\ 0 & y & z \end{matrix})

→ (\begin{matrix}1 & 0 & 0 \\ −1 & 0 & x \\ 0 & y & z \end{matrix}) (\begin{matrix}1 & −1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix}1 & −1 & 0 \\ −1 & 1 & x \\ 0 & y & z \end{matrix})

→ (\begin{matrix}1 & −1 & 0 \\ −1 & 1 & x \\ 0 & y & z \end{matrix}) (\begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix}0 & −1 & 0 \\ 0 & 1 & x \\ y & y & z \end{matrix})

→ (\begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}0 & −1 & 0 \\ 0 & 1 & x \\ y & y & z \end{matrix}) = (\begin{matrix}0 & 0 & x \\ 0 & 1 & x \\ y & y & z \end{matrix}) .

If above for any k we have x ≠ 0, then x < 0 and the (i_{1}, k) entry lies in an ij block with i ≺ j; then y = 0 and it is a positive equivalence to add column i_{1} of C′′ |x| times to column k. Doing this as needed, and dealing similarly with nonzero entries y using rows in place of columns, we produce another version of C′′ which enjoys the additional property that i_{1} = ℓ for the cycle component i. Then we repeat until i_{1} = ℓ for every cycle component i. The resulting matrix C satisfies the statement of the lemma. □

Lemma A.2. Suppose A ∈ 𝔐_{P,+}^{∘}(n, ℤ), and n = (n_{1}, …, n_{N}) is a vector with positive integer entries. Then there is a positive SL_{P}(n, ℤ) equivalence in I − 𝔐_{P,+}^{∘}(ℤ) from (I − A) to a matrix with the properties 2,3,4 of Proposition 4.5.

Proof of Lemma A.2. We will describe a sequence of row and column operations (corresponding, by repeated tacit appeal to Lemma 2.5, to positive SL_{P}(n, ℤ) equivalences in I − 𝔐_{P,+}^{∘}(ℤ)) which put the matrix I − A into the required form. To simplify notation, rather than renaming I − A after an equivalence, we will discuss changing properties of I − A. We begin with a matrix A with the properties stated (for C) in Lemma A.1, i.e., A satisfies the properties 3,4 of Proposition 4.5.

Our first goal will be, given t ∈ P which is not a cycle component, to arrange that the block (I − A)_{tt} be strictly negative. Recall I_{t} denotes the index set for rows/columns of A_{tt}. Let S denote the index set for the unique maximal irreducible submatrix of A_{tt}, let S′ denote the complement of S in I_{t}, and e.g. let A{S} denote the principal submatrix of A on index set S. We will arrange (in order) the following properties (after each stage keeping the properties achieved at earlier stages, and not changing entries in any block A_{ss} with s ≠ t, and not losing the properties 3,4 of Proposition 4.5).

(1) ∃i ∈ S such that (I − A)(i, i) ≤ 0.

(2) {i, j} ∩ S′ ≠ ∅ ⟹ (I − A)(i, j) = δ_{ij}.

(3) If S′ ≠ ∅, then |S| > 1.

(4) S′ = ∅.

(5) The block (I − A)_{tt} is strictly negative.

(1) If necessary achieve this with the initial row operations of the cycle-shortening construction of the Lemma A.1.

(2) First suppose this condition does not hold for some {i, j} ⊂ I_{t}. Then pick some i ∈ S′ and j ∈ I_{t} such that j ≠ i and one of the following hold:

• (I − A)(i, j) ≠ 0 and column i of A_{tt} is zero, or
• (I − A)(j, i) ≠ 0 and row i of A_{tt} is zero.

In the former case, add column i of (I−A) to other columns j where (I−A)(i, j) < 0, until (I − A)(i, j) = δ_{ij} for all j ∈ I_{t}. In the latter case, similarly use row additions to achieve (I − A)(j, i) = δ_{ij} for all j ∈ I_{t}. This procedure reduces the cardinality of the set of entries in (I − A)_{tt} at which condition (2) fails, and it may be repeated until condition (2) holds for {i, j} ⊂ I_{t}. We then add rows and columns indexed by S′ to others as needed until (2) holds in general.

(3) Suppose (for concreteness) that S = {1} and 2 ∈ S′. Then we must have A(1, 1) = k > 1 (since t is not a cycle component). Now, subtract row 2 of (I − A) from row 1; then subtract column 2 from column 1. The effect of these moves is to enlarge S = {1} to S = {1, 2}. The moves are summarized below in principal submatrices on indices {1, 2, 3}, where 3 is an arbitrary additional index:

(\begin{matrix}1 − k & 0 & w \\ 0 & 1 & 0 \\ x & 0 & z \end{matrix}) → (\begin{matrix}1 − k & −1 & w \\ 0 & 1 & 0 \\ x & 0 & z \end{matrix}) → (\begin{matrix}−(k − 2) & −1 & w \\ −1 & 1 & 0 \\ x & 0 & z \end{matrix}) .

(4) Suppose S′ ≠ ∅. By (1) and (3), we may pick i_{1}, j_{1} in S such that i_{1} ≠ j_{1}, (I − A)(i_{1}, i_{1}) ≤ 0, and (I − A)(i_{1}, j_{1}) ≤ −1. Add row i_{1} of (I − A) to row j_{1}, (|S′| + 1) times, producing (I − A)(j_{1}, j_{1}) ≤ −|S′|. For each j in S′, subtract row j of (I − A) from row j_{1}. Then subtract each S′ column from column j_{1}. This produces A with S′ = ∅.

(5) With i_{1}, j_{1} as in (4): add row i_{1} to row j_{1} (now (I − A)(j_{1}, j_{1}) < 0); for each i in S with i ≠ j_{1}, add column j_{1} to column i (now row j_{1} of (I − A) is negative); and for each i in S with i ≠ j_{1}, add row j_{1} to row i. We now have (I − A)_{tt} strictly negative as required.

After applying a positive equivalence, then, we may assume that (I − A)_{ii} < 0 for every noncycle component i. Consequently, if i ≺ j, and i or j is not a cycle component, then for large n the block (A^{n})_{ij} is strictly positive. We can then get a positive equivalence to (I − A) whose block (I − A)_{ij} is strictly negative, by adding columns through i to columns through j (if i ∉ C_{A}) or by adding rows through j to rows through i (if j ∉ C_{A}). Similarly, for every noncycle component j and cycle component i, with C_{i}^{prim} = {ℓ}, add a j-row to row ℓ if i ≺ j, and add a j-column to column ℓ if j ≺ i.

Note, if i ≺ j and {i, j} ⊂ C, with say C_{i}^{prim} = {ℓ_{i}} and C_{j}^{prim} = {ℓ_{j}}, then A(ℓ_{i}, ℓ_{j}) > 0, because the block A_{ij} is not the zero block (because A ∈ 𝔐_{P,+}^{o}(C, n, ℤ)) and the only possible nonzero entry is A(ℓ_{i}, ℓ_{j}) > 0. Finally, whenever (I − A)_{ij} < 0 with {i, j} ⊂ C_{A} and i ≺ k ≺ j for some k in P, pick k such that i ≺ k ≺ j, and add columns of I − A through component k to columns through component j. The resulting matrix satisfies the statement of the lemma. □

Lemmas A.1 and A.2 finish the proof for Stage I. We now shift our focus to the form of the equivalence (U, V). The next lemma gives the proof for Stage II.

Lemma A.3. Suppose (U, V): (I−A) → (I−A′) is an SL_{P}(n, ℤ) equivalence which is positive on cycle components, and A, A′ satisfy conditions 2,3,4 of Proposition 4.5. Then there is a commuting diagram

(I − A) ⟶ (I − Ã)
(U,V)↓  ↓^{(Ũ,Ṽ)}
(I − A′) ⟶ (I − Ã′)

in which the horizontal arrows are positive equivalences; Ã and Ã′ still satisfy those conditions 2,3,4; and for each i ∈ C, Ũ_{ii} = Ṽ_{ii} = Id.

Proof. Suppose i is a cycle component for which n_{i} > 1 (otherwise there is nothing

to prove). Then (I − A)_{ii} = (I − A′)_{ii} = Q, where Q = (\begin{matrix}0 & 0 \\ 0 & I \end{matrix}), in which I is

(n_{i} −1)×(n_{i} −1). Considering blocks of U_{ii}Q = QV_{ii}^{−1}, we see U_{ii} and V_{ii} have the

corresponding block forms U_{ii} = (\begin{matrix}a & 0 \\ x & Z \end{matrix}) and V_{ii} = (\begin{matrix}b & y \\ 0 & Z^{−1} \end{matrix}). The positive on

cycle components assumption implies a = 1. Then det(U) = 1 implies det(Z) = 1. Then det(Z^{−1}) = 1 = detV implies b = 1. So we have

U_{ii} = (\begin{matrix}1 & 0 \\ x & Z \end{matrix}) and V_{ii} = (\begin{matrix}1 & y \\ 0 & Z^{−1} \end{matrix}) (A.4)

for some Z in SL(n_{i} − 1, ℤ).

Now suppose E is a basic elementary matrix with offdiagonal entry E(j, k) = 1, where j, k index rows of the ii block other than the first row. Then

(A.5)  (I − A) ⟶^{(I,E^{−1})} · ⟶^{(E,I)} (I − A)

gives a factorization of (E, E^{−1}): (I −A) → (I −A) into basic positive equivalences. For example, if rows 1,2,3 run through Q and Q(1, 1) = 0, then in the principal

submatrix on indices 1,2,3 we could have E = (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}), and (A.5) would become

(\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟶^{(I,E^{−1})} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & −1 \\ 0 & 0 & 1 \end{matrix}) ⟶^{(E,I)} (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) .

Now we can factor (U, V) as

(A.6)  (I − A) ⟶^{(I,E^{−1})} · ⟶^{(E,I)} (I − A) ⟶^{(UE^{−1},EV)} (I − A′)

Because Z is a composition of elementary matrices, and the conditions 2,3,4 are not disturbed by this move, we can repeat this move to obtain a positive equivalence (G, G^{−1}): (I − A) → (I − A) such that the (U, V) equals (G, G^{−1}) followed by (UG^{−1}, GV) where (UG^{−1})_{ii} and (GV)_{ii} have the forms (A.4) with Z = I. After doing this as needed for every cycle component i, we can assume for each i ∈ C

with n_{i} > 1 that we have the forms U_{ii} = (\begin{matrix}1 & 0 \\ x^{(i)} & I \end{matrix}) and V_{ii} = (\begin{matrix}1 & y^{(i)} \\ 0 & I \end{matrix}).

Let D and D′ be the block diagonal matrices equal to Id except in cycle component diagonal blocks, where D_{ii} = U_{ii} and D′_{ii} = V_{ii}^{−1}. We will produce matrices P, Q in U_{P}(n, ℤ) such that (D, Q): (I − A) → D(I − A)Q and (P, D′): (I − A′) → P (I −A′)D′ are positive equivalences, and the matrices D(I −A)Q and P (I −A′)D′ satisfy those conditions 2,3,4. Then the lemma will follow by defining (Ũ, Ṽ) by requiring the following diagram to commute:

(I − A) ⟶^{(D,Q)} D(I − A)Q
(U,V)↓  ↓^{(Ũ,Ṽ)}
(I − A′) ⟶_{(P,D′)} P (I − A′)D′

We will prove the first claim, for (D, Q); the proof of the second claim is similar. Let i_{1} < i_{2} < ⋯ < i_{k} be the elements of C. (Recall, i ≺ j ⟹ i < j.) To begin, let i = i_{k} and let 1, 2, … m index the rows through U_{ii}. For 2 ≤ j ≤ m, let R_{j} be the elementary matrix which acts from the right to subtract column j from column 1. Let R = R_{2} ⋯ R_{m} and let 1 denote a vector with every entry equal to 1, then

((I − A)R)_{ii} = (\begin{matrix}0 & 0 \\ −1 & I \end{matrix}) , and
((I − A)R)_{rs} = (I − A)_{rs} if rs ≠ ii ,

and we get a positive equivalence

(I − A) ⟶^{(I,R_{2})} ⋯ ⟶^{(I,R_{m})} (I − A)R .

Next, let D_{k} be a product of elementary matrices, E = E_{n} ⋯ E_{1}, where E_{t} acts from the left to add ϵ_{t} (ϵ_{t} = 1 or ϵ_{t} = −1) times row 1 to row j_{t}, and 2 ≤ j_{t} ≤ m. Consider the equivalence (E_{1}, I): (I − A)R → E_{1}(I − A)R. Notice (E_{1}(I − A)R)_{ii} = ((I − A)R)_{ii}. So, this equivalence (E_{1}, I) is positive unless (E_{1}(I − A)R)(j, k) > 0 for some columns p to the right of the ii block. Let F_{1} be the product of basic elementary matrices F_{1,t}, 1 ≤ t ≤ T say, which act from the right to subtract column j_{1} from such columns p enough times to guarantee (with F_{1} = F_{1,1} ⋯ F_{1,T}) that (E_{1}(I − A)RF_{1})(j_{1}, p) < 0. Then

(I − A)R ⟶^{(I,F_{1,1})} ⋯ ⟶^{(I,F_{1,T})} · ⟶^{(E_{1},I)} E_{1}(I − A)RF_{1}

gives a positive equivalence (E_{1}, F_{1}): (I − A)R → E_{1}(I − A)RF_{1}. Recursively, for 1 ≤ t < m, apply this procedure, to produce F_{t+1} giving a positive equivalence

E_{t} ⋯ E_{1}(I − A)RF_{1} ⋯ F_{t} ⟶^{(I,F_{t+1})} · ⟶^{(E_{t+1},I)} E_{t+1} ⋯ E_{1}(I − A)RF_{1} ⋯ F_{t+1} .

Let Q_{k} = F_{1} ⋯ F_{m}: then we have a positive equivalence

(I − A) ⟶^{(D_{k},RQ_{k})} D_{k}(I − A)RQ_{k} ⟶^{(I,R^{−1})} D_{k}(I − A)RQ_{k}R^{−1} .

Because RQ_{k} = Q_{k}R, altogether we get

(I − A) ⟶^{(D_{k},Q_{k})} D_{k}(I − A)RQ_{k} .

Notice, Q_{k} ∈ U_{P}(n, ℤ). Moreover, if j ∈ P and j < i_{k}, then for any t the tj blocks of (I − A) and (D_{k}(I − A)_{k}Q_{k}) are equal.

Next, for the cycle components i_{k−1}, …, i_{1} (in that order) we repeat the procedure used above for (D_{k}, Q_{k}) to produce pairs (D_{k−1}, Q_{k−1}), …, (D_{1}, Q_{1}) with D = D_{k}D_{k−1} ⋯ D_{1} and Q_{(−)} := Q_{k}Q_{k−1} ⋯ Q_{1} giving a positive equivalence

(I − A) ⟶^{(D_{k},Q_{k})} · ⟶^{(D_{k−1},Q_{k−1})} ⋯ ⟶^{(D_{1},Q_{1})} D(I − A)Q_{(−)} .

To see that the (D_{i}, Q_{i}) define positive equivalences, note that for i_{s} ≠ i_{k}, the column-subtracting moves we use to prepare the entries in a block i_{s}j to the right of the i_{s}i_{s} block do not change the sign of entries outside the i_{s}j block (because we are subtracting columns through the i_{s}i_{s} block with diagonal entry 1, and these columns have no other nonzero entry at this stage, because the earlier subtractions of columns through block i_{r}i_{r} with r ≥ s do not affect the i_{s} block column).

For every cycle component i, the ii block of the matrix D(I − A)Q_{(−)} equals Id. Suppose there exists (r, s) such that r ∈ C^{sec} and (D(I − A)Q_{(−)})(r, s) < 0; then choose such an (r, s) with r minimal, and add column r to column s. Because the (r, s) entry cannot lie in a diagonal block, this elementary positive equivalence is implemented by multiplication from the right by a matrix in U_{P}(n, ℤ). Repeat this move until a matrix is produced in which the (r, s) entry is zero whenever r ∈ C^{sec}. Let the corresponding positive equivalence be denoted (I, Q_{(+)}): D(I − A)Q_{(−)} → D(I − A)Q_{(−)}Q_{(+)}. The proof is finished by setting Q = Q_{(−)}Q_{(+)}. □

The next lemma gives the last ingredient, Stage III, for the proof of Prop. 4.5.

Lemma A.7. Suppose U, V, A, A′ satisfy the assumptions of Lemma A.3 and in addition assume that U_{ii} = V_{ii} = Id for every i ∈ C. Then there is a commuting diagram of SL_{P}(n, ℤ) equivalences

(I − A) ⟶ (I − \overline{A})
(U,V)↓  ↓^{(\overline{U},\overline{V})}
(I − A′) ⟶ (I − \overline{A′})

satisfying the conclusion of Proposition 4.5. (Moreover, \overline{A} = A and \overline{A′} = A′.)

Proof. We will build a suitable commuting diagram

(I − A) ⟶^{(E^{−1},H)} (I − A) ⟶^{(\overline{H},\overline{E}^{−1})} (I − A)
(U,V)↓  ^{(U_{3},V_{3})}↓  ↓^{(\overline{U},\overline{V})}
(I − A′) ⟶_{(I,I)} (I − A′) ⟶_{(I,I)} (I − A′)

and then use (\overline{H}E^{−1}, H\overline{E}^{−1}) and (I, I) for the upper and lower horizontal arrows in the diagram required for the lemma. First we work on the left half of the diagram. We will choose E, H, U_{3} satisfying

(i) U_{3}(i, j) = δ_{ij} , ∀i ∈ C^{sec}, (ii) (E^{−1}, H): (I − A) → (I − A) is a positive equivalence, and (iii) H^{−1}(i, j) = δ_{ij} , ∀i ∉ C^{sec} .

Recall, I_{s} denotes the set of indices for rows/columns through A_{ss}. To choose E, let the entries (i, j) for which i ∈ C^{sec} and U(i, j) ≠ δ_{ij} be listed as (i_{1}, j_{1}), …, (i_{n}, j_{n}), where i_{k} ∈ I_{s(k)} and s(1) ⪯ s(2) ⪯ ⋯ ⪯ s(n). (So, j_{k} ∈ I_{t(k)} with s(k) ≺ t(k) since by assumption U_{s(k)s(k)} = Id.) Let μ_{k} = U(i_{k}, j_{k}). Define matrices E_{k}, 1 ≤ k ≤ n, by E_{k}(i_{k}, j_{k}) = −μ_{k} and otherwise E_{k}(i, j) = δ_{ij}. Then (UE_{k})(i_{k}, j_{k}) = 0. Define E = E_{1}E_{2} ⋯ E_{n}. Then by our ordering s(1) ⪯ s(2) ⪯ ⋯ ⪯ s(n), we have (UE)(i, j) = δ_{ij} for i ∈ C^{sec}. Let U_{3} = UE, now (i) holds, and U = (UE)E^{−1} = U_{3}E^{−1} as required for the diagram to commute. Also E(i, j) = δ_{ij} if i ∉ C^{sec}, so E^{−1}(i, j) = δ_{ij} if i ∉ C^{sec}.

Next for 1 ≤ k ≤ n, we will define H_{k} such that (E_{k}^{−1}, H_{k}): (I − A) → (I − A) is a positive equivalence and H_{k}(i, j) = δ_{ij} when i ∉ C^{sec}. Then we will set (E^{−1}, H) = (E_{n}^{−1} ⋯ E_{1}^{−1}, H_{1} ⋯ H_{n}), so that (E^{−1}, H): (I − A) → (I − A) is the composition of positive equivalences and satisfies (ii). To prepare for the definition of H_{k}, given k pick M a positive integer greater than the absolute value of any entry in row i_{k} of E_{k}^{−1}(I − A), and define a matrix F_{k} as follows: F_{k}(i_{k}, j) = −M if i_{k} ≠ j and (E_{k}^{−1}(I − A))(i_{k}, j) ≠ 0, and F_{k}(i, j) = δ_{ij} otherwise. Define a matrix G_{k} by setting G_{k}(i_{k}, j) = −(E_{k}^{−1}(I − A)F_{k})(i_{k}, j) and G_{k}(i, j) = δ_{ij} otherwise. Then we have the positive equivalence

(I − A) ⟶^{(I,F_{k})} · ⟶^{(E_{k}^{−1},I)} · ⟶^{(I,G_{k})} (I − A) .

Let H_{k} = F_{k}G_{k}. Note H_{k}(i, j) = δ_{ij} if i ∉ C^{sec}, so H(i, j) = δ_{ij} if i ∉ C^{sec}, and therefore also H^{−1}(i, j) = δ_{ij} if i ∉ C^{sec}. We now have E, H, U_{3} satisfying (i)−(iii).

To get the right half of the commuting diagram, we apply to the equivalence (U_{3}, V_{3}) the transpose of the procedure above to get matrices \overline{E}, \overline{H}, \overline{V} , \overline{U} satisfying

\overline{(i)} \overline{V} (i, j) = δ_{ij} , ∀j ∈ C^{sec}, \overline{(ii)} (\overline{H}, \overline{E}^{−1}): (I − A) → (I − A) is a positive equivalence, and \overline{(iii)} \overline{H}^{−1}(i, j) = δ_{ij} , ∀j ∉ C^{sec} ,

where \overline{U} and \overline{V} are defined by \overline{U} = U_{3}\overline{H}^{−1} and \overline{V} = \overline{E}V_{3}. Using \overline{(i)} and the forms of (I − A) and (I − A′), we get for every j ∈ C^{sec} and every i that

\overline{U}(i, j) = (\overline{U}(I − A))(i, j) = (\overline{U}(I − A)\overline{V})(i, j) = (I − A′)(i, j) = δ_{ij} = \overline{V} (i, j) .

Now suppose i ∈ C^{sec}. We claim that \overline{U}(i, j) = δ_{ij}. Suppose not. Pick j ≠ i such that \overline{U}(i, j) ≠ 0. Because \overline{U} = U_{3}\overline{H}^{−1}, it follows from (i) that \overline{U}(i, j) = \overline{H}^{−1}(i, j), and then from \overline{(iii)} that j ∈ C^{sec}. This is a contradiction.

Finally, for i ∈ C^{sec} we obtain

\overline{V} (i, j) = ((I − A)\overline{V})(i, j) = (\overline{U}(I − A)\overline{V})(i, j) = (I − A′)(i, j) = δ_{ij} .

This finishes the proof. □

References

[Ba1] L. Badoian, Flow equivalences of shifts of finite type and flow K-theory. PhD. thesis, University of California, Berkeley (1998), 143 pages.

[Ba2] L. Badoian, personal communication (2000).

[Bow] R. Bowen, Equilibrium states and the ergodic theory of Anosov Diffeomorphisms, Springer Lecture Notes in Math. 470 (1975), Springer-Verlag.

[BowF] R. Bowen and J. Franks. Homology for zero-dimensional basic sets. Annals of Math. 106 (1977), 73-92.

[B1] M. Boyle, Symbolic dynamics and matrices, in Combinatorial and graph-theoretical problems in linear algebra, I. M. A. Volumes in Math. 50 (1993), Springer-Verlag, 1-38.

[B2] M. Boyle, talk at Mt. Holyoke conference “Classification problems in C^{∗}-algebras and dynamics” (1996).

[BFF] M. Boyle, D. Fiebig and U. Fiebig, A dimension group for local homeomorphisms and endomorphisms of onesided shifts of finite type, J. Reine Angew. Math. 487 (1997), 27–59.

[BHa] M. Boyle and D. Handelman, Orbit equivalence, flow equivalence and ordered cohomology, Israel J. Math. 95 (1996), 169-210.

[BH] M. Boyle and D. Huang, Poset block equivalence of integral matrices, preprint (2000) www.math.umd.edu/ ∼mmb .

[BW] M. Boyle and J. B. Wagoner, in preparation.

[C] J. Cuntz, A class of C^{∗}-algebras and topological Markov chains II: reducible chains and the Ext-functor for C^{∗}-algebras, Inventiones Math. 63 (1981), 25-40.

[CK] J. Cuntz and W. Krieger, A class of C*-Algebras and topological Markov chains, Inventiones Math. 56 (1980), 251-268.

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

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

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

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

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

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

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

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

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

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

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

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

[KRW3] K.H. Kim, F.W. Roush, and J.B. Wagoner, Characterization of inert actions on periodic points. Part II, Forum Math., to appear.

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

[Kr1] W. Krieger, On a dimension for a class of homeomorphism groups, Math. Ann. 252 (1980), 239-250.

[Kr2] W. Krieger, On dimension functions and topological Markov chains, Inventiones Math. 56 (1980), 239-250.

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

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

[Ne] M. Newman, Integral Matrices, Academic Press, New York (1972).

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

[PT] W. Parry and S. Tuncel, Classification Problems in Ergodic Theory, LMS Lecture Note Series 67, Cambridge Press, Cambridge (1982).

[Rob] C. Robinson, Dynamical systems. Stability, symbolic dynamics, and chaos, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL (1995).

[R] M. Rørdam, Classification of Cuntz-Krieger algebras, K-theory 9 (1995), 31-58.

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

[S] S. Smale Differentiable dynamical systems, Bull. Amer. Math. Soc. 73 (1967), 747–817.

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

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

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

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

E-mail address: mmb@math.umd.edu