POSET BLOCK EQUIVALENCE OF INTEGRAL MATRICES

MIKE BOYLE AND DANRUN HUANG

Abstract. Given square matrices B and B′ with a poset-indexed block structure (for which an ij block is zero unless i ⪯ j), when are there invertible matrices U and V with this required-zero-block structure such that UBV = B′? We give complete invariants for the existence of such an equivalence for matrices over a principal ideal domain R. As one application, when R is a field we classify such matrices up to similarity by matrices respecting the block structure. We also give complete invariants for equivalence under the additional requirement that the diagonal blocks of U and V have determinant 1. The invariants involve an associated diagram (the “K-web”) of R-module homomorphisms. The study is motivated by applications to symbolic dynamics and C^{∗}-algebras.

Contents

1. Introduction 1 2. Definitions 3 3. The K-web 4 4. The results 8 5. Equivalences inducing cokernel isomorphisms 12 6. Realizing isomorphisms of K-webs by equivalences 15 7. Examples 18 8. Special cases 20 9. GL_{P} similarity 23 References 25

1. Introduction

Let R be a principal ideal domain, let P = {1, …, N} be a finite poset, and let 𝔐_{P} denote the set of square matrices B over R with a fixed N × N block structure for which an ij block is zero unless i ⪯ j. (Some infinite matrices are allowed; complete definitions are in Section 2.) Let GL_{P} be the invertible matrices in 𝔐_{P} and let SL_{P} be those invertible matrices for which each diagonal block has determinant 1. We say matrices B, B′ in 𝔐_{P} are GL_{P} equivalent (or just

Date: September 3, 2001. 2000 Mathematics Subject Classification. Primary: 15A21; Secondary: 06A11,06F99, 15A36,

16G20, 37B10, 46L35.

Key words and phrases. block, equivalence, poset, integer, matrix, principal ideal domain, cokernel, flow equivalence, representation, similarity .

The first author gratefully acknowledges support of NSF Grant DMS9706852, and sabbatical support from the University of Maryland and the University of Washington. The second author gratefully acknowledges support of Research Grant 211243 from the St.Cloud State University.

equivalent) if there exist U, V in GL_{P} such that UBV = B′. We say they are SL_{P} equivalent if there exist U, V in SL_{P} such that UBV = B′. In this paper we classify matrices in 𝔐_{P} up to GL_{P} equivalence and up to SL_{P} equivalence.

When P = {1} (i.e. posets are irrelevant), the classification is classical. Matrices B and B′ (of the same size, over R) are GL equivalent iff they have a common Smith normal form, iff the R-modules cok(B) and cok(B′) are isomorphic. For more general P, a Smith form is not enough: modules attached to certain principal block submatrices appear as additional invariants, and also homomorphisms among these.

So, following [H6], we attach to each matrix B in 𝔐_{P} a diagram (the “K-web” of B) of homomorphisms of finitely generated R-modules. These are kernel and cokernel modules of certain principal submatrices of B related to the poset block structure. Given matrices B and B′ in 𝔐_{P}, we characterize the GL_{P} and SL_{P} equivalence of B and B′ by the existence of an appropriate isomorphism of their K-webs. The problem of deciding when such K-web isomorphisms exist is tractable in some cases, but we have no general decision procedure.

While we work over a PID, the existing work we know on block equivalence [KL] and the closely related subject of poset representations (e.g. [NR, Ar, S]) mostly concerns matrices over a field. Our exploitation of the poset blocking structure, our study of block SL equivalence, and our (limited) consideration of infinite matrices also appear to be unusual in the study of block equivalence.

Most results in this paper are extracted or generalized from the algebraic invariants introduced and computed for the case R = ℤ by the second author in [H1]-[H6], especially [H4, H6], in the course of his classification of flow equivalence of shifts of finite type up to flow equivalence (following [PS, BowF, F]), with applications to Cuntz-Krieger algebras (following [C, CK, R]). Nevertheless, we have several reasons for the current paper. We develop the invariants (and the open problems which accompany them) in an accessible and purely matrix-theoretic form. The arguments of [H5, H6] intertwine the algebraic questions with issues of positivity and symbolic dynamics. We sharpen and clarify the classifying algebraic results implicit in [H4, H6]. In particular, given B, B′ in 𝔐_{P} with isomorphic K-webs, [H4, H6] will produce an equivalence between possibly larger matrices ιB, ιB′, where e.g. the additional entries of ιB agree with the identity (see (4.10) for a precise definition of ι). In this paper we give complete results for matrices of a given fixed size, and these require additional structure. There is a treatment of the SFT flow equivalence problem [B] which differs from the earlier approach of the second author [H3, H6] and which reduces the flow equivalence classification to precisely the algebraic problem addressed in this paper. This treatment, which produces additional information, requires the current paper for completion. The results in the current paper on automorphisms induced by self-equivalences are applied in [B] with results of that paper to give new information on the mapping class group of a shift of finite type. The SL_{P}(ℤ) equivalence problem addressed in this paper is an easier cousin of SL_{P}(ℤ[t]) equivalence, which plays a role in the classification of shifts of finite type up to isomorphism which is analogous to the role of SL_{P}(ℤ) equivalence for the classification up to flow equivalence. We want to understand the easier problem clearly. Finally, methods and results introduced in this paper may have application to the classification of nonsimple Cuntz-Krieger algebras, following [H2, H3]. (We use “K” in “K-web” because when R = ℤ, the R-modules in the reduced K-web can be identified with the K-theoretic groups of certain ideals and quotients of an associated nonsimple Cuntz-Krieger C^{∗}-algebra [C][H6].)

We now describe the structure of the paper. In section 2, we give precise definitions and notation for our matrices and block structures. In section 3, we define our diagrams (“K-webs”) of homomorphisms, and the web isomorphisms induced by equivalences. In section 4 we state our classification theorems; in addition to classifying poset block equivalence by isomorphisms of K-webs, we explain which web isomorphisms can be induced by an equivalence. The proofs are carried out in sections 5 and 6. Section 7 gives examples illustrating the invariants. Section 8 explains how the invariants simplify in certain cases. Section 9, in the case R is a field, applies the equivalence results to classify matrices in 𝔐_{P} up to GL_{P} similarity.

We thank Shmuel Friedland and Lawrence Levy for helpful comments.

2. Definitions

For the rest of the paper, we fix a poset (partially ordered set) (P, ⪯), or simply P. We describe the order with a relation ≺ satisfying the following conditions (in which < refers to the usual order on ℕ) for all i, j, k in P:

(2.1)  i ≺ j ⟹ i < j , and
i ≺ j ≺ k ⟹ i ≺ k .

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

We say that a matrix (or a block in a matrix) is square if its rows and columns are indexed by the same set. Let n denote the vector (n_{1}, …, n_{N}), where n_{i} ∈ {1, 2, …, ∞} = ℕ ∪ {∞}, and ∞ denotes countable infinity. We say a square matrix M is “n-blocked” if it splits into blocks M_{ij}, 1 ≤ i, j ≤ N, where M_{ij} denotes the intersection of the ith block row and the jth block column, and has size n_{i} × n_{j}. We also use the notation M{i, j} = M_{ij} and M{i} = M_{ii}. More generally, for s ⊂ P, we let M{s} denote the principal submatrix of M on blocks indexed by s. For example, M{i, j} = M_{ij} and M{i} = M_{ii}.

Let 𝔐_{P}(n, R) denote the set of n-blocked matrices, with entries in R, satisfying the following conditions:

• If M_{ij} is not the zero block, then i ⪯ j.

• For all but finitely many entries of M, M(s, t) = δ_{st}. In the latter condition, we used the Kronecker delta: δ_{st} = 1 if s = t and δ_{st} = 0 otherwise. This condition is vacuous if every n_{i} is finite. The matrices in 𝔐_{P}(n, R) are block upper triangular and in addition certain blocks above the diagonal must be zero. The set 𝔐_{P}(n, R) is closed under addition, and is closed under matrix multiplication because the relation ⪯ is transitive.

For M ∈ 𝔐_{P}(n, R), we define the determinant detM in the obvious way: it equals detF for any finite principal submatrix F such that M(s, t) = δ_{st} except for entries (s, t) of F. Let SL_{P}(n, R) denote the set of matrices in 𝔐_{P}(n, R) with determinant 1 and similarly let GL_{P}(n, R) denote the set of matrices in 𝔐_{P}(n, R) with determinant a unit in R. So, in the trivial case N = 1, there is no block condition and we have SL_{P}(n, R) = SL(n_{1}, R) and GL_{P}(n, R) = GL(n_{1}, R). We will use abbreviated notations such as 𝔐_{P}, GL_{P}, and SL_{P} for 𝔐_{P}(n, R), GL_{P}(n, R), and SL_{P}(n, R); also 𝔐(R) or 𝔐 for 𝔐_{P}(n_{1}, R), GL or GL(R) for GL_{P}(n_{1}, R), and SL or SL(R) for for SL_{P}(n_{1}, R).

We say two matrices B, B′ in 𝔐_{P} are equivalent in 𝔐_{P} (or are GL_{P} equivalent) if there are matrices U, V in GL_{P} such that UBV = B′. We say they are SL_{P} equivalent if in addition U and V are in SL_{P}. (If n_{1} = ∞ and e.g. R = ℤ, then two matrices in GL(n_{1}, R) are SL(R) equivalent if and only if they lie in the same element of the algebraic K-theory group K_{1}(R) [Ros].)

Remark 2.2. Note, the semigroups SL_{P}(n, R) and GL_{P}(n, R) are actually groups. For example, given B ∈ SL_{P}(n, R), by assumption the diagonal blocks of B are invertible, so we may find a block diagonal matrix D in SL_{P}(n, R) such that every diagonal block of DB is an identity matrix. Then we may multiply by elementary matrices E_{i} in SL_{P}(n, R) to clear out any remaining nonzero offdiagonal entries. So, if E is the product of these E_{i} in the appropriate order, then EDB = I. But ED ∈ SL_{P}(n, R) because SL_{P}(n, R) is a semigroup.

3. The K-web

We adopt the notations and definitions of the previous section.

To any element B of 𝔐_{P} we will attach a diagram of homomorphisms of Rmodules (the “K-web” of B), which will be an invariant of GL_{P}-equivalence. For SL_{P}-equivalence there will be a finer invariant. Then we will define the isomorphism of K-webs induced by an equivalence. The invariant is built up from exact sequences derived from two by two block triangular matrices [H5], and we discuss these next.

2 × 2 block triangular matrices.

Let S = ( \begin{matrix}R & X \\ 0 & D \end{matrix}) be a 2 × 2 block triangular matrix. It is routine to verify that we have well defined R-module homomorphisms of finitely generated R-modules,

kerD → cokR  cokR → cokS  cokS → cokD
v ↦ [Xv]  [v] ↦ [( \begin{matrix}v \\ 0 \end{matrix} )]  [( \begin{matrix}v \\ w \end{matrix})] ↦ [w]

and with these homomorphisms, the following sequence is exact:

(3.1) kerD → cokR → cokS → cokD → 0 .

Now suppose

S′ = (\begin{matrix}R′ & X′ \\ 0 & D′ \end{matrix}) ,  U = (\begin{matrix}U_{1} & U_{2} \\ 0 & U_{4} \end{matrix}) ,  V = (\begin{matrix}V_{1} & V_{2} \\ 0 & V_{4} \end{matrix}) ,

where S′, U and V are presented with the same 2 × 2 block structure as S, and also (U, V) is an equivalence from S to S′, that is USV = S′ with U and V invertible.

Proposition 3.2. The equivalence (U,V) above induces an isomorphism of exact sequences

kerD ⟶ cokR ⟶ cokS ⟶ cokD ⟶ 0
a↓  ^{b}↓  ^{c}↓  ^{d}↓
kerD′ ⟶ cokR′ ⟶ cokS′ ⟶ cokD′ ⟶ 0

by the rules

a: x ↦ (V_{4})^{−1}x ,  b: [x] ↦ [U_{1}x] ,  c: [x] ↦ [Ux] ,  d: [x] ↦ [U_{4}x] .

The verification of the proposition is an exercise [H5]. In the proposition, “isomorphism” means that each of the maps a, b, c, d is an R-module isomorphism and the diagram commutes.

Because R is a PID, a finitely generated R-module is the direct sum of a free module F and a torsion module T. An endomorphism φ: F ⊕ T → F ⊕ T has the form (f, t) ↦ (φ_{1}(f), φ_{2}(f, t)). Of course, the endomorphism φ_{1} : F → F can be represented as multiplying vectors in the free module F by some matrix Φ_{1} over R, and det(Φ_{1}) is independent of the choice of basis for the vector representation. We define det(φ_{1}) = det(Φ_{1}) and det(φ) = det(φ_{1}). In the case F = 0 we adopt the notational convention that det(φ) = det(φ_{1}) = 1.

Proposition 3.3. Suppose in Proposition 3.2 that the following additional conditions hold: D = D′ (so det(a) and det(d) are defined), and det(U_{4}) = det(V_{4}) = 1. Then det(a) = det(d).

Proof. KerD and the free part of cokD are R-modules of equal rank, hence the claim is true by our notational convention if D is nonsingular. The claim is also easily checked if D = 0. So suppose det(D) = 0 and D ≠ 0.

Consider first the special case that D has the block form D = (\begin{matrix}0 & 0 \\ 0 & W \end{matrix} ) with W

nonsingular. The equivalence USV = S′ implies U_{4}DV_{4} = D. Letting U_{4} = E and V_{4}^{−1} = F, we write the equation U_{4}D = DV_{4}^{−1} in the block form

(\begin{matrix}E_{11} & E_{12} \\ E_{21} & E_{22} \end{matrix}) (\begin{matrix}0 & 0 \\ 0 & W \end{matrix} ) = (\begin{matrix}0 & 0 \\ 0 & W \end{matrix} ) (\begin{matrix}F_{11} & F_{12} \\ F_{21} & F_{22} \end{matrix})

which gives

(\begin{matrix}0 & E_{12}W \\ 0 & E_{22}W \end{matrix} ) = (\begin{matrix}0 & 0 \\ W F_{21} & W F_{22} \end{matrix}) .

The nonsingularity of W implies E_{12} = 0 and F_{21} = 0, so we have

(\begin{matrix}E_{11} & 0 \\ E_{21} & E_{22} \end{matrix}) (\begin{matrix}0 & 0 \\ 0 & W \end{matrix} ) = (\begin{matrix}0 & 0 \\ 0 & W \end{matrix} ) (\begin{matrix}F_{11} & F_{12} \\ 0 & F_{22} \end{matrix}) .

It follows from the definition of a and d that det(d) = det(E_{11}) and det(a) = det(F_{11}). Now E_{22}W = W F_{22} implies det(E_{22}) = det(F_{22}) and then det(E_{11})det(E_{22}) = 1 and det(F_{11})det(F_{22}) = 1 imply det(E_{11}) = det(F_{11}). This proves the proposition in the special case.

In the general case, it is a consequence of the Smith normal form (reviewed in

Section 4) that there exist P, Q in GL(R) such that P DQ has the form (\begin{matrix}0 & 0 \\ 0 & W \end{matrix} )

with W nonsingular. The equivalence (U_{4}, V_{4}): D → U_{4}DV_{4} = D is a composition of equivalences

D ⟶^{(P,Q)} P DQ ⟶^{(P U_{4}P^{−1},Q^{−1}V_{4}Q)} P DQ ⟶^{(P^{−1},Q^{−1})} D

and we have the homomorphisms a: kerD → kerD and d: cokD → cokD as corresponding compositions

kerD ⟶^{a_{1}} kerP DQ ⟶^{a_{2}} kerP DQ ⟶^{(a_{1})^{−1}} kerD ,

cokD ⟶^{d_{1}} cokP DQ ⟶^{d_{2}} cokP DQ ⟶^{(d_{1})^{−1}} cokD .

Now det(a) = det(a_{1})det(a_{2})det((a_{1})^{−1}) = det(a_{2}), likewise det(d) = det(d_{2}), and det(a_{2}) = det(d_{2}) by the special case considered earlier. Therefore det(a) = det(d).

□

The full K-web of B.

We say a subset s of P is convex if s is nonempty and for all k in P,

{i, j} ⊂ s and i ≺ k ≺ j ⟹ k ∈ s .

We say a subset d of P is a difference set if d is convex and there are convex sets r, s in P, r ⊆ s, such that d = s \ r and

i ∈ r and j ∈ d ⟹ j ⊀ i .

Given such r, s, and d, let B{s} = S, B{r} = R, and B{d} = D. Then S has the block form S = ( \begin{matrix}R & X \\ 0 & D \end{matrix}) and we have an associated exact sequence

(3.4) kerD → cokR → cokS → cokD → 0

as discussed above for (3.1).

The full K-web of B is a certain family of R-modules and R-module homomorphisms. To each convex subset c of P, we attach the module C_{c}(B) := cokB{c}. To each difference set d in P, we attach the module K_{d}(B) := KerB{d}. The modules C_{c}, K_{d} are the modules of the full K-web. (More formally, we have a family of modules indexed by the disjoint union of C and D, where C is the collection of convex subsets of P and D is the collection of difference sets in P.) The homomorphisms (or strands) of the full K-web are the homomorphisms arising from one of the exact sequences (3.4). (More formally, each triple (r, s, d) giving rise to one of the sequences (3.4), together with one of the pairs (d, r), (r, s), (s, d), indexes a corresponding strand of the full K-web.) We visualize the web as a directed graph.

The (reduced) K-web of B.

The full K-web of B is a powerful (often complete) invariant of GL_{P} equivalence. We will focus on a more managable invariant, the reduced K-web of B, which turns out to be equally strong (Corollary 4.12). The reduced K-web is a certain subfamily of the modules and strands comprising the full K-web. To describe these, we use a little more notation. For i ∈ P, let r_{i} = {j: j ≺ i} and s_{i} = {j: j ⪯ i}; so, if r_{i} is nonempty then {i} = s_{i} \r_{i} is a difference set. The index set for the modules C_{c}(B) retained in the reduced K-web is the set of c such that for some i ∈ P, c = {i} or c = s_{i} or c = r_{i} ≠ ∅. The index set for the modules K_{d}(B) retained in the reduced K-web is the set of d = {i} such that r_{i} ≠ ∅.

Given r_{i} ≠ ∅, let B{s_{i}} = S_{i}, B{r_{i}} = R_{i}, and B{i} = D_{i} (D for difference set or diagonal block), and write S_{i} in the block form

S_{i} = (\begin{matrix}R_{i} & X_{i} \\ 0 & D_{i} \end{matrix}) .

If i ∈ P and r_{i} ≠ ∅, then the ith level of the reduced K-web is composed of the modules and strands in the exact sequence

(3.5) kerD_{i} → cokR_{i} → cokS_{i} → cokD_{i} → 0

(representing K_{{i}} → C_{r_{i}} → C_{s_{i}} → C_{{i}} → 0). If i has no predecessor, then the ith level is simply the module cokS_{i}, with no maps. Notice that different levels can overlap, since it is possible that r_{i} = r_{j} or r_{i} = s_{j} with j ≺ i. The set of strands of the reduced K-web is the union of the strands on all the levels, 1 ≤ i ≤ N, together with the strands cokS_{j} → cokR_{i} satisfying the following two conditions:

• j is an immediate predecessor of i (this means j ≺ i and there is no k such that j ≺ k ≺ i), and

• j is not the unique immediate predecessor of i. Note, any such strand cokS_{j} → cokR_{i} does occur in the full K-web, in the exact sequence associated in (3.4) to the triple (r, s, d) = (s_{j}, r_{i}, r_{i} \ s_{j}).

From this point on, unless we refer explicitly to a full K-web, by K-web we will mean the reduced K-web. We write K(B) for the K-web of B. K(B) depends on P and is defined for B ∈ 𝔐_{P}.

Example 3.6. The diagram below gives the K-web for the poset P = {1, 2, 3, 4} for which the order ⪯ agrees with ≤ except that 2 ⪯̸ 3. For this P and B ∈ 𝔐_{P}, there is no R_{1} (since 1 has no predecessor), R_{2} = R_{3} = B{1}, R_{4} = B{1, 2, 3}; S_{1} = B{1}, S_{2} = B{1, 2}, S_{3} = B{1, 3}, S_{4} = B; and D_{i} = B{i}, i = 1, 2, 3, 4. This same P is used in Example 7.2, which has some further numerical calculations.

[figure: kerD_{2}; cokR_{2}; kerD_{3}]
[figure]
[figure: cokD_{2}; cokS_{2}; cokS_{3}; cokD_{3}]
[figure]
[figure: ker D_{4}; cokR_{4}; cokS_{4}; cokD_{4}]

Induced isomorphism and SL isomorphism of K-webs.

Given P, the definition of isomorphism of (full or reduced) K-webs is obvious: an isomorphism is a collection of isomorphisms of all correspondingly indexed modules, which intertwine all the corresponding strands. Suppose B, B′ are in 𝔐_{P} and UBV = B′, with U, V in GL_{P}. When s is a convex set in P, one easily checks that there is an induced equivalence

U{s}B{s}V {s} = B′{s} .

Therefore, given a convex set d which is the difference set of convex sets, d = s \ r, the equivalence UBV = B′ induces a 2 × 2 block equivalence

(\begin{matrix}U\{r\} & U\{r, d\} \\ 0 & U\{d\} \end{matrix}) (\begin{matrix}B\{r\} & B\{r, d\} \\ 0 & B\{d\} \end{matrix}) (\begin{matrix}V \{r\} & V \{r, d\} \\ 0 & V \{d\} \end{matrix}) = (\begin{matrix}B′\{r\} & B′\{r, d\} \\ 0 & B′\{d\} \end{matrix}) .

Then we define the induced isomorphism of K-webs (full or reduced) to be given by the isomorphisms

cokB{s} → cokB′{s}
[x] ↦ [U{s}x]

(for every convex set s) and

kerB{d} → kerB′{d}
y ↦ (V {d})^{−1}y

(for every difference set d).

It follows from the discussion of the 2 × 2 block case that these are indeed Rmodule isomorphisms, and that adding these isomorphisms to the disjoint union of the full K-webs of B and B′ produces a commuting diagram as required. We call the collection of these induced isomorphisms the full K-web isomorphism induced by the equivalence (U, V). The K-web isomorphism κ_{(U,V)} induced by (U, V) is simply the restriction of the full K-web isomorphism to the modules of the reduced K-web. The restriction of a K-web isomorphism κ to level i is denoted κ_{i}. When i has a predecessor, we use notation κ_{i} = (a_{i}, b_{i}, c_{i}, d_{i}):

kerD_{i} ⟶ cokR_{i} ⟶ cokS_{i} ⟶ cokD_{i} ⟶ 0
a_{i}↓  ^{b_{i}}↓  ^{c_{i}}↓  ^{d_{i}}↓
kerD′_{i} ⟶ cokR′_{i} ⟶ cokS′_{i} ⟶ cokD′_{i} ⟶ 0

(3.7)

If i has no predecessor, we may still use the names c_{i} and d_{i}, which make sense and are equal in this case.

Let Imm(i) denote the set of immediate predecessors of i in P. We explain now why we include in the reduced K-web the strands cok(S_{j}) → cokR_{i}, j ∈ Imm(i), when |Imm(i)| > 1: with the inclusion of these strands, it holds for a K-web isomorphism κ that when |Imm(i)| > 1, the map b_{i}: cokR_{i} → cokR′_{i} is determined by the maps c_{j}: cokS_{j} → cokS′_{j}, j ∈ Imm(i). A specific case of this is the next proposition, whose easy proof is left to the reader. This proposition is the precise consequence of the additional strands which will be used in our construction of GL_{P} equivalences from K-web isomorphisms.

Proposition 3.8. Using the notation of (3.7), suppose κ is a K-web isomorphism, i ∈ P, i has a predecessor, c_{j} = Id for every j in Imm(i), and R_{i} = R′_{i}. Then b_{i} = Id.

Continuing with the notation of (3.7), note that the isomorphism d_{i} is uniquely determined by (b_{i}, c_{i}). In the special case that each D_{i} = D′_{i} and U{i} and V {i} have determinant 1, we get by Proposition 3.3 the additional condition that det(a_{i}) = det(d_{i}).

Definition 3.9. Suppose that B, B′ are matrices in 𝔐_{P} such that (in the notation above) D_{i} = D′_{i}, 1 ≤ i ≤ N. Then an isomorphism of their full or reduced K-webs is an SL-isomorphism if det(a_{i}) = det(d_{i}) whenever {i} is a difference set.

We can now state the following theorem.

Theorem 3.10. Suppose B and B′ are matrices in 𝔐_{P} and (U, V): B → B′ is a GL_{P} equivalence. Then this equivalence induces a full K-web isomorphism giving by restriction the reduced K-web isomorphism κ_{(U,V)} : K(B) → K(B′). If (U, V) is an SL_{P} equivalence and B{i} = B′{i} for all i in P, then these are SL K-web isomorphisms.

Example 7.2 gives two matrices whose K-webs are isomorphic but are not SLisomorphic. When we are only concerned with GL equivalence, we can ignore the strands cokS_{i} → cokD_{i} in the K-web. These strands are included only for the expression of the extra constraint involved in SL equivalence.

4. The results

Suppose C is an m × n matrix over the PID R, with rows indexed by {1, …, m} and columns indexed by {1, …, n}. It is a classical theorem [AW, Ne] that there exist U ∈ GL(m, R) and V ∈ GL(n, R) such that the matrix D = UCV satisfies the following conditions:

• D(i, j) = 0 if i ≠ j,

• If D(i, i) ≠ 0 and i < min{m, n}, then D(i, i) divides D(i + 1, i + 1),
• If D(i, i) = 0 and i < min{m, n}, then D(i + 1, i + 1) = 0.

The matrix D is called the Smith normal form of C. The entries of D are unique up to multiplication by units in R. The Smith normal form can also be achieved by an SL(R) equivalence, simply by postmultiplication of the GL(R) equivalence by suitable invertible diagonal matrices. When R is a Euclidean domain (e.g. R = ℤ), there is an algorithm for producing an equivalence to Smith normal form.

Now suppose B and B′ in 𝔐(R) have the same size. The existence of the Smith normal form has the following easy consequences.

(1) There exist GL(R) matrices U, V such that UBV = B′ if and only if the R-modules cokB and cokB′ are isomorphic.

(2) There exist SL(R) matrices U, V such that UBV = B′ if and only if the

R-modules cokB and cokB′ are isomorphic and detB = detB′. We record the following corollary of these facts.

Proposition 4.1. Suppose B and B′ are in 𝔐_{P}(R).

(1) There exist block diagonal matrices U, V in GL_{P}(R) such that (UBV){i} = B′{i} for all i ∈ P if and only if for all i ∈ P, the R-modules cokB_{i} and cokB′_{i} are isomorphic.

(2) There exist block diagonal matrices U, V in SL_{P}(R) such that (UB′V){i} = B{i} for all i ∈ P if and only if for all i in P, detB_{i} = detB′_{i} and the modules cokB_{i} and cokB′_{i} are isomorphic.

Suppose B and B′ are in 𝔐_{P}. Then a necessary condition for GL_{P}(SL_{P}) equivalence of B and B′ is the GL(SL) equivalence of the diagonal blocks B{i} and B′{i} for all i in P. Whether this necessary condition holds may be determined by the computation of some cokernel modules and (in the SL case) determinants, as explained before Proposition 4.1. Given this necessary condition, by Proposition 4.1 we have that B′ is GL_{P}(SL_{P}) equivalent to a matrix B′′ such that B{i} = B′′{i} for all i in P. Consequently, to address problems involving GL_{P} or SL_{P} equivalence, we can reduce to the case where B and B′ have corresponding diagonal blocks equal. For simplicity, we will make this equal-diagonal-blocks assumption in the statement of our main results.

Suppose B ∈ 𝔐(R). A self-equivalence of B is a pair (U, V) of GL(R) matrices such that UBV = B. An SL self-equivalence is a self-equivalence (U, V) with det(U) = det(V) = 1. The automorphism Ũ of the R-module cokB induced by (U, V) is given by the rule [x] ↦ [Ux], where [x] denotes the coset, x + Image(B). Given an automorphism φ of cokB, it is easy to find a matrix M over R such that φ is defined by the rule [x] ↦ [Mx], but it is not always the case that φ can be induced by a self-equivalence. For example, if B = [5] and R = ℤ, then cokB = ℤ/5, and the automorphism [x] ↦ [2x] cannot be induced by a self equivalence of B.

Definition 4.2. Supose B ∈ 𝔐(R). An automorphism φ of cok(B) is GLallowable (or just allowable) if there exists a GL self-equivalence of B which induces φ. An automorphism φ of cok(B) is SL-allowable if there exists an SL selfequivalence of B which induces φ.

Definition 4.3. For a matrix B with entries in R, gcdB denotes the greatest common divisor of the entries of B.

It is easy to see that for any B ∈ 𝔐(R) and automorphism φ of cokB, there exists a matrix M over R such that φ: [x] ↦ [Mx], for all x.

Theorem 4.4. Suppose B ∈ 𝔐(R) and δ = gcdB. Suppose φ is an automorphism of cokB and M is any matrix over R defining φ, that is, φ: [x] ↦ [Mx] for all x.

Then φ is SL-allowable iff det(M) ≡ 1 (mod δ), and φ is GL-allowable iff det(M) ≡ u (mod δ) for some unit u in R.

Note, given B and φ above, det(M) (mod δ) is independent of the choice of matrix M. Also note, if gcdB=1 in Theorem 4.4, then every automorphism of cokB is SL-allowable. If gcdB = 0 (i.e., B = 0), then φ is SL-allowable iff det(M) = 1, and φ is GL-allowable iff det(M) is a unit in R. Section 5 is devoted to the proof of Theorem 4.4.

In Example 7.1, we will exhibit B and B′ in 𝔐_{P} which have equal diagonal blocks, such that B and B′ are not GL_{P} equivalent, although there exists an SL Kweb isomorphism K(B) → K(B′) (for which one of the maps d_{i} is not allowable). So, while the isomorphism class of the K-web is an invariant of GL_{P} equivalence, it is in general not a complete invariant.

We can now state our main results.

Theorem 4.5. Suppose B and B′ are matrices in 𝔐_{P} with corresponding diagonal blocks equal, and κ: K(B) → K(B′) is a K-web isomorphism. Then there exists a GL_{P} equivalence (U, V): B → B′ such that κ_{(U,V)} = κ if and only if each of the automorphisms d_{i}: cokB{i} → cokB′{i} defined by κ is GL-allowable. There exists an SL_{P} equivalence (U, V): B → B′ such that κ_{(U,V)} = κ if and only if κ is an SL K-web isomorphism and each of the automorphisms d_{i}: cokB{i} → cokB′{i} defined by κ is SL-allowable.

Section 6 is devoted to the proof of Theorem 4.5. The combination of Theorems 3.10 and 4.5 immediately gives the following classification theorem.

Theorem 4.6. Suppose B and B′ are matrices in 𝔐_{P} with corresponding diagonal blocks equal. Then B and B′ are GL_{P} equivalent if and only if there is a K-web isomorphism κ: K(B) → K(B′) such that each of the automorphisms d_{i}: cokB{i} → cokB′{i} defined by κ is GL-allowable. The matrices B and B′ are SL_{P} equivalent if and only if there is an SL K-web isomorphism κ: K(B) → K(B′) such that each of the automorphisms d_{i}: cokB{i} → cokB′{i} defined by κ is SLallowable.

Among various special cases, we single out a few in the following easy corollaries of the preceding results.

Corollary 4.7. Suppose B and B′ are matrices in 𝔐_{P} such that gcdB{i} = 1 = gcdB′{i} for all i in P. Then for any K-web isomorphism κ: K(B) → K(B′), there exists a GL_{P} equivalence (U, V): B → B′ such that κ_{(U,V)} = κ. The matrices B and B′ are GL_{P} equivalent if and only if the K-webs K(B) and K(B′) are isomorphic.

Corollary 4.8. Suppose B and B′ are matrices in 𝔐_{P} such that B{i} = B′{i} with gcdB{i} = 1, for all i in P. Then for any SL K-web isomorphism κ: K(B) → K(B′), there exists a SL_{P} equivalence (U, V): B → B′ such that κ_{(U,V)} = κ. The matrices B and B′ are SL_{P} equivalent if and only if the K-webs K(B) and K(B′) are SL isomorphic.

The next corollary is included because it is precisely the result appealed to in [B] for the classification of shifts of finite type up to flow equivalence.

Corollary 4.9. Suppose B and B′ are matrices in 𝔐_{P} such that for each i ∈ P, B{i} = B′{i}, and either gcdB{i} = 1 or B{i} is the 1 × 1 matrix (0). Then an SL K-web isomorphism κ: K(B) → K(B′), is induced by an SL_{P} equivalence iff the automorphism d_{i}: cokB{i} → cokB′{i} defined by κ is the identity whenever B{i} = (0). The matrices B and B′ are SL_{P} equivalent if and only if such an SL K-web isomorphism exists.

The classification results have a stabilization corollary, which is applied in [B]. We give notation for that statement now.

Definition 4.10. Given n ≤ r, we have a natural embedding ι_{n,r} = ι: 𝔐_{P}(n, ℤ) → 𝔐_{P}(r, ℤ) as follows. For each ij, the map ι embeds the ij block of M as the upper left corner of the ij block of ιM. Outside this embedded upper left corner, the ij block of ιM is zero if i ≠ j and agrees with the identity matrix if i = j.

Make the following observation: the map ι induces an isomorphism of K-webs and respects the additional SL invariants. The stabilization corollary below follows from this observation and the classification results.

Corollary 4.11 (Stabilization). Suppose B and B′ are matrices in 𝔐_{P}(n, R). Suppose n ≤ r, and let ι be the embedding of 𝔐_{P}(n, R) into 𝔐_{P}(r, R) given above. Suppose for all i that n_{i} < r_{i} implies gcd B{i} = 1.

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

Corollary 4.12. Suppose B and B′ are matrices in 𝔐_{P}(n, R). If there is an isomorphism of their reduced K-webs, then there is an isomorphism of their full K-webs. If they have equal diagonal blocks and there is an SL isomorphism of their reduced K-webs, then there is an SL isomorphism of their full K-webs.

Proof. If necessary after applying an embedding ι of B and B′, we may assume that each diagonal block in B and B′ has gcd=1. Then the result follows from the classification theorems and the induction of a full K-web isomorphism by an equivalence. □

Discussion. How good are the K-web invariants? The K-webs are computable, and the invariants can be used to give subtle examples of nonequivalence (e.g., Example 7.2). But, although there are some tractable cases (see Section 8), even over ℤ or ℚ we have no general algorithm for deciding isomorphism or SL isomorphism of K-webs, we have no canonical forms, and we have no characterization of the diagrams which arise as K-webs. So our theorems are by no means the end to the problem of understanding block equivalence of matrices in 𝔐_{P}.

The classification of K-webs involves known hard problems (already familiar in the block equivalence problem [KL]). In a given poset, it could be the case that j has several immediate predecessors i, so that there are strands in the K-web from several modules cokS_{i} into cokR_{j}. The images in cokR_{j} can overlap. Therefore determining the isomorphism of K-webs involves the subproblem of classifying how these images can overlap. When R is a field, this is the topic of classifying representations of partially ordered sets, initiated by Nazarova and Roiter [NR] and studied subsequently in dozens of papers (some of which are reviewed in [Ar, S]). For more general rings (e.g. ℤ), this is the topic of classifying R-representations of posets [Ar, Pl], which seems to be less developed.

The problem of classifying poset representations has as a subproblem the following problem: classify n-tuples of matrices over R up to simultaneous similarity. For R = ℂ, a classification scheme was given by Friedland [Fri]. For R = ℤ, see [Fa], and for decision procedures (for n = 1) [G, GS].

5. Equivalences inducing cokernel isomorphisms

Posets are not involved in this section. The purpose of this section is the proof of Theorem 4.4.

Proof of Theorem 4.4. The case B = 0 is clear. Without loss of generality, we assume that B ≠ 0, and that B is an η × η matrix with 2 ≤ η < ∞. The proof proceeds in several parts.

Reduction of B to a Smith form. First we remark that an equivalence (W, X): B′ → B (i.e. B = W B′X) induces

(1) an isomorphism W̃: cokB′ → cokB given by the rule [x] ↦ [W x];

(2) a bijection of self-equivalences, by the following correspondence: if (U, V) is a self-equivalence of B′ (UB′V = B′), then (W UW^{−1}, X^{−1}V X) is a self-equivalence of B; and

(3) a bijection from Aut(cokB′) to Aut(cokB) given by the rule α ↦ W̃αW̃^{−1}.

Comparing (2) and (3), we see that if there is any B′ SL equivalent to B such that every SL-allowable automorphism of B′ is induced by an SL self-equivalence of B′, then every SL-allowable automorphism of cokB is induced by an SL self equivalence of B. Also, a matrix M defines φ iff W MW^{−1} defines W̃φW̃^{−1}, and det(M) = det(W MW^{−1}). Therefore by appeal to the Smith normal form, we may assume that B is diagonal, with diagonal entries b_{1}, …, b_{η} with the following properties:

(1) b_{1} = δ.
(2) b_{i}|b_{i+1} if b_{i} ≠ 0, 1 ≤ i < η,
(3) b_{i+1} = 0 if b_{i} = 0, 1 ≤ i < η,
(4) b_{i} = b_{i+1} if b_{i+1}/b_{i} is a unit, 2 ≤ i < η.

In the last property above, we exclude the case i = 1 because after achieving the Smith form as UBV with U and V invertible, we multiply U by diag((detU^{−1}, 1, …, 1)) and V by diag((detV^{−1}, 1, …, 1)) to achieve an SL equivalence. To write b_{1} = δ, if necessary we revise our choice of δ (multiplying it by a unit).

Let s_{1}, …, s_{k} denote the distinct elements of {b_{2}, …, b_{η}}, let s_{0} = δ, and write B in the block diagonal form

(5.1)  B = (\begin{matrix}B_{00} \\ & s_{1}I \\ & & s_{2}I \\ & & & . & . & . \\ & & & & & & s_{k}I \end{matrix}) = (\begin{matrix}B_{00} & 0 \\ 0 & B_{∗} \end{matrix})

in which (1) B_{00} is the 1 × 1 matrix (s_{0}) = (δ).

(2) s_{i} divides s_{i+1} if 1 ≤ i < k,

(3) of the s_{i}, only s_{k} might be zero, and

(4) each I is the identity matrix of appropriate size.

Matrix presentation for α in Aut(cokB).

We write the initially given matrix M with the blocking of B in (5.1),

M = (\begin{matrix}M_{00} & … & M_{0k} \\ ⋮ & ... & ⋮ \\ M_{k0} & … & M_{kk} \end{matrix}) ,

where e.g. M_{00} is a 1 × 1 matrix. The choice of M is not uniquely determined by α; a matrix M′ of the same size will also induce α if and only if

M_{ij} ≡ M′_{ij} (mod s_{i}) , 0 ≤ i, j ≤ k .

Because the matrix M induces the cokernel automorphism, it satisfies the following divisibility properties:

(5.2) For i > j, every entry of M_{ij} is a multiple of s_{i}/s_{j}; and,

if s_{k} = 0, then M_{kk} ∈ GL(R).

Strategy of the proof. Suppose UBV = B and U is blocked as follows into submatrices U_{ij}, 0 ≤ i, j ≤ k, to match the blocking of B in (5.1):

U = (\begin{matrix}U_{00} & U_{01} & … & U_{0k} \\ U_{10} & U_{11} & … & U_{1k} \\ ⋮ & ⋮ & ... & ⋮ \\ U_{k0} & U_{k1} & … & U_{kk} \end{matrix}) .

Let Ũ denote the automorphism of cokB induced by U. If there are self-equivalences (U_{1}, V_{1}) and (U_{2}, V_{2}) of B such that the matrix U_{1}MU_{2} induces the identity map on cokB, then Ũ_{1}φŨ_{2} = Id, so φ = (Ũ_{1})^{−1}(Ũ_{2})^{−1}. So, our strategy will be to multiply M from the left and right by matrices U arising from self-equivalences until we have produced a matrix which acts like the identity.

The supply of induced automorphisms. We will assemble four types of matrix U which occur in SL self-equivalences (U, V) of B. In each case, U = Id except perhaps on a principal submatrix, and we describe this principal submatrix. Here e.g. U{j} is the 1 × 1 matrix whose entry is U(j, j), and U{{i, j}} is the 2 × 2 principal submatrix of U on indices i, j, where 1 ≤ i < j ≤ η (the matrices U,B are η × η). We let U^{(j)} denote the principal submatrix of U on the indices t for which t ≥ 2 and b_{t} = s_{j}, and suppose the block s_{j}I in B is m_{j} × m_{j}. Here are the four types.

(1) U^{(j)} = C, for any C ∈ GL(m_{j}, R), 1 ≤ j ≤ k.

(2) U\{\{i, j\}\} = ( \begin{matrix}1 & x \\ 0 & 1 \end{matrix} ) , if x ∈ R.

(3) U\{\{i, j\}\} = ( \begin{matrix}1 & 0 \\ x & 1 \end{matrix} ) , if b_{j} ≠ 0 and x is a multiple of b_{j}/b_{i} in R.

(4) U\{\{1, j\}\} = ( \begin{matrix}a & b \\ b_{j} & d \end{matrix} ) , if gcd(b_{j}, d) = 1, and ad − bb_{j} = 1.

Types (1)−(3) are realized in SL self-equivalences (U, V) of B as follows. For Type (1), we set U(1, 1) = (detC)^{−1} and V (1, 1) = detC. Otherwise, U = V = I outside the indicated principal submatrix. Here for these cases are the descriptions for V:

(1) V^{(j)} = C^{−1}.

(2) V \{\{i, j\}\} = ( \begin{matrix}1 & y \\ 0 & 1 \end{matrix} ) , with y = −xb_{j}/b_{i}.

(3) V \{\{i, j\}\} = ( \begin{matrix}1 & 0 \\ y & 1 \end{matrix} ) , with y = −xb_{i}/b_{j}.

For U of type (4), note that δ|b_{j}. So we may define V achieving the self equivalence (U, V) by setting V = Id except for

V \{\{1, j\}\} = (\begin{matrix}d & −bb_{j}δ^{−1} \\ −δ & a \end{matrix}) .

It is an exercise to verify that UBV = B in each case.

The reduction step. Given i with 2 ≤ i ≤ η, consider the following condition:

M(i, j) ≡ δ_{ij} (mod b_{i}), 1 ≤ j ≤ η . (5.3)

Suppose 2 ≤ m < η, and (5.3) holds if 2 ≤ i < m, and (5.3) fails if i = m. We will multiply the matrix M from the left and/or right by matrices of the forms U above to produce a new matrix M for which (5.3) holds if 2 ≤ i ≤ m. Clearly by induction this will establish the reduction of the theorem to the case that (5.3) holds for 2 ≤ i ≤ m. Let μ = M(m, m).

CASE 1: b_{m} ≠ 0 and gcd(μ, b_{m}) = 1.

Pick γ in R such that γμ ≡ 1 (mod b_{m}), and multiply M from the left by a matrix of type (4) (setting j = m and d = γ), to produce a new matrix M in which M(m, m) ≡ 1 (mod b_{m}). Multiplying from the right by matrices U of type (2), we may add multiples of column m to columns i > m until M(m, i) ≡ 0 (mod b_{m}) for i > m. Because M(m, j) ≡ 0 (mod b_{m}/b_{j}) for j < m, by multiplying from the right by matrices U of type (3), we may add multiplies of column m to columns i < m until M(m, j) ≡ 0 (mod b_{m}) for j < m. Now M satisfies (5.3) for i = m, and all of our operations respected (5.3) holding when 2 ≤ i < m.

CASE 2: b_{m} ≠ 0 and gcd(μ, b_{m}) ≠ 1.

(This can happen: for example, let R = ℤ, B = diag(1, 6, 12), and M = ( \begin{matrix}3 & 4 \\ 4 & 9 \end{matrix} ).) Define d = gcd({b_{m}δ^{−1}M(1, m)} ∪ {M(j, m): m + 1 ≤ j ≤ η}). We first claim

that gcd(b_{m}, μ, d) = 1. Suppose the claim is false, and p is a prime dividing d. For x nonzero in cokB, let ht_{p}(x) denote the largest nonnegative integer s such that x = p^{s}y for some y ∈ cokB. We consider two subcases. Subcase (i): p does not divide b_{m}δ^{−1}. Then p divides M(1, m), as well as M(j, m), m ≤ j ≤ η. Thus ht_{p}([Me_{m}]) > 0, and because M̃ is an automorphism this implies ht_{p}([e_{m}]) > 0, which contradicts the fact ht_{p}([e_{m}]) = 0. (If [e_{m}] = py had a solution, then the solution could be chosen in the direct summand R[e_{m}], and b_{m}p^{−1} would annihilate R[e_{m}] ≅ R/b_{m}, which is absurd.) Subcase (ii): p divides b_{m}δ^{−1}. Let s be the largest power of p dividing δ. Then δ[e_{m}] ≠ 0, and ht_{p}(δ[e_{m}]) = s. But ht_{p}(δ[Me_{m}]) = ht_{p}([(0, …, 0, δM(m, m), …, δM(η, m))^{t}] ≥ s + 1. This is again a contradiction.

Now write b_{m} = abc, where a is a product of primes dividing μ, b is a product of primes dividing d, and c is a product of primes dividing neither μ nor d. It follows that any prime dividing b_{m} divides exactly one of the two terms μ and cd, so gcd(b_{m}, μ + cd) = 1. Choose r_{2}, r_{m+1}, …, r_{η} in R such that

r_{2}b_{m}δ^{−1}M(1, m) + ∑_{i=m+1}^{η} r_{i}M(i, m) = cd .

For m + 1 ≤ i ≤ η, let U_{i} be the type (2) matrix U{{m, i}} with x = r_{i}. Let U_{2} be the type (3) matrix U{{m, 1}} with x = r_{2}b_{m}δ^{−1}. Let M′ = U_{2}U_{m+1} ⋯ U_{η}M. Now M′ still satisfies (5.3) for 2 ≤ i < m, and also M′(m, m) = μ + cd. Since gcd(M′(m, m), b_{m}) = 1, this reduces Case 2 to Case 1.

CASE 3: b_{m} = 0.

According to (5.1), b_{m} = s_{k}, s_{k−1} ≠ 0 and b_{i} = 0 for i ≥ m. Without loss of generality, we may assume m is the least i such that b_{i} = 0. So, b_{m} is the upper-left entry of M_{kk} which has indices m ≤ i, j ≤ η. Apply matrices U of type (1) (with j = k) to achieve M_{kk} = Id. Now (5.3) still holds for i < m; for m ≤ i ≤ η, (5.3) holds for j ≥ m since M_{kk} = Id; and for j < m ≤ i, we have M(i, j) = 0 simply because s_{k} = 0 and s_{i} ≠ 0 if i ≠ k. This finishes the reduction step.

The final step.

After applying SL equivalences, we have reduced to the case where M satisfies (5.3) for 2 ≤ i ≤ η. Now M(i, j) ≡ δ_{ij} (mod δ) for 2 ≤ i ≤ η and 1 ≤ j ≤ η, so det(M) ≡ M(1, 1) (mod δ). Then by assumption there is a unit u in R (with u = 1 if φ is an SL equivalence) such that so M(1, 1) ≡ u (mod δ). Let U = diag(u^{−1}, 1, …, 1), then UBU^{−1} = B and (UM)(1, 1) = 1 (mod δ). Finally, apply matrices U{{1, j}} of type 2 to UM to produce a matrix which induces the identity automorphism. This finishes the proof. □

6. Realizing isomorphisms of K-webs by equivalences

This section is devoted to the proof of Theorem 4.5. We begin with the following lemma, in which T denotes the poset {1, 2} with the relation 1 ≺ 2.

Lemma 6.1. Suppose S and S′ are matrices in M_{T} (R) with

S = (\begin{matrix}R & X \\ 0 & D \end{matrix}) , S′ = (\begin{matrix}R & X′ \\ 0 & D \end{matrix}) ,

where D is diagonal, and suppose (a, b, c, d) is an isomorphism of their associated exact sequences,

kerD ⟶ cokR ⟶ cokS ⟶ cokD ⟶ 0
a↓  ^{Id}↓  ^{c}↓  ^{Id}↓
kerD ⟶ cokR ⟶ cokS′ ⟶ cokD ⟶ 0

in which b = Id and d = Id.

Then there is a GL equivalence (U, V): S → S′, where U has the form ( \begin{matrix}I & ∗ \\ 0 & I \end{matrix}) and V has the form ( \begin{matrix}I & ∗ \\ 0 & C \end{matrix}), such that (U, V) induces the isomorphism (a, b, c, d). Given det(a) = 1, we may require detU = detV = 1.

Proof. We will consider the case in which D has the form D = ( \begin{matrix}0 & 0 \\ 0 & D_{∗} \end{matrix} ), in which D_{∗} is nonsingular and the complementary zero diagonal block is k × k. (It is a purely notational matter that we present the maximal principal submatrix D_{∗} as the given corner block, and the pure cases D = 0 and D = D_{∗} can be addressed using parts of our argument for the mixed case.)

Let A be the member of GL(k, R) such that the block matrix A′′ = ( \begin{matrix}A & 0 \\ 0 & I \end{matrix}) (of size matching D) satisfies a(x) = A^{−1}x, for all x in ker(D). Let V′′ = ( \begin{matrix}I & 0 \\ 0 & A′′ \end{matrix} ) (of size matching S) and consider the equivalence (I, V′′): S → ISV′′, which induces the exact sequence isomorphism (a, Id, Id, Id). Note, if det(a) = 1, then detA′′ = 1 = detV′′. After replacing S with ISV′′, we reduce to the original problem, with the additional condition a = Id.

Now it suffices to find U, V of the form

(\begin{matrix}I & ∗ & ∗ \\ 0 & I & ∗ \\ 0 & 0 & I \end{matrix})

(in which the central I is k × k and the upper left block I has the same size as R) such that USV = S′. Write S and S′ with this block structure (with blockings X = (X_{1} X_{2}) and X′ = (X′_{1} X′_{2})):

S = (\begin{matrix}R & X_{1} & X_{2} \\ 0 & 0 & 0 \\ 0 & 0 & D_{∗} \end{matrix}) , S′ = (\begin{matrix}R & X′_{1} & X′_{2} \\ 0 & 0 & 0 \\ 0 & 0 & D_{∗} \end{matrix}) .

Since now a = Id, and D_{∗} is nonsingular, the first (leftmost) square in the commuting diagram gives us X_{1} = X′_{1} + RW for some matrix W. Let

V′ = (\begin{matrix}I & W & 0 \\ 0 & I & 0 \\ 0 & 0 & I \end{matrix}) .

We may replace S′ with S′V′, and so without loss of generality we simply assume that X_{1} = X′_{1}.

Let (I + F) be a matrix such that for all x, the coset c([x]) in cokS′ equals [(I + F)x]. Express F in the 3 × 3 block form above,

F = (\begin{matrix}F_{11} & F_{12} & F_{13} \\ F_{21} & F_{22} & F_{23} \\ F_{31} & F_{32} & F_{33} \end{matrix}) .

On account of the second commuting square, all columns in the first block column of F lie in the image of S′. So we may revise our choice of F to require F_{i1} = 0 for 1 ≤ i ≤ 3.

On account of the third commuting square, there is a block matrix ( \begin{matrix}K_{1} & K_{2} \\ K_{3} & K_{4} \end{matrix} ) such that

(\begin{matrix}F_{22} & F_{23} \\ F_{32} & F_{33} \end{matrix}) = (\begin{matrix}0 & 0 \\ 0 & D_{∗} \end{matrix}) (\begin{matrix}K_{1} & K_{2} \\ K_{3} & K_{4} \end{matrix})

= (\begin{matrix}0 & 0 \\ D_{∗}K_{3} & D_{∗}K_{4} \end{matrix}) .

So we may revise our choice of F again by subtracting from F the following matrix (which has all columns in the image of S′):

(\begin{matrix}R & X_{1} & X′_{2} \\ 0 & 0 & 0 \\ 0 & 0 & D_{∗} \end{matrix}) (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & K_{3} & K_{4} \end{matrix}) .

This puts I + F into the desired form

U = (\begin{matrix}I & F_{12} & F_{13} \\ 0 & I & 0 \\ 0 & 0 & I \end{matrix})

with U inducing the desired maps Id, c, Id on cokR, cokS, cokD.

There is a matrix X′′_{2} such that

US = (\begin{matrix}R & X_{1} & X′′_{2} \\ 0 & 0 & 0 \\ 0 & 0 & D_{∗} \end{matrix})  and  S′ = (\begin{matrix}R & X_{1} & X′_{2} \\ 0 & 0 & 0 \\ 0 & 0 & D_{∗} \end{matrix}) .

If x is a column of S′, then U^{−1}x must be in the image of S (otherwise the map cokS → cokS′ induced by U would not be injective). Therefore every column of S′ is an R combination of columns of US, and there is a matrix Z such that USZ = S′. We can choose this Z to have the form

Z = (\begin{matrix}I & 0 & Z_{1} \\ 0 & I & Z_{2} \\ 0 & 0 & Z_{3} \end{matrix}) .

Now D_{∗}Z_{3} = D_{∗}, and the nonsingularity of D_{∗} then implies Z_{3} = Id. Setting V = Z concludes the proof of the lemma. □

Proof of Theorem 4.5. The proofs in the GL and SL cases are almost the same, so we will give them together. We are working with the given κ and B, B′ with corresponding diagonal blocks equal.

By Theorem 4.4, for each diagonal block D_{i} of B, there exists an SL selfequivalence (U′_{i}, V′_{i}) of D_{i} which induces the automorphism d_{i}. Let U′ and V′ be the block diagonal matrices with diagonal blocks U_{i} and V_{i}. It now suffices to realize the K-web isomorphism κ(κ(U′, V′))^{−1} : K(B) → K(B′) by an equivalence (U, V) which is an SL_{P} equivalence if κ is an SL K-web isomorphism (for in this case, the equivalence (UU′, V′V) realizes κ). So without loss of generality, we simply assume the additional condition d_{i} = Id, 1 ≤ i ≤ N.

To prove the theorem, it now suffices to produce recursively matrices B_{i} and GL_{P} equivalences (U_{i}, V_{i}): B_{i−1} → B_{i}, 1 ≤ i ≤ N, such that the following conditions hold (in which B_{0} = B, L_{i} = {j: j ⪯ i}, and κ^{<i>} = κ(U_{i}, V_{i}) ⋯ κ(U_{1}, V_{1})):

B_{i}{{1, …, i}} = B′{{1, …, i}} . (6.2)

(6.3) (κ^{<i>})_{j} = κ_{j} , 1 ≤ j ≤ i .(See (3.6) for the definition of κ_{j}.)

(6.4) U_{i} = V_{i} = Id , except on indices in L_{i} .

(6.5) (U_{i}, V_{i}): B_{i−1} → B_{i} is an SL_{P} equivalence if κ is an SL isomorphism.

Because 1 has no predecessor, κ_{1} is given by d_{1} : cok(D_{1}) → cok(D′_{1}), and by our assumption, d_{1} = Id. So for the case i = 1, (6.2) − (6.5) are satisfied by (U_{1}, V_{1}) = (Id, Id) : B_{0} → B_{1} (we let Id denote both a matrix and a map).

Now suppose 1 < n ≤ N and for i < n we have carried out the construction of U_{i}, V_{i} and B_{i} satisfying (6.2) − (6.5). To finish the proof, it suffices to construct (U_{n}, V_{n}): B_{n−1} → B_{n} such that (6.2) − (6.5) hold for i = n. Let κ′ denote κ(κ^{<n−1>})^{−1}. Then (6.3) holds for i = n if (κ(U_{n}, V_{n}))_{j} = κ′_{j} for 1 ≤ j ≤ n. Because (6.3) holds for 1 ≤ i < n, we have κ′_{j} = Id for 1 ≤ j < n. Because (6.4) holds for 1 ≤ i < n, we have κ′_{n} = κ_{n}. Therefore it suffices to find (U_{n}, V_{n}) satisfying (6.2), (6.4), (6.5) for i = n and also

(6.6)  κ((U_{n}, V_{n}))_{j} = Id ,  1 ≤ j < n
= κ_{n} ,  j = n .

If n has no predecessor in P, then we may use (U_{n}, V_{n}) = (Id, Id). So suppose n has a predecessor. Define

S = B_{n−1}\{L_{n}\} = (\begin{matrix}R & X \\ 0 & D \end{matrix})  and  S′ = B′\{L_{n}\} = (\begin{matrix}R & X′ \\ 0 & D \end{matrix}) ,

in which D = B{n} = B′{n}. Denote κ′_{n} as (a′_{n}, b′_{n}, c′_{n}d′_{n}); it then follows from Proposition 3.8 that b′_{n} = Id, so κ′_{n} = (a′_{n}, Id, c′_{n}, Id). Appealing to Lemma 6.1, pick invertible U′′, V′′ with block forms compatible with the blocking of S and S′ and satisfying

U′′ = (\begin{matrix}I & ∗ \\ 0 & I \end{matrix}) , V′′ = (\begin{matrix}I & ∗ \\ 0 & C \end{matrix}) ,

such that • U′′SV′′ = S′ ,

• κ(U′′, V′′) = κ_{n} , and
• if det(a′_{n}) = 1, then detV′′ = 1.

Let U_{n} and V_{n} be the matrices satisfying (6.4) which agree with U′′ and V′′ on L_{i}. Set B_{n} = U_{n}B_{n−1}V_{n}.

Clearly U_{n}, V_{n}, B_{n} satisfy (6.6) and for i = n satisfy (6.2) and (6.4). It remains to verify (6.5) for i = n. So, suppose κ is an SL K-web isomorphism. Then by the inductive assumption, (U_{i}, V_{i}) is an SL_{P} equivalence for 1 ≤ i < n. Consequently κ′ is an SL K-web isomorphism. Because d′_{n} = Id, it follows that det(a′_{n}) = 1, and therefore detV′′ = 1, which implies that (U_{n}, V_{n}) is an SL_{P} equivalence. This finishes the proof of the theorem. □

7. Examples

Example 7.1. We will exhibit two matrices B, B′ ∈ 𝔐_{P}(ℤ) which are not GL_{P} equivalent, but which have SL isomorphic K-webs. We use P = {1, 2} with 1 ≺ 2,

and set B = (\begin{matrix}5 & 1 \\ 0 & 5 \end{matrix}) and B′ = (\begin{matrix}5 & 2 \\ 0 & 5 \end{matrix}). First, if there were a GL_{P}(ℤ) equivalence,

say (\begin{matrix}a & b \\ 0 & d \end{matrix}) (\begin{matrix}5 & 1 \\ 0 & 5 \end{matrix}) = (\begin{matrix}5 & 2 \\ 0 & 5 \end{matrix}) (\begin{matrix}a′ & b′ \\ 0 & d′ \end{matrix}), then we would have a + 5b = 5b′ + 2d′

with {a, d′} ⊂ {1, −1}, which is impossible. Next, for the K-web isomorphism note that for this P the K-web is the single strand

kerD_{1} → cokR_{2} → cokS_{2} → cokD_{2} → 0

and for both of our matrices this takes the form

0 → ℤ/5 → ℤ/25 → ℤ/5 → 0 .

A K-web isomorphism K(B) → K(B′) is exhibited by the following commuting diagram between the strands for B and B′,

0 = ker(5) ⟶ cok(5) ⟶^{[x]↦[( \begin{matrix}x \\ 0 \end{matrix} )]} cok (\begin{matrix}5 & 1 \\ 0 & 5 \end{matrix}) ⟶^{[( \begin{matrix}x \\ y \end{matrix})]↦[y]} cokD ⟶ 0
↓  ↓^{2}  ↓^{( \begin{matrix}2 & 0 \\ 0 & 1 \end{matrix} )}  ↓^{1}
0 = ker(5) ⟶ cok(5) ⟶^{[x]↦[( \begin{matrix}x \\ 0 \end{matrix} )]} cok (\begin{matrix}5 & 2 \\ 0 & 5 \end{matrix}) ⟶^{[( \begin{matrix}x \\ y \end{matrix})]↦[y]} cokD ⟶ 0

in which 2 denotes multiplication by 2, and the central map is given by the rule

(\begin{matrix}x \\ y \end{matrix}) + (\begin{matrix}5 & 1 \\ 0 & 5 \end{matrix}) ℤ^{2} ↦ (\begin{matrix}2 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix}x \\ y \end{matrix}) + (\begin{matrix}5 & 2 \\ 0 & 5 \end{matrix}) ℤ^{2} .

We leave to the reader the verification that we have defined three isomorphisms giving a commuting diagram as claimed. The example does not contradict our classification result Theorem 4.6, because Theorem 4.4 shows multiplication by 2 is not a GL(ℤ)-allowable isomorphism of ℤ/5.

Example 7.2. We will exhibit two matrices B, B′ ∈ 𝔐_{P}(ℤ) which are GL_{P} equivalent and which have corresponding diagonal blocks equal, but which are not SL_{P} equivalent.

We use the poset P = {1, 2, 3, 4} for which the order ≺ agrees with < except that 2 ⊀ 3. The matrices B, B′ have the block forms

B = (\begin{matrix}D_{1} & X & X & 0 \\ 0 & D_{2} & 0 & X \\ 0 & 0 & D_{3} & X \\ 0 & 0 & 0 & D_{4} \end{matrix}) , B′ = (\begin{matrix}D_{1} & X′ & X & 0 \\ 0 & D_{2} & 0 & X \\ 0 & 0 & D_{3} & X \\ 0 & 0 & 0 & D_{4} \end{matrix})

where D_{i} = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) for i = 1, 2, 3, 4; X = ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ); and X′ = ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ).

Let V be the permutation matrix that switches the 3rd and 4th columns of B. Then BV = B′ and therefore B and B′ are GL_{P} equivalent. To show B and B′ are not SL_{P} equivalent, by Theorem 4.6 it suffices to show that the full K-webs K(B) and K(B′) are not SL isomorphic. (We could alternately show the reduced K-webs are not isomorphic, but the argument would be more complicated.) The full web includes the following four exact sequences (associated respectively to the difference sets {1, 2} \ {2}, {1, 3} \ {3}, {2, 4} \ {4}, and {3, 4} \ {4}).

kerD_{2} ⟶ cokD_{1} ⟶ cokS_{2} ⟶ cokD_{2} ⟶ 0
kerD_{3} ⟶ cokD_{1} ⟶ cokS_{3} ⟶ cokD_{3} ⟶ 0
kerD_{4} ⟶ cokD_{2} ⟶ cokB{2, 4} ⟶ cokD_{4} ⟶ 0
kerD_{4} ⟶ cokD_{3} ⟶ cokB{3, 4} ⟶ cokD_{4} ⟶ 0

One easily checks the following:

(1) For each group in one of the sequences above, the corresponding groups in K(B) and K(B′) are the same (not just isomorphic).

(2) Each of the four exact sequences is isomorphic in both K(B) and K(B′) to

ℤ ⟶^{≅} ℤ ⟶^{0} ℤ ⟶^{≅} ℤ ⟶ 0 .

(3) The arrows (maps) kerD_{2} → cokD_{1} are not the same in K(B) and K(B′), but all other corresponding arrows from the four sequences are the same in K(B) and K(B′).

Now suppose there is an SL K-web isomorphism κ from the full K-web of B to that of B′, with associated group isomorphisms (automorphisms in this example) a_{i}: kerD_{i} → kerD_{i} and d_{i}: cokD_{i} → cokD_{i}. These automorphisms of ℤ can only be 1 (the identity) or −1. Without loss of generality (because −κ is also an SL Kweb isomorphism), we may assume that d_{1} = 1. This gives the following diagram chasing chain of deductions:

• a_{2} = −1, because κ intertwines the arrows kerD_{2} → cokD_{1},

• d_{2} = −1, by the SL paired determinant condition (i.e., det(a_{2}) = det(d_{2})),

• a_{4} = −1, because κ intertwines the arrows kerD_{4} → cokD_{2},

• d_{3} = −1, because κ intertwines the arrows kerD_{4} → cokD_{3},

• a_{3} = −1, by the SL paired determinant condition. But this is a contradiction, because a_{3} = 1 since κ intertwines the arrows kerD_{3} → cokD_{1}. Therefore no SL isomorphism of the full K-webs of B and B′ can exist, and these matrices are not SL_{P} equivalent.

8. Special cases

In this section we consider several special cases in which the complete K-web invariants for poset block equivalence can be simplified.

The case with R a field and P linearly ordered.

Now suppose P is linearly ordered (that is, the relation ≺ on {1, …, N} is the same as <), and R is a field. For purposes of contrast and illustration, we’ll give the classification up to GL_{P}(R) equivalence in this case, even though this is contained in the more general results of [KL]. We’ll consider the GL_{P} equivalence in 𝔐_{P}(n, R) (so, the ith diagonal block of a matrix in this set is n_{i} × n_{i}) in the case that every n_{i} < ∞. The infinite matrix case is essentially the same and the SL case is similar.

Every element of 𝔐_{P}(n, R) is GL_{P}(R) equivalent to a block upper triangular matrix in a certain canonical form, and a complete invariant for GL_{P}(R) equivalence in 𝔐_{P}(n, R) is given by an array of numbers r_{i,j}, 1 ≤ i ≤ j ≤ N, where r_{i,j} is the rank of the ij block (of size n_{i} × n_{j}, of course) of the canonical form. To describe the canonical form, let us suppose for convenience that a block M_{ij} has rows indexed by {1, …, n_{i}} and columns indexed by {1, …, n_{j}}. Let us say the block is standard if every entry is zero, except that there might be integers g ≤ h such that M_{ij}(t, t) = 1 for g ≤ t ≤ h. Now a matrix M is in the canonical form if the following hold (in which M_{i} denotes the principal submatrix M_{i1}M_{i2} … M_{iN}):

• Each block is standard.

• A block M_{ij} is zero if i > j.

• A row or column of M has at most one nonzero entry.

• If a row of M_{i} is the zero row, then every lower row in M_{i} is also the zero row.

To get a picture of the canonical form, and see how it is achieved, we’ll discuss the 3 × 3 case.

B = (\begin{matrix}B_{11} & B_{12} & B_{13} \\ 0 & B_{22} & B_{23} \\ 0 & 0 & B_{33} \end{matrix}) → B′ = (\begin{matrix}I & 0 & | & 0 & 0 & | & 0 & 0 \\ 0 & 0 & | & 0 & C_{12} & | & 0 & C_{13} \\ − & − & · & − & − & · & − & − \\ 0 & 0 & | & I & 0 & | & 0 & 0 \\ 0 & 0 & | & 0 & 0 & | & 0 & C_{23} \\ − & − & · & − & − & · & − & − \\ 0 & 0 & | & 0 & 0 & | & I & 0 \\ 0 & 0 & | & 0 & 0 & | & 0 & 0 \end{matrix})

(\begin{matrix}C_{12} & C_{13} \\ 0 & C_{23} \end{matrix}) → (\begin{matrix}I & 0 & | & 0 & 0 \\ 0 & 0 & | & 0 & D \\ − & − & · & − & − \\ 0 & 0 & | & I & 0 \\ 0 & 0 & | & 0 & 0 \end{matrix})

D → (\begin{matrix}I & | & 0 \\ − & · & − \\ 0 & | & 0 \end{matrix}) .

Begin with B as given in block form. Multiplying from both sides by invertible block diagonal matrices, put each diagonal block into the standard form, then add multiples of each I block along the diagonal to zero out the rest of any row or column through that block. This produces the matrix B′ with the block form shown (each 2 × 2 block in B′ replaces some B_{ij}, and correspondingly has n_{i} rows and n_{j} columns). Now repeat these operations through the blocks C_{ij} formed, and then finally through the last block D. This produces a matrix F in the canonical form (rather than exhibit F, we leave it to the reader’s visualization).

One way to check that this form is canonical is to recover the numbers r_{ij} as invariants from the K-web. For this linear/field case, the K web reduces to the following diagram:

kerB{2}  kerB{3}  …  kerB{N}
f_{1}↓  ^{f_{2}}↓  ^{f_{N−1}}↓
cokB^{(1)} ⟶^{g_{2}} cokB^{(2)} ⟶^{g_{3}} … ⟶^{g_{N−1}} cokB^{(N−1)} ⟶^{g_{N}} cokB^{(N)}

in which we use B^{(i)} to denote B{1, …, i}, and the image of f_{n} equals the kernel of g_{n+1}. Now n_{i} − r_{ii} = dim(kerB{i}). For 1 < i < j ≤ N, the dimension of the image of cokB^{(1)} in cokB^{(j)} under the map g_{j} ⋯ g_{2} is equal to n_{1} −(r_{11} +⋯+r_{1j}); so for 1 ≤ j ≤ N, r_{1j} is determined by the K-web. Similarly, for 1 < i < j ≤ N, the dimension of the image of cokB^{(i)} in cokB^{(j)} under the map g_{j} ⋯ g_{i+1} is

(n_{1} + ⋯ + n_{i}) − ∑_{\begin{matrix}s, \\ 1≤s≤i \end{matrix}} ( ∑_{\begin{matrix}t, \\ s≤t≤j \end{matrix}} r_{st}) ,

and we can recursively recover the entire r_{ij} array from dimension data determined by the isomorphism class of the K-web.

If the order is not linear, then in general we cannot put an element of 𝔐_{P}(R) into this canonical form, because some of the clearing out operations may not be allowed.

The nonsingular case.

If R is a field, then any two nonsingular elements of 𝔐_{P}(R) are GL_{P}(R) equivalent. One can verify this by observing that every group in the K-web of such an element vanishes, or by using allowed operations to reduce a nonsingular matrix to the identity. In this nonsingular case, the additional invariants for the SL equivalence are the determinants of the diagonal blocks.

Now suppose only that R is a PID, and B is a nonsingular matrix in 𝔐_{P}(R). Then every cokernel module in the K-web of B is a torsion module, and for each i with a predecessor in P, the ith level K-web map cokR_{i} → cokS_{i} of (3.5) is injective (on account of the exactness, since ker(D_{i}) = 0). Consequently each of these cokernel modules ultimately embeds in cokB. We end up with a torsion module (cokB) and a list of distinguished submodules (the embeddings of the cokernel modules cokR_{i} and cokS_{i}); isomorphism of the K-webs of B and B′ is equivalent to isomorphism of the torsion modules cokB and cokB′ respecting the distinguished submodules. Moreover, here we can neglect the modules cokR_{i}, as they are determined as unions of the cokS_{j} for which j ≺ i. In particular, if P is linearly ordered, then cokS_{i} = cokB^{(i)} for all i in P, and K(B) is completely characterized by cokB with the chain of distinguished submodules

cokB^{(1)} ⊂ cokB^{(2)} ⊂ ⋯ ⊂ cokB^{(N)} = cokB

(in which cokB^{(i)} is identified with its image under the embedding g_{N} ⋯ g_{i+1}).

In the nonsingular case, the subtle issue of paired determinants disappears. The additional invariant for SL isomorphism of K webs here is simply the list of determinants of the diagonal blocks. For R = ℤ, the absolute value of these determinants can be extracted from the K-web data, and the only additional information is the list of signs of determinants of diagonal blocks.

Note in particular the case that B and B′ are nonsingular with gcdD = 1 for each diagonal block D of B and B′. Here B and B′ are GL_{P}(R) equivalent iff their K-webs are isomorphic (Cor. 4.7); and if in addition the corresponding diagonal blocks of B and B′ are equal, then B and B′ are SL_{P}(R) equivalent iff their K-webs are SL isomorphic (Cor. 4.8). This is useful for classification of some dynamical systems and C^{∗}-algebras, as follows. Suppose A ∈ 𝔐_{P}(ℤ_{+}) and each of its N diagonal blocks is irreducible. Let B_{1}, B_{2}, …, B_{N} denote the diagonal blocks of B = I − A ∈ 𝔐_{P}(ℤ), and suppose B is nonsingular (i.e., 1 is not an eigenvalue of A). Then modulo a permutation of irreducible components, the group cokB together with its distiguished subgroups as discussed above, under group isomorphisms respecting the distinguished subgroups, is a complete invariant of stable isomorphism of the nonsimple Cuntz-Krieger algebras defined by A [H3]. Again modulo a permutation of irreducible components, this invariant plus the assignment det(B_{i}), i = 1, 2, …, N, is a complete invariant of flow equivalence of reducible shifts of finite type defined by A [H3]. (Note, det(B_{i}) is invariant under SL-equivalence, but not under GL-equivalence. We need both types of equivalence.)

In particular, for R = ℤ, there are decision procedures for determining whether nonsingular matrices B, B′ in 𝔐_{P}(R) are GL_{P} equivalent or SL_{P} equivalent.

The 2×2 case.

Suppose P = {1, 2} with 1 ≺ 2. Let us work out the subblock form of a GL_{P}(R) equivalence (U, V) from B to B′, as follows:

UBV = (\begin{matrix}U_{1} & U_{2} \\ 0 & U_{4} \end{matrix}) (\begin{matrix}B_{1} & B_{2} \\ 0 & B_{4} \end{matrix}) (\begin{matrix}V_{1} & V_{2} \\ 0 & V_{4} \end{matrix})

= (\begin{matrix}U_{1}B_{1}V_{1} & U_{1}B_{1}V_{2} + U_{1}B_{2}V_{4} + U_{2}B_{4}V_{4} \\ 0 & U_{4}B_{4}V_{4} \end{matrix})

= (\begin{matrix}B′_{1} & B′_{2} \\ 0 & B′_{4} \end{matrix}) = B′ .

For the moment, we use colcokB_{1} to denote what we have been calling cokB_{1}, so that we may similarly use rowcokB_{4} to denote the cokernel of B_{4} considered as a map on row vectors. A GL_{P}(R) equivalence as above induces isomorphisms

colcokB_{1} → colcokB′_{1} ,  rowcokB_{4} → rowcokB′_{4}
[x] ↦ [U_{1}x]  [x] ↦ [xV_{4}]

and also

colcokB_{1} ⊗ rowcokB_{4} → colcokB′_{1} ⊗ rowcokB′_{4}
[B_{2}] ↦ [U_{1}B_{2}V_{4}] .

Thus, as invariants of GL_{P}(R) equivalence we get first the isomorphism classes of those cokernels colcokB_{1} and rowcokB_{4} and then (after passing to the problem of considering matrices with equal diagonal blocks) an orbit of the action on the tensor product module colcokB_{1} ⊗ rowcokB_{4} by Aut(colcokB_{1}) × Aut(rowcokB_{4}). (In the case that the diagonal block cokernels are free R-modules, we can identify [B_{2}] with a matrix and the orbit is simply the GL(R) equivalence class of this matrix.) Under the assumption that the gcd of the entries of each diagonal block is 1, we have shown that the cokernel automorphisms are induced by (block diagonal) SL_{P}(R) self equivalences, and it follows that colcokB_{1}, rowcokB_{4}, and the orbit of [B_{2}] in colcokB_{1} ⊗ rowcokB_{4} under the action of “product-type” isomorphisms comprise a complete invariant of GL_{P}(R) equivalence. The additional invariants for SL_{P}(R) equivalence are simply det(B_{1}) and det(B_{4}).

This tensor product invariant for the 2 × 2 case was developed in [H1] following [C]. Suppose A ∈ 𝔐_{P}(ℤ_{+}) has two irreducible components and B = I − A of the form above. [H1] shows that the tensor product invariant, together with det(B_{1}) and det(B_{4}), are complete flow equivalence invariants for shifts of finite type defined by A. [H2] shows that the tensor product invariant alone, is a complete invariant of stable isomorphism for the Cuntz-Krieger algebras arising from such matrices A, i.e., the Cuntz-Krieger algebras with exactly one proper closed ideal [C].

9. GL_{P} similarity

In this section, F denotes a field. The following correspondence is classical.

Theorem 9.1. Suppose B, B′ ∈ 𝔐(n_{1}, F). Then B and B′ are similar over F if and only if tI − B and tI − B′ are GL(n_{1}, F[t]) equivalent.

Because F is a field, the polynomial ring F[t] is a principal ideal domain. Thus the correspondence given by Theorem 9.1 reduces the classification of square matrices over F up to similarity over F to the theory of equivalence of matrices over a PID, as is well known (e.g. [AW, Ne]). In this section, we will generalize this classical theory to the classification of matrices in 𝔐_{P}(F) up to GL_{P} similarity.

Definition 9.2. Let F be a field and B, B′ ∈ 𝔐_{P}(n, F). The matrices B and B′ are said to be GL_{P} similar over F if there is S ∈ GL_{P}(n, F) such that S^{−1}BS = B′.

Geometrically, GL_{P} similarity reflects the constraint that the similarity must preserves certain invariant subspaces (Sec. 4 of [H5]). Recall (Remark 2.2), if S is in GL_{P}(n, F), then so is S^{−1}.

Lemma 9.3. Suppose F is a field and B ∈ 𝔐(k, F). Then every automorphism of the F[t]-module cok (tI − B) is allowable.

Proof. Let α ∈ Aut[cok (tI −B)]. It suffices to show that α is allowable. If gcd(tI − B) = 1, then α is even SL allowable, by Theorem 4.4.

Suppose gcd(tI − B) ≠ 1. Then B = cI for some constant c ∈ F. Then cok(tI − B) = cok[(t − c)I], so we have an isomorphism F^{k} → cok(tI − B) given by the rule v ↦ [v], and we see that for every automorphism α of the F[t]-module cok(tI − B) there exists a unique matrix P (α) = P ∈ GL(k, F) such that α is given by the rule α: [v] ↦ [P v]. Also, P (tI − B)P^{−1} = P (t − c)P^{−1} = tI − B; so, (P, P^{−1}) is a self-equivalence which induces α. □

Remark 9.4. For the case tI−B = (t−c)I in the proof above, an automorphism α of cok(tI −B) is SL allowable if and only if the matrix P (α) over F has determinant 1. This is because SL allowability requires that there exist Q ∈ SL(k, F[t]) such that Q ≡ P mod (t−c), and then the conditions det(P) ∈ F and det(P) ≡ 1 mod (t−c) imply det(P) = 1.

The following theorem generalizes Theorem 9.1 and also Theorem 4.8 in [H5].

Theorem 9.5. Suppose B and B′ are in 𝔐_{P}(n, F). Then the following are equivalent.

(1) B and B′ are GL_{P} similar over F.

(2) tI − B and tI − B′ are GL_{P} equivalent over F[t].

(3) There exist R_{0}, S_{0} ∈ GL_{P}(n, F) such that tI − B′ = R_{0}(tI − B)S_{0}.

(4) The K-webs of F[t]-modules K(tI − B) and K(tI − B′) are isomorphic.

(5) There is a F[t]-module isomorphism δ : cok (tI − B) → cok (tI − B′) such that δ(cok (tI − B){s_{i}}) = cok (tI − B′){s_{i}}, i ∈ P, where s_{i} = {j : j ∈ P, j ⪯ i}.

Proof. (1) ⇒ (3) Suppose B′ = S^{−1}BS for some S ∈ GL_{P}(n, F). We let R_{0} = S^{−1}, S_{0} = S and (3) follows.

(3) ⇒ (2) It is trivial, since GL_{P}(n, F) ⊂ GL_{P}(n, F[t]).

(2) ⇒ (3) Suppose U(t), V (t) in GL_{P}(n, F[t]) satisfy (tI − B′) = U(t)(tI − B)V (t). Now we show that

U(t) = (tI − B′)P (t) + T_{0} and V (t) = Q(t)(tI − B′) + S_{0} (9.6)

for some P (t), Q(t) ∈ 𝔐_{P}(n, F[t]) and S_{0}, T_{0} ∈ 𝔐_{P}(n, F).

Let us prove the first equation in (9.6). Since U(t) ∈ GL_{P}(n, F[t]), we have U(t) = ∑_{i=0}^{m} U_{i}t^{i} for some U_{i} ∈ 𝔐_{P}(n, F), i = 0, 1, …, m. Let P (t) = ∑_{i=0}^{m−1} P_{i}t^{i}, where P_{i} ∈ 𝔐_{P}(n, F), i = 0, 1, …, m − 1, are defined inductively as follows:

P_{m−1} = U_{m}, P_{m−2} = U_{m−1} + B′P_{m−1}, ⋯, P_{1} = U_{2} + B′P_{2}, P_{0} = U_{1} + B′P_{1}, and finally, we define T_{0} := U_{0}+B′P_{0} ∈ 𝔐_{P}(n, F). Then U(t) = (tI −B′)P (t)+T_{0}. The second equation in (9.6) can be proved exactly the same way.

Since U(t)^{−1}(tI − B′) = (tI − B)V (t), using the second equation in (9.6) for V (t), we obtain U(t)^{−1}(tI − B′) = (tI − B)[Q(t)(tI − B′) + S_{0}]. Therefore

[U(t)^{−1} − (tI − B)Q(t)](tI − B′) = (tI − B)S_{0} . (9.7)

Let W = U(t)^{−1} − (tI − B)Q(t). Since 𝔐_{P}(n, F[t]) is closed under addition, subtraction and multiplication, and GL_{P}(n, F[t]) ⊂ 𝔐_{P}(n, F[t]) is closed under inversion, we have W ∈ 𝔐_{P}(n, F[t]). Comparing the degrees of t on both sides of W (tI − B′) = (tI − B)S_{0} in (9.7), we see that actually W = S_{0} ∈ 𝔐_{P}(n, F). So it suffices to show that W is invertible. Using (9.6), (9.7) and tI − B′ = U(t)(tI − B)V (t), we obtain

I = U(t)U(t)^{−1}
= U(t)[W + (tI − B)Q(t)]
= U(t)W + U(t)(tI − B)Q(t)
= U(t)W + (tI − B′)V (t)^{−1}Q(t)
= [(tI − B′)P (t) + T_{0}]W + (tI − B′)V (t)^{−1}Q(t)
= T_{0}W + (tI − B′)[P (t)W + V (t)^{−1}Q(t)].

Comparing the degrees of t again we see that I = T_{0}W. Therefore, W = S_{0} ∈ GL_{P}(n, F) and tI − B′ = W^{−1}(tI − B)S_{0}.

(3) ⇒ (1). Here tI − B′ = R_{0}S_{0}t − R_{0}BS_{0}. Hence I = R_{0}S_{0} and B′ = R_{0}BS_{0} = S_{0}^{−1}BS_{0}.

(2) ⇒ (4). It follows from Theorem 3.8

(4) ⇒ (2). Because their K-webs are isomorphic, we may by Proposition 4.1 assume B and B′ have equal diagonal blocks. The claim then follows from Lemma 9.3 and Theorem 4.6.

(4) ⇔ (5). This follows from the discussion of the nonsingular case in Section 8, as det(tI − B′) and det(tI − B′) are nonzero in F[t]. □

Remark 9.8. As the proof shows, the conditions (1), (2) and (3) in Theorem 9.5 are still equivalent under the weaker assumption that F is a commutative ring with 1. The classical version of this fact (i.e., the case P = {1}) is well known (see Remark 5.3.9 in [AW]).

References

[AW] W.A. Adkins and S.H. Weintraub, Algebra: An Approach via Module Theory, Graduate Texts in Math 136, Springer-Verlag (1992).

[Ar] D.M.Arnold, Representations of partially ordered sets and abelian groups, Contemporary Math. 87 (1989), 91-109.

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

[B] M. Boyle, Flow equivalence of reducible shifts of finite type via positive factorizations, Pacific J. Math, to appear.

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

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

[Fa] D.K.Faddeev, On the equivalence of systems of integral matrices, Izv. Akad. Nauk SSSR Ser. Mat. 30(1966), 449–454.

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

[Fri] S. Friedland, Simultaneous similarity of matrices, Advances in Math. 50, No. 3 (1983), 189-265.

[G] F. Grunewald, Solution of the conjugacy problem in certain arithmetic groups, in Stud. Logic Foundations Math. 95, Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), pp. 101–139, North-Holland, 1980.

[GS] F. Grunewald and D. Segal, Some general algorithms. I. Arithmetic groups, Annals of Math. (2) 112 (1980) 531-583.

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

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

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

[H4] D. Huang, Automorphisms of Bowen-Franks groups for shifts of finite type, Ergod. Th. & Dynam. Sys. 21 (2001), 1113-1137.

[H5] D. Huang, A cyclic six-term exact sequence for block matrices over a PID, Linear and Multilinear Algebra 49(2) (2001), 91-114.

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

[KL] L. Klinger and L. Levy, Sweeping-similarity of matrices, Linear Alg and Appl. 75 (1986), 67-104.

[NR] L.A. Nazarova and A.V. Roiter, Representations of partially ordered sets, J. Soviet Math. 23 (1975), 585-607.

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

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

[Pl] V.V. Plahotnik, Representations of partially ordered sets over commutative rings, Math. USSR Izvestija 10 (1976), No.3, 497-514.

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

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

[S] D. Simson, Linear representations of partially ordered sets and vector space categories, Algebra, Logic and Applications 4, Gordon and Breach (1992).

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

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

Department of Mathematics, St.Cloud State University, St.Cloud, MN 56301-4498, U.S.A.

   E-mail address: dhuang@stcloudstate.edu