Presentations of Subshifts

and Their Topological Conjugacy Invariants

Kengo Matsumoto

Received: November 23, 1998 Revised: May 19, 1999

Communicated by Joachim Cuntz

Abstract. We introduce the notions of symbolic matrix system and λ-graph system that are presentations of subshifts. They are generalized notions of symbolic matrix and λ-graph for sofic subshifts to general subshifts. We then formulate strong shift equivalence and shift equivalence between symbolic matrix systems and show that two subshifts are topologically conjugate if and only if the associated canonical symbolic matrix systems are strong shift equivalent. We construct several kinds of shift equivalence invariants for symbolic matrix systems. They are the dimension groups, the Bowen-Franks groups and the nonzero spectrum that are generalizations of the corresponding notions for nonnegative matrices. The K-groups for symbolic matrix systems are introduced. They are also shift equivalence invariants and stronger than the Bowen-Franks groups but weaker than the dimension triples. These kinds of shift equivalence invariants naturally induce topological conjugacy invariants for subshifts.

1991 Mathematics Subject Classification: Primary 58F03, Secondary 54H20, 34C35, 19K14, 19K33 Keywords and Phrases: subshifts, symbolic dynamics, topological conjugacy, strong shift equivalence, shift equivalence, dimension group, Bowen-Franks group

Contents

1. Introduction

2. Symbolic matrix systems and λ-graph systems

3. Presentations of subshifts

4. Strong shift equivalence

5. Higher λ-graph systems

6. Shift equivalence

7. Nonnegative matrix systems

8. Dimension groups

9. K-groups and Bowen-Franks groups

10. Spectrum

11. Example.

1.Introduction

The classification of symbolic dynamical systems has been a very important and one of central problems in the theory of topological dynamical systems and the ergodic theory. The classification problem has been first examined for a class of symbolic dynamical systems called subshifts of finite type or topological Markov shifts. Each dynamical system of the class is determined by a single square matrix with entries in nonnegative integers. Hence the behavior of such a dynamical system depends on the underlying matrix. In [Wi], R. F. Williams introduced the notions of strong shift equivalence and shift equivalence between nonnegative matrices and showed that two topological Markov shifts are topologically conjugate if and only if the associated matrices are strong shift equivalent. He also showed that strong shift equivalence implies shift equivalence. Although the converse implication had been a long standing problem, Kim-Roush [KimR2] has recently solved negatively for even irreducible matrices. There is a class of subshifts called sofic subshifts that are generalized class of Markov shifts and that are determined by square matrices with entries in alphabet (see [Kit], [Kr3], [LM], [We], etc.). A square matrix with entries in alphabet is simply called a symbolic matrix. It is an equivalent object to a labeled graph called a λ-graph. M. Nasu in [N], [N2] generalized the notion of strong shift equivalence to symbolic matrices. He showed that two sofic subshifts are topologically conjugate if and only if their canonical symbolic matrices are strong shift equivalent ([N], [N2], see also [HN]). M. Boyle and W. Krieger in [BK] introduced the notion of shift equivalence for symbolic matrices and studied topologically conjugacy for sofic subshifts. In this paper, we first introduce the notions of symbolic matrix system and λ-graph system. They are generalized notions of symbolic matrix and λ-graph for sofic subshifts. We will show that they are presentations of subshifts. A symbolic matrix system consists of two sequences of rectangular matrices (M_{l,l+1}, I_{l,l+1}), l ∈ ℕ. The matrices M_{l,l+1} have entries in symbols and the matrices I_{l,l+1} have entries in {0, 1}. They satisfy the following commutation relations

I_{l,l+1}M_{l+1,l+2} = M_{l,l+1}I_{l+1,l+2}, l ∈ ℕ.

A λ-graph system is an inductive sequence of Bratteli diagrams, that come from the theory of operator algebras, with labeled edges by symbols. We will know that the symbolic matrix systems and the λ-graph systems are the same objects and give rise to subshifts. There is a canonical method to construct a symbolic matrix system from an arbitrary subshift (Theorem 3.7). The obtained symbolic matrix system is said to be canonical for the subshift. If a subshift is sofic, the canonical symbolic matrix system corresponds to the symbolic matrix of its left Krieger cover graph. As a generalization of the notion of strong shift equivalence for nonnegative matrices and symbolic matrices, we will introduce the notion of strong shift equivalence for our symbolic matrix systems. We will prove Theorem A (Theorem 4.2 and Theorem 4.15). Two subshifts are topologically conjugate if and only if their canonical symbolic matrix systems are strong shift equivalent.

Hence classification problem for subshifts are completely reduced to the classification of symbolic matrix systems up to strong shift equivalence in our sense. In the proof of the only if part of Theorem A, we provide the notion of bipartite λ-graph system. We then essentially use Nasu’s factorization theorem for topological conjugacy between subshifts into bipartite codes and symbolic conjugacies. We will next define shift equivalence between two symbolic matrix systems. That is a generalization of the corresponding notion for symbolic matrices defined by Boyle-Krieger in [BK]. We will see that strong shift equivalence implies shift equivalence even in our setting (Theorem 6.2). Similarly to the case of topological Markov shifts, we can prove that shift equivalence between two canonical symbolic matrix systems gives rise to an eventual conjugacy for the associated subshifts, that is, a topological conjugacy for their corresponding higher power shifts (Proposition 6.3). This result was motivated by a question raised by W. Krieger at a workshop at Kyushu University, Japan, March 1998. For nonnegative matrices, there are two crucial shift equivalence invariants consisting of abelian groups. One is the dimension groups defined by W. Krieger in [Kr], [Kr2] and the other one is the Bowen-Franks groups in [BF]. They induce topological conjugacy invariants for the associated topological Markov shifts. We will generalize the two shift equivalence invariants to our symbolic matrix systems. For a symbolic matrix system (M, I), let M_{l,l+1} be the nonnegative rectangular matrix obtained from M_{l,l+1} by setting all the symbols equal to 1 for each l ∈ ℕ. Then the resulting pair (M, I) still satisfies the following relations.

I_{l,l+1}M_{l+1,l+2} = M_{l,l+1}I_{l+1,l+2}, l ∈ ℕ.

We call (M, I) the nonnegative matrix system for (M, I). We say (M, I) to be canonical when (M, I) is canonical. More generally, for a sequence M_{l,l+1}, l ∈ ℕ of rectangular matrices with entries in nonnegative integers and a sequence I_{l,l+1}, l ∈ ℕ of rectangular matrices with entries in {0, 1}, the pair (M, I) is called a nonnegative matrix system if they satisfy the relations above. For a single n×n nonnegative square matrix A, if we set M_{l,l+1} = A and I_{l,l+1} = I_{n} : the n × n identity matrix for all l ∈ ℕ, the pair (M, I) is a nonnegative matrix system. We will similarly formulate strong shift equivalence and shift equivalence between nonnegative matrix systems. These equivalences are generalizations of the corresponding equivalences for single nonnegative square matrices. We will define the following three kinds of objects for a nonnegative matrix system (M, I).

(i) The dimension triple: (Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}).

(ii) The K-groups: K_{0}(M, I), K_{1}(M, I).

(iii) The Bowen-Franks groups: BF^{0}(M, I), BF^{1}(M, I).

The dimension triple (Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}) consist of an ordered abelian group Δ_{(M,I)} with positive cone Δ_{(M,I)}^{+} and an ordered automorphism δ_{(M,I)} on it. The K-groups K_{i}(M, I), i = 0, 1 consist of a pair of abelian groups. The Bowen-Franks groups BF^{i}(M, I), i = 0, 1 also consist of a pair of abelian groups. Let m(l) be the row size of the matrix I_{l,l+1} for each l ∈ ℕ. Let ℤ_{I^{t}} be the abelian group defined by the inductive limit ℤ_{I^{t}} = \underrightarrow{lim}_{l}\{I_{l,l+1}^{t} : ℤ^{m(l)} →

ℤ^{m(l+1)}}. The sequence M_{l,l+1}^{t}, l ∈ ℕ of the transposes of M_{l,l+1} naturally yields an endomorphism on ℤ_{I^{t}} that is denoted by λ_{(M,I)}. The dimension group and the K-groups are defined as follows:

Δ_{(M,I)} = \underrightarrow{lim}\{λ_{(M,I)} : ℤ_{I^{t}} → ℤ_{I^{t}}\}

and

K_{0}(M, I) = ℤ_{I^{t}}/(id − λ_{(M,I)})ℤ_{I^{t}}, K_{1}(M, I) = Ker(id − λ_{(M,I)}) in ℤ_{I^{t}}.

The positive cone Δ_{(M,I)}^{+} of Δ_{(M,I)} is \underrightarrow{lim}\{λ_{(M,I)} : ℤ_{I^{t}}^{+} → ℤ_{I^{t}}^{+}\} where ℤ_{I^{t}}^{+} is the natural positive cone of ℤ_{I^{t}} and the automorphism δ_{(M,I)} on Δ_{(M,I)} is induced one from λ_{(M,I)}. Set the projective limit of the abelian group as

ℤ_{I} = \underleftarrow{lim}_{l}\{I_{l,l+1} : ℤ^{m(l+1)} → ℤ^{m(l)}\}. The sequence M_{l,l+1}, l ∈ ℕ acts on ℤ_{I} as

an endomorphism that we denote by M. The identity on ℤ_{I} is denoted by I. The Bowen-Franks groups for (M, I) are defined by

BF^{0}(M, I) = ℤ_{I}/(I − M)ℤ_{I}, BF^{1}(M, I) = Ker(I − M) in ℤ_{I}.

The above notions of dimension triple and Bowen-Franks group of degree zero for a nonnegative matrix system are generalizations of the corresponding notions for a single nonnegative square matrix. We will prove that the following Universal Coefficient Theorem holds (Theorem 9.6). It says that there exists a short exact sequence

0 ⟶ Ext_{ℤ}^{1}(K_{0}(M, I), ℤ) ⟶^{δ} BF^{0}(M, I) ⟶^{γ} Hom_{ℤ}(K_{1}(M, I), ℤ) ⟶ 0

that splits unnaturally. We also see that

BF^{1}(M, I) ≅ Hom_{ℤ}(K_{0}(M, I), ℤ).

The three kinds of objects above are proved to be invariant under shift equivalence in nonnegative matrix systems. Hence they are naturally induce topological conjugacy invariants for subshifts by taking their canonical nonnegative matrix systems. We will describe relationships among the equivalences and the invariants for the matrix systems as in the following way :

Theorem B. For two symbolic matrix systems (M, I), (M′, I′) and their nonnegative matrix systems (M, I), (M′, I′), consider the following situations:

(S1) (M, I) ≈ (M′, I) : strong shift equivalence, (N1) (M, I) ≈ (M′, I) : strong shift equivalence, (S2) (M, I) ∼ (M′, I) : shift equivalence, (N2) (M, I) ∼ (M′, I) : shift equivalence,

(3) (Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}) ≅ (Δ_{(M′,I′)}, Δ_{(M′,I′)}^{+}, δ_{(M′,I′)}) : isomorphic dimension triples,

(4) (Δ_{(M,I)}, δ_{(M,I)}) ≅ (Δ_{(M′,I′)}, δ_{(M′,I′)}) : isomorphic dimension pairs,

(5) K_{∗}(M, I) ≅ K_{∗}(M′, I) : isomorphic K-groups,

(6) BF^{∗}(M, I) ≅ BF^{∗}(M′, I) : isomorphic Bowen-Franks groups. Then we have the following implications:

(S1) ⟹ (S2)
⇓  ⇓
(N1) ⟹ (N2) ⟹ (3) ⟹ (4) ⟹ (5) ⟹ (6).

It is well-known that the set of all nonzero eigenvalues of a nonnegative matrix A is also a shift equivalence invariant. The set for A is called the nonzero spectrum of A and plays an important rôle for studying dynamical properties of the associated topological Markov shift (cf.[LM], [Kit]). We introduce eigenvalues and eigenvectors of a nonnegative matrix system and then generalize the notion of the nonzero spectrum of a single nonnegative matrix to a nonnegative matrix system (M, I). We denote by Sp^{×}(M, I) the set of all nonzero eigenvalues of (M, I). A nonnegative matrix system (M, I) in general is an infinite sequence of pairs of matrices M_{l,l+1}, I_{l,l+1}, l ∈ ℕ for which sizes of matrices are increasing. Hence it seems to be natural to deal with eigenvalues having a certain boundedness condition on the corresponding eigenvectors. We denote by Sp_{b}^{×}(M, I) the set of all nonzero eigenvalues of (M, I) with the boundedness condition on the corresponding eigenvectors. We will prove, in Section 10, that the both of the nonzero spectrums Sp^{×}(M, I) and Sp_{b}^{×}(M, I) are not empty and invariant under shift equivalence of (M, I). In particular, if (M, I) is the canonical nonnegative matrix system for a subshift, the set Sp_{b}^{×}(M, I) is bounded by the topological entropy of the subshift. We then define the nonzero spectrum and the nonzero bounded spectrum for subshifts by the corresponding sets for the canonical nonnegative matrix systems (Theorem 10.14). In the final section, we present an example of the canonical symbolic matrix system for a certain nonsofic subshift, called the context free shift in [LM;Example 1.2.9]. Its K-groups and Bowen-Franks groups are calculated. We see that the types of the invariants can not appear in those of sofic shifts. The maximum of the absolute values of the bounded spectrums of the canonical nonnegative matrix system for the subshift is 1 + \sqrt{1 + \sqrt{3}}. The value is the maximum in the bounded spectrum and coincides with the topological entropy of the subshift.

The author has recently constructed the C^{∗}-algebra O_{Λ} associated with subshift Λ ([Ma]). The C^{∗}-algebra O_{Λ} has a canonical action of the one dimensional torus group, called gauge action and written as α. The fixed point algebra F_{Λ} of O_{Λ} under α is an AF-algebra which is stably isomorphic to the crossed product O_{Λ} ×_{α} 𝕋 ([Ma2]). Let (M, I) be the canonical nonnegative matrix system for the subshift Λ. The invariants mentioned above are described in terms of the K-theory for the C^{∗}-algebras as in the following way:

(Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}) = (K_{0}(F_{Λ}), K_{0}(F_{Λ})_{+}, α̂_{∗}),
K_{i}(M, I) = K_{i}(O_{Λ}),  i = 0, 1,
BF^{i}(M, I) = Ext^{i+1}(O_{Λ}),  i = 0, 1

where α̂ denotes the dual action of α and Ext^{1}(O_{Λ}) = Ext(O_{Λ}), Ext^{0}(O_{Λ}) = Ext(O_{Λ} ⊗ C_{0}(ℝ)). The normalized nonnegative eigenvectors of (M, I) exactly correspond to the KMS-states for α on the C^{∗}-algebra O_{Λ}. Hence the set of all bounded spectrums with nonnegative eigenvectors are the set of all inverse temperatures for the admitted KMS states.

Acknowledgements: The author would like to thank Wolfgang Krieger for his valuable advices and suggestions, in particular for his question on Proposition 6.3. The author also would like to thank Toshihiro Hamachi and Yasuo Watatani for pointing out an error and an inaccuracy in an earlier version of this paper. Finally, the author wishes to express his gratitude to Joachim Cuntz and referees for advices and suggestions in the presentation of this paper.

2. symbolic matrix systems and λ-graph systems

We fix a finite set Σ and call it the alphabet. Each element of Σ is called a symbol. We always write the empty symbol ∅ in Σ as 0. We denote by 𝔖_{Σ} the set of all finite formal sums of elements of Σ. A square matrix with entries in 𝔖_{Σ} is called a symbolic matrix over Σ.

Definition. Let (M_{l,l+1}, I_{l,l+1}), l ∈ ℕ be a pair of sequences of rectangular matrices such that the following four conditions for each l ∈ ℕ are satisfied:

(1) M_{l,l+1} is an m(l) × m(l + 1) rectangular matrix with entries in 𝔖_{Σ}.

(2) I_{l,l+1} is an m(l) × m(l + 1) rectangular matrix with entries in {0, 1}

satisfying the following two conditions: (2-a) For i, there exists j such that I_{l,l+1}(i, j) ≠ 0. (2-b) For j, there uniquely exists i such that I_{l,l+1}(i, j) ≠ 0.

(3) m(l) ≤ m(l + 1).

(4) I_{l,l+1}M_{l+1,l+2} = M_{l,l+1}I_{l+1,l+2}. The pair (M, I) is called a symbolic matrix system over Σ. For i = 1, …, m(l), j = 1, …, m(l + 1), we denote by M_{l,l+1}(i, j), I_{l,l+1}(i, j) the (i, j)- components of M_{l,l+1}, I_{l,l+1} respectively. A symbolic matrix system (M, I) is said to be essential if it satisfies the following further conditions:

(5-i) For i, there exists j such that M_{l,l+1}(i, j) ≠ 0. (5-ii) For j, there exists i such that M_{l,l+1}(i, j) ≠ 0.

We henceforth study essential symbolic matrix systems and call them symbolic matrix systems for simplicity. The following notion of specified equivalence between symbolic matrices has been introduced by M. Nasu in [N1], [N2]. For two symbolic matrices A over alphabet Σ and A′ over alphabet Σ′ and bijection ϕ from a subset of Σ onto a subset of Σ′, we call A and A′ are specified equivalence under specification ϕ if A′ can be obtained from A by

replacing every symbol a appearing in A by ϕ(a). We write it as A ≃^{ϕ} A′. We call ϕ a specification from Σ to Σ′. Two symbolic matrix systems (M, I) over Σ and (M′, I′) over Σ′ are said to be isomorphic if there exists a specification ϕ from Σ to Σ′ and an m(l) × m(l)- square permutation matrix P_{l} for each l ∈ ℕ such that

P_{l}M_{l,l+1} ≃^{ϕ} M′_{l,l+1}P_{l+1},  P_{l}I_{l,l+1} = I′_{l,l+1}P_{l+1}  for l ∈ ℕ.

The notion of symbolic matrix system is a generalized notion of symbolic matrix. We say a symbolic matrix system (M, I) to be sofic if there exists a number L ∈ ℕ such that

M_{l,l+1} = M_{L,L+1}, I_{l,l+1} = I_{L,L+1}

for all l ≥ L. Hence in this case, we see m(L) = m(l) for all l ≥ L. A symbolic matrix corresponds to a labeled graph, called a λ-graph, that is a presentation of a sofic subshift. We will next consider a generalization of λ-graphs corresponding to symbolic matrix systems. We first explain the notion of Bratteli diagram that appears in the theory of operator algebras (see [Bra], [Ef], [El]). A Bratteli diagram consists of a vertex set V and an edge set E satisfying the following conditions. We have a decomposition of V as a disjoint union V = V_{1} ∪ V_{2} ∪ ⋯ where each V_{l} is finite and nonempty. Similarly E decomposes as a disjoint union E = E_{1,2}∪E_{2,3}∪⋯ where each E_{l,l+1} is finite and nonempty. Moreover we have maps s, r : E → V such that s(E_{l,l+1}) ⊂ V_{l}, r(E_{l,l+1}) ⊂ V_{l+1}. They are called a source map and a range map respectively. A Bratteli diagram (V, E) is said to be essential if it satisfies the condition that s^{−1}(v) is nonempty for all v ∈ V and r^{−1}(v) is nonempty for all v ∈ V ⧹V_{1}. For u ∈ V_{l}, v ∈ V_{l+1}, put

E_{l,l+1}(u, v) = {e ∈ E_{l,l+1}|s(e) = u, r(e) = v}.

We next introduce the notion of labeled Bratteli diagram. A labeled Bratteli diagram over alphabet Σ consists of a Bratteli diagram (V, E) and a map λ from E to Σ. Definition. A λ-graph system over alphabet Σ consists of a labeled Bratteli diagram (V, E, λ) over Σ and a surjective map ι from V ⧹V_{1} to V satisfying the following two conditions:

(1) ι(V_{l+1}) = V_{l} for l ∈ ℕ.

(2) For u ∈ V_{l}, w ∈ V_{l+2}, there exists a bijective correspondence between the edge sets

E_{l,l+1}(u, ι(w)) and ⋃_{v∈V_{l+1},ι(v)=u} E_{l+1,l+2}(v, w)

that is compatible with the labeling λ. We denote by (V, E, λ, ι) the λ-graph system. The following two conditions are implied from the above condition (2).

(2-i) For e ∈ E_{l+1,l+2}, there exists e′ ∈ E_{l,l+1} such that

ι(s(e)) = s(e′), ι(r(e)) = r(e′) and λ(e) = λ(e′).

(2-ii) For f ∈ E_{l,l+1}, v ∈ V_{l+2} with ι(v) = r(f), there exists e ∈ E_{l+1,l+2}

such that

ι(s(e)) = s(f), r(e) = v and λ(e) = λ(f).

A λ-graph system (V, E, λ, ι) is said to be essential if the Bratteli diagram (V, E) is essential. We always treat an essential λ-graph system and call it a λgraph system for simplicity. We remark that by the condition (1) in Definition of λ-graph system the cardinality of the set V_{l+1} is greater than or equal to that of the set V_{l}. Two λ-graph systems (V, E, λ, ι) over alphabet Σ and (V′, E′, λ′, ι′) over alphabet Σ′ are said to be isomorphic if there exist bijections Φ_{V} : V → V′, Φ_{E} : E → E′ and a specification ϕ : Σ → Σ′ such that

(1) Φ_{V} (V_{l}) = V′_{l} and Φ_{E}(E_{l,l+1}) = E′_{l,l+1} for l ∈ ℕ,

(2) Φ_{V} (s(e)) = s(Φ_{E}(e)) and Φ_{V} (r(e)) = r(Φ_{E}(e)) for e ∈ E,

(3) ι′(Φ_{V} (v)) = Φ_{V} (ι(v)) for v ∈ V,

(4) λ′(Φ_{E}(e)) = ϕ(λ(e)) for e ∈ E.

Proposition 2.1. There exists a bijective correspondence between the set of all isomorphism classes of symbolic matrix systems and the set of all isomorphism classes of λ-graph systems.

Proof. 1. From symbolic matrix systems to λ-graph systems: Let (M, I) be a symbolic matrix system over Σ. We are always assuming that it is essential. For each l ∈ ℕ, let V_{l} = {1, …, m(l)} be the set of all rows of the matrix M_{l,l+1} and E_{l,l+1} the disjoint union of elements appearing in the components of M_{l,l+1}. For each e ∈ E_{l,l+1} we put s(e) = i and r(e) = j if e appears in M_{l,l+1}(i, j). The map ι : V ⧹V_{1} → V is defined as ι(j) = i for j ∈ V_{l+1} if I_{l,l+1}(i, j) = 1. The map λ : E → Σ is defined by λ(e) = e. Then it is straightforward to see that (V, E, λ, ι) is a λ-graph system.

2. From λ-graph systems to symbolic matrix systems : Let (V, E, ι, λ) be a λ-graph system over Σ. We denote by m(l) the cardinality of the vertex set V_{l}. We identify V_{l} with the set {1, …, m(l)}. We define m(l) × m(l + 1) matrices as follows: For i ∈ V_{l}, j ∈ V_{l+1}, set I_{l,l+1}(i, j) = 1 if ι(j) = i otherwise I_{l,l+1}(i, j) = 0. For e_{k} ∈ E_{l,l+1}, k = 1, …, n with s(e_{k}) = i, r(e_{k}) = j, we put M_{l,l+1}(i, j) = λ(e_{1})+⋯+λ(e_{n}). It is straightforward to see that the relations I_{l,l+1}M_{l+1,l+2} = M_{l,l+1}I_{l+1,l+2} for l ∈ ℕ hold.

3. Presentations of subshifts

As in the preceding section, symbolic matrix systems may be identified with λgraph systems. We will in this section construct subshifts, a class of topological dynamical systems, from λ-graph systems. We will further show that any subshift comes from a λ-graph system. This is a generalized observation of the correspondences between the sofic subshits and the symbolic matrices. Hence studies of subshifts are completely reduced to the studies of λ-graph systems and hence symbolic matrix systems.

We will review on subshifts. Let Σ be an alphabet. Let Σ^{ℤ}, Σ^{ℕ} be the infinite product spaces ∏_{i=−∞}^{∞} Σ_{i}, ∏_{i=1}^{∞} Σ_{i} where Σ_{i} = Σ, endowed with the product topology respectively. The transformation σ on Σ^{ℤ}, Σ^{ℕ} given by (σ(x_{i})) = (x_{i+1}), i ∈ ℤ, ℕ is called the (full) shift. Let Λ be a shift invariant closed subset of Σ^{ℤ} i.e. σ(Λ) = Λ. The topological dynamical system (Λ, σ|_{Λ}) is called a subshift. We denote σ|_{Λ} by σ and write the subshift as Λ for short. We denote by X_{Λ}(⊂ ∏_{i=1}^{∞} Σ_{i}) the set of all right-infinite sequences that appear in Λ. The dynamical system (X_{Λ}, σ) is called the right one-sided subshift for Λ. We will give examples of subshifts as follows (cf.[LM], [Kit]): Let A be an n × n matrix with entries in nonnegative integers. Put V_{A} = {1, …, n}: the vertex set. Write A(i, j) edges from i ∈ V_{A} to j ∈ V_{A}. Hence we have a directed graph from A. We denote it by G_{A}. Let E_{A} be the set of all edges of the graph G_{A}. Let s_{A}, r_{A} be the map from E_{A} to V_{A} that assigns the source and the range of the edge. Let Λ_{A} be the set of all biinfinite sequences (e_{i})_{i∈ℤ} of e_{i} ∈ E_{A} with r_{A}(e_{i}) = s_{A}(e_{i+1}), i ∈ ℤ. Then Λ_{A} becomes a subshift, called the topological Markov shift defined by A. Let A be an n × n symbolic matrix over Σ. Each entry A(i, j), i, j = 1, …, n consists of elements of 𝔖_{Σ}. Similarly to the construction above, we have a directed graph G_{A} from the matrix A with labeled edges by the symbols in Σ. We denote by λ(e) = α ∈ Σ the label α of edge e. Let Λ_{A} be the set of all biinfinite sequences λ(e_{i})_{i∈ℤ} of labels of the sequence of edges e_{i} ∈ E_{A} with r_{A}(e_{i}) = s_{A}(e_{i+1}), i ∈ ℤ. Then Λ_{A} becomes a subshift, called the sofic subshift defined by A. The labeled graph G_{A} is called a λ-graph for A. There are many nonsofic subshifts as seen in [LM]. We will see an example of nonsofic subshift in the final section. A finite sequence μ = (μ_{1}, ..., μ_{k}) of elements μ_{j} ∈ Σ is called a block or a word. We denote by |μ| the length k of μ. A block μ = (μ_{1}, ..., μ_{k}) is said to occur or appear in x = (x_{i}) ∈ Σ^{ℤ} if x_{m} = μ_{1}, ..., x_{m+k−1} = μ_{k} for some m ∈ ℤ.

We will first construct subshifts from symbolic matrix systems. Let (M, I) be a symbolic matrix system over Σ and (V, E, λ, ι) its corresponding λ-graph system. For k < l, let P_{k,l} be the set of all paths from V_{k} to V_{l}, that is,

P_{k,l} ={(e_{k}, e_{k+1}, …, e_{l−1})|e_{i} ∈ E_{i,i+1}, r(e_{i}) = s(e_{i+1}) for i = k, k+1, …, l−2}.

We define the maps s : P_{k,l} → V_{k} and r : P_{k,l} → V_{l} by

s(e_{k}, e_{k+1}, …, e_{l−1}) = s(e_{k}), r(e_{k}, e_{k+1}, …, e_{l−1}) = r(e_{l−1}).

The labeling λ : P_{k,l} → Σ^{l−k} = \underbrace{Σ × ⋯ × Σ}_{l−k times} is defined by

λ(e_{k}, e_{k+1}, …, e_{l−1}) = λ(e_{k})λ(e_{k+1}) ⋯ λ(e_{l−1}).

Set

L_{k,l} = {λ(w) ∈ Σ^{l−k}|w ∈ P_{k,l}}.

Put L_{l} = L_{1,l+1} and endow it with discrete topology. The map π_{l} : L_{l+1} → L_{l} is defined by

π_{l}(α_{1}, …, α_{l+1}) = (α_{1}, …, α_{l}).

We set

X_{(M,I)} = \underleftarrow{lim}\{π_{l} : L_{l+1} → L_{l}\}

the projective limit in the category of compact Hausdorff spaces. That is

X_{(M,I)} = {(λ(e_{1}), λ(e_{2}), …) ∈ Σ^{ℕ}|e_{i} ∈ E_{i,i+1}, r(e_{i}) = s(e_{i+1}) for i ∈ ℕ}

the set of all right infinite sequences consisting of labels along infinite paths. The topology on X_{(M,I)} is defined from open sets of the form

U_{(μ_{1},...,μ_{k})} = {(α_{1}, α_{2}, …) ∈ X_{(M,I)}|α_{i} = μ_{i} for i = 1, …, k}

for (μ_{1}, …, μ_{k}) ∈ L_{k}.

Lemma 3.1. If (α_{1}, α_{2}, …) ∈ X_{(M,I)}, we have (α_{2}, α_{3}, …) ∈ X_{(M,I)}.

Proof. The assertion is direct from the condition (2-i) of Definition of λ-graph system.

Lemma 3.2. For l > k, if (α_{k}, …, α_{l−1}) ∈ L_{k,l}, we have (α_{k}, …, α_{l−1}) ∈ L_{k+1,l+1}.

Proof. For (α_{k}, …, α_{l−1}) ∈ L_{k,l}, take f_{i} ∈ E_{i,i+1} such as α_{i} = λ(f_{i}) for i = k, k + 1, …, l − 1 and r(f_{i}) = s(f_{i+1}) for i = k, k + 1, …, l − 2. We find v_{l+1} ∈ V_{l+1} with ι(v_{l+1}) = r(f_{l−1}). By the condition (2-ii) of Definition of λgraph system, there exists e_{l} ∈ E_{l,l+1} such that ι(s(e_{l})) = s(f_{l−1}), r(e_{l}) = v_{l+1} and λ(e_{l}) = λ(f_{l−1}). Put v_{l} = s(e_{l}) ∈ V_{l}. We continue theses procedures so that we get e_{i} ∈ E_{i,i+1} for i = k + 1, k + 2, …, l satisfying ι(s(e_{i})) = s(f_{i−1}), r(e_{i}) = s(e_{i+1}) and λ(e_{i}) = λ(f_{i−1}) for i = k + 1, k + 2, …, l. Hence α_{i} = λ(e_{i+1}) and (α_{k}, …, α_{l−1}) ∈ L_{k+1,l+1}.

As in [LM; Definition 1.3.1], a set 𝔏 of words of alphabet Σ is called a language if it satisfies the following conditions:

(a) Every subword of a word w in 𝔏 belongs to 𝔏.

(b) For a word w in 𝔏, there are nonempty words u, v in 𝔏 such that uwv

belongs to 𝔏. Let 𝔏(M, I) be the set of all words appearing in X_{(M,I)}. That is

𝔏(M, I) = ∪_{k≤l}L_{k,l}.

Then we have Proposition 3.3. 𝔏(M, I) is a language.

Proof. 𝔏(M, I) clearly satisfies the condition (a) above. For a word w ∈ L_{k,l}, we know w ∈ L_{k+1,l+1} by Lemma 3.2. We write w = (λ(e_{k+1}), λ(e_{k+2}), …, λ(e_{l})) for e_{i} ∈ E_{i,i+1} with r(e_{i}) = s(e_{i+1}), i = k + 1, …, l − 1. Since both the sets r^{−1}(s(e_{k+1})) and s^{−1}(s(e_{l})) are not empty, we may find words u, v ∈ 𝔏(M, I) such that uwv ∈ 𝔏(M, I). Thus 𝔏(M, I) satisfies the condition (b).

By [LM;Proposition 1.3.4], we see

Theorem 3.4. There exists a subshift Λ over alphabet Σ whose language is 𝔏(M, I). Namely the set of all admissible words of the subshift Λ is 𝔏(M, I).

We denote by Λ_{(M,I)} the subshift Λ in the theorem above and call it the subshift associated with symbolic matrix system (M, I).

It is also possible to construct the subshift Λ_{(M,I)} by using projective limit method as in the folloing way.

Lemma 3.5. For (α_{1}, α_{2}, …) ∈ X_{(M,I)}, there exists a symbol α_{0} ∈ Σ such that (α_{0}, α_{1}, α_{2}, …) ∈ X_{(M,I)}.

Proof. Put w_{k} = (α_{1}, α_{2}, …, α_{k−1}) ∈ L_{1,k}. By Lemma 3.2 and Proposition 3.3, there exists a symbol β_{k} ∈ Σ such that β_{k}w_{k} ∈ L_{1,k+1}. Hence we may find y_{k} ∈ X_{(M,I)} such that β_{k}w_{k}y_{k} ∈ X_{(M,I)}. As the alphabet Σ is a finite set, there exists a symbol α_{0} ∈ Σ and a subsequence of (β_{k})_{k∈ℕ} such that β_{k_{n}} = α_{0} for n = 1, 2, … and k_{1} < k_{2} < · · · . Put x_{k_{n}} = α_{0}w_{k_{n}}y_{k_{n}}, n ∈ ℕ. They converge to an element

x = (α_{0}, α_{1}, α_{2}, …) ∈ X_{(M,I)}.

By Lemma 3.1, the following map

S : (α_{1}, α_{2}, α_{3}, …) ∈ X_{(M,I)} → (α_{2}, α_{3}, …) ∈ X_{(M,I)}

is well-defined, continuous and surjective. We set

Λ = \underleftarrow{lim}\{S : X_{(M,I)} → X_{(M,I)}\}

the projective limit in the category of compact Hausdorff spaces. Thus Λ is identified with the set of all biinfinite sequences arising from the sequences in X_{(M,I)}. That is

Λ = {(…, α_{2}, α_{1}, α_{0}, α_{1}, α_{2}, …)|(α_{n}, α_{n+1}, …) ∈ X_{(M,I)} for all n ∈ ℤ}.

The map S induces a homeomorphism on it. We denote it by σ that satisfies σ((α_{i})_{i∈ℤ}) = (α_{i+1})_{i∈ℤ}. Therefore we have a subshift (Λ, σ) from symbolic matrix system (M, I). It is nothing but the subshift (Λ_{(M,I)}, σ) defined in the preceding discussion.

We will next construct symbolic matrix systems from subshifts. For a subshift (Λ, σ) over Σ and a number k ∈ ℕ, let Λ^{k} be the set of all words of length k in Σ^{ℤ} occurring in some x ∈ Λ. Put Λ^{∗} = ∪_{k=0}^{∞}Λ^{k} where Λ^{0} denotes the empty word ∅. Set

Λ^{l}(x) = {μ ∈ Λ^{l}|μx ∈ X_{Λ}} for x ∈ X_{Λ}, l ∈ ℕ.

We define a nested sequence of equivalence relations in the space X_{Λ}. Two points x, y ∈ X_{Λ} are said to be l-past equivalent if Λ^{l}(x) = Λ^{l}(y). We write this equivalence as x ∼_{l} y. We denote by Ω_{l} = X_{Λ}/ ∼_{l} the quotient space by l-past equivalence classes of X_{Λ} ([Ma3]).

Lemma 3.6. For x, y ∈ X_{Λ} and μ ∈ Λ^{k},

(i) if x ∼_{l} y, we have x ∼_{m} y for m < l.

(ii) if x ∼_{l} y and μx ∈ X_{Λ}, we have μy ∈ X_{Λ} and μx ∼_{l−k} μy for l > k.

Hence we have the following sequence of surjections in a natural way:

Ω_{1} ← Ω_{2} ← ⋯ ← Ω_{l} ← Ω_{l+1} ← · · · .

We easily see that (Λ, σ) is a sofic subshift if and only if Ω_{l} = Ω_{l+1} for some l ∈ ℕ. For a fixed l ∈ ℕ, let F_{i}^{l}, i = 1, 2, …, m(l) be the set of all l-past equivalence classes of X_{Λ}. Hence X_{Λ} is a disjoint union of the subsets F_{i}^{l}, i = 1, 2, …, m(l). We define two rectangular m(l) × m(l + 1) matrices I_{l,l+1}^{Λ}, M_{l,l+1}^{Λ} with entries in {0, 1} and entries in 𝔖_{Σ} respectively as in the following way. For i = 1, 2, …, m(l), j = 1, 2, …, m(l + 1), the (i, j)-component I_{l,l+1}^{Λ}(i, j) of I_{l,l+1}^{Λ} is one if F_{i}^{l} contains F_{j}^{l+1} otherwise zero. Let a_{1}, …, a_{n} be the set of all symbols in Σ for which a_{k}x ∈ F_{i}^{l} for some x ∈ F_{j}^{l+1}. We then define the (i, j)- component of the matrix M_{l,l+1}^{Λ}(i, j) as M_{l,l+1}^{Λ}(i, j) = a_{1} +⋯+a_{n}: the formal sum of a_{1}, …, a_{n}. We call I_{l,l+1}^{Λ} the inclusion matrices for Λ and M_{l,l+1}^{Λ} the symbolic representation matrices for Λ respectively. We next construct a labeled graph from subshift Λ for each l ∈ ℕ. The vertices of the graph consist of the sets F_{i}^{l}, i = 1, …, m(l) and F_{j}^{l+1}, j = 1, …, m(l +1) which we denote by V_{l} and V_{l+1} respectively. We write an arrow with label a, denoted by λ^{Λ}(a), from the vertex F_{i}^{l} to F_{j}^{l+1} if ax ∈ F_{i}^{l} for some x ∈ F_{j}^{l+1}. We denote by E_{l,l+1} the set of all arrows from V_{l} to V_{l+1}. Since for each j = 1, …, m(l+1) there uniquely exists i = 1, …, m(l) such that I_{l,l+1}(i, j) = 1, we have a natural map ι_{l}^{Λ} from V_{l+1} to V_{l}. Set V^{Λ} = ∪_{l=1}^{∞}V_{l} and E^{Λ} = ∪_{l=1}^{∞}E_{l,l+1}. We then see Theorem 3.7. For a subshift (Λ, σ), the pair (M^{Λ}, I^{Λ}) is a symbolic matrix system for which its λ-graph is (V^{Λ}, E^{Λ}, λ^{Λ}, ι^{Λ}). Moreover the subshift Λ_{(M^{Λ},I^{Λ})} associated with (M^{Λ}, I^{Λ}) coincides with the original subshift Λ.

Proof. For each l ∈ ℕ, it is straightforward to check that the relation

I_{l,l+1}^{Λ}M_{l+1,l+2}^{Λ} = M_{l,l+1}^{Λ}I_{l+1,l+2}^{Λ}

holds. It then follows that the pair (M^{Λ}, I^{Λ}) is a symbolic matrix system whose associated λ-graph system is (V^{Λ}, E^{Λ}, λ^{Λ}, ι^{Λ}). It is also easy to see that the subshift associated with (M^{Λ}, I^{Λ}) coincides with the original subshift Λ because their forbidden words coincide.

Therefore we have a symbolic matrix system (M^{Λ}, I^{Λ}) and a λ-graph system (V^{Λ}, E^{Λ}, λ^{Λ}, ι^{Λ}) from subshift (Λ, σ). We call them the canonical symbolic matrix system for Λ and the canonical λ-graph system for Λ respectively. It is now clear that sofic symbolic matrix systems exactly correspond to sofic subshifts. For a symbolic matrix system (M, I), let Λ_{(M,I)} be the associated subshift constructed from (M, I). Then its canonical symbolic matrix system (M^{Λ}, I^{Λ}) does not necessarily coincide with the original symbolic matrix system (M, I). We indeed see the following proposition. Its proof is direct.

Proposition 3.8. For a subshift Λ, we have

(i) the representation matrices M_{l,l+1}^{Λ} are left resolving, i.e. the incoming edges to each vertex carry different labels.

(ii) the labeled Bratteli diagram (V^{Λ}, E^{Λ}, λ^{Λ}) is predecessor-separated, i.e. distinct vertices at each level have distinct predecessor sets of labels.

For example set, for each l ∈ ℕ, M_{l,l+1} = [ \begin{matrix}a & b \\ b & 0 \end{matrix} ] and I_{l,l+1} = [ \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ] . The

symbolic matrix system gives rise to the even shift that is denoted by Y. Its canonical symbolic matrix system is given by the following matrices:

M_{1,2}^{Y} = [ \begin{matrix}a & a + b & b \\ b & 0 & 0 \end{matrix} ] , I_{1,2}^{Y} = [ \begin{matrix}1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ]

and

M_{l,l+1}^{Y} = [ \begin{matrix}a & a & b \\ 0 & b & 0 \\ b & 0 & 0 \end{matrix} ] ,  I_{l,l+1}^{Y} = [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ]  for l ≥ 2.

We indeed have

Proposition 3.9. If Λ is a sofic subshift, its canonical λ-graph system is eventually realized as the left Krieger cover graph for Λ. Hence the canonical symbolic matrix system for Λ is eventually realized as the symbolic representation matrix for the left Krieger cover graph.

4. Strong shift equivalence.

In this section, we will define two kinds of strong shift equivalences between two symbolic matrix systems. One is called the properly strong shift equivalence that exactly reflects a bipartite decomposition of the associated λ-graph systems. The other one is called the strong shift equivalence that is weaker than the former strong shift equivalence. They coincide at least between canonical symbolic matrix systems and between sofic symbolic matrix systems. The latter is easier defined and treated than the former. We will see, in the next section, that the latter strong shift equivalence directly leads to the shift equivalence between symbolic matrix systems. The main result in this section is that topological conjugacy between two subshifts are completely characterized by strong shift equivalence between their canonical symbolic matrix systems. We first define properly strong shift equivalence in 1-step between two symbolic matrix systems as a generalization of strong shift equivalence in 1-step between two nonnegative matrices defined by R. Williams in [Wi] and between two symbolic matrices defined by M. Nasu in [N](see also [BK]). For alphabets C, D, put C · D = {cd|c ∈ C, d ∈ D}. For x = ∑_{j} c_{j} ∈ 𝔖_{C} and y = ∑_{k} d_{k} ∈ 𝔖_{D}, define xy = ∑_{j,k} c_{j}d_{k} ∈ 𝔖_{C·D}. Let (M, I) and (M′, I′) be symbolic matrix systems over alphabets Σ, Σ′ respectively, where M_{l,l+1}, I_{l,l+1} are m(l) × m(l + 1) matrices and M′_{l,l+1}, I′_{l,l+1} are m′(l) × m′(l + 1) matrices. Definition. Two symbolic matrix systems (M, I) and (M′, I′) are said to be properly strong shift equivalent in 1-step if there exist alphabets C, D and specifications

φ : Σ → C · D, ϕ : Σ′ → D · C

and increasing sequences n(l), n′(l) on l ∈ ℕ such that for each l ∈ ℕ, there exist an n(l) × n′(l + 1) matrix P_{l} over C, an n′(l) × n(l + 1) matrix Q_{l} over D, an n(l) × n(l + 1) matrix X_{l} over {0, 1} and an n′(l) × n′(l + 1) matrix X′_{l} over {0, 1} satisfying the following equations:

(4.1)  M_{l,l+1} ≃^{φ} P_{2l}Q_{2l+1},  M′_{l,l+1} ≃^{ϕ} Q_{2l}P_{2l+1},

(4.2)  I_{l,l+1} = X_{2l}X_{2l+1},  I′_{l,l+1} = X′_{2l}X′_{2l+1}

and

(4.3)  X_{l}P_{l+1} = P_{l}X′_{l+1},  X′_{l}Q_{l+1} = Q_{l}X_{l+1}.

We write this situation as

(M, I) ≈_{1−pr} (M′, I′).

It follows by (4.1) that n(2l) = m(l) and n′(2l) = m(l) for l ∈ ℕ.

Two symbolic matrix systems (M, I) and (M′, I′) are said to be properly strong shift equivalent in N-step if there exists a sequence of symbolic matrix systems (M^{(i)}, I^{(i)}), i = 1, 2, …, N − 1 such that

\begin{aligned}(M, I) ≈_{1−pr} (M^{(1)}, I^{(1)}) & ≈_{1−pr} (M^{(2)}, I^{(2)}) \\ & ≈_{1−pr} ⋯ ≈_{1−pr} (M^{(N−1)}, I^{(N−1)}) ≈_{1−pr} (M′, I′) \end{aligned}

We denote this situation by

(M, I) ≈_{N−pr} (M′, I′)

and simply call it a properly strong shift equivalence.

Proposition 4.1. Properly strong shift equivalence is an equivalence relation on symbolic matrix systems.

Proof. It is clear that properly strong shift equivalence is symmetric and transitive. It suffices to show that (M, I) ≈_{1−pr} (M, I). Put C = Σ, D = {0, 1}.

Define φ : a ∈ Σ → a · 1 ∈ C · D and ϕ : a ∈ Σ → 1 · a ∈ D · C. Let E_{k} be the k × k identity matrix. Set

P_{2l} = P_{2l+1} = M_{l,l+1}, Q_{2l} = E_{m(l)}, Q_{2l+1} = E_{m(l+1)},
X_{2l} = E_{m(l)}, X_{2l+1} =I_{l,l+1}, X′_{2l} = I_{l,l+1}, X′_{2l+1} = E_{m(l+1)}.

It is straightforward to see that they give a properly strong shift equivalence in 1-step between (M, I) and (M, I).

We will prove the following theorem.

Theorem 4.2. Two subshifts Λ and Λ′ are topologically conjugate if and only if their canonical symbolic matrix systems (M^{Λ}, I^{Λ}) and (M^{Λ′}, I^{Λ′}) are properly strong shift equivalent.

We will first show the only if part of the theorem above. In our proof, we will use Nasu’s factorization theorem for topological conjugacy between subshifts into bipartite codes ([N]). We now introduce the notion of bipartite symbolic matrix system. Definition. A symbolic matrix system (M, I) over alphabet Σ is said to be bipartite if there exist disjoint subsets C, D ⊂ Σ and increasing sequences n(l), n′(l) on l ∈ ℕ with m(l) = n(l)+n′(l) such that for each l ∈ ℕ, there exist an n(l) × n′(l + 1) matrix P_{l,l+1} over C, an n′(l) × n(l + 1) matrix Q_{l,l+1} over D, an n(l) × n(l + 1) matrix X_{l,l+1} over {0, 1} and an n′(l) × n′(l + 1) matrix X′_{l,l+1} over {0, 1} satisfying the following equations:

M_{l,l+1} = [ \begin{matrix}0 & P_{l,l+1} \\ Q_{l,l+1} & 0 \end{matrix} ] , I_{l,l+1} = [ \begin{matrix}X_{l,l+1} & 0 \\ 0 & X′_{l,l+1} \end{matrix} ] .

We thus see Lemma 4.3. For a bipartite symbolic matrix system (M, I) as above, set

P_{l} = P_{l,l+1}, Q_{l} = Q_{l,l+1}, X_{l} = X_{l,l+1}, X′_{l} = X′_{l,l+1}

and

M_{l,l+1}^{CD} = P_{2l}Q_{2l+1}, M_{l,l+1}^{DC} = Q_{2l}P_{2l+1},
I_{l,l+1}^{CD} = X_{2l}X_{2l+1}, I_{l,l+1}^{DC} = X′_{2l}X′_{2l+1}.

Then the both pairs (M^{CD}, I^{CD}) and (M^{DC}, I^{DC}) are symbolic matrix systems over alphabets C · D and D · C respectively and they are properly strong shift equivalent in 1-step.

Proof. The relations I_{l,l+1}M_{l+1,l+2} = M_{l,l+1}I_{l+1,l+2} and

\begin{matrix}I_{2l,2l+1}I_{2l+1,2l+2}M_{2l+2,2l+3}M_{2l+3,2l+4} \\ = & M_{2l,2l+1}M_{2l+1,2l+2}I_{2l+2,2l+3}I_{2l+3,2l+4} \end{matrix}

shows that the both pairs (M^{CD}, I^{CD}) and (M^{DC}, I^{DC}) are symbolic matrix systems and they are properly strong shift equivalent in 1-step because we see

X_{l−1,l}P_{l,l+1} = P_{l−1,l}X′_{l,l+1}, X′_{l−1,l}Q_{l,l+1} = Q_{l−1,l}X_{l,l+1}.

Definition. A λ-graph system (V, E, λ, ι) over alphabet Σ is said to be bipartite if there exist disjoint subsets C, D ⊂ Σ such that Σ = C ∪ D and disjoint subsets V_{l}^{C}, V_{l}^{D} ⊂ V_{l} for each l ∈ ℕ such that V_{l}^{C} ∪ V_{l}^{D} = V_{l} and

(1) for each e ∈ E_{l,l+1}

s(e) ∈V_{l}^{D}, r(e) ∈ V_{l+1}^{C} if and only if λ(e) ∈ C,
s(e) ∈V_{l}^{C}, r(e) ∈ V_{l+1}^{D} if and only if λ(e) ∈ D.

(2)

ι(V_{l+1}^{D}) = V_{l}^{D}, ι(V_{l+1}^{C}) = V_{l}^{C}.

Proposition 4.4. A symbolic matrix system is bipartite if and only if its corresponding λ-graph system is bipartite.

Proof. It is clear that a bipartite symbolic matrix system gives rise to a bipartite λ-graph system. Conversely, suppose that a λ-graph system (V, E, λ, ι) is bipartite. Let n(l) and n′(l) be the cardinalities of the sets V_{l}^{D} and V_{l}^{C} respectively. We may identify V_{l}^{D} and V_{l}^{C} with the sets {1, …, n(l)} and {1, …, n′(l)} respectively. For i ∈ V_{l}^{D}, j ∈ V_{l+1}^{C}, put P_{l,l+1}(i, j) = λ(e_{1}) + ⋯ + λ(e_{p}) where e_{k} ∈ E_{l,l+1}, k = 1, …, p are the set of all edges in E_{l,l+1} satisfying s(e_{k}) = i, r(e_{k}) = j. Similarly we define for i ∈ V_{l}^{C}, j ∈ V_{l+1}^{D}, put Q_{l,l+1}(i, j) = λ(f_{1}) + ⋯ + λ(f_{q}) where f_{k} ∈ E_{l,l+1}, k = 1, …, q are the set of all edges in E_{l,l+1} satisfying s(f_{k}) = i, r(f_{k}) = j. For i ∈ V_{l}^{D}, j ∈ V_{l+1}^{D}, put X_{l,l+1}(i, j) = 1 if ι(j) = i and X_{l,l+1}(i, j) = 0 otherwise. Similarly for i ∈ V_{l}^{C}, j ∈ V_{l+1}^{C}, put X′_{l,l+1}(i, j) = 1 if ι(j) = i and X′_{l,l+1}(i, j) = 0 otherwise. Then by these matrices, we know that the corresponding symbolic matrix system (M, I) for (V, E, λ, ι) is bipartite.

M. Nasu introduced the notion of bipartite subshift in [N] and [N2]. A subshift Λ over alphabet Σ is said to be bipartite if there exist disjoint subsets C, D ⊂ Σ such that any (x_{i})_{i∈ℤ} ∈ Λ is either

x_{i} ∈ C and x_{i+1} ∈ D for all i ∈ ℤ or x_{i} ∈ D and x_{i+1} ∈ C for all i ∈ ℤ.

Let Λ^{(2)} be the 2-higher power shift for Λ. Put

Λ_{CD} = {(c_{i}d_{i})_{i∈ℤ} ∈ Λ^{(2)}|c_{i} ∈ C, d_{i} ∈ D},
Λ_{DC} = {(d_{i}c_{i})_{i∈ℤ} ∈ Λ^{(2)}|c_{i} ∈ C, d_{i} ∈ D}.

They are subshifts over alphabets C · D and D · C respectively. Hence Λ^{(2)} is partitioned into the two subshifts Λ_{CD} and Λ_{DC}.

Proposition 4.5. A subshift Λ is bipartite if and only if its canonical symbolic matrix system (M^{Λ}, I^{Λ}) is bipartite.

Proof. It is clear that a bipartite canonical symbolic matrix system gives rise to a bipartite subshift from the preceding proposition. Suppose that Λ is bipartite with respect to alphabets C, D. It suffices to show that its canonical λ-graph system (V, E, λ, ι) is bipartite. As in the construction of the canonical λ-graph system, the vertex set V_{l} is the set of all l-past equivalence classes {F_{i}^{l}}_{i=1,...,m(l)}. Put

V_{l}^{C} ={F_{i}^{l}|x_{1} ∈ D for all (x_{1}, x_{2}, …,) ∈ F_{i}^{l}},
V_{l}^{D} ={F_{i}^{l}|x_{1} ∈ C for all (x_{1}, x_{2}, …,) ∈ F_{i}^{l}}

so that we have a disjoint union V_{l}^{C} ∪ V_{l}^{D} = V_{l}. It is easy to see that this decomposition of V_{l}, l ∈ ℕ yields a bipartite decomposition of the λ-graph system (V, E, λ, ι).

Let Λ be a bipartite subshift over Σ with respect to alphabets C, D. As in Lemma 4.3, we have two symbolic matrix systems (M^{CD}, I^{CD}) and (M^{DC}, I^{DC}) over alphabets C · D and D · C from the bipartite canonical symbolic matrix system (M^{Λ}, I^{Λ}) for Λ respectively. They are naturally identified with the canonical symbolic matrix systems for the subshifts Λ_{CD} and Λ_{DC} respectively. We thus see by Lemma 4.3.

Corollary 4.6. For a bipartite subshift Λ with respect to alphabets C, D, we have

(M^{CD}, I^{CD}) ≈_{1−pr} (M^{DC}, I^{DC})

a properly strong shift equivalence in 1-step.

The following notion of bipartite conjugacy has been introduced by Nasu in [N], [N2]. The conjugacy from Λ_{CD} onto Λ_{DC} that maps (c_{i}d_{i})_{i∈ℤ} to (d_{i}c_{i+1})_{i∈ℤ} is called the forward bipartite conjugacy. The conjugacy from Λ_{CD} onto Λ_{DC} that maps (c_{i}d_{i})_{i∈ℤ} to (d_{i−1}c_{i})_{i∈ℤ} is called the backward bipartite conjugacy. A topological conjugacy between subshifts is called a symbolic conjugacy if it is a 1-block map given by a bijection between the underlying alphabets of the subshifts. M. Nasu proved the following factorization theorem.

Lemma 4.7(M.Nasu [N]). Any topological conjugacy ψ between subshifts is factorized into a composition of the form

ψ = κ_{n}ζ_{n}κ_{n−1}ζ_{n−1} ⋯ κ_{1}ζ_{1}κ_{0}

where κ_{0}, …, κ_{n} are symbolic conjugacies and ζ_{1}, …, ζ_{n} are either forward or backward bipartite conjugacies.

Thanks to the Nasu’s result above, we reach the following theorem

Theorem 4.8. For two subshifts Λ, Λ′, let (M, I), (M′, I′) be their canonical symbolic matrix systems for Λ, Λ′ respectively. If Λ and Λ′ are topologically conjugate, the symbolic matrix systems (M, I), (M′, I′) are properly strong shift equivalent.

We will prove the converse implication of the theorem above. We will indeed prove the following proposition.

Proposition 4.9. If two symbolic matrix systems are properly strong shift equivalent in 1-step, their associated subshifts are topologically conjugate.

To prove the proposition, we provide a notation and a lemma.

Set the m(l) × m(l + k) matrices:

I_{l,l+k} = I_{l,l+1} · I_{l+1,l+2} ⋯ I_{l+k−1,l+k},
M_{l,l+k} = M_{l,l+1} · M_{l+1,l+2} ⋯ M_{l+k−1,l+k}

for each l, k ∈ ℕ.

Lemma 4.10. Assume that two symbolic matrix systems (M, I) over Σ and (M′, I′) over Σ′ are properly strong shift equivalent in 1-step. Let φ : Σ → C·D and ϕ : Σ′ → D · C be specifications that give a properly strong shift equivalence in 1-step between them. For any word x_{1}x_{2} ∈ (Λ_{(M,I)})^{2} of length two in the associated subshift Λ_{(M,I)}, put φ(x_{i}) = c_{i}d_{i}, i = 1, 2 where c_{i} ∈ C, d_{i} ∈ D. Then there uniquely exists a symbol y_{0} ∈ Σ′ such that ϕ(y_{0}) = d_{1}c_{2}.

Proof. Note that by definition the specification ϕ is not necessarily defined on all the elements of Σ′. It suffices to show the existence of y_{0}. Since x_{1}x_{2} ∈ (Λ_{(M,I)})^{∗}, for any fixed l ≥ 3, we find j = 1, 2, …, m(l + 2) and k = 1, 2, …, m(l) such that x_{1}x_{2} appears in M_{l,l+2}(k, j). Take i = 1, 2, …, m(l−2) with I_{l−2,l}(i, k) = 1. Hence x_{1}x_{2} appears in I_{l−2,l}M_{l,l+2}(i, j). As we know the equality:

I_{l−2,l}M_{l,l+2} ≃^{φ} I_{l−2,l−1}X_{2l−1}P_{2l−1}Q_{2l}P_{2l+1}Q_{2l+2}X_{2l+3},

the word φ(x_{1}x_{2}) = c_{1}d_{1}c_{2}d_{2} appears in a component of the right hand symbolic matrix above. Thus the word d_{1}c_{2} appears in a component of Q_{2l}P_{2l+1}.

By the equality M′_{l,l+1} ≃^{ϕ} Q_{2l}P_{2l+1}, we can find a symbol y_{0} in the corresponding component of the matrix M′_{l,l+1} so that ϕ(y_{0}) = d_{1}c_{2}.

Proof of Proposition 4.9. Suppose that (M, I) and (M′, I′) are properly strong shift equivalent in 1-step. We use the same notation as in Definition of properly strong shift equivalence. Set Λ = Λ_{(M,I)} and Λ′ = Λ_{(M′,I′)}. By the preceding lemma, we have a 2-block map Φ from Λ^{2} to Σ′ defined by Φ(x_{1}x_{2}) = y_{0} where ϕ(y_{0}) = d_{1}c_{2} and φ(x_{i}) = c_{i}d_{i}, i = 1, 2. Let Φ_{∞} be the sliding block code induced by Φ so that Φ_{∞} is a map from Λ to Σ′^{ℤ}. We also write as Φ the map from Λ^{∗} to the set of all words of Σ′ defined by

Φ(x_{1}x_{2} ⋯ x_{n}) = Φ(x_{1}x_{2})Φ(x_{2}x_{3}) ⋯ Φ(x_{n−1}x_{n}).

We will prove that Φ_{∞}(Λ) ⊂ Λ′. To prove this, it suffices to show that for any word w in Λ, Φ(w) is an admissible word in Λ′. For w = w_{1}w_{2} ⋯ w_{n} ∈ Λ^{n} and any fixed l ≥ n + 1, we find j = 1, 2, …, m(l + n) and k = 1, 2, …, m(l) such that w appears in M_{l,l+n}(k, j). Take i = 1, 2, …, m(l−n) with I_{l−n,l}(i, k) = 1. Hence w appears in I_{l−n,l}M_{l,l+n}(i, j). Put φ(w_{i}) = c_{i}d_{i}, i = 1, 2, …, n. By the equality

I_{l−1,l}M_{l,l+n} ≃^{φ} X_{2l−2}P_{2l−1}Q_{2l}P_{2l+1}Q_{2l+2} ⋯ P_{2l+2n−3}Q_{2l+2n−2}X_{2l+2n−1},

the word d_{1}c_{2}d_{2}c_{3} ⋯ d_{n−1}c_{n} appears in a component of Q_{2l}P_{2l+1}Q_{2l+2} ⋯ P_{2l+2n−3}. Hence the word ϕ^{−1}(d_{1}c_{2})ϕ^{−1}(d_{2}c_{3}) ⋯ ϕ^{−1}(d_{n−1}c_{n}) appears in a component of M′_{l,l+1} · M′_{l+1,l+2} ⋯ M′_{l+n−2,l+n−1}. Thus we see that Φ(w) is an admissible word in Λ′ and that the sliding block code Φ_{∞} maps Λ to Λ′. Similarly, we can construct a sliding block code Ψ_{∞} from Λ′ to Λ that is an inverse of Φ_{∞}. Thus two subshifts Λ′ and Λ are topologically conjugate.

Therefore we conclude the following theorem

Theorem 4.11. If two symbolic matrix systems are properly strong shift equivalent, their associated subshifts are topologically conjugate.

By Theorem 4.8 and Theorem 4.11, we conclude Theorem 4.2. Remark. If there exist the matrices P_{l}, Q_{l} for all sufficiently large number l in Definition of properly strong shift equivalence in 1-step, we may show that the associated subshifts are topologically conjugate because of the proof of Proposition 4.9.

Properly strong shift equivalence exactly corresponds to a finite sequence of bipartite decompositions of symbolic matrix systems and λ-graph systems. The definition of properly strong shift equivalence for symbolic matrix systems however needs rather complicated formulations than that of strong shift equivalence for nonnegative matrices. We will next introduce the notion of strong shift equivalence between two symbolic matrix systems that is simpler and weaker condition than properly strong shift equivalence. It is also a generalization of the notion of strong shift equivalence between nonnegative matrices defined by Williams in [Wi] and between symbolic matrices defined by Nasu in [N]. Let (M, I), (M′, I) be two symbolic matrix systems over alphabet Σ, Σ′ respectively. Let m(l), m′(l) be the sequences for which M_{l,l+1}, I_{l,l+1} are m(l) × m(l + 1) matrices and M′_{l,l+1}, I′_{l,l+1} are m′(l) × m′(l + 1) matrices respectively. Definition. Two symbolic matrix systems (M, I), (M′, I) are said to be strong shift equivalent in 1-step if there exist alphabets C, D and specifications

φ : Σ → C · D, ϕ : Σ′ → D · C

such that for each l ∈ ℕ, there exist an m(l − 1) × m′(l) matrix H_{l} over C and an m′(l − 1) × m(l) matrix K_{l} over D satisfying the following equations:

I_{l−1,l}M_{l,l+1} ≃^{φ} H_{l}K_{l+1}, I′_{l−1,l}M′_{l,l+1} ≃^{ϕ} K_{l}H_{l+1}

and

H_{l}I′_{l,l+1} = I_{l−1,l}H_{l+1}, K_{l}I_{l,l+1} = I′_{l−1,l}K_{l+1}.

We write this situation as

(M, I) ≈_{1−st} (M′, I′).

Two symbolic matrix systems (M, I) and (M′, I′) are said to be strong shift equivalent in N-step if there exist symbolic matrix systems (M^{(i)}, I^{(i)}), i = 1, 2, …, N − 1 such that

\begin{aligned}(M, I) ≈_{1−st} (M^{(1)}, I^{(1)}) & ≈_{1−st} (M^{(2)}, I^{(2)}) \\ & ≈_{1−st} ⋯ ≈_{1−st} (M^{(N−1)}, I^{(N−1)}) ≈_{1−st} (M′, I′). \end{aligned}

We denote this situation by

(M, I) ≈_{N−st} (M′, I′)

and simply call it a strong shift equivalence.

Similarly to the case of properly strong shift equivalence, we see that strong shift equivalence on symbolic matrix systems is an equivalence relation.

Proposition 4.12. Properly strong shift equivalence in 1-step implies strong shift equivalence in 1-step.

Proof. Let P_{l}, Q_{l}, X_{l} and X′_{l} be the matrices in Definition of properly strong shift equivalence in 1-step between (M, I) and (M′, I′). We set

H_{l} = X_{2l−1}P_{2l−1}, K_{l} = X′_{2l−1}Q_{2l−1}.

They give rise to a strong shift equivalence in 1-step between (M, I) and (M′, I′).

Conversely we have

Proposition 4.13. Suppose that both (M, I) and (M′, I′) are canonical. If they are strong shift equivalent in 1-step, they are properly strong shift equivalent in 1-step. Hence strong shift equivalence on canonical symbolic matrix systems is completely the same as properly strong shift equivalence.

Proof. Let Λ, Λ′ be the associated subshifts for (M, I), (M′, I′) respectively. Suppose that (M, I) ≈_{1−st} (M′, I′). We use the same notation as in Definition

of strong shift equivalence. Set

Λ_{φ} = {(…, c_{−1}, d_{−1}, ċ_{0}, d_{0}, c_{1}, d_{1}, …)|
there exists (x_{i})_{i∈ℤ} ∈ Λ; φ(x_{i}) = c_{i}d_{i} for all i ∈ ℤ},
Λ′_{ϕ} = {(…, d_{−1}, c_{0}, ḋ_{0}, c_{1}, d_{1}, c_{2}, …)|
there exists (y_{i})_{i∈ℤ} ∈ Λ′; ϕ(y_{i}) = d_{i}c_{i} for all i ∈ ℤ}

where ċ_{0}, ḋ_{0} locate at the position of the 0-th coordinate in the sequences. Put

Λ_{o} = Λ_{φ} ∪ Λ′_{ϕ}

that becomes a subshift over C ∪D because of strong shift equivalence between (M, I) and (M′, I′). It is clear that Λ_{o} is a bipartite subshift with respect to the alphabets C, D. Hence the 2-higher power shift Λ_{o}^{(2)} is decomposed as Λ_{o}^{(2)} = Λ_{φ}^{(2)} ∪ Λ_{ϕ}^{(2)}. As there exist symbolic conjugacies:

Λ ≃^{φ} Λ_{φ}^{(2)}, Λ′ ≃^{ϕ} Λ_{ϕ}^{(2)},

the canonical symbolic matrix systems for the subshifts Λ and Λ′ are properly strong shift equivalence in 1-step by the previous discussions.

By a similar argument to the proof of Proposition 4.9, we obtain

Proposition 4.14. If two symbolic matrix systems ( not necessarily canonical ) are strong shift equivalent in 1-step, their associated subshifts are topologically conjugate.

Thus we conclude

Theorem 4.15. If two symbolic matrix systems (not necessarily canonical) are strong shift equivalent, their associated subshifts are topologically conjugate.

5. Higher λ-graph systems

In studies of symbolic dynamics, the operation of taking higher block presentation plays important rôles (cf.[Kit], [LM]). In topological Markov shifts, the operation of taking 2-higher block presentation is a typical example of giving strong shift equivalence in 1-step. The N-higher block presentation of an edge shift corresponds to the edge shift of the N-higher edge graph. We in this section introduce higher λ-graph systems and correspondingly higher symbolic matrix systems. It follows that the subshift associated with the N-higher λgraph system is the N-higher block presentation of the subshift associated with the original λ-graph system. We see that a symbolic matrix system is properly strong shift equivalent in N-step to its N-higher symbolic matrix system. We treat a left resolving λ-graph system, that is, the incoming edges to each vertex carry different labels. General case and also general state splitting procedure of λ-graph systems will be treated in a forthcoming paper. For a left resolving λ-graph system (V, E, λ, ι) over alphabet Σ and a natural number N ∈ ℕ, we will define a λ-graph system (V^{[N]}, E^{[N]}, λ^{[N]}, ι^{[N]}) over Σ^{[N]} = \underbrace{Σ ⋯ Σ}_{N-times} as follows:

V_{l}^{[N]} = {(e_{1}, e_{2}, …, e_{N−1}) ∈ E_{l,l+1} × E_{l+1,l+2} × ⋯ × E_{l+N−2,l+N−1}|
r(e_{i}) = s(e_{i+1}) for i = 1, 2, …, N − 2},
E_{l,l+1}^{[N]} = {((e_{1}, …, e_{N−1}),(f_{1}, …, f_{N−1})) ∈ V_{l}^{[N]} × V_{l+1}^{[N]}|
e_{i+1} = f_{i} for i = 1, 2, …, N − 2}.

The maps

s^{[N]} : E_{l,l+1}^{[N]} → V_{l}^{[N]}, r^{[N]} : E_{l,l+1}^{[N]} → V_{l+1}^{[N]}

are defined by

s^{[N]}((e_{1}, …, e_{N−1}), (f_{1}, …, f_{N−1})) = (e_{1}, …, e_{N−1}),
r^{[N]}((e_{1}, …, e_{N−1}), (f_{1}, …, f_{N−1})) = (f_{1}, …, f_{N−1}).

Set V^{[N]} = ∪_{l∈ℕ}V_{l}^{[N]} and E^{[N]} = ∪_{l∈ℕ}E_{l,l+1}^{[N]}. Hence (V^{[N]}, E^{[N]}, s^{[N]}, r^{[N]}) is a Bratteli diagram. A labeling λ^{[N]} on (V^{[N]}, E^{[N]}) is defined by

λ^{[N]}((e_{1}, …, e_{N−1}), (f_{1}, …, f_{N−1})) = λ(e_{1})λ(e_{2}) … λ(e_{N−1})λ(f_{N−1}) ∈ Σ^{[N]}

for ((e_{1}, …, e_{N−1}), (f_{1}, …, f_{N−1})) ∈ E^{[N]}. A sequence of surjections ι^{[N]} : V_{l+1}^{[N]} → V_{l}^{[N]}, l ∈ ℕ is defined as follows. For (e_{1}, …, e_{N−1}) ∈ V_{l+1}^{[N]}, since the λ-graph system (V, E, λ, ι) is left resolving, there uniquely exist e′_{i} ∈ E_{l+i−1,l+i} for i = 1, 2, …, N − 2 such that

ι(s(e_{i})) = s(e′_{i}), ι(r(e_{i})) = r(e′_{i}), λ(e_{i}) = λ(e′_{i}).

As we know (e′_{1}, …, e′_{N−1}) ∈ V_{l}^{[N]}, by setting ι^{[N]}(e_{1}, …, e_{N−1}) = (e′_{1}, …, e′_{N−1}). We get a λ-graph system (V^{[N]}, E^{[N]}, λ^{[N]}, ι^{[N]}) over Σ^{[N]}. Definition. We call the λ-graph system (V^{[N]}, E^{[N]}, λ^{[N]}, ι^{[N]}) the N-higher λ-graph system for (V, E, λ, ι). For a symbolic matrix system (M, I), the Nhigher symbolic matrix system (M^{[N]}, I^{[N]}) is defined to be the symbolic matrix system associated with the N-higher λ-graph system for the λ-graph system of (M, I). It is routine to show the following proposition.

Proposition 5.1. Λ_{(M^{[N]},I^{[N]})} = (Λ_{(M,I)})^{[N]}.

As seen in the case of nonnegative matrices, we see

Proposition 5.2. (M, I) ≈_{1−pr} (M^{[2]}, I^{[2]}) : a properly strong shift equivalence

in 1-step.

Proof. Let (V, E, λ, ι) and (V^{[2]}, E^{[2]}, λ^{[2]}, ι^{[2]}) be the associated λ-graph systems for (M, I), (M^{[2]}, I^{[2]}) over alphabets Σ and Σ^{[2]} respectively. We will construct a bipartite λ-graph system (V̂ , Ê, λ̂, ι̂) that gives rise to a properly strong shift equivalence in 1-step between the λ-graph systems. We set for l ∈ ℕ

V̂_{2l−1} = E_{l,l+1} ∪ V_{l},  V̂_{2l} = V_{l+1} ∪ E_{l,l+1}

and

Ê_{2l−1,2l} ={(f, u) ∈ E_{l,l+1} × V_{l+1}|u = r(f)} ∪ {(v, e) ∈ V_{l} × E_{l,l+1}|v = s(e)},
Ê_{2l,2l+1}={(v, e) ∈ V_{l+1} × E_{l+1,l+2}|v = s(e)} ∪{(f, u)∈E_{l,l+1}×V_{l+1}|u = r(f)}.

The source maps ŝ_{2l−1,2l} : Ê_{2l−1,2l} → V̂_{2l−1} and ŝ_{2l,2l+1} : Ê_{2l,2l+1} → V̂_{2l} are defined as follows:

ŝ_{2l−1,2l}(f, u) = f ∈ E_{l,l+1},  ŝ_{2l−1,2l}(v, e) = v ∈ V_{l},
ŝ_{2l,2l+1}(v, e) = v ∈ V_{l+1},  ŝ_{2l,2l+1}(f, u) = f ∈ E_{l,l+1}.

The range maps r̂_{2l−1,2l} : Ê_{2l−1,2l} → V̂_{2l} and r̂_{2l,2l+1} : Ê_{2l,2l+1} → V̂_{2l+1} are defined as follows:

r̂_{2l−1,2l}(f, u) = u ∈ V_{l+1},  r̂_{2l−1,2l}(v, e) = e ∈ E_{l,l+1},
r̂_{2l,2l+1}(v, e) = e ∈ E_{l+1,l+2},  r̂_{2l,2l+1}(f, u) = u ∈ V_{l+1}.

The maps ι̂_{2l,2l−1} : V̂_{2l} → V̂_{2l−1} and ι̂_{2l+1,2l} : V̂_{2l+1} → V̂_{2l} are defined as follows:

ι̂_{2l,2l−1}(u) = ι(u) for u ∈ V_{l+1}, ι̂_{2l,2l−1}(f) = f for f ∈ E_{l,l+1},
ι̂_{2l+1,2l}(e) = ι(e) for e ∈ E_{l+1,l+2}, ι̂_{2l+1,2l}(v) = v for v ∈ V_{l+1}

where ι(e) ∈ E_{l,l+1} is naturally defined for e ∈ E_{l+1,l+2}. Put D_{Σ} = {D_{α}|α ∈ Σ}, C_{Σ} = {C_{α}|α ∈ Σ} and Σ̂ = D_{Σ} ∪ C_{Σ}. The labeling λ̂ is defined as a map from Ê to the alphabet Σ̂ as follows: For (f, u), (v, e) in Ê_{2l−1,2l} = {(f, u) ∈ E_{l,l+1} × V_{l+1}|u = r(f)} ∪ {(v, e) ∈ V_{l} × E_{l,l+1}|v = s(e)}, we set

λ̂(f, u) = C_{λ(f)}, λ̂(v, e) = D_{λ(e)}.

For (v, e), (f, u) in Ê_{2l,2l+1} = {(v, e) ∈ V_{l+1} × E_{l+1,l+2}|v = s(e)} ∪ {(f, u) ∈ E_{l,l+1} × V_{l+1}|u = r(f)}, we set

λ̂(v, e) = D_{λ(e)}, λ̂(f, u) = C_{λ(f)}.

Then it is routine to check that (V̂ , Ê, λ̂, ι̂) is a bipartite λ-graph system over alphabet Σ̂. Through the specifications φ : Σ → D_{Σ}·C_{Σ} and ϕ : Σ^{[2]} → C_{Σ}·D_{Σ} defined by

φ(α) = D_{α} · C_{α} and ϕ(α, β) = D_{α} · C_{β},

we know that the symbolic matrix system for (V̂ , Ê, λ̂, ι̂) gives rise to a properly strong shift equivalence in 1-step between (M, I) and (M^{[2]}, I^{[2]}).

Since (M^{[N+1]}, I^{[N+1]}) is isomorphic to ((M^{[N]})^{[2]}, (I^{[N]})^{[2]}), we have

Corollary 5.3. For any symbolic matrix system (M, I), we have

(M^{[N]}, I^{[N]}) ≈_{N−st} (M, I)

a properly strong shift equivalence in N-step.

6. Shift equivalence

By the discussions of Section 4, the topological conjugacy classes of subshifts are completely characterized by the strong shift equivalence classes of the associated canonical symbolic matrix systems. However, even for topological Markov shifts, there is no general algorithm known for deciding whether two nonnegative matrices are strong shift equivalent. R. F. Williams introduced the notion of shift equivalence between two nonnegative matrices that is weaker but easier to treat than the notion of strong shift equivalence ([Wi]). The formulation of shift equivalence between nonnegative matrices is described by certain algebraic relations between the matrices that determine a crucial invariant called the dimension group ([Kr], [Kr2]). The notion of shift equivalence has been generalized to symbolic matrices by Boyle-Krieger and studied as a topological conjugacy invariant for sofic subshifts in [BK]. We in this section introduce the notion of shift equivalence between two symbolic matrix systems as a generalization of Williams’s notion for nonnegative matrices and Boyle-Krieger’s notion for symbolic matrices. Let (M, I), (M′, I′) be two symbolic matrix systems over alphabets Σ, Σ′ respectively. For N ∈ ℕ, we put (Σ)^{N} = Σ ⋯ Σ, (Σ′)^{N} = Σ′ ⋯ Σ′ : the N-times products.

Definition. For N ∈ ℕ, two symbolic matrix systems (M, I), (M′, I′) are said to be shift equivalent of lag N if there exist alphabets C_{N}, D_{N} and specifications

φ_{1} : Σ · C_{N} → C_{N} · Σ′, φ_{2} : Σ′ · D_{N} → D_{N} · Σ

and

ψ_{1} : (Σ)^{N} → C_{N} · D_{N}, ψ_{2} : (Σ′)^{N} → D_{N} · C_{N}

such that for each l ∈ ℕ, there exist an m(l) × m′(l + N) matrix H_{l} over C_{N} and an m′(l) × m(l + N) matrix K_{l} over D_{N} satisfying the following equations:

M_{l,l+1}H_{l+1} ≃^{φ_{1}} H_{l}M′_{l+N,l+N+1}, M′_{l,l+1}K_{l+1} ≃^{φ_{2}} K_{l}M_{l+N,l+N+1},

I_{l,l+N}M_{l+N,l+2N} ≃^{ψ_{1}} H_{l}K_{l+N}, I′_{l,l+N}M′_{l+N,l+2N} ≃^{ψ_{2}} K_{l}H_{l+N}

and

I_{l,l+1}H_{l+1} = H_{l}I′_{l+N,l+N+1}, I′_{l,l+1}K_{l+1} = K_{l}I_{l+N,l+N+1}.

We denote this situation by

(M, I) ∼_{lagN} (M′, I′) or (H, K) : (M, I) ∼_{lagN} (M′, I′)

and simply call it a shift equivalence.

Similarly to the case of nonnegative matrices and symbolic matrices, we can see the following lemma.

Lemma 6.1.

(i) (M, I) ∼_{lagN} (M′, I′) implies (M, I) ∼_{lagL} (M′, I′) for all L ≥ N.

(ii) (M, I) ∼_{lagN} (M′, I′) and (M′, I′) ∼_{lagN′} (M′′, I′′) implies

(M, I) ∼_{lagN+N′} (M′′, I′′). Hence shift equivalence is an equivalence

relation on symbolic matrix systems.

Proof. (i) Suppose that (M, I) and (M′, I′) are shift equivalent of lag N. It suffices to show that they are shift equivalent of lag N + 1. We use the same notation as above. Set the alphabets

C_{N+1} = C_{N}, D_{N+1} = D_{N} · Σ.

Put the specification φ′_{1} = φ_{1} : Σ·C_{N+1} → C_{N+1}·Σ′. Through the specification φ_{2}, we have a natural specification φ′_{2} : Σ′ · D_{N+1} → D_{N+1} · Σ. Similarly, through the specifications ψ_{1}, ψ_{2}, φ_{1}, we have natural specifications

ψ′_{1} : (Σ)^{N+1} → C_{N+1} · D_{N+1}, ψ′_{2} : (Σ′)^{N+1} → D_{N+1} · C_{N+1}.

Put the matrices

H′_{l} = H_{l}I′_{l+N,l+N+1}, K′_{l} = K_{l}M_{l+N,l+N+1}.

Then it is straightforward to see that they give a shift equivalence of lag N + 1 between (M, I) and (M′, I′). (ii) Assume that

(H, K) : (M, I) ∼_{lagN} (M′, I′), (H′, K′) : (M′, I′) ∼_{lagN′} (M′′, I′′).

Then it is routine to check that

(HH′, K′K) : (M, I) ∼_{lagN+N′} (M′′, I′′).

Similarly to the case of matrices, we have

Theorem 6.2. Strong shift equivalence in N-step implies shift equivalence of lag N.

Proof. Suppose that (M, I) ≈_{N−st} (M′, I′) a strong shift equivalence in N-step.

There exist symbolic matrix systems (M^{(i)}, I^{(i)}) for i = 1, …, N − 1 such that

(M, I) = (M^{(0)}, I^{(0)}) ≈_{1−st}(M^{(1)}, I^{(1)}) ≈_{1−st} (M^{(2)}, I^{(2)}) ≈_{1−st}
⋯ ≈_{1−st}(M^{(N−1)}, I^{(N−1)}) ≈_{1−st} (M^{(N)}, I^{(N)}) = (M′, I′).

Let H_{l}^{(i)}, K_{l}^{(i)} be rectangular symbolic matrices that give a strong shift equivalence between (M^{(i−1)}, I^{(i−1)}) and (M^{(i)}, I^{(i)}) where H_{l}^{(i)} is an m^{(i−1)}(l −1)× m^{(i)}(l) matrix over alphabet C(i) and K_{l}^{(i)} is an m^{(i)}(l − 1) × m^{(i−1)}(l) matrix over alphabet D(i) for each l ∈ ℕ and i = 1, …, N. Set the alphabets

C_{N} = C(1) ⋯ C(N), D_{N} = D(1) ⋯ D(N).

Put the matrices

P_{l} = H_{l+2}^{(1)}H_{l+3}^{(2)} ⋯ H_{l+N+1}^{(N)}, Q_{l} = K_{l+2}^{(1)}K_{l+3}^{(2)} ⋯ K_{l+N+1}^{(N)}

an m(l) × m′(l + N) matrix over C_{N}, an m′(l) × m(l + N) matrix over D_{N} respectively. We then have the following natural specifications

φ_{1} : Σ · C_{N} → C_{N} · Σ′, φ_{2} : Σ′ · D_{N} → D_{N} · Σ

and

ψ_{1} : (Σ)^{N} → C_{N} · D_{N}, ψ_{2} : (Σ′)^{N} → D_{N} · C_{N}

that yield a shift equivalence of lag N between (M, I) and (M′, I′).

For a subshift (Λ, σ) over Σ, its n-higher power shift (Λ^{(n)}, σ) is defined to be the subshift (Λ, σ^{n}) over (Σ)^{n} (cf.[LM]). Two subshifts is called eventually conjugate if their n-higher power shifts are conjugate for all large enough n ([Wi], [KimR]). Williams and Kim-Roush showed that two square nonnegative matrices are shift equivalent if and only if the associated topological Markov shifts are eventually conjugate. Boyle-Krieger generalized their result to symbolic matrices and sofic subshifts ([BK]). W. Krieger kindly asked the author whether or not these results can be generalized to general subshifts. The author sincerely thanks him for his question.

Proposition 6.3. If symbolic matrix systems (M, I) and (M′, I′) are shift equivalent, their associated subshifts Λ_{(M,I)} and Λ_{(M′,I′)} are eventually conjugate.

To show the proposition, we provide a lemma that is proved by a straightforward calculation.

Lemma 6.4. For a symbolic matrix system (M, I), let Λ the associated subshift. We set for n, l ∈ ℕ,

I_{l,l+1}^{n} = I_{nl,nl+1}I_{nl+1,nl+2} ⋯ I_{nl+n−1,nl+n},
M_{l,l+1}^{n} = M_{nl,nl+1}M_{nl+1,nl+2} ⋯ M_{nl+n−1,nl+n}.

Then (M^{n}, I^{n}) becomes a symbolic matrix system whose associated subshift is the n-higher power shift Λ^{(n)} of Λ.

Proof of Proposition 6.3. Put Λ = Λ_{(M,I)}, Λ′ = Λ_{(M′,I′)} over Σ, Σ′ respectively. Assume that

(H, K) : (M, I) ∼_{lagN} (M′, I′).

For a number K ∈ ℕ, put n = K + N. We will see that Λ^{(n)} ≈_{1−st} Λ′^{(n)}. Let

C_{N}, D_{N} be alphabets as in Definition of shift equivalence. Set C = C_{N}, D = D_{N} · (Σ)^{K}. There are natural specifications

(Σ)^{n} → C · D, (Σ′)^{n} → D · C

by using the specifications in the shift equivalence between Λ and Λ′. Put the matrices

P_{l} = H_{nl−n}I′_{nl−K,nl−K+1}I′_{nl−K+1,nl−K+2} ⋯ I′_{nl−1,nl},
Q_{l} = K_{nl−n}M_{nl−K,nl−K+1}M_{nl−K+1,nl−K+2} ⋯ M_{nl−1,nl}.

They are an m(nl − n) × m′(nl) matrix over C and an m′(nl − n) × m(nl) matrix over D respectively. We see that they yield a strong shift equivalence in 1-step between (M^{n}, I^{n}) and (M′^{n}, I′^{n}) so that their associated subshifts are topologically conjugate by Theorem 4.15.

We will comment on the notion of properly shift equivalence between symbolic matrix systems. The following is the definition of properly shift equivalence that is a slightly stronger than shift equivalence and weaker than properly strong shift equivalence. Let (M, I) and (M′, I′) be symbolic matrix systems over alphabets Σ, Σ′ respectively. Hence M_{l,l+1}, I_{l,l+1} are m(l) × m(l + 1) matrices and M′_{l,l+1}, I′_{l,l+1} are m′(l) × m′(l + 1) matrices. Definition. (M, I) and (M′, I′) are said to be properly shift equivalent of lag N if there exist alphabets C_{N}, D_{N} and specifications

φ_{1} :Σ · C_{N} → C_{N} · Σ′,  φ_{2} : Σ′ · D_{N} → D_{N} · Σ,
ψ_{1} :(Σ)^{N} → C_{N} · D_{N},  ψ_{2} : (Σ′)^{N} → D_{N} · C_{N}

and increasing sequences n(l), n′(l) on l ∈ ℕ such that for each l ∈ ℕ, there exist an n(k) × n′(k + 2N − 1) matrix P_{k} over C_{N}, an n′(k) × n(k + 2N − 1) matrix Q_{k} over D_{N} for k = 2l, 2l + 2N − 1, an n(l) × n(l + 1) matrix X_{l} over {0, 1} and an n′(l) × n′(l + 1) matrix X′_{l} over {0, 1} satisfying the following equations: (6.1)

M_{l,l+N}I_{l+N,l+2N−1} ≃^{ψ_{1}} P_{2l}Q_{2l+2N−1}, M′_{l,l+N}I′_{l+N,l+2N−1} ≃^{ψ_{2}} Q_{2l}P_{2l+2N−1},

M_{l,l+1}P_{2(l+1)}X′_{2l+2N+1} ≃^{φ_{1}}P_{2l}X′_{2l+2N−1}M′_{l+N,l+N+1},
M′_{l,l+1}Q_{2(l+1)}X_{2l+2N+1} ≃^{φ_{2}}Q_{2l}X_{2l+2N−1}M_{l+N,l+N+1},
I_{l,l+1} = X_{2l}X_{2l+1}, I′_{l,l+1} = X′_{2l}X′_{2l+1}

and

X_{l}P_{l+1} = P_{l}X′_{l+2N−1}, X′_{l}Q_{l+1} = Q_{l}X_{l+2N−1}.

We denote this situation by

(M, I) ∼_{N−pr} (M′, I′).

It follows that by (6.1), n(2l) = m(l) and n′(2l) = m′(l) for l ∈ ℕ. For N = 1, if we understand that the matrices I_{l+1,l+1} and I′_{l+1,l+1} are the m(l +1)×m(l +1) identity matrix and the m′(l +1)×m′(l +1) identity matrix respectively, the properly shift equivalence of lag 1 is exactly the same as the properly strong shift equivalence in 1-step.

This definition is also a generalization of Boyle-Krieger ’s shift equivalence between symbolic matrices ([BK] see also [N2]). The following proposition is routine.

Proposition 6.5.

(i) (M, I) ∼_{N−pr} (M′, I′) implies (M, I) ∼_{lagN} (M′, I′). That is, properly

shift equivalence implies shift equivalence. (ii) (M, I) ≈_{N−pr} (M′, I′) implies (M, I) ∼_{N−pr} (M′, I′). That is, properly

strong shift equivalence implies properly shift equivalence.

We thus summarize as in the following way:

(M, I) ≈_{N−pr} (M′, I′) ⟹ (M, I) ∼_{N−pr} (M′, I′))
⇓  ⇓
(M, I) ≈_{N−st} (M′, I′) ⟹ (M, I) ∼_{lagN} (M′, I′).

We may define strong shift equivalence and shift equivalence between subshifts as their corresponding properties for their canonical symbolic matrix systems. Hence we can say that two subshifts are topologically conjugate if and only if they are strong shift equivalence. The strong shift equivalence for subshifts imply the shift equivalence.

7. Nonnegative matrix systems

In this section, we will introduce the notion of nonnegative matrix system that is also a generalization of nonnegative matrices. We will then generalize strong shift equivalence and shift equivalence between nonnegative matrices to between nonnegative matrix systems. Let (A_{l,l+1}, I_{l,l+1}), l ∈ ℕ be a pair of sequences of rectangular matrices such that the following four conditions for each l ∈ ℕ are satisfied:

(1) A_{l,l+1} is an m(l) × m(l + 1) rectangular matrix with entries in nonnegative integers.

(2) I_{l,l+1} is an m(l) × m(l + 1) rectangular matrix with entries in {0, 1}

satisfying the following two conditions: (2-a) For i, there exists j such that I_{l,l+1}(i, j) ≠ 0. (2-b) For j, there uniquely exists i such that I_{l,l+1}(i, j) ≠ 0.

(3) m(l) ≤ m(l + 1).

(4) I_{l,l+1}A_{l+1,l+2} = A_{l,l+1}I_{l+1,l+2}. The pair (A, I) is called a nonnegative matrix system. For i = 1, …, m(l), j = 1, …, m(l + 1), we denote by A_{l,l+1}(i, j), I_{l,l+1}(i, j) the (i, j)-components of A_{l,l+1}, I_{l,l+1} respectively. A nonnegative matrix system (A, I) is said to be essential if it satisfies the following further conditions

(5-i) For i, there exists j such that A_{l,l+1}(i, j) ≠ 0. (5-ii) For j, there exists i such that A_{l,l+1}(i, j) ≠ 0. We henceforth study essential nonnegative matrix systems and call them nonnegative matrix systems for simplicity. The property “sofic ”for nonnegative matrix systems are similarly defined to the cases of symbolic matrix systems. The following is basic.

Lemma 7.1. For a symbolic matrix system (M, I), let M_{l,l+1} be the m(l) × m(l+1) rectangular matrix obtained from M_{l,l+1} by setting all the symbols equal to 1. Then the resulting pair (M, I) becomes a nonnegative matrix system.

We write the matrices above as supp(M_{l,l+1}) = M_{l,l+1} and call M_{l,l+1} the support of M_{l,l+1}. The pair (M, I) is called the nonnegative matrix system associated with (M, I). Conversely we see

Proposition 7.2. For a nonnegative matrix system (A, I) and a symbolic matrix M_{1,2} over alphabet Σ such that supp(M_{1,2}) = A_{1,2}, there exists a sequence M_{l,l+1}, l ∈ ℕ of symbolic matrices over Σ such that the pair (M, I) is a symbolic matrix system and supp(M_{l,l+1}) = A_{l,l+1} for all l ∈ ℕ.

Proof. We will prove the assertion by induction. Assume that a symbolic matrix M_{k,k+1} is determined. For j = 1, …, m(k + 2), take a unique index j′ = 1, …, m(k + 1) such that I_{k+1,k+2}(j′, j) = 1. For i = 1, …, m(k), suppose that M_{k,k+1}(i, j′) = α_{1} + ⋯ + α_{n}. Let l_{1}, …, l_{p} be the set of all numbers l = 1, …, m(k + 1) satisfying I_{k,k+1}(i, l) = 1. Hence we have n = ∑_{r=1}^{p} A_{k+1,k+2}(l_{r}, j). Put ξ_{r} = A_{k+1,k+2}(l_{r}, j). Now we define

M_{k+1,k+2}(l_{1}, j) = α_{1} + ⋯ + α_{ξ_{1}},
M_{k+1,k+2}(l_{2}, j) = α_{ξ_{1}+1} + ⋯ + α_{ξ_{1}+ξ_{2}},
M_{k+1,k+2}(l_{3}, j) = α_{ξ_{1}+ξ_{2}+1} + ⋯ + α_{ξ_{1}+ξ_{2}+ξ_{3}},
· · · · · ·
M_{k+1,k+2}(l_{p}, j) = α_{ξ_{1}+···+ξ_{p−1}+1} + ⋯ + α_{n}.

Since for any l = 1, …, m(k + 1), there uniquely exists i = 1, …, m(k) such that I_{k,k+1}(i, l) = 1 we may define M_{k+1,k+2}(l, j) for all l = 1, …, m(k + 1) by the above way. The matrices satisfy I_{k,k+1}M_{k+1,k+2} = M_{k,k+1}I_{k+1,k+2} and supp(M_{k+1,k+2})(l, j) = A_{k+1,k+2}(l, j).

For nonnegative matrix systems we will formulate strong shift equivalence as follows. Definition. Two nonnegative matrix systems (A, I), (A′, I′) are said to be strong shift equivalent in 1-step if for each l ∈ ℕ, there exist an m(l −1)×m′(l) matrix H_{l} with entries in nonnegative integers and an m′(l − 1) × m(l) matrix K_{l} with entries in nonnegative integers satisfying the following equations:

I_{l−1,l}A_{l,l+1} = H_{l}K_{l+1}, I′_{l−1,l}A′_{l,l+1} = K_{l}H_{l+1}

and

H_{l}I′_{l,l+1} = I_{l−1,l}H_{l+1}, K_{l}I_{l,l+1} = I′_{l−1,l}K_{l+1}.

We write this situation as

(A, I) ≈_{1−st} (A′, I′).

Two nonnegative matrix systems (A, I) and (A′, I′) are said to be strong shift equivalent in N-step if there exist nonnegative matrix systems (A^{(i)}, I^{(i)}), i = 1, 2, …, N − 1 such that

\begin{aligned}(A, I) ≈_{1−st} (A^{(1)}, I^{(1)}) & ≈_{1−st} (A^{(2)}, I^{(2)}) \\ & ≈_{1−st} ⋯ ≈_{1−st} (A^{(N−1)}, I^{(N−1)}) ≈_{1−st} (A′, I′). \end{aligned}

We denote this situation by

(A, I) ≈_{N−st} (A′, I′)

and simply call it a strong shift equivalence.

This formulation is also a generalization of Williams’s strong shift equivalence between nonnegative matrices ([Wi]). Similarly to symbolic matrix systems, strong shift equivalence is an equivalence relation on nonnegative matrix systems. We directly have

Proposition 7.3. If two symbolic matrix systems are strong shift equivalence (in N-step), then the associated nonnegative matrix systems are strong shift equivalent (in N-step).

We will describe the matrix relations appearing in the formulation of strong shift equivalence between nonnegative matrix systems in terms of certain single homomorphisms between inductive limits of abelian groups. For a nonnegative matrix system (A, I), the transpose I_{l,l+1}^{t} of the matrix I_{l,l+1} naturally induces

an ordered homomorphism from ℤ^{m(l)} to ℤ^{m(l+1)}, where the positive cone ℤ_{+}^{m(l)} of the group ℤ^{m(l)} is defined by

ℤ_{+}^{m(l)} = {(n_{1}, n_{2}, …, n_{m(l)}) ∈ ℤ^{m(l)}|n_{i} ≥ 0, i = 1, 2 … m(l)}.

We put the inductive limits:

ℤ_{I^{t}} = \underrightarrow{lim}\{I_{l,l+1}^{t} : ℤ^{m(l)} → ℤ^{m(l+1)}\},
ℤ_{I^{t}}^{+} = \underrightarrow{lim}\{I_{l,l+1}^{t} : ℤ_{+}^{m(l)} → ℤ_{+}^{m(l+1)}\}.

The condition (2-a) for the matrix I_{l,l+1} says the following lemma.

Lemma 7.4. For each l ∈ ℕ, the homomorphism I_{l,l+1}^{t} : ℤ^{m(l)} → ℤ^{m(l+1)} is injective. Hence the canonical homomorphism ι_{l} : ℤ^{m(l)} → ℤ_{I^{t}} is injective.

By the relation: I_{l,l+1}A_{l+1,l+2} = A_{l,l+1}I_{l+1,l+2}, the sequence of the transposed matrices A_{l,l+1}^{t}, l ∈ ℕ of the matrices A_{l,l+1}, l ∈ ℕ yields an endomorphism of the ordered group ℤ_{I^{t}}. We write it as λ_{(A,I)}. Definition. For nonnegative matrix systems (A, I), (A′, I′) and L ∈ ℕ, a homomorphism ξ from the group ℤ_{I^{t}} to the group ℤ_{I′}^{t} is said to be finite homomorphism of lag L if it satisfies the condition

ξ(ℤ^{m(l)}) ⊂ ℤ^{m′(l+L)} for all l ∈ ℕ

where ℤ^{m(l)} and ℤ^{m′(l)} are naturally imbedded into ℤ_{I^{t}} and ℤ_{I′}^{t} respectively. We then have Proposition 7.5. Two nonnegative matrix systems (A, I) and (A′, I′) are strong shift equivalence in 1-step if and only if there exist order preserving finite homomorphisms of lag 1: ξ : ℤ_{I^{t}} → ℤ_{I′}^{t} and η : ℤ_{I′}^{t} → ℤ_{I^{t}} such that

η ∘ ξ = λ_{(A,I)}, ξ ∘ η = λ_{(A′,I′)}.

Proof. Suppose that (A, I) and (A′, I′) are strong shift equivalent in 1-step. Let H_{l}, K_{l} be sequences of matrices that give rise to a strong shift equivalence between them. Then by the condition I_{l,l+1}^{′t}H_{l}^{t} = H_{l+1}^{t}I_{l−1,l}^{t}, the family H_{l}^{t}, l ∈ ℕ yields a homomorphism from ℤ_{I^{t}} to ℤ_{I′}^{t} which we denote by ξ. Similarly we define a homomorphism η from ℤ_{I′}^{t} to ℤ_{I^{t}} induced by the family K_{l}, l ∈ ℕ. It is easy to see that the homomorphisms ξ, η are order preserving and finite homomorphisms of lag 1. By the condition A_{l,l+1}^{′t}I_{l−1,l}^{t} = K_{l+1}^{t}H_{l}^{t}, we see η ∘ ξ = λ_{(A,I)}. Similarly, we have ξ ∘ η = λ_{(A′,I′)}. The converse implication is also easy by using Lemma 7.4. We in fact see that the matrices H_{l}, K_{l} are given by the transposed matrices of the restrictions of the homomorphisms ξ to ℤ^{m(l)}(↪ ℤ_{I^{t}}) and η to ℤ^{m′(l)}(↪ ℤ_{I′}^{t}) respectively. They satisfy the required conditions of strong shift equivalence between (A, I) and (A′, I′).

We will next formulate shift equivalence between two nonnegative matrix systems. For a nonnegative matrix system (A, I), we set the m(l) × m(l + k) matrices:

I_{l,l+k} = I_{l,l+1} · I_{l+1,l+2} ⋯ I_{l+k−1,l+k},
A_{l,l+k} = A_{l,l+1} · A_{l+1,l+2} ⋯ A_{l+k−1,l+k}

for each l, k ∈ ℕ. Definition. Two nonnegative matrix systems (A, I), (A′, I′) are said to be shift equivalent of lag N if for each l ∈ ℕ, there exist an m(l) × m′(l + N) matrix H_{l} with entries in nonnegative integers and an m′(l) × m(l + N) matrix K_{l} with entries in nonnegative integers satisfying the following equations:

A_{l,l+1}H_{l+1} = H_{l}A′_{l+N,l+N+1}, A′_{l,l+1}K_{l+1} = K_{l}A_{l+N,l+N+1},
H_{l}K_{l+N} = I_{l,l+N}A_{l+N,l+2N}, K_{l}H_{l+N} = I′_{l,l+N}A′_{l+N,l+2N}

and

I_{l,l+1}H_{l+1} = H_{l}I′_{l+N,l+N+1}, I′_{l,l+1}K_{l+1} = K_{l}I_{l+N,l+N+1}.

We write this situation as

(A, I) ∼_{lagN} (A′, I′) or (H, K) : (A, I) ∼_{lagN} (A′, I′)

and simply call it a shift equivalence.

This formulation is a generalization of Williams’s shift equivalence between square matrices with entries in nonnegative integers ([Wi] see also [BK]). Similarly to the case of shift equivalence for nonnegative matrices and symbolic matrix systems, we have.

Lemma 7.6.

(i) (A, I) ∼_{lagN} (A′, I′) implies (A, I) ∼_{lagL} (A′, I′) for all L ≥ N.

(ii) (A, I) ∼_{lagN} (A′, I′) and (A′, I′) ∼_{lagN′} (A′′, I′′) implies (A, I) ∼_{lagN+N′}

(A′′, I′′). Hence shift equivalence is an equivalence relation on nonnegative matrix systems.

Similarly to Theorem 6.2, we have

Proposition 7.7. For nonnegative matrix systems, strong shift equivalence in N-step implies shift equivalence of lag N.

As in the case of strong shift equivalence, we may describe the matrix relations appearing in the formulation of shift equivalence in terms of single homomorphisms between inductive limits of abelian groups.

Proposition 7.8. Two nonnegative matrix systems (A, I) and (A′I′) are shift equivalent of lag N if and only if there exist order preserving finite homomorphisms of lag N: ξ : ℤ_{I^{t}} → ℤ_{I′}^{t} and η : ℤ_{I′}^{t} → ℤ_{I^{t}} such that

λ_{(A′,I′)} ∘ ξ = ξ ∘ λ_{(A,I)}, λ_{(A,I)} ∘ η = η ∘ λ_{(A′,I′)}

and

η ∘ ξ = λ_{(A,I)}^{N}, ξ ∘ η = λ_{(A′,I′)}^{N}.

Let (M, I), (M′, I′) be symbolic matrix systems and (M, I), (M′, I′) be their supports respectively. The following proposition is direct.

Proposition 7.9.

(i) (M, I) ≈_{n−st} (M′, I′) implies (M, I) ≈_{n−st} (M′, I′).

(ii) (M, I) ∼_{lagN} (M′, I′) implies (M, I) ∼_{lagN} (M′, I′).

8. Dimension groups

In this section, we will introduce the notions of dimension group and dimension triple for nonnegative matrix systems that is shown to be a shift equivalence invariant. It is a generalization of the notions of dimension group and dimension triple for nonnegative matrices defined by W. Krieger in [Kr], [Kr2]. The Krieger’s idea to define dimension groups for nonnegative matrices is based on the K-theory for C^{∗}-algebras (cf.[Ef]). The author considered the dimension groups for subshifts by using K_{0}-groups for certain C^{∗}-algebras associated with subshifts as in [Ma2],[Ma3]. It is a generalization of the original idea of Krieger. We will in this section formulate the dimension groups and the dimension triples for nonnegative matrix systems. Let (A, I) be a nonnegative matrix system. Recall that ℤ_{I^{t}} denotes the ordered group of the inductive limit of the sequence of the ordered abelian groups ℤ^{m(l)}, l ∈ ℕ through the transposed matrices I_{l,l+1}^{t}, l ∈ ℕ. As seen in the previous discussion, the sequence of the transposed matrices A_{l,l+1}^{t} naturally induces an order preserving endomorphism on the ordered group ℤ_{I^{t}} that is denoted by λ_{(A,I)}. We set ℤ_{I^{t}}(k) = ℤ_{I^{t}} and ℤ_{I^{t}}^{+}(k) = ℤ_{I^{t}}^{+} for k ∈ ℕ. We define an abelian group and its positive cone by the following inductive limits:

Δ_{(A,I)} = \underrightarrow{lim}_{k}\{λ_{(A,I)} : ℤ_{I^{t}}(k) → ℤ_{I^{t}}(k + 1)\},
Δ_{(A,I)}^{+} = \underrightarrow{lim}_{k}\{λ_{(A,I)} : ℤ_{I^{t}}^{+}(k) → ℤ_{I^{t}}^{+}(k + 1)\}.

We call the ordered group (Δ_{(A,I)}, Δ_{(A,I)}^{+}) the dimension group for (A, I). Since the map δ_{(A,I)} : ℤ_{I^{t}}(k) → ℤ_{I^{t}}(k+1) defined by δ_{(A,I)}([X, k]) = ([X, k+1]) for X ∈ ℤ_{I^{t}} yields an automorphism on Δ_{(A,I)} that preserves the positive cone Δ_{(A,I)}^{+}. We also denote it by δ_{(A,I)} and call it the dimension automorphism. We call the triple (Δ_{(A,I)}, Δ_{(A,I)}^{+}, δ_{(A,I)}) the dimension triple for (A, I) and the pair (Δ_{(A,I)}, δ_{(A,I)}) the dimension pair for (A, I).

Proposition 8.1. If two nonnegative matrix systems are shift equivalent, their dimension triples are isomorphic.

Proof. Suppose that two nonnegative matrix systems (A, I) and (A′, I′) are shift equivalent of lag N. By Proposition 7.8, there exist order preserving finite homomorphisms ξ : ℤ_{I^{t}} → ℤ_{I′}^{t} and η : ℤ_{I′}^{t} → ℤ_{I^{t}} of lag N such that

λ_{(A′,I′)} ∘ ξ = ξ ∘ λ_{(A,I)}, λ_{(A,I)} ∘ η = η ∘ λ_{(A′,I′)}

and

η ∘ ξ = λ_{(A,I)}^{N}, ξ ∘ η = λ_{(A′,I′)}^{N}.

Define the maps Φ_{ξ} : ℤ_{I^{t}}(k) → ℤ_{I′}^{t}(k) and Φ_{η} : ℤ_{I′}^{t}(k) → ℤ_{I^{t}}(k) as Φ_{ξ}([X, k]) = ([ξ(X), k]) and Φ_{η}([Y, k]) = ([η(Y), k]) for X ∈ ℤ_{I^{t}}, Y ∈ ℤ_{I′}^{t}. It is easy to see that they induce homomorphisms from Δ_{(A,I)} to Δ_{(A′,I′)} and Δ_{(A′,I′)} to Δ_{(A,I)} respectively. We still denote them by Φ_{ξ} and Φ_{η} respectively. Since the homomorphisms ξ, η are order preserving, the maps Φ_{ξ}, Φ_{η} also preserve order structures of the dimension groups. It then follows that

δ_{(A,I)} ∘ Φ_{η} = Φ_{η} ∘ δ_{(A′I′)}, δ_{(A′,I′)} ∘ Φ_{ξ} = Φ_{ξ} ∘ δ_{(A,I)}

and

Φ_{η} ∘ Φ_{ξ} = δ_{(A,I)}^{−N}, Φ_{ξ} ∘ Φ_{η} = δ_{(A′,I′)}^{−N}.

Therefore we see that the both maps Φ_{ξ} and Φ_{η} are isomorphisms and the corresponding dimension triples are isomorphic.

In particular we have (cf.[BK])

Proposition 8.2. Two sofic nonnegative matrix systems are shift equivalent if and only if their dimension triples are isomorphic. Thus the dimension triple are complete invariants for shift equivalence of sofic nonnegative matrix systems.

Proof. The only if part is from the preceding proposition. By a similar discussion to [Kr],[Kr2], we obtain the if part of the assertion.

We will define the dimension triples for symbolic matrix systems as the dimension triples for their supports. Namely let (M, I) be a symbolic matrix system and (M, I) its support. Then the dimension triple (Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}) is defined to be the dimension triple (Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}). We may also define dimension triples for subshifts as the dimension triple for their canonical symbolic matrix systems. Let Λ be a subshift and (M, I) its canonical symbolic matrix system for Λ. Then the future dimension triple (Δ_{Λ}, Δ_{Λ}^{+}, δ_{Λ}) for subshift Λ is defined to be the dimension triple (Δ_{(M,I)}, Δ_{(M,I)}^{+}, δ_{(M,I)}). The past dimension triple for Λ is defined as the future dimension triple for the transposed subshift Λ^{T} for Λ. Thus we have

Proposition 8.3. The future dimension triples for subshifts are shift equivalence invariants and in particular topological conjugacy invariants.

The notion of dimension pair (Δ_{Λ}, δ_{Λ}) for subshifts has been also seen in [Le].

9. K-groups and Bowen-Franks groups

The Bowen-Franks groups for nonnegative matrices and hence for topological Markov shifts have been introduced by R. Bowen and J. Franks in [BF]. For an n × n nonnegative square matrix A, its Bowen-Franks group BF (A) is defined by the group ℤ^{n}/(1−A)ℤ^{n}. This group has discovered in a study of suspension flows of topological Markov shifts by Bowen and Franks (cf. [PS]). They showed that the groups are not only invariants under shift equivalence but also almost complete invariants under flow equivalence between nonnegative matrices. We will in this section introduce and study the notion of Bowen-Franks groups for nonnegative matrix systems as a generalization of the original Bowen-Franks groups for nonnegative matrices. Our Bowen-Franks groups for a nonnegative matrix system consist of a pair of abelian groups. One corresponds to a generalization of the original Bowen-Franks group, called the Bowen-Franks group of degree zero, and the other one corresponds to its suspension, called the Bowen-Franks group of degree one. For matrices, the latter group is the torsion-free part of the original Bowen-Franks group. But in general nonnegative matrix systems the group of degree one is not necessarily the torsion-free part of the group of degree zero (see Section 10). Before going to definition of the Bowen-Franks groups for nonnegative matrix systems, we introduce two abelian groups for nonnegative matrix systems, called K-groups, that will be proved to be invariant under shift equivalence.

Let (A, I) be a nonnegative matrix system. For l ∈ ℕ, we set the abelian groups

K_{0}^{l}(A, I) = ℤ^{m(l+1)}/(I_{l,l+1}^{t} − A_{l,l+1}^{t})ℤ^{m(l)},
K_{1}^{l}(A, I) = Ker(I_{l,l+1}^{t} − A_{l,l+1}^{t}) in ℤ^{m(l)}.

Lemma 9.1. The map I_{l,l+1}^{t} : ℤ^{m(l)} → ℤ^{m(l+1)} naturally induces homomorphisms between the following groups:

i_{∗}^{l} : K_{∗}^{l}(A, I) → K_{∗}^{l+1}(A, I) for ∗ = 0, 1.

The proof is straightforward by using the relations

I_{l,l+1}A_{l+1,l+2} = A_{l,l+1}I_{l+1,l+2}.

We now define the K-groups for nonnegative matrix system (A, I). Definition. The K-groups for (A, I) are defined as the following inductive limits of the abelian groups:

K_{0}(A, I) = \underrightarrow{lim}_{l}\{i_{0}^{l} : K_{0}^{l}(A, I) → K_{0}^{l+1}(A, I)\},
K_{1}(A, I) = \underrightarrow{lim}_{l}\{i_{1}^{l} : K_{1}^{l}(A, I) → K_{1}^{l+1}(A, I)\}.

For a symbolic matrix system (M, I), its K-groups K_{0}(M, I), K_{1}(M, I) are defined to be the K-groups for the associated nonnegative matrix systems. It is easy to see that the groups K_{∗}(A, I) are also represented as in the following way

Proposition 9.2.

(i) K_{0}(A, I) = ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}}, (ii) K_{1}(A, I) = Ker(id − λ_{(A,I)}) in ℤ_{I^{t}}.

We will see that the groups K_{∗}(A, I) are invariant under shift equivalence.

Lemma 9.3.

(i) K_{0}(A, I) = Δ_{(A,I)}/(id − δ_{(A,I)})Δ_{(A,I)}, (ii) K_{1}(A, I) = Ker(id − δ_{(A,I)}) in Δ_{(A,I)}.

Proof. As the automorphism δ_{(A,I)} is given by λ_{(A,I)} = {A_{l,l+1}^{t}} on Δ_{(A,I)}, the assertions are easily proved.

Since the dimension triple (Δ_{(A,I)}, Δ_{(A,I)}^{+}, δ_{(A,I)}) is invariant under shift equivalence of nonnegative matrix systems, we thus have Proposition 9.4. The groups K_{i}(A, I), i = 0, 1 are invariant under shift equivalence of nonnegative matrix systems.

Set the abelian group

ℤ_{I} = \underleftarrow{lim}_{l}\{I_{l,l+1} : ℤ^{m(l+1)} → ℤ^{m(l)}\}

the projective limit of the system: I_{l,l+1} : ℤ^{m(l+1)} → ℤ^{m(l)}, l ∈ ℕ. The sequence A_{l,l+1}, l ∈ ℕ naturally acts on ℤ_{I} as an endomorphism that we denote by A. The identity on ℤ_{I} is denoted by I. We now define the Bowen-Franks groups for (A, I) as follows: Definition. For a nonnegative matrix system (A, I),

BF^{0}(A, I) = ℤ_{I}/(I − A)ℤ_{I}, BF^{1}(A, I) = Ker(I − A) in ℤ_{I}.

We call BF^{0}(A, I) the Bowen-Franks group for (A, I) of degree zero and BF^{1}(A, I) the Bowen-Franks group for (A, I) of degree one. We see

Theorem 9.5. The Bowen-Franks groups BF^{i}(A, I), i = 0, 1 are invariant under shift equivalence of nonnegative matrix systems.

Proof. (i) Suppose that two nonnegative matrix systems (A, I) and (A′, I′) are shift equivalent of lag N. Let H_{l}, K_{l} be sequences of nonnegative matrices

such that (H, K) : (A, I) ∼_{lagN} (A′, I′). For (x_{i})_{i∈ℕ} ∈ ℤ_{I}, put Φ_{K}((x_{i})_{i∈ℕ}) =

(K_{i}(x_{N+i})_{i∈ℕ}). It is easy to see that the Φ_{K} gives rise to a homomorphism from ℤ_{I} to ℤ_{I′}. As we see the equality: K_{i} ∘ (I_{N+i,N+i+1} − A_{N+i,N+i+1}) = (I′_{i,i+1} − A′_{i,i+1}) ∘ K_{i+1}, the homomorphism induces a homomorphism from ℤ_{I}/(I − A)ℤ_{I} to ℤ_{I′}/(I′ − A′)ℤ_{I′}. We denote it by Φ̄_{K}. We similarly have a homomorphism Φ̄_{H} from ℤ_{I′}/(I′ − A′)ℤ_{I′} to ℤ_{I}/(I − A)ℤ_{I}. Since we have Φ_{H} ∘ Φ_{K} = A^{N} on ℤ_{I} and Φ_{K} ∘ Φ_{H} = A′^{N} on ℤ_{I′}, the homomorphisms Φ̄_{H} and Φ̄_{K} are inverses each other. (ii) It is direct to see that the homomorphisms Φ_{H} and Φ_{K} induce isomorphisms between Ker(I − A) in ℤ_{I} and Ker(I′ − A′) in ℤ_{I′}.

We will prove the following Universal Coefficient Theorem. It says that the Bowen-Franks groups are determined by the K-groups.

Theorem 9.6.

(i) There exists a short exact sequence

0 ⟶ Ext_{ℤ}^{1}(K_{0}(A, I), ℤ) ⟶^{δ} BF^{0}(A, I) ⟶^{γ} Hom_{ℤ}(K_{1}(A, I), ℤ) ⟶ 0

that splits unnaturally. (ii)

BF^{1}(A, I) ≅ Hom_{ℤ}(K_{0}(A, I), ℤ).

In the theorem above, Ext_{ℤ}^{1} is the derived functor of the Hom-functor in homological algebra. The formulations above come from the Universal Coefficient Theorem for K-theory of the C^{∗}-algebra O_{Λ} associated with subshift Λ ([Ma4]). General framework of the Universal Coefficient Theorem for K-theory of C^{∗}- algebras have been proved in [Bro], [RS]. If an abelian group G is finitely generated, it is well known that

Hom_{ℤ}(G, ℤ) = The torsion-free part of G,
Ext_{ℤ}^{1}(G, ℤ) = The torsion part of G.

We provide some lemmas to prove Theorem 9.6.

Lemma 9.7. Ext_{ℤ}^{1}(ℤ_{I^{t}}, ℤ) = 0.

Proof. It suffices to show that an extension

0 ⟶ ℤ ⟶ G ⟶^{ρ} ℤ_{I^{t}} ⟶ 0

of abelian groups splits. For each l ∈ ℕ, let ι_{l} be the canonical inclusion of ℤ^{m(l)} into ℤ_{I^{t}}. We will choose homomorphisms φ_{l} : ℤ^{m(l)} → G such that

ρ ∘ φ_{l} = ι_{l}, φ_{l+1} ∘ I_{l,l+1}^{t} = φ_{l}

as follows: Let e_{i}^{l}, i = 1, …, m(l) be the standard basis of ℤ^{m(l)}. We first take homomorphisms ϕ_{l} : ℤ^{m(l)} → G such that ρ ∘ ϕ_{l} = ι_{l} for l ∈ ℕ. Put φ_{1} = ϕ_{1}. Since we see ρ((ϕ_{2} ∘ I_{1,2}^{t} − φ_{1})(e_{i}^{1})) = 0, we may regard the element ϕ_{2} ∘ I_{1,2}^{t}(e_{i}^{1}) − φ_{1}(e_{i}^{1}) as an integer m_{i}^{1}. For each i = 1, …, m(1), take r_{i} = 1, …, m(2) such that I_{1,2}(i, r_{i}) = 1. We set

φ_{2}(e_{j}^{2}) = \{ \begin{matrix}ϕ_{2}(e_{j}^{2}) − m_{i}^{1} & if j = r_{i} \\ ϕ_{2}(e_{j}^{2}) & otherwise. \end{matrix}

Then it is easy to see that

ρ ∘ φ_{2} = ι_{2}, φ_{2} ∘ I_{1,2}^{t} = φ_{1}.

By continuing these procedures, we can find a sequence of homomorphisms φ_{l}, l ∈ ℕ that have the desired property. They give rise to a homomorphism φ : ℤ_{I^{t}} → G such that ρ ∘ φ = id.

Lemma 9.8.

(i) Ext_{ℤ}^{1}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) = 0.

(ii) Ext_{ℤ}^{1}(Ker(id − λ_{(A,I)}) in ℤ_{I^{t}}, ℤ) = 0.

Proof. Regard (id − λ_{(A,I)})ℤ_{I^{t}} and Ker(id − λ_{(A,I)}) in ℤ_{I^{t}} as subgroups of ℤ_{I^{t}}. Consider the following short exact sequences:

(9.1) 0 ⟶(id − λ_{(A,I)})ℤ_{I^{t}} ⟶^{ι} ℤ_{I^{t}} ⟶^{q} ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}} ⟶ 0,

(9.2) 0 ⟶Ker(id − λ_{(A,I)}) ⟶^{j} ℤ_{I^{t}} ⟶^{id−λ_{(A,I)}} (id − λ_{(A,I)})ℤ_{I^{t}} ⟶ 0

of abelian groups. They yield the following exact sequences respectively:

⋯ ⟶Ext_{ℤ}^{1}(ℤ_{I^{t}}, ℤ) ⟶ Ext_{ℤ}^{1}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)
⟶ Ext_{ℤ}^{2}(ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) ⟶ ⋯

and

⋯ ⟶Ext_{ℤ}^{1}(ℤ_{I^{t}}, ℤ) ⟶ Ext_{ℤ}^{1}(Ker(id − λ_{(A,I)}), ℤ)
⟶ Ext_{ℤ}^{2}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) ⟶ ⋯

As Ext_{ℤ}^{2} = 0, we have

Ext_{ℤ}^{1}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) = Ext_{ℤ}^{1}(Ker(id − λ_{(A,I)}), ℤ) = 0

by the preceding lemma.

Lemma 9.9.

(i)

Ext_{ℤ}^{1}(ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)
≅ Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)/ι^{∗}Hom_{ℤ}(ℤ_{I^{t}}, ℤ).

(ii)

Hom_{ℤ}(Ker(id − λ_{(A,I)}), ℤ)
≅ Hom_{ℤ}(ℤ_{I^{t}}, ℤ)/(id − λ_{(A,I)})^{∗}Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ).

Proof. The short exact sequences (9.1) and (9.2) make the following sequences exact:

0 ⟶Hom_{ℤ}(ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) (9.3)

⟶^{q^{∗}} Hom_{ℤ}(ℤ_{I^{t}}, ℤ) ⟶^{ι^{∗}} Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)

⟶ Ext_{ℤ}^{1}(ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) ⟶ Ext_{ℤ}^{1}(ℤ_{I^{t}}, ℤ) ⟶ ⋯,

0 ⟶Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) ⟶^{(id−λ_{(A,I)})^{∗}} Hom_{ℤ}(ℤ_{I^{t}}, ℤ) (9.4)

⟶^{j^{∗}} Hom_{ℤ}(Ker(id − λ_{(A,I)}), ℤ) ⟶ Ext_{ℤ}^{1}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) ⟶ · · · .

Hence we get the desired isomorphisms.

Proof of Theorem 9.6. (i) By Proposition 9.2 and the previous lemmas, we have

Hom_{ℤ}(K_{1}(A, I), ℤ) ≅Hom_{ℤ}(ℤ_{I^{t}}, ℤ)/(id − λ_{(A,I)})^{∗}Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ),
Ext_{ℤ}^{1}(K_{0}(A, I), ℤ) ≅Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)/ι^{∗}Hom_{ℤ}(ℤ_{I^{t}}, ℤ).

The exact sequence (9.4) says the map

(id − λ_{(A,I)})^{∗} : Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) ⟶ Hom_{ℤ}(ℤ_{I^{t}}, ℤ)

is injective. Hence we know that the group

Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)/ι^{∗}Hom_{ℤ}(ℤ_{I^{t}}, ℤ)

is isomorphic to the group

(id − λ_{(A,I)})^{∗}Hom_{ℤ}(id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)/(id − λ_{(A,I)})^{∗}ι^{∗}Hom_{ℤ}(ℤ_{I^{t}}, ℤ).

The map

(id − λ_{(A,I)})^{∗}ι^{∗} : Hom_{ℤ}(ℤ_{I^{t}}, ℤ) ⟶ Hom_{ℤ}(ℤ_{I^{t}}, ℤ)

is naturally regarded as the endomorphism

I − A : ℤ_{I} → ℤ_{I}

through a natural identification between Hom_{ℤ}(ℤ_{I^{t}}, ℤ) and ℤ_{I}. As there exists an short exact sequence

0 ⟶(id − λ_{(A,I)})^{∗}Hom_{ℤ}(id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)/(id − λ_{(A,I)})^{∗}ι^{∗}Hom_{ℤ}(ℤ_{I^{t}}, ℤ)
⟶Hom_{ℤ}(ℤ_{I^{t}}, ℤ)/(id − λ_{(A,I)})^{∗}ι^{∗}Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)
⟶Hom_{ℤ}(ℤ_{I^{t}}, ℤ)/(id − λ_{(A,I)})^{∗}Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)
⟶0,

we obtain a short exact sequence:

0 ⟶ Ext_{ℤ}^{1}(K_{0}(A, I), ℤ) ⟶^{δ} ℤ_{I}/(I − A)ℤ_{I} ⟶^{γ} Hom_{ℤ}(K_{1}(A, I), ℤ) ⟶ 0.

The short exact sequence above splits unnaturally, since the group Ext_{ℤ}^{1}(G, ℤ) is algebraically compact and the group Hom_{ℤ}(H, ℤ) is torsion-free for any abelian groups G, H (cf. [KKS]). (ii) By the exact sequence (9.3), we see

Hom_{ℤ}(K_{0}(A, I), ℤ) ≅Hom_{ℤ}(ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}},), ℤ)
≅Ker ι^{∗} : Hom_{ℤ}(ℤ_{I^{t}}, ℤ) ⟶ Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ)

By a natural identification between Hom_{ℤ}(ℤ_{I^{t}}, ℤ) and ℤ_{I}, we obtain Ker ι^{∗} : Hom_{ℤ}(ℤ_{I^{t}}, ℤ) ⟶ Hom_{ℤ}((id − λ_{(A,I)})ℤ_{I^{t}}, ℤ) is regarded as Ker(I − A) in ℤ_{I}. Thus we end the proof of the theorem.

Remark. Lemma 9.8 (ii) means Ext_{ℤ}^{1}(K_{1}(A, I), ℤ) = 0. Hence the following short exact sequence clearly holds by Theorem 9.6 (ii):

0 ⟶ Ext_{ℤ}^{1}(K_{1}(A, I), ℤ) ⟶^{δ} BF^{1}(A, I) ⟶^{γ} Hom_{ℤ}(K_{0}(A, I), ℤ) ⟶ 0.

Example. Let M be an n × n nonnegative matrix . Put for each l ∈ ℕ

A_{l,l+1} = M, I_{l,l+1} = the n × n identity matrix.

Then (A, I) is a nonnegative matrix system. The K-groups are

K_{0}(A, I) = ℤ^{n}/(1 − M^{t})ℤ^{n}, K_{1}((A, I) = Ker(1 − M^{t}) in ℤ^{n}.

The Bowen-Franks groups are

BF^{0}(A, I) = ℤ^{n}/(1 − M)ℤ^{n}, BF^{1}((A, I) = Ker(1 − M) in ℤ^{n}.

Hence we have

K_{0}(A, I) ≅ BF^{0}(A, I) = BF (M) : the original Bowen-Franks group for M,
K_{1}(A, I) ≅ BF^{1}(A, I) = the torsion-free part of BF (M)

We will next define K-groups and Bowen-Franks groups for subshifts. Definition. For a subshift Λ, let (A_{Λ}, I_{Λ}) be the canonical nonnegative matrix system associated with Λ. We define

K_{i}(Λ) = K_{i}(A_{Λ}, I_{Λ}), i = 0, 1 : the K-groups for Λ
BF^{i}(Λ) = BF^{i}(A_{Λ}, I_{Λ}), i = 0, 1 : the Bowen-Franks groups for Λ

We thus have

Theorem 9.10. The K-groups K_{i}(Λ) and the Bowen-Franks groups BF^{i}(Λ) for subshift Λ are abelian groups that are invariant under shift equivalence of subshifts. In particular, they are topological conjugacy invariants of subshifts.

Proposition 9.11. Let Λ be a sofic subshift. We denote by m(Λ) the cardinality of the vertices of the left Krieger cover graph for Λ and A_{Λ} its adjacency matrix. Then we have

BF^{0}(Λ) = ℤ^{m(Λ)}/(1 − A_{Λ})ℤ^{m(Λ)}, BF^{1}(Λ) = Ker(1 − A_{Λ}) in ℤ^{m(Λ)}.

Proof. As we see

K_{0}(Λ) = ℤ^{m(Λ)}/(1 − A_{Λ})ℤ^{m(Λ)}, K_{1}(Λ) = Ker(1 − A_{Λ}) in ℤ^{m(Λ)},

the assertion is clear.

In the final section, we will see an example of a nonsofic subshift Λ for which BF^{1}(Λ) is no longer the torsion-free part of the group BF^{0}(Λ). Remark. In [Ma], the author introduced the C^{∗}-algebra O_{Λ} associated with subshift Λ as a generalization of the construction of the Cuntz-Krieger algebra O_{A} associated with the topological Markov shift Λ_{A} determined by a matrix A with entries in {0, 1}. Cuntz-Krieger proved in [CK] that the Ext-group Ext(O_{A}) of the C^{∗}-algebra O_{A} is ℤ^{n}/(1 − A)ℤ^{n} : the Bowen-Franks group of the matrix A. The author in [Ma4] generalized the notion of the Bowen-Franks group to the subshifts as:

BF (Λ) := Ext(O_{Λ}).

From the view point of the K-theory for C^{∗}-algebras, the invariants K_{i}, BF^{i}, i = 0, 1 introduced in this section appear as

K_{0}(Λ) = K_{0}(O_{Λ}), K_{1}(Λ) = K_{1}(O_{Λ})

and

BF^{0}(Λ) = Ext(O_{Λ}), BF^{1}(Λ) = Ext(O_{Λ} ⊗ C_{0}(ℝ)).

The formulations in Theorem 9.6 come from the Universal Coefficients Theorem for C^{∗}-algebras ([Bro], [RS] ). As the K-groups and the Ext-groups for C^{∗}-algebras are stably isomorphic invariant and the stable isomorphism class of the C^{∗}-algebra O_{Λ} with gauge action is invariant under topological conjugacy class of subshifts ([Ma5]), we know that the dimension triple, the K-groups and the Bowen-Franks groups for subshifts are topological conjugacy invariants without using discussions of this paper under some mild conditions for subshifts. The Bowen-Franks group for nonnegative matrix was first invented for use as an invariant of flow equivalence of the associated topological Markov shift rather than topological conjugacy ([BF],[Fr],[PS]). We can prove that the Kgroups K_{∗}(Λ) and hence the Bowen-Franks groups BF^{∗}(Λ) for subshift are also invariant under flow equivalence of subshift by using a result of Parry-Sullivan [PS]. The proof, that we do not give in this paper, will appear in a forthcoming paper (cf.[Ma4],[Ma5]).

We will finally present another candidate of Bowen-Franks groups for subshifts. For a topological Markov shift Λ_{A} determined by an n×n matrix A with entries in {0, 1}, the group BF (Λ_{A}) is isomorphic to the K_{0}-group for the subshift Λ_{A^{t}} determined by the transpose of the matrix A. The subshift Λ_{A^{t}} is the transpose Λ_{A}^{T} of Λ_{A} as a subshift. From this point of view, it seems to be one way to define the Bowen-Franks group for canonical symbolic matrix systems as the K-groups for their transpose. Let (M, I) be a canonical symbolic matrix system and Λ_{(M,I)} the associated subshift. We define the transpose (M^{T} , I^{T}) of (M, I) as the canonical symbolic matrix system for the transpose Λ_{(M,I)}^{T} of the subshift Λ_{(M,I)}. We will define another pair of Bowen-Franks groups as in the following way. Definition. For a canonical symbolic matrix system (M, I), we define

BF_{K}^{i}(M, I) = K_{i}(M^{T} , I^{T}), i = 0, 1

where K_{i}(M^{T} , I^{T}) is defined as the K_{i}-groups for the nonnegative matrix system associated with (M^{T} , I^{T}). We call them the Bowen-Franks groups from K for (M, I). For a subshift Λ, let (M, I) be its canonical symbolic matrix system. We will then define Bowen-Franks groups (from K) for subshift as follows:

BF_{K}^{i}(Λ) = BF_{K}^{i}(M, I), i = 0, 1.

We thus have

Proposition 9.12. The Bowen-Franks groups BF_{K}^{i}(Λ), i = 0, 1 from K for subshift Λ are topological conjugacy invariants of subshifts.

Proof. Suppose that two subshifts Λ, Λ′ are topologically conjugate. We denote by (M, I), (M′, I′) their canonical symbolic matrix systems respectively. Hence their transposed subshifts Λ^{T} , Λ′^{T} are topologically conjugate so that their canonical symbolic matrix systems (M^{T} , I^{T}), (M′^{T} , I′^{T}) are strong shift equivalent and hence shift equivalent. As their corresponding nonnegative matrix systems (M^{T} , I^{T}), (M′^{T} , I′^{T}) are shift equivalent, we have K_{i}(M^{T} , I^{T}) = K_{i}(M′^{T} , I′^{T}) for i = 0, 1.

Proposition 9.13. For a topological Markov shift Λ_{A} determined by an n × n square matrix A with entries in {0, 1}, we have

BF_{K}^{0}(Λ_{A}) = ℤ^{n}/(1 − A)ℤ^{n} = BF (Λ_{A}), BF_{K}^{1}(Λ_{A}) = Ker(1 − A) in ℤ^{n}.

Hence the group BF_{K}^{1}(Λ) is the torsion-free part of the group BF_{K}^{0}(Λ).

We will finally present the calculation formulae for the Bowen-Franks groups from K. For a subshift Λ, let X_{Λ}^{−} be the set of all left-infinite sequences appearing in Λ. That is

X_{Λ}^{−} = {(..., z_{−2}, z_{−1}, z_{0}) ∈ ∏_{i=−∞}^{0} Σ_{i}|(z_{i})_{i∈ℤ} ∈ Λ}.

We will define l-future equivalence in the space X_{Λ}^{−} in a symmetric way to the previous l-past equivalence. Namely, for z ∈ X_{Λ}^{−} and l ∈ ℕ, put

Λ^{−l}(z) = {μ ∈ Λ^{l}|zμ ∈ X_{Λ}^{−}}.

Two points z, w ∈ X_{Λ}^{−} are said to be l-future equivalent if Λ^{−l}(z) = Λ^{−l}(w). We write this equivalence as x ∼_{−l} y. For a fixed l ∈ ℕ, let P_{i}^{l}, i = 1, 2, …, n(l) be the set of all l-future equivalence classes of X_{Λ}^{−}. We define two rectangular n(l) × n(l + 1) matrices J_{l,l+1}, B_{l,l+1} with entries in {0, 1} and entries in nonnegative integers similarly to the matrix I_{l,l+1}, A_{l,l+1}. Namely, we define

J_{l,l+1} for Λ = I_{l,l+1} for Λ^{T} , B_{l,l+1} for Λ = A_{l,l+1} for Λ^{T} .

By [Ma2;Theorem 4.9], we have

Theorem 9.14.

(i) BF_{K}^{0}(Λ) = \underrightarrow{lim}_{l}\{J_{l,l+1}^{t} : ℤ^{n(l)}/(J_{l,l+1}^{t} − B_{l,l+1}^{t})ℤ^{n(l)}\}.

(ii) BF_{K}^{1}(Λ) = \underrightarrow{lim}_{l}\{J_{l,l+1}^{t} : Ker(J_{l,l+1}^{t} − B_{l,l+1}^{t}) in ℤ^{n(l)}\}.

We similarly obtain by Lemma 9.2,

Theorem 9.15. The past dimension pair (Δ_{Λ^{T}} , δ_{Λ^{T}}) for subshift Λ determines the Bowen-Franks group BF_{K}^{i}(Λ), i = 0, 1 from K for Λ,

10. Spectrum

It is well-known that the set of all nonzero eigenvalues of a nonnegative matrix M is a shift equivalence invariant. The set of M is called the nonzero spectrum of M and plays an important rôle for studying dynamical properties of the associated topological Markov shift (cf.[LM],[Ki]). In this section, we introduce the notion of spectrum of nonnegative matrix system (A, I). It is an eigenvalue of (A, I) in the sense stated bellow. We denote by Sp(A, I) the set of all eigenvalues of (A, I). As the sequence of the sizes of matrices A_{l,l+1}, I_{l,l+1}, l ∈ ℕ are increasing, it seems to be natural to deal with eigenvalues of (A, I) with a certain boundedness condition defined bellow on the corresponding eigenvectors. We denote by Sp_{b}(A, I) the set of all eigenvalues of (A, I) with the boundedness condition on the corresponding eigenvectors. We will prove that the both of the sets of nonzero spectrum of Sp(A, I) and Sp_{b}(A, I) are invariant under shift equivalence of (A, I). We fix a nonnegative matrix system (A, I) throughout this section. Definition. A sequence {v^{l}}_{l∈ℕ} of vectors v^{l} = (v_{1}^{l}, …, v_{m(l)}^{l}) ∈ ℂ^{m(l)}, l ∈ ℕ is called an I-compatible vector if it satisfies the conditions:

(10.1)  v^{l} = I_{l,l+1}v^{l+1}  for all l ∈ ℕ.

An I-compatible vector {v^{l}}_{l∈ℕ} is said to be nonzero if v^{l} is a nonzero vector for some l. If v_{i}^{l} ≥ 0 (resp. v_{i}^{l} > 0 ) for all i = 1, …, m(l) and l ∈ ℕ, {v^{l}}_{l∈ℕ} is said to be nonnegative (resp. positive). If there exists a number M such that ∑_{i=1}^{m(l)} |v_{i}^{l}| ≤ M for all l ∈ ℕ, {v^{l}}_{l∈ℕ} is said to be bounded. We remark that, for an I-compatible vector {v^{l}}_{l∈ℕ}, v^{N} ≠ 0 for some N implies v^{l} ≠ 0 for all l ≥ N.

Definition. For a complex number β, a nonzero I-compatible vector {v^{l}} is called an eigenvector of (A, I) for eigenvalue β if it satisfies the conditions:

(10.2)  A_{l,l+1}v^{l+1} = βv^{l}  for all l ∈ ℕ.

An eigenvalue β is said to be bounded if it is an eigenvalue for a bounded eigenvector. Remark. If a sequence v^{l} of vectors satisfies the above conditions (10.1),(10.2) for l = N, N + 1, … for some N, we may extendedly define vectors v^{l} for l = 1, …, N − 1 for which {v^{l}}_{l∈ℕ} satisfy the conditions (10.1),(10.2) for all l ∈ ℕ by using the condition (10.1). Definition. Let Sp^{×}(A, I) be the set of all nonzero eigenvalues of (A, I) and Sp_{b}^{×}(A, I) the set of all nonzero bounded eigenvalues of (A, I). We call them the nonzero spectrum of (A, I) and the nonzero bounded spectrum of (A, I) respectively. We will prove

Theorem 10.1. If two nonnegative matrix systems are shift equivalent, their nonzero spectrum coincide.

Proof. Suppose that two nonnegative matrix systems (A, I) and (A′, I′) are shift equivalent of lag N. Let H_{l}, K_{l} be sequences of nonnegative matrices

such that (H, K) : (A, I) ∼_{lagN} (A′, I′). We will show Sp^{×}(A, I) ⊂ Sp^{×}(A′, I′).

For β ∈ Sp^{×}(A, I) with nonzero eigenvector v^{l}, we set u^{l} = K_{l}v^{l+N} for l ∈ ℕ. It is direct to see that

u^{l} = I′_{l,l+1}u^{l+1}, A′_{l,l+1}u^{l+1} = βu^{l}.

Now if the vectors u^{l} are zero for all l ≥ l_{0} for some l_{0}, by the equality H_{l}K_{l+N}v^{l+2N} = I_{l,l+N}A_{l+N,l+2N}v^{l+2N}, it follows that

0 = A_{l,l+N}I_{l+N,l+2N}v^{l+2N} = A_{l,l+N}v^{l+N} = βv^{l}.

Thus v^{l} = 0 for all l ≥ l_{0} and hence for all l ∈ ℕ, a contradiction. Therefore β is a nonzero eigenvalue of (A′, I′).

We will next show that the nonzero bounded spectrum of (A, I) is also invariant under shift equivalence. We must provide some lemmas.

Lemma 10.2. Put N_{A}^{l} = max_{j} ∑_{i=1}^{m(l)} A_{l,l+1}(i, j) for l ∈ ℕ. We have N_{A}^{l} = N_{A}^{l+1}. That is, the value N_{A}^{l} does not depend on the choice of l ∈ ℕ.

Proof. We note that ∑_{i=1}^{m(l)} I_{l,l+1}(i, j) = 1 for each j. It follows that

∑_{j=1}^{m(l+1)} A_{l+1,l+2}(j, k) = ∑_{i=1}^{m(l)} ∑_{j=1}^{m(l+1)} I_{l,l+1}(i, j)A_{l+1,l+2}(j, k)

= ∑_{i=1}^{m(l)} ∑_{p=1}^{m(l+1)} A_{l,l+1}(i, p)I_{l+1,l+2}(p, k).

Hence for k = 1, …, m(l + 2), there uniquely exists p_{k} = 1, …, m(l + 1) such that

∑_{j=1}^{m(l+1)} A_{l+1,l+2}(j, k) = ∑_{i=1}^{m(l)} A_{l,l+1}(i, p_{k}).

This implies the inequality N_{A}^{l+1} ≤ N_{A}^{l}. For p = 1, …, m(l + 1), take k_{p} = 1, …, m(l + 2) with I_{l+1,l+2}(p, k_{p}) = 1. It follows that

∑_{i=1}^{m(l)} A_{l,l+1}(i, p) = ∑_{i=1}^{m(l)} A_{l,l+1}(i, p)I_{l+1,l+2}(p, k_{p})

= ∑_{i=1}^{m(l)} ∑_{q=1}^{m(l+1)} A_{l,l+1}(i, q)I_{l+1,l+2}(q, k_{p})

= ∑_{i=1}^{m(l)} ∑_{j=1}^{m(l+1)} I_{l,l+1}(i, j)A_{l+1,l+2}(j, k_{p})

= ∑_{j=1}^{m(l+1)} A_{l+1,l+2}(j, k_{p}).

This implies the inequality N_{A}^{l} ≤ N_{A}^{l+1}.

Set N_{A} = max_{j} ∑_{i=1}^{m(l)} A_{l,l+1}(i, j) that is independent of the choice of l ∈ ℕ. For an I-compatible vector {v^{l}}_{l∈ℕ}, we put ∥v^{l}∥ = ∑_{i=1}^{m(l)} |v_{i}^{l}|.

Lemma 10.3. The sequence {∥v^{l}∥}_{l∈ℕ} is increasing. If {v^{l}}_{l∈ℕ} is nonnegative, {∥v^{l}∥}_{l∈ℕ} is constant and hence {v^{l}}_{l∈ℕ} is bounded.

Proof. We know ∑_{i=1}^{m(l)} |I_{l,l+1}(i, j)v_{j}^{l+1}| = |v_{j}^{l+1}| and

∥v^{l}∥ ≤ ∑_{i=1}^{m(l)} ∑_{j=1}^{m(l+1)} |I_{l,l+1}(i, j)v_{j}^{l+1}| ≤ ∑_{j=1}^{m(l+1)} |v_{j}^{l+1}| = ∥v^{l+1}∥.

If {v^{l}}_{l∈ℕ} is nonnegative, both of the inequalities above go to equalities.

For a bounded I-compatible vector v = {v^{l}}_{l∈ℕ}, we put

∥v∥_{1} = sup_{l→∞} ∥v^{l}∥.

Proposition 10.4. Sp_{b}^{×}(A, I) ⊂ {z ∈ ℂ||z| ≤ N_{A}}.

Proof. For β ∈ Sp(A, I) with a bounded eigenvector {v^{l}}_{l∈ℕ}, we have

β ∑_{i=1}^{m(l)} |v_{i}^{l}| ≤ ∑_{j=1}^{m(l+1)}(max_{j} ∑_{i=1}^{m(l)} A_{l,l+1}(i, j))|v_{j}^{l+1}|.

Hence we obtain the inequality

β∥v^{l}∥ ≤ N_{A}∥v^{l+1}∥.

As {v^{l}} is bounded, the limit lim_{l→∞} ∥v^{l}∥ = ∥v∥_{1} exists so that we have a desired assertion.

We denote by 𝔅_{I} the set of all bounded I-compatible vectors. It is a complex Banach space with norm ∥ · ∥_{1}. A nonnegative I-compatible vector v = {v^{l}}_{l∈ℕ} is called a state for I if ∥v∥_{1} = 1. Let 𝔖_{I} be the set of all states for I. It is a convex subset of 𝔅_{I}.

Lemma 10.5. For v = {v^{l}}_{l∈ℕ} ∈ 𝔅_{I}, put

|v|_{i}^{l} = sup_{N≥l} ∑_{j=1}^{m(N)} I_{l,N}(i, j)|v_{j}^{N}| for i = 1, …, m(l), l ∈ ℕ.

We then have (i) |v|_{i}^{l} < ∞. (ii) The vectors defined by |v|^{l} = (|v|_{1}^{l}, |v|_{2}^{l}, …, |v|_{m(l)}^{l}) for l ∈ ℕ give rise

to a nonnegative I-compatible vector.

Proof. (i) By the inequality ∑_{j=1}^{m(N)} I_{l,N}(i, j)|v_{j}^{N}| ≤ ∑_{j=1}^{m(N)} |v_{j}^{N}| = ∥v^{N}∥, we get |v|_{i}^{l} ≤ ∥v∥_{1}. (ii) As we easily see

∑_{k=1}^{m(N)} I_{l,N}(i, k)|v_{k}^{N}| ≤ ∑_{j=1}^{m(N+1)} I_{l,N+1}(i, j)|v_{j}^{N+1}|,

the sequence of sums ∑_{j=1}^{m(N)} I_{l,N}(i, j)|v_{j}^{N}| is increasing on N so that we have

|v|_{i}^{l} = lim_{N→∞} ∑_{j=1}^{m(N)} I_{l,N}(i, j)|v_{j}^{N}|.

Hence the following equalities hold

∑_{j=1}^{m(l+1)} I_{l,l+1}(i, j)|v|_{j}^{l+1} = ∑_{j=1}^{m(l+1)} lim_{N→∞}( ∑_{k=1}^{m(N)} I_{l,l+1}(i, j)I_{l+1,N}(j, k)|v_{k}^{N}|)

= lim_{N→∞} ∑_{k=1}^{m(N)} ∑_{j=1}^{m(l+1)} I_{l,l+1}(i, j)I_{l+1,N}(j, k)|v_{k}^{N}|

= lim_{N→∞} ∑_{k=1}^{m(N)} I_{l,N}(i, k)|v_{k}^{N}| = |v|_{i}^{l}

so that the vectors {|v|^{l}}_{l∈ℕ} yield an I-compatible vector.

The I-compatible vector |v| for v ∈ 𝔅_{I} is called the total variation of v. A bounded I-compatible vector v ∈ 𝔅_{I} is said to be real if all elements v_{i}^{l} of the vectors v^{l}, l ∈ ℕ are real numbers. Thus we obtain Corollary 10.6. For a real bounded I-compatible vector v ∈ 𝔅_{I}, there exist nonnegative bounded I-compatible vectors v^{+}, v^{−} ∈ 𝔅_{I} such that

v = v^{+} − v^{−}, |v| = v^{+} + v^{−}.

This decomposition is called the Jordan decomposition of v.

Proof. As |v|_{i}^{l} ≥ |v_{i}^{l}| for each i, l, by putting

v^{+} = \frac{1}{2}(|v| + v), v^{−} = \frac{1}{2}(|v| − v)

we get the desired assertions.

Corollary 10.7. For a bounded I-compatible vector v ∈ 𝔅_{I}, there exist states v_{j} ∈ 𝔖_{I} and nonnegative real numbers c_{j} ∈ ℝ such that

v = c_{1}v_{1} − c_{2}v_{2} + i(c_{3}v_{3} − c_{4}v_{4}).

Proposition 10.8. For a bounded I-compatible vector v ∈ 𝔅_{I}, we put

(L_{A}v)_{i}^{l} = ∑_{j=1}^{m(l+1)} A_{l,l+1}(i, j)v_{j}^{l+1} for i = 1, …, m(l), l ∈ ℕ.

Then L_{A} gives rise to a bounded linear operator on the Banach space 𝔅_{I} that satisfies ∥L_{A}∥ = N_{A}, where the norm of L_{A} is given by ∥L_{A}∥ = sup_{v≠0} \frac{∥L_{A}v∥_{1}}{∥v∥_{1}} .

To prove the proposition above, we note the following lemma.

Lemma 10.9. For an arbitrary fixed l ∈ ℕ and nonnegative real numbers c_{i} for i = 1, …, m(l), there exists a nonnegative I-compatible vector v ∈ 𝔅_{I} such that v_{i}^{l} = c_{i} for i = 1, …, m(l).

Proof. Put v_{i}^{l} = c_{i}^{l} for i = 1, …, m(l). For k ≤ l, we put v^{k} = I_{k,l}v^{l}. For k = l + 1, we can choose nonnegative real numbers v_{j}^{l+1}, j = 1, …, m(l + 1) such that v_{i}^{l} = ∑_{j=1}^{m(l+1)} v_{j}^{l+1} because for each j there uniquely exists i satisfying I_{l,l+1}(i, j) = 1 and I_{l,l+1}(i′, j) = 0 for other i′. Hence we may get a nonnegative I-compatible vector v by induction such that v_{i}^{l} = c_{i}, i = 1, …, m(l).

Proof of Proposition 10.8. We first show that L_{A}v is a bounded I-compatible vector. By the relation I_{l,l+1}A_{l+1,l+2} = A_{l,l+1}I_{l+1,l+2}, it is direct to see that L_{A}v is an I-compatible vector. We have ∥(L_{A}v)^{l}∥ ≤ N_{A}∥v^{l+1}∥ so that ∥L_{A}v∥_{1} ≤ N_{A}∥v∥_{1}. Hence L_{A}v is bounded and ∥L_{A}∥ ≤ N_{A}. Fix l ∈ ℕ. Take i_{0} such that max_{i} ∑_{h=1}^{m(l−1)} A_{l−1,l}(h, i) = ∑_{h=1}^{m(l−1)} A_{l−1,l}(h, i_{0}). By the previous lemma, there exists a nonnegative I-compatible vector v ∈ 𝔅_{I} such that v_{i_{0}}^{l} = 1 and v_{i}^{l} ≠ 0 for i ≠ i_{0}. It then follows that

∥(L_{A}v)^{l−1}∥ = ∑_{h=1}^{m(l−1)} A_{l−1,l}(h, i_{0}) = N_{A}.

Thus we get ∥(L_{A}v)∥_{1} = N_{A}. As ∥v∥_{1} = ∥v^{l}∥ = 1, we conclude ∥L_{A}∥ ≥ N_{A} so that ∥L_{A}∥ = N_{A}.

Therefore we have Corollary 10.10. For a complex number β, it belongs to Sp_{b}(A, I) if and only if it satisfies L_{A}v = βv for some v ∈ 𝔅_{I}. That is, the bounded spectrum of (A, I) are nothing but the eigenvalues of the bounded positive operator L_{A} on the Banach space 𝔅_{I}.

Corresponding to Theorem 10.1, we have

Theorem 10.11. If two nonnegative matrix systems are shift equivalent, their nonzero bounded spectrum coincide.

Proof. Suppose that two nonnegative matrix systems (A, I) and (A′, I′) are shift equivalent of lag N. Let H_{l}, K_{l} be sequences of nonnegative matrices such that (H, K) : (A, I) ∼_{lagN} (A′, I′). Following the proof of Theorem 10.1,

it suffices to show that for a bounded vector v ∈ 𝔅_{I}, the vectors defined by u^{l} = K_{l}v^{l+N}, l ∈ ℕ give rise to a bounded vector. As the equalities I′_{l,l+1}K_{l+1} = K_{l}I_{l+N,l+N+1} hold, the boundedness of the vector {u^{l}}_{l∈ℕ} is shown by a similar manner to the proof of the boundedness of the vector L_{A}v as in the proof of Proposition 10.8. Hence we know Sp_{b}^{×}(A, I) = Sp_{b}^{×}(A′, I′).

We will next see that the set Sp_{b}^{×}(A, I) is not empty. We will consider another topology on 𝔅_{I}. The topology is defined from the subbases of open sets of the form:

U_{l}(v, i, ϵ) = {u ∈ 𝔅_{I}||v_{i}^{l} −u_{i}^{l}| < ϵ} for v ∈ 𝔅_{I}, i = 1, …, m(l), ϵ > 0, l ∈ ℕ.

We call it the weak topology on 𝔅_{I}. It is straightforward to see that the state space 𝔖_{I} is compact in the topology. Let σ(L_{A}) be the set of all spectrum of L_{A} as a bounded linear operator on the Banach space 𝔅_{I}. General theory of bounded linear operators tells us that the set σ(L_{A}) is not empty. Let r_{A} be the spectral radius of the operator L_{A} on 𝔅_{I}, that is, r_{A} = sup{|r| : r ∈ σ(L_{A})}.

Proposition 10.12. There exists a state v ∈ 𝔖_{I} such that L_{A}v = r_{A}v. Hence we have r_{A} ∈ Sp_{b}^{×}(A, I).

Our proof is completely similar to the proof of [MWY;Lemma 4.1]. We will give a proof for the sake of completeness.

Proof. Let R_{A}(z) be the resolvent of L_{A} that is defined by R_{A}(z)v = (z − L_{A})^{−1}v for z ∈ ℂ with |z| > r_{A} and v ∈ 𝔅_{I}. For z ∈ ℂ with |z| > r_{A}, we see R_{A}(z)v = ∑_{k=0}^{∞} \frac{1}{z^{k+1}} L_{A}^{k}(v) and

|(L_{A}^{k}(v)_{i}^{l}| ≤ ∑_{j=1}^{m(l+k)} A_{l,l+k}(i, j)|v_{j}^{l+k}|.

As |v_{j}^{l+k}| ≤ |v|_{j}^{l+k}, it follows that |(R_{A}(z)v)_{i}^{l}| ≤ (R_{A}(|z|)|v|)_{i}^{l} and hence

(10.3)  ∥R_{A}(z)v∥_{1} ≤ ∥R_{A}(|z|)|v|∥_{1}.

Since {R_{A}(z)}_{|z|>r_{A}} can not be uniformly bounded in the set L(𝔅_{I}) of all bounded linear operators on 𝔅_{I}, by the inequality (10.3) we may find v_{0} ∈ 𝔖_{I} so that ∥R_{A}(t)v_{0}∥_{1} is unbounded for t ↓ r_{A}. Put

v_{n} = \frac{R_{A}(r_{A} + \frac{1}{n})v_{0}}{∥R_{A}(r_{A} + \frac{1}{n})v_{0}∥} for n = 1, 2, ….

As L_{A} is a positive operator on 𝔅_{I}, the operator R_{A}(t) is also positive so that the vectors v_{n}, n = 1, 2, … are states. Hence there exists a limit point v_{∞} of the sequence {v_{n}} in 𝔖_{I} in the weak topology of 𝔖_{I}. The following identity

(r_{A} − L_{A})v_{n} = −\frac{1}{n}v_{n} + \frac{v_{0}}{∥R_{A}(r_{A} + \frac{1}{n})v_{0}∥}

implies r_{A}v_{∞} = L_{A}v_{∞}. As (A, I) is essential, the vector L_{A}v_{∞} can not be zero. Hence we have r_{A} > 0 and r_{A} ∈ Sp_{b}^{×}(A, I).

The author would like to thank Yasuo Watatani for pointing out an inaccuracy of a proof of the proposition above given in an earlier version of this paper. We finally show that the spectrum are majorizied by topological entropy of the associated subshift. It is well-known that topological entropy h_{top}(Λ) for subshift Λ is given by

h_{top}(Λ) = lim_{k→∞} \frac{1}{k} log ♯|Λ^{k}|

where ♯|Λ^{k}| denotes the cardinality of the set of all admissible words of length k in the subshift Λ (cf.[LM],[Ki]). We say a symbolic matrix system (M, I) to be left resolving if a symbol appearing in M(i, j) can not appear in M(i′, j) for other i′ ≠ i, equivalently, its λ-graph system is left resolving. As in Proposition 3.8, a canonical symbolic matrix system is left resolving.

Proposition 10.13. Let (M, I) be a left resolving symbolic matrix system and (M, I) its associated nonnegative matrix system. For any β ∈ Sp_{b}(M, I), we have the inequalities:

log |β| ≤ log r_{M} ≤ h_{top}(Λ_{(M,I)})

where r_{M} is the spectral radius of the operator L_{M} on 𝔅_{I} and Λ_{(M,I)} is the associated subshift with (M, I).

Proof. The inequality log |β| ≤ log r_{M} is clear. By the previous lemma, take v ∈ 𝔖_{I} such that L_{M}v = r_{M}v. We have for k ∈ ℕ,

r_{M}^{k}v_{i}^{1} = ∑_{j=1}^{m(k+1)} M_{1,k+1}(i, j)v_{j}^{k+1}.

As ∑_{i=1}^{m(1)} v_{i}^{1} = 1, it follows that

r_{M}^{k} ≤ (max_{j} ∑_{i=1}^{m(1)} M_{1,k+1}(i, j)) ∑_{j=1}^{m(k+1)} v_{j}^{k+1} = ∥L_{M}^{k}∥.

We may find j_{0} such that ∥L_{M}^{k}∥ = ∑_{i=1}^{m(1)} M_{1,k+1}(i, j_{0}). Since (M, I) is left resolving, the number ∑_{i=1}^{m(1)} M_{1,k+1}(i, j_{0}) is majorized by the cardinality ♯|Λ_{(M,I)}^{k}| of the set of all admissible words of length k in the subshift Λ_{(M,I)}. Thus we obtain the inequalities

r_{M}^{k} ≤ ∥L_{M}^{k}∥ ≤ ♯|Λ_{(M,I)}^{k}|.

As ∥L_{M}^{k}∥^{\frac{1}{k}} → r_{M} for k → ∞, we have desired inequalities.

For subshift (Λ, σ), let (M, I) be its canonical nonnegative matrix system. We define the nonzero spectrum Sp^{×}(Λ) and the nonzero bounded spectrum Sp_{b}^{×}(Λ) of Λ by the nonzero spectrum and the nonzero bounded spectrum of (M, I) respectively. We have thus proved

Theorem 10.14. Both the sets Sp^{×}(Λ) and Sp_{b}^{×}(Λ) are not empty and topological conjugacy invariants of subshifts. In particular, Sp_{b}^{×}(Λ) is bounded by the topological entropy of the subshift (Λ, σ).

11. Example

We will give an example of the canonical symbolic matrix system, the K-groups and the Bowen-Franks groups for a certain nonsofic subshift, that is called the context free shift in [LM]. Let Σ be the set of symbols {a, b, c}. The nonsofic subshift is defined to be the subshift Z over Σ whose forbidden words are

F_{Z} = {ab^{m}c^{k}a|m ≠ k}

where the word ab^{m}c^{k}a means a \underbrace{b ⋯ b}_{m times} \underbrace{c ⋯ c}_{k times} a (cf.[LM]). In [Ma6], the C^{∗}-

algebra O_{Z} associated with the subshift Z has been studied so that its K-groups has been calculated. By using discussions of the computation of the K-groups, we may write the canonical symbolic matrix system for Z. Let X_{Z} be the corresponding one-sided subshift for Z. Define sequences of subsets of X_{Z} in the following way.

P_{0} = {c^{k}b^{∞}|k ≥ 0} ∪ {b^{k}c^{m}by ∈ X_{Z}|k ≥ 0, m ≥ 1, y ∈ X_{Z}}

and for n, j = 0, 1, …,

E_{j} ={c^{j}ay ∈ X_{Z}|y ∈ X_{Z}},
Q_{n} = ∪_{j>n} E_{j},
F_{j} ={b^{m}c^{m+j}ay ∈ X_{Z}|m ≥ 1, y ∈ X_{Z}},
R_{n} ={b^{m}c^{k}ay ∈ X_{Z}|m ≥ 1, k ≥ 0, m + j ≠ k for j = 0, 1, …, n}.

Lemma 11.1([Ma6;Lemma 4.3]). For each l ∈ ℕ, the space X_{Z} is decomposed into the disjoint union:

X_{Z} = P_{0} ∪_{j=0}^{l−1} E_{j} ∪ Q_{l−1} ∪_{j=0}^{l−1} F_{j} ∪ R_{l−1}.

This decomposition of X_{Z} into 2l + 3-components corresponds to the l-past equivalence classes of X_{Z}.

The canonical symbolic matrix systems M_{l,l+1}, I_{l,l+1} for Z are m(l)(= 2l + 3) × m(l + 1)(= 2l + 5) matrices that are written as follows:

\begin{matrix}M & _{l,l+1} = \\ [ \begin{matrix}b + c & & c & & c & & c & & & & c & & c & & ⋯ & & ⋯ & & c \\ a & a & a \\ & & & b & b \\ & c \\ & & & & & b & b \\ & & & c \\ & & & & & & & & b & & b \\ & & & & & c \\ & & & & & & & & & & & ... & ... \\ & & & & & & & . & . & . \\ & & & & & & & & & & & & & ... & ... \\ . & . & . \\ & & & & & & & & & & & & & & & b & b \\ & & & & & & & & & & & & & c & & c & & c \\ & b & b & & & & & & & & & & & & & & & b & b \end{matrix} ] , \end{matrix}

I_{l,l+1} = [ \begin{matrix}1 \\ & 1 \\ & & 1 \\ & & & 1 \\ & & & & 1 \\ & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & 1 \\ & & & & & & & & 1 \\ & & & & & & & & & 1 \\ & & & & & & & & & & 1 \\ & & & & & & & & & & & . & . & . \\ & & & & & & & & & & & & & & . & . & . \\ & & & & & & & & & & & & & & & & & 1 & & 1 \\ & & & & & & & & & & & & & & & & & & 1 & & 1 \end{matrix} ]

Presentations of Subshifts 337

along the following ordered basis

P_{0}, E_{0}, F_{0}, E_{1}, F_{1}, …, E_{l−1}, F_{l−1}, Q_{l−1}, R_{l−1}

where in the matrices above, blanks denote zeros. The transposed matrices of its nonnegative matrix systems are written as:

A_{l,l+1}^{t} = [ \begin{matrix}2 & 1 \\ & 1 & & 1 & & & & & & & & & & & 1 \\ 1 & 1 & & & & & & & & & & & & & 1 \\ & & 1 & & & 1 \\ 1 & & 1 \\ & & & & 1 & & & 1 \\ 1 & & & & 1 \\ & & & & & & 1 & & & ... \\ 1 & & & & & & 1 \\ & & & & & & & & 1 & & & ... \\ 1 & & & & & & & & 1 \\ & & & & & & & & & & ... & & & 1 \\ ⋮ & & & & & & & & & & ... \\ & & & & & & & & & & & & 1 & 1 \\ ⋮ & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & 1 & 1 \\ 1 & & & & & & & & & & & & & & 1 \end{matrix} ] ,

I_{l,l+1}^{t} = [ \begin{matrix}1 \\ & 1 \\ & & 1 \\ & & & 1 \\ & & & & 1 \\ & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & 1 \\ & & & & & & & & 1 \\ & & & & & & & & & 1 \\ & & & & & & & & & & 1 \\ & & & & & & & & & & & . & . & . \\ & & & & & & & & & & & & & & . & . & . \\ & & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & & 1 \end{matrix} ] .

Hence we have

Documenta Mathematica 4 (1999) 285–340

Proposition 11.2.

K_{0}(Z) = ℤ,  K_{1}(Z) = 0 and BF^{0}(Z) = 0,  BF^{1}(Z) = ℤ.

Since the subshift Z is conjugate to its transpose Z^{T} and by the formula for the Bowen-Franks groups from K for subshifts, we obtain

Proposition 11.3.

BF_{K}^{0}(Z) = ℤ, BF_{K}^{1}(Z) = 0.

Hence these types of the Bowen-Franks groups can not be realized in sofic subshifts because BF^{1}(Z) (resp. BF_{K}^{1}(Z)) is not the torsion-free part of BF^{0}(Z) (resp. BF_{∗}^{0}(Z)). We finally see

Proposition 11.4([Ma6:Theorem 6.9]). The spectral radius of the operator L_{A} is 1 + \sqrt{1 + \sqrt{3}} = 2.65289 ⋯ that is the topological entropy for the subshift Z. Hence the maximum value of Sp_{b}^{×}(A, I) is 1 + \sqrt{1 + \sqrt{3}}.

In [KMW], the K-groups and the dimension groups for β-shifts have been calculated. The K-groups and the Bowen-Franks groups for the Dyck shifts are also calculated in [Ma7].

References

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

[BF] R. Bowen and J. Franks, Homology for zero-dimensional nonwandering sets, Ann. Math. 106 (1977), 73–92.

[Bra] O. Bratteli, Inductive limits of finite-dimensional C^{∗}-algebras, Trans. Amer. Math. Soc. 171 (1972), 195–234.

[Bro] L. G. Brown, The universal coefficient theorem for Ext and quasidiagonality, Operator Algebras and Group Representation, Pitmann Press 17 (1983), 60–64.

[C] J. Cuntz, Simple C^{∗}-algebras generated by isometries, Comm. Math. Phys. 57 (1977), 173–185.

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

[CK] J. Cuntz and W. Krieger, A class of C^{∗}-algebras and topological Markov chains, Inventions Math. 56 (1980), 251–268.

[DGS] M. Denker, C. Grillenberger and K. Sigmund, Ergodic theory on compact spaces, Springer-Verlag, Berlin, Heidelberg and New York, 1976.

[Ef] E. G. Effros, Dimensions and C^{∗}-algebras, AMS-CBMS Reg. Conf. vol 46, Providence, 1981.

[El] G. A. Elliott, On the classification of inductive limits of sequences of semisimple finite-dimensional algebras, J. Algebra 38 (1976), 29– 44.

[EFW] M. Enomoto, M. Fujii and Y. Watatani, Tensor algebras on the sub-Fock space associated with O_{A}, Math. Japon 26 (1981), 171–177.

[Ev] D. E. Evans, The C^{∗}-algebras of topological Markov chains, Tokyo Metropolitan University Lecture Note, 1982.

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

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

[KKS] D. S. Kahn, J. Kaminker and C. Schochet, Generalized homology theories on compact metric spaces, Michigan Math. J. 24 (1977), 203–224.

[KP] J. Kaminker and I. Putnam, K-theoretic duality for shifts of finite type, preprint..

[Ka] G. G. Kasparov, The operator K-functor and extensions of C^{∗}- algebras, Math. USSR. Izvestijia 16 (1981), 513–572.

[KMW] Y. Katayama, K. Matsumoto and Y. Watatani, Simple C^{∗}-algebras arising from β-expansion of real numbers, Ergod.Th. & Dynam. Sys. 18 (1998), 937–962.

[KimR] K. H. Kim and F. W. Roush, Some results on decidability of shift equivalence, J. combinatorics, Info. Sys.Sci. 4 (1979), 123–146.

[KimR2] K. H. Kim and F. W. Roush, Williams conjecture is false for irreducible subshifts, preprint..

[Ki] E. Kirchberg, The classification of purely infinite C^{∗}-algebras using Kasparov’s theory, preprint. 1994.

[Kit] B. P. Kitchens, Symbolic dynamics, Springer-Verlag, Berlin, Heidelberg and New York, 1998.

[Kr] W. Krieger, On dimension functions and topological Markov chains, Invent. Math. 56 (1980), 239–250.

[Kr2] W. Krieger, On dimension for a class of homeomorphism groups, Math. Ann 252 (1980), 87–95.

[Kr3] W. Krieger, On sofic systems I, Israel J. Math. 48 (1984), 305–330.

[Kr4] W. Krieger, On syntactically defined invariant of symbolic dynamics, to appear in Ergod. Th. & Dynam. Sys..

[KPRR] A. Kumjian, D. Pask, I. Raeburn and J. Renault, Graphs, groupoids and Cuntz-Krieger algebras, J. Funct. Anal. 144 (1997), 505–541.

[Le] J. Lee, Equivalences in subshifts, J. Korean Math. Soc. 33 (1996), 685–692.

[LM] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press., 1995.

[Ma] K. Matsumoto, On C^{∗}-algebras associated with subshifts, Internat. J. Math. 8 (1997), 357–374.

[Ma2] K. Matsumoto, K-theory for C^{∗}-algebras associated with subshifts, Math. Scand. 82 (1998), 237–255.

[Ma3] K. Matsumoto, Dimension groups for subshifts and simplicity of the associated C^{∗}-algebras, J. Math. Soc. Japan 51 (1999), 679–698.

[Ma4] K. Matsumoto, Bowen-Franks groups for subshifts and Ext-groups for C^{∗}-algebras, preprint, 1997.

[Ma5] K. Matsumoto, Stabilized C^{∗}-algebras constructed from symbolic dynamical systems, to appear in Ergod. Th. and Dyn. Sys..

[Ma6] K. Matsumoto, A simple C^{∗}-algebra arising from certain subshift, to appear in J. Operator Theory.

[Ma7] K. Matsumoto, K-theoretic invariants and conformal measures on the Dyck shifts, preprint, 1999.

[MWY] K. Matsumoto, Y. Watatani and M. Yoshida, KMS-states for gauge actions on C^{∗}-algebras associated with subshifts, Math. Z. 228 (1998), 489–509.

[N] M. Nasu, Topological conjugacy for sofic shifts, Ergod. Th. & Dynam. Sys. 6 (1986), 265–280.

[N2] M. Nasu, Textile systems for endomorphisms and automorphisms of the shift, Mem. Amer. Math. Soc. 546 (1995).

[Pa] W. Parry, On the β-expansion of real numbers, Acta Math. Acad. Sci. Hung. 11 (1960), 401–416.

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

[Ph] N. C. Phillips, A classification theorem for nuclear purely infinite simple C^{∗}-algebras, preprint. 1995.

[Re] A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hung 8 (1957), 477–493.

[RS] J. Rosenberg and C. Schochet, The Künneth theorem and the universal coefficient theorem for Kasparov’s generalized K-functor, Duke Math. J. 55 (1987), 431–474.

[Tu] S.Tuncel, A dimension, dimension modules, and Markov chains, Proc. London Math. Soc. 46 (1983), 100–116.

[We] B. Weiss, Subshifts of finite type and sofic systems, Monats. Math. 77 (1973), 462–474.

[Wi] R. F. Williams, Classification of subshifts of finite type, Ann. Math. 98 (1973), 120–153, erratum, Ann. Math. 99(1974), 380 − 381.

Kengo Matsumoto

Department of Mathematics Joetsu University of Education Joetsu 943-8512 Japan matsu@juen.ac.jp