A NORMAL FORM ALGORITHM

FOR MODULES OVER k[x, y]/⟨xy⟩

Reinhard C. Laubenbacher and Bernd Sturmfels

Abstract. This paper gives an algorithm to classify finitely generated modules over the ring k[x, y]/⟨xy⟩, k any field. The given module is presented as the cokernel of a matrix with entries in the ring. Our algorithm reduces this matrix to a normal form analogous to the Smith normal form for a matrix over a polynomial ring in one variable. A natural application is the classification of pairs of mutually annihilating linear operators on a vector space.

I. Introduction

A fundamental result in algebra is the classification of finitely generated modules over a principal ideal domain. Every such module can be written uniquely, up to order of summands, as a direct sum of indecomposable modules which are either free of rank one or are quotients of the ring modulo a power of a prime ideal. If the module is presented as the cokernel of a matrix then we can find this decomposition by computing the Smith normal form of the matrix. In this paper we generalize the Smith normal form algorithm to modules over the ring R = k[x, y]/⟨xy⟩.

Our motivation for studying this particular ring comes from the work of L. Levy [L2, L3] who classified modules over Dedekind-like rings, namely pullback rings of Dedekind rings over common residue fields. Important examples are integral group rings of groups of square-free order. Levy’s classification is based on earlier work in the local case by Nazarova and Roiter [NR1,NR2]. In [ALa] it was shown that R = k[x, y]/⟨xy⟩ is the prototype of Dedekind-like ring in the following sense: for every local Dedekind-like ring there is a one-to-one correspondence between its finitely generated modules and finitely generated modules over the localization of R at its maximal ideal ⟨x, y⟩. The ring R also appears in a variety of other contexts, such as K-theory [DK] and algebraic geometry [Kl, Lemma 4.5].

Our goal is to derive an algorithmic version of Levy’s results for R = k[x, y]/⟨xy⟩. Following [L2, L3], we represent our ring by the pullback square

R ⟶ k[y]
↓  ↓
k[x] ⟶ k,

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 13P99, 15A21, 16D70.

Key words and phrases. Module classification, Smith normal form, pairs of linear operators, Gröbner basis.

The authors would like to thank the referee for a very careful reading of the manuscript.

where the lower horizontal map and the right vertical map send the variables to zero. If M is a finitely generated R-module then we present M as a quotient of a free module

R^{n} ⟶^{f} R^{m} ⟶ M ⟶ 0,

and f corresponds to a matrix A(x, y) with entries in R. Our algorithm transforms A(x, y) to a normal form, resulting in a normal form for the module M. It is not true that every R-module is a pullback of modules over the “coordinate rings” k[x] and k[y], but it is true that there is a pullback module which is “closest” to M, called a separated representation of M. In Section 3 we apply Gröbner bases theory to construct an algorithm for finding a matrix whose cokernel is a separated representation for M. In Sections 4 and 5 we reduce our problem to that of classifying modules whose associated primes are contained in the maximal ideal ⟨x, y⟩. For this case our normal form problem ends up being a generalization of the study of matrix pencils due to Weierstrass and Kronecker (see [Ga, Ch. 12]). This part of our algorithm (Section 6) follows the matrix reduction carried out in [NR2]. The structure of the final output is summarized in Theorems 7.1 and 7.2.

Finally, one may look at the problem of classifying R-modules from a different point of view, namely, as the classification of pairs of mutually annihilating linear operators on a k-vector space. This problem arises in the decomposition of Harish-Chandra modules due to Gel’fand and Ponomarev [GP]. A brief discussion of artinian R-modules in their incarnation as pairs of mutually annihilating matrices is given in Section 8. For more details on this problem see [Kr, p. 201].

II. Getting rid of constants

Our first step is to reduce to the case where A(0, 0) is the zero matrix, that is, where no entry of the given matrix A(x, y) has a constant term.

Proposition 2.1. Let A ∈ R^{m×n} and r = rank(A(0, 0)). There exists a product U of m × m-elementary matrices and a product V of n × n-elementary matrices such that

U(x, y) · A(x, y) · V (x, y) = ( \begin{matrix}f_{1}(x, y) & 0 & ⋯ & 0 & 0 \\ 0 & f_{2}(x, y) & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & f_{r}(x, y) & 0 \\ 0 & 0 & ⋯ & 0 & B(x, y) \end{matrix} ) ,

where f_{i} ∈ R with f_{i}(0, 0) ≠ 0 for i = 1, …, r, and B ∈ R^{(m−r)×(n−r)} with B(0, 0) = 0.

Observe that each of the diagonal entries f_{i}(x, y) can be factored over R:

(2.1)  f_{i}(x, y) = \frac{f_{i}(x, 0) · f_{i}(0, y)}{f_{i}(0, 0)}.

Corollary 2.2. In Proposition 2.1 we obtain the following isomorphism of Rmodules:

coker(A) ≅ ⨁_{i=1}^{r} k[x]/⟨f_{i}(x, 0)⟩ ⊕ ⨁_{i=1}^{r} k[y]/⟨f_{i}(0, y)⟩ ⊕ coker(B).

Proof. This follows from (2.1) and the observation that y ∈ ⟨f_{i}(x, 0)⟩ and x ∈ ⟨f_{i}(0, y)⟩. ■

For the proof of Proposition 2.1 we shall use the following lemma.

Lemma 2.3. Let (g_{1}, g_{2}, …, g_{n}) be a row vector over R such that at least one entry g_{i} has non-zero constant term. Then ⟨g_{1}, g_{2}, …, g_{n}⟩ is a principal ideal, its generator g has non-zero constant term, and there exists a product V of n × nelementary matrices with

(2.2)  (g, 0, 0, …, 0) = (g_{1}, g_{2}, …, g_{n}) · V.

Proof and Algorithm. Order the terms of each entry g_{i} using the purely lexicographic order ≺ induced from x > y. For a polynomial f, let in_{≺}(f) denote the highest (or initial) term of f with respect to the term order ≺. We now describe a sequence of elementary row operations:

(1) While there exist indices i and j such that in_{≺}(g_{i}) = c_{i} · x^{a_{i}}, in_{≺}(g_{j}) = c_{j} · x^{a_{j}} and a_{i} ≥ a_{j} do: replace g_{i} by g_{i} − \frac{c_{i}}{c_{j}} · x^{a_{i}−a_{j}} · g_{j}.

(2) While there exist indices i and j such that in_{≺}(g_{i}) = c_{i} · y^{a_{i}}, in_{≺}(g_{j}) = c_{j} · y^{a_{j}} and a_{i} ≥ a_{j} do: replace g_{i} by g_{i} − \frac{c_{i}}{c_{j}} · y^{a_{i}−a_{j}} · g_{j}.

(3) If there exist indices i and j such that in_{≺}(g_{i}) = c_{i} · x^{a_{i}} and in_{≺}(g_{j}) =

c_{j} · y^{a_{j}} then Let h(y) := g_{i}(0, y). If h(y) = 0 then replace g_{i} by g_{i} − \frac{c_{i}}{g_{j}(0,0)} · x^{a_{i}} · g_{j}. If h(y) ≠ 0 then 3.1 Let in_{≺}(h) = γ · y^{b}. 3.2. If b ≥ a_{j} then replace g_{i} by g_{i} − \frac{c_{j}}{γ} · y^{b−a_{j}} · g_{j}. 3.3. If b < a_{j} then replace g_{j} by g_{j} − \frac{γ}{c_{i}} · y^{a_{j}−b} · g_{i}. Return to step 1.

After termination of this algorithm all but one of the entries g_{i} are zero, and the unique non-zero entry has non-zero constant term. Permuting this entry (or its negative) into the first position can be done by a sequence of elementary operations. ■

Proof and Algorithm for Proposition 2.1. We proceed by induction on r, the conclusion being trivial for r = 0. If r ≥ 1, then we may assume that the upper left entry a_{11}(x, y) has non-zero constant term, after permuting rows and columns if necessary. Now apply the algorithm of Lemma 2.3 to the first row of A. The new matrix looks like

A · V =: B = ( \begin{matrix}b_{11}(x, y) & 0 & 0 & ⋯ & 0 \\ b_{21}(x, y) & b_{22}(x, y) & b_{23}(x, y) & ⋯ & b_{2n}(x, y) \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ b_{m1}(x, y) & b_{m2}(x, y) & b_{m3}(x, y) & ⋯ & b_{mn}(x, y) \end{matrix} ) ,

where b_{11}(0, 0) ≠ 0. Let I be the principal ideal generated by the first column of B. If I is generated by b_{11}, then there exists a product U of elementary matrices such that

U · A · V = U · B = ( \begin{matrix}b_{11}(x, y) & 0 & 0 & ⋯ & 0 \\ 0 & b_{22}(x, y) & b_{23}(x, y) & ⋯ & b_{2n}(x, y) \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & b_{m2}(x, y) & b_{m3}(x, y) & ⋯ & b_{mn}(x, y) \end{matrix} ) ,

and we are done by induction. If not, then the ideal I is generated by a proper factor c_{11} of b_{11}. In this case we apply the algorithm of Lemma 2.3 to the first column of B to get

U · A · V =: C = ( \begin{matrix}c_{11}(x, y) & c_{12}(x, y) & c_{13}(x, y) & ⋯ & c_{1n}(x, y) \\ 0 & c_{22}(x, y) & c_{23}(x, y) & ⋯ & c_{2n}(x, y) \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & c_{m2}(x, y) & c_{m3}(x, y) & ⋯ & c_{mn}(x, y) \end{matrix} ) ,

where c_{11}(0, 0) ≠ 0. Let J be the principal ideal generated by the first row of C. If J is generated by c_{11}, then we are done by the same argument as above. If not, then the ideal J is generated by a proper factor d_{11} of c_{11}. In this case we apply the algorithm of Lemma 2.3 to the first row of C ... etc...etc... Clearly, this process must terminate since the chain of proper factors a_{11}, b_{11}, c_{11}, d_{11}, … cannot become infinite. ■

For practical implementations it is possible to improve the above algorithm, for instance by employing the techniques used in Kannan’s polynomial time algorithm for Smith normal forms [Ka]. We close this section by noting the following consequence of Proposition 2.1.

Corollary 2.4. (Suslin Stability) Every invertible matrix A ∈ SL_{n}(R), n ≥ 1, can be factored into a product of elementary matrices over R.

Proof. If A ∈ SL_{n}(R) then A(0, 0) ∈ SL_{n}(k). Therefore we have r = m = n in Proposition 2.1. We see that U · A · V is a diagonal matrix with determinant ∏_{i=1}^{n} f_{i}(x, y) = 1. This implies that each polynomial f_{i} is a constant. After applying additional elementary row and column operations over k we may assume f_{1} = ⋯ = f_{n} = 1. The formula A = U^{−1} · V^{−1} then gives us a factorization of A into elementary matrices. ■

III. Computing A Separated Representation

In this section we shall compute Gröbner bases for a submodule N of R^{m}. Such computations are carried out over the ambient polynomial ring k[x, y]. (We refer to Chapter 3 in [ALo] for Gröbner bases of modules.) If a_{1}(x, y), …, a_{n}(x, y) are (representatives of) generators of N and {e_{1}, …, e_{m}} is the standard basis of k[x, y]^{m}, then we represent N as the submodule N′ of k[x, y]^{m} generated by {a_{1}(x, y), …, a_{n}(x, y), xye_{1}, …, xye_{m}}. Every reduced Gröbner basis G′ of N′ contains one of the elements xye_{i}, xe_{i}, ye_{i}, e_{i} for each i. We regard G′ minus all elements xye_{i} as the Gröbner basis G of N.

Let A ∈ R^{m×n} such that A(0, 0) = 0, let N be the submodule of R^{m} spanned by the columns of A, and let M = R^{m}/N = coker(A). Let G_{1} (resp. G_{2}) be the reduced Gröbner basis of N with respect to the purely lexicographic term order y > x (resp. x > y), where term order (in k[x, y]) comes before position, and let G := G_{1} ∪ G_{2}. Let A_{1}(x), A_{2}(y) and A_{3}(x, y) be the matrices whose column vectors are, respectively, G ∩ k[x]^{m}, G ∩ k[y]^{m} and G \ (G ∩ (k[x]^{m} ∪ k[y]^{m})). Clearly, G generates N, so that M = coker(A) = coker(A_{1}(x), A_{2}(y), A_{3}(x, y)).

Lemma 3.1. Let N_{i} denote the column R-span of A_{i} for i = 1, 2, 3. Then

(3.1)  N_{3} ∩ k[x]^{m} ⊆ N_{1} and N_{3} ∩ k[y]^{m} ⊆ N_{2}.

Proof. This follows from the elimination properties of lexicographic Gröbner bases. ■

In the remainder of this section we connect our algorithm to some of Levy’s work. We show that the construction leading up to Lemma 3.1 allows the computation of a separated representation of the indecomposable module M, which plays a central role in Levy’s classification. The following theorem is not needed subsequently, and the reader only interested in the algorithm may skip to Section IV.

Definition. (Levy, [L1, Sect. 1])

(1) An R-module S is separated if S is an R-submodule of a direct sum S_{1} ⊕S_{2}, where S_{1} is a module over k[x] and S_{2} is a module over k[y].

(2) A separated representation of an R-module M is an R-module epimorphism φ : S ↠ M such that S is a separated R-module, and S is “as close as possible” to M in the sense that, if φ admits a factorization

φ : S ⟶^{f} S′ ↠ M,

with S′ also a separated R-module, then f must be one-to-one.

Levy shows that if S is a pullback ring of two arbitary rings over a common semisimple artinian quotient ring, then every S-module has a separated representation, which is unique up to isomorphism. The separated representation of a module may be thought of as a pullback module “closest” to it. The following result can be viewed as a constructive proof, independent of Levy’s result, of the existence of separated representations for modules over our ring R = k[x, y]/⟨xy⟩.

Theorem 3.2. Let A_{1}(x), A_{2}(y), A_{3}(x, y) be m-rowed matrices without constant terms whose column R-spans N_{1}, N_{2}, N_{3} satisfy the property (3.1) in Lemma 3.1.

(1) The module M′ = coker(A_{1}(x), A_{2}(y)) is separated.

(2) The canonical map from M′ onto M = coker(A_{1}(x), A_{2}(y), A_{3}(x, y)) is a separated representation of M.

Proof. For part (1) we apply the criterion in Lemma 2.9 of [L1]: An R-module M′ is separated if and only if ⟨x⟩ · M′ ∩ ⟨y⟩ · M′ = 0. Let m′ be any element in ⟨x⟩ · M′ ∩ ⟨y⟩ · M′. Then there exist vectors u, v ∈ R^{m} such that m′ = xu and m′ = yv in M′. This implies xu−yv ∈ N_{1} +N_{2}. More precisely, there exist vectors λ and μ such that

x · u(x, y) − y · v(x, y) = A_{1}(x) · λ(x, y) + A_{2}(y) · μ(x, y) in R^{m}.

The fact that the entries in A_{2} have no constant term implies that x · u(x, 0) = A_{1}(x) · λ(x, 0) and hence xu ∈ N_{1}. This proves that m′ is the zero element in M′.

For part (2) we apply the criterion for separated representations in Proposition 2.3 (ii) of [L1]. Let ϕ denote the canonical map from M′ onto M. We need to verify that

(3.2) ker(ϕ) ⊆ ⟨x, y⟩ · M′  and  ker(ϕ) ∩ ⟨x⟩ · M′ = ker(ϕ) ∩ ⟨y⟩ · M′ = 0.

The kernel of ϕ is generated by the columns of A_{3}(x, y), modulo N_{1} + N_{2}. The left hand inclusion in (3.2) holds because each entry in A_{3}(x, y) lies in the ideal ⟨x, y⟩. The equations on the right hand side of (3.2) are a direct consequence of the hypothesis (3.1). ■

We record the following algorithmic criterion for separatedness of R-modules.

Corollary 3.3. Let A ∈ R^{m×n} with A(0, 0) = 0 and let G be the reduced Gröbner basis for the column R-span of A with respect to \underline{any} term order on k[x, y]^{m}. Then M = coker(A) is a separated R-module if and only if G ⊂ k[x]^{m} ∪ k[y]^{m}.

Proof. The “if”-direction is a corollary of Theorem 3.2 (1). For the “only-if”- direction we suppose that m = m(x, y) is a vector in G \ (G ∩ (k[x]^{m} ∪ k[y]^{m})). Our hypothesis A(0, 0) = 0 implies that m(0, 0) = 0, and therefore m(x, y) = m(x, 0)+m(0, y). Since the Gröbner basis G is reduced, neither m(x, 0) nor m(0, y) lies in the column R-span of A. Therefore, in the quotient the vectors m(x, 0) and −m(0, y) represent the same non-zero element of ⟨x⟩ · M ∩ ⟨y⟩ · M . By Lemma 2.9 of [L1], we conclude that M is not separated. ■

IV. The parallel Smith normal form

The algorithm developed in this section will be used subsequently as a subroutine in the transformation of the output B(x, y) of Proposition 2.1. We will call the output of our next algorithm the parallel Smith normal form.

Proposition 4.1. Let A_{1} ∈ k[x]^{m×n_{1}} and A_{2} ∈ k[y]^{m×n_{2}} be matrices with the same number of rows such that A_{1}(0) = 0 and A_{2}(0) = 0. Then one can compute products of elementary matrices U ∈ SL_{m}(R), V_{1} ∈ SL_{n_{1}}(k[x]), and V_{2} ∈ SL_{n_{2}}(k[y]) such that the following identity holds over R:

U(x, y) · ( A_{1}(x) A_{2}(y) ) · ( \begin{matrix}V_{1}(x) & 0 \\ 0 & V_{2}(y) \end{matrix} ) =

( \begin{matrix}f_{1}(x) & 0 & ⋯ & 0 & 0 & ⋯ & 0 & g_{1}(y) & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & f_{2}(x) & ⋯ & 0 & 0 & ⋯ & 0 & 0 & g_{2}(y) & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & f_{r}(x) & 0 & ⋯ & 0 & 0 & 0 & ⋯ & g_{s}(y) & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \end{matrix} ) ,

such that f_{i+1}(x) divides f_{i}(x) for i = 1, …, r − 1.

Proof and Algorithm. If A_{1}(x) = 0 or A_{2}(y) = 0, then the problem reduces to the ordinary Smith normal form over k[x], resp. k[y]. Therefore we may assume that A_{1}(x) ≠ 0.

We apply the Smith normal form algorithm over k[x] to the matrix A_{1}(x). As the result we get products of elementary matrices U′(x) and V′_{1}(x) such that

\begin{aligned}& U′(x) · ( A_{1}(x) A_{2}(y) ) · ( \begin{matrix}V′_{1}(x) & 0 \\ 0 & I \end{matrix} ) = \\ ( & \begin{matrix}f_{1}(x) & 0 & ⋯ & 0 & 0 & ⋯ & 0 & h_{11}(y) & h_{12}(y) & ⋯ & h_{1n_{2}}(y) \\ 0 & f_{2}(x) & ⋯ & 0 & 0 & ⋯ & 0 & h_{21}(y) & h_{22}(y) & ⋯ & h_{2n_{2}}(y) \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & f_{r}(x) & 0 & ⋯ & 0 & h_{s1}(y) & h_{s2}(y) & ⋯ & h_{sn_{2}}(y) \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 0 & h_{m1}(y) & h_{m2}(y) & ⋯ & h_{mn_{2}}(y) \end{matrix} & ) \end{aligned} (4.1)

where f_{i+1}(x) divides f_{i}(x) for i = 1, …, r − 1. We next perform elementary row operations determined by the first column of the matrix (h_{ij}(y)). An operation of the form “replace h_{i1} by h_{i1} − c · y^{α} · h_{j1}” is called allowed if α > 0 or i > j. If α > 0 then this row operation does not change the left hand diagonal matrix diag(f_{1}(x), …, f_{r}(x)), because x · y = 0 !! If α = 0 and i > j then the left hand diagonal matrix diag(f_{1}(x), …, f_{r}(x)) can be restored by an elementary column operation, because f_{i}(x) divides f_{j}(x).

The next step is to diagonalize the y-part of the matrix, without disturbing the Smith normal form of the x-part, just accomplished. This can be done essentially by applying the Smith normal form algorithm to the y-part, except that only allowable row operations are to be used. Note that in the output of the following algorithm no assertions are made about any divisibility properties of the diagonal entries.

Set j := 1. While j ≤ n_{2} do:

(1) If column j of the y-part is zero, go to Step (4). Otherwise, select the highest non-zero entry among all entries of minimum degree. Then perform allowable row operations until the j-th column contains exactly one non-zero entry.

(2) If this non-zero entry has minimal degree among all entries in its row, then perform elementary column operations to get all other entries in the row to have smaller degree. If this makes these other entries all zero, go to Step (3). Otherwise locate the first column to the right of column j with an entry in this row of minimal degree, and switch the two columns. Then go to Step (1).

(3) Perform elementary column operations on the x-part of the matrix to restore its Smith normal form.

(4) Set j := j + 1, and return to Step (1).

(5) Now permute the columns of the y-part to obtain the desired diagonal form. ■

Note that this procedure can result in zero diagonal entries in the y-part of matrix (4.1) above row s.

We now return to the main algorithm, after the reduction in Proposition 2.1. Let A_{1}(x), A_{2}(y), A_{3}(x, y) be matrices computed by the method preceding Lemma 3.1. The first two matrices define a separated representation for the R-module

M = coker(A_{1}(x), A_{2}(y), A_{3}(x, y)).

We apply the parallel Smith normal form algorithm of Proposition 4.1 to the matrix pair (A_{1}(x), A_{2}(y)). We then redo the same row operations (defined by the matrix U) and no column operations also for the matrix A_{3}(x, y). This process yields a new presentation matrix (F (x), G(y), H(x, y)) for our module M. After deleting zero columns, if necessary, and performing further row and column operations, as described below, the presentation matrix satisfies the following properties:

(1) F (x) = diag (f_{1}(x), f_{2}(x), …, f_{r}(x), 0, …, 0), a diagonal matrix;

(2) G(y) = diag (g_{1}(y), g_{2}(y), …, g_{s}(y), 0, …, 0), a diagonal matrix;

(3) every entry in the i-th row of H(x, y) is a k-linear combination of f_{i}(x)/x and g_{i}(y)/y.

Condition (3) can be accomplished as follows. First of all, if f_{r}(x) or some g_{i}(y) is a nonzero constant, then we can use elementary row and column operations to clear out all entries in the r-th, resp. i-th, row and column. Permuting rows and columns, we can split off a nonzero 1 × 1-matrix without changing the module M. Thus, we may assume that deg(f_{i}) > 0, and g_{i} = 0 or deg(g_{i}) > 0 for all i. Write the (i, j)-entry of H(x, y) as

h_{ij}(x, y) = u(x) + v(y).

If necessary, perform elementary column operations to achieve that deg(u) < deg(f_{i}), and v = 0 or deg(v) < deg(g_{i}). It follows from Part (2) of Theorem 3.2 that x · u is a scalar multiple of f_{i} and y · v is a scalar multiple of g_{i}. Condition (3) now follows. If max(r, s) = t < m, then the last m − t rows of the matrix (F (x), G(y), H(x, y)) are all zero. We delete these zero rows. This amounts to splitting off the free module R^{m−t} = span_{R}{e_{t+1}, …, e_{m}} as a direct summand from the R-module M. Therefore we shall from now on assume that t = m.

V. Localization

Definition. An R-module is local if all of its associated primes are contained in the maximal ideal ⟨x, y⟩.

The next step in our algorithm presents an R-module M as a direct sum of local modules and modules over k[x] and k[y]. We shall use the abbreviation [r_{i}] to denote an m×m-diagonal matrix diag(r_{1}, r_{2}, …, r_{m}) over R. After the procedure in Section 4, we can factor out powers of x from f_{i}(x) and powers of y from g_{i}(y), and achieve that our module M is now presented by a matrix of the form

(5.1)  ( [x^{a_{i}+1}f_{i}(x)] , [y^{b_{i}+1}g_{i}(y)] , [x^{a_{i}}f_{i}(x)] · A + [y^{b_{i}}g_{i}(y)] · B ).

If f_{i}(x) = 0 for all i, then the subsequent algorithm for a normal form for (5.1) reduces to a Smith normal form computation over k[y], so we will assume that (5.1) has non-zero x-entries. In this case the matrix is subject to the following four conditions:

(1) the matrix has no zero rows, and f_{i}(0) ≠ 0 for all i = 1, …, r; if g_{i}(y) ≠ 0, then g_{i}(0) ≠ 0;

(2) A and B are scalar matrices over k having m rows and the same number n of columns;

(3) the three blocks of the matrix (5.1) satisfy the elimination property (3.1);

(4) the exponents a_{1}, …, a_{m}, b_{1}, …, b_{m} are non-negative integers, such that a_{i+1} ≤ a_{i}, and if a_{i} = a_{i+1}, then b_{i+1} ≥ b_{i}.

Condition (3) follows directly from Lemma 3.1. To achieve (4) it may be necessary to perform additional row and column permutations to arrange the b_{i} in the asserted order.

The decomposition of our given module M into local modules and modules over the coordinate rings is effected by the following explicit transformation.

Proposition 5.1. There exists a sequence of elementary row and column operations over R which transforms the following cokernel-preserving extension of our given matrix (5.1)

U = ( \begin{matrix}[ 1 ] & 0 & 0 & 0 & 0 \\ 0 & [ 1 ] & 0 & 0 & 0 \\ 0 & 0 & [x^{a_{i}+1}f_{i}(x)] & [y^{b_{i}+1}g_{i}(y)] & [x^{a_{i}}f_{i}(x)] · A + [y^{b_{i}}g_{i}(y)] · B \end{matrix} )

into the matrix (5.2)

V = ( \begin{matrix}[f_{i}(x)] & 0 & 0 & 0 & 0 \\ 0 & [g_{i}(y)] & 0 & 0 & 0 \\ 0 & 0 & [x^{a_{i}+1}] & [δ_{i}y^{b_{i}+1}] & [x^{a_{i}}f_{i}(0)] · A + [y^{b_{i}}g_{i}(0)] · B \end{matrix} )

where δ_{i} = 1 if g_{i}(y) ≠ 0, δ_{i} = 0 otherwise, and in [g_{i}(y)] zeroes must be skipped.

Proof. The algorithm for the asserted transformation gets applied to the rows of the matrix in question. First assume that g_{1}(0) ≠ 0. Then permute columns and add a 2 × 2-identity matrix in the upper left hand corner of (5.1) to obtain the matrix

( \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & 1 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & x^{a_{1}+1}f_{1}(x) & y^{b_{1}+1}g_{1}(y) & a_{11}x^{a_{1}}f_{1}(x) + b_{11}y^{b_{1}}g_{1}(y) & ⋯ & ∗ \\ 0 & 0 & 0 & 0 & ∗ & ⋯ & ∗ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \end{matrix} ) ,

which has the same cokernel as (5.1). Here a_{1}, b_{1} are nonnegative integers and f_{1}(0) ≠ 0. Performing elementary row and column operations we transform this matrix into

( \begin{matrix}1 & 0 & f_{1}(x) & 0 & 0 & ⋯ & 0 \\ 0 & 1 & 0 & g_{1}(y) & 0 & ⋯ & 0 \\ −x^{a_{1}+1} & −y^{b_{1}+1} & 0 & 0 & a_{11}x^{a_{1}}f_{1}(x) + b_{11}y^{b_{1}}g_{1}(y) & ⋯ & ∗ \\ 0 & 0 & 0 & 0 & ∗ & ⋯ & ∗ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \end{matrix} )

without changing the rest of the matrix. Since f_{1} and g_{1} have non-zero constant term, we can find polynomials u, u′, v, v′ such that the following hold:

u(x)f_{1}(x) + u′(x)x^{a_{1}+1} = 1  and  v(y)g_{1}(y) + v′(y)y^{b_{1}+1} = 1,

and u(0) ≠ 0 ≠ v(0). Using these polynomials we can now perform elementary row and column operations to obtain the matrix

(\begin{matrix}0 & −u′(0)y^{b_{1}+1} & f_{1}(x) & 0 & a_{11}x^{a_{1}}f_{1}(x)u′(x) + b_{11}y^{b_{1}}g_{1}(y)u′(0) & ∗ \\ −v′(0)x^{a_{1}+1} & 0 & 0 & g_{1}(y) & a_{11}x^{a_{1}}f_{1}(x)v′(0) + b_{11}y^{b_{1}}g_{1}(y)v′(y) & ∗ \\ −x^{a_{1}+1} & −y^{b_{1}+1} & 0 & 0 & a_{11}x^{a_{1}}f_{1}(x) + b_{11}y^{b_{1}}g_{1}(y) & ∗ \\ 0 & 0 & 0 & 0 & ∗ & ∗ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix} ) .

Using the facts that f_{1} and g_{1} have non-zero constant term and that f_{1} and g_{1} divide the first, resp. second, summand of the non-zero entries in their respective rows to the right, we can use elementary column operations and column permutations to obtain the matrix

( \begin{matrix}f_{1}(x) & 0 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & g_{1}(y) & 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & x^{a_{1}+1} & y^{b_{1}+1} & a_{11}x^{a_{1}}f_{1}(0) + b_{11}y^{b_{1}}g_{1}(0) & ⋯ & a_{1n}x^{a_{1}}f_{1}(0) + b_{1n}y^{b_{1}}g_{1}(0) \\ 0 & 0 & 0 & 0 & ∗ & ⋯ & ∗ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋯ & ⋮ \\ 0 & 0 & 0 & 0 & ∗ & ⋯ & ∗ \end{matrix} ) .

If g_{1}(y) = 0, then add only a 1 × 1-identity matrix and perform an appropriately modified procedure.

Now apply the same procedure to the row of this matrix which contains the exponents a_{2}, b_{2}, etc.. Likewise, if f_{i}(x) = 0, that is, if i > r, then add only a 1 × 1-identity matrix and perform an appropriately modified procedure. Finally permute columns to put the matrix into the form V. This completes the proof. ■

The transformation in Proposition 5.1 expresses the module M as the direct sum of the modules k[x]/⟨f_{i}(x)⟩, k[y]/⟨g_{i}(y)⟩, i = 1, …, m, and the cokernel of a matrix of the form

(5.3)  ([x^{a_{i}+1}] , [δ_{i}y^{b_{i}+1}] , [x^{a_{i}}] · A + [y^{b_{i}}] · B).

Subsequently, let us denote such a matrix by

( [x^{a_{i}+1}] [y^{b_{j}+1}] C(x, y) ) .

In (5.3) we have incorporated the constants f_{i}(0) and g_{i}(0), which appeared in (5.2), into the new scalar matrices A and B. The hypotheses (1)-(4) stated in the beginning of this section remain valid for the matrix (5.3).

VI. The Local Normal Form

In this section we derive the normal form for the matrix (5.3) by a sequence of elementary operations. In the output the left and middle part are diagonal matrices which are obtained from the ones in (5.3) by permutation of the diagonal entries. The right part C(x, y) will be written as a sum of matrices, each of which is indecomposable and is in normal form. Our algorithm follows the treatment in [NR2] (which is a corrected version of [NR1]).

Step 1: Use elementary row and column operations to transform (5.3) so that the left two blocks remain diagonal matrices, and in the right block C(x, y) = [x^{a_{i}}] · A + [y^{b_{i}}] · B the matrix A is the identity matrix, possibly with additional rows of zeros, such as

A = ( \begin{matrix}I \\ 0 \end{matrix} ) .

This is accomplished as follows. Locate the lowest row of C(x, y) with a non-zero x-entry, and permute columns so that it appears in the last column of C(x, y). Now use elementary row and column operations to clear out all other non-zero x-entries in the row and the column containing this entry. Of course, the row operations disturb the diagonal form of the two left blocks of the matrix (5.3). The row operations carried out are all of the form: multiply a row by a monomial c · x^{a} and add it to a row above it. Note that these operations are NOT allowed operations as defined in Section 4. However, the newly created off-diagonal monomials in x have the same exponent as the diagonal x-entry in the same row. Thus, we can clear them out by a column operation. If a > 0 then this row operation does not affect the diagonal y-part. If a = 0 then the newly created off-diagonal power of y has exponent greater than or equal to that of the diagonal entry, by virtue of Condition (4) after (5.1).

Now proceed to the next higher row. If it contains a non-zero x-entry, then repeat the procedure. If it has no non-zero x-entry, then make it the last row and push all the rows that were below it up by one. Note that if the [x^{a_{i}+1}]-part of the matrix contains a diagonal entry with a_{i} = 0, then the entries in the corresponding row of A are all zero. Otherwise C(x, y) would contain an entry of the form a+by^{b_{i}} with a a unit of k. We could then use elementary row operations to eliminate all x-entries in the corresponding column, and restore the diagonal form of the first two blocks to obtain a column in C(x, y) which only contains y-entries. But this contradicts the elimination property (3).

Once no more rows with non-zero x-entries are left, delete zero columns and permute rows to achieve the desired form for A. Furthermore, permute rows so that the a_{i} corresponding to zero rows of A are in decreasing order. Then permute columns to restore the diagonal form of the x- and y-parts. Observe that these row permutations may destroy the decreasing order on the a_{i} in the diagonal x-part of the large matrix. However, the a_{i} in the upper part which correspond to non-zero rows of A will still be in decreasing order. Likewise, the decreasing order of the a_{i} in C(x, y) is preserved. Also, note that if a zero column appears in A sometime during this process, then the corresponding column in B must also be zero, otherwise the elimination property (3) would be violated. Therefore it is admissible to delete zero columns in A and the corresponding zero columns in B, and we may assume that neither A nor B contains any zero columns.

All subsequent transformations are intended to change the shape of B. If they alter the shape of A or the two diagonal parts, then we will always perform column operations to restore them.

Step 2: We assign weights to the rows and columns of the matrix C(x, y). If a column contains an entry x^{a}, then the weight of this column is a. Similarly, if a row contains an entry y^{b} (in which case all nonzero y-entries in this row also have exponent b), then we assign the weight b to it. If it contains no y-entries we assign to it the weight ∞. We partition C(x, y) into horizontal and vertical strips so that in each horizontal strip all rows have the same weight and in each vertical strip all columns have the same weight. Thus, C(x, y) is divided into blocks of the form x^{a} · U + y^{b} · V, where U and V are matrices over k. A block is called a y-block if U is the zero matrix, and it is called an xy-block otherwise. Following is an example of a matrix with horizontal and vertical weights indicated:

( \begin{matrix}& 5 & 5 & 2 & 2 & 1 \\ ∞ & x^{5} & 0 & 0 & 0 & 0 \\ 3 & y^{3} & x^{5} + y^{3} & y^{3} & 0 & 0 \\ 1 & 0 & 0 & x^{2} & y & y \\ 3 & y^{3} & 0 & y^{3} & x^{2} + y^{3} & y^{3} \\ 4 & 0 & 0 & y^{4} & 0 & x + y^{4} \\ 1 & 0 & y & 0 & 0 & y \end{matrix} )

Note that each column of C(x, y) must contain non-zero x- and y-entries, because of elimination property (3), therefore every vertical strip contains an xy-block.

Introduce further horizontal partitions in C(x, y) so that for all horizontal strips the a_{i} in the left diagonal x-part are equal.

Step 2.1: Now consider all the horizontal strips with lowest horizontal weight. Choose the highest one for which the large matrix does not contain any x-entries. Suppose there is no such strip. Consider the highest strip corresponding to zero rows of A. If the a_{i} occuring in this strip (which are all equal) are greater than or equal to all a_{j} occuring in horizontal strips of lowest weight above this strip, then choose it. Otherwise choose the highest strip of lowest horizontal weight.

This choice will ensure that when we subsequently perform row operations we can restore the shape of A as well as the diagonal x-part.

Step 2.2: In this horizontal strip choose the non-zero block with the highest vertical weight, that is, the leftmost non-zero block; call it B. In the example above, B is a 1 × 1-block containing the entry y.

Step 2.3: If the block B is a y-block then proceed as follows:

Step 2.3.1: Perform elementary row and column operations to put B into the form

( \begin{matrix}[y^{b}] & 0 \\ 0 & 0 \end{matrix} ) .

The vertical and possibly the horizontal strip containing B contains an xy-block. Since we have now disturbed the diagonal form of A within this xy-block we need to apply elementary column and row operations to restore it; likewise, permute columns to restore the left x- and y-diagonal parts of (5.3).

Step 2.3.2: Introduce a new horizontal and vertical partition in the matrix C(x, y) so that B contains only zero and identity blocks. For any xy-block contained in the same horizontal or vertical strip as B introduce further partitions in C(x, y) so that the upper left hand part of this xy-block is square. Now we use the non-zero entries in B to clear out their rows and columns in C(x, y) of y-entries. Note that, by the choice of B, there are no non-zero y-entries in the horizontal strip of B and to its left, and all y-entries in the vertical strip of B above it occur to a higher power, or to the same power if the horizontal strip contains no x-entries. So the elementary row operations to clear them out will not disturb the x-part of the matrix (5.3). Clearing out y-entries to the right and below B may produce extraneous x-entries, but these can be cleared out by elementary row and column operations, since the x-entries are arranged on the diagonal with decreasing exponents. Now select the next lower horizontal strip with the same y-weight, if there is one. Otherwise, move to the horizontal strips of the next highest y-weight, and go to Step 2.2.

We remark that in subsequent iterations the diagonal form of the current block B may be destroyed again. It may end up as a general matrix with nonsingular coefficient matrix.

Step 2.4: Now suppose that B is an xy-block. If B is not square, then introduce further horizontal and vertical partitions into the matrix C(x, y) so that the upper left hand part of B is square. Now return to Step 2.1. If B is square, then B = x^{a} · I − y^{b} · V, where I is an identity matrix and V is an arbitrary square matrix over k. In this case we proceed as follows:

Step 2.4.1: Compute the rational canonical form (or Frobenius form) of the matrix V:

(6.1)  P^{−1} · V · P = C(f_{1}^{n_{1}}) ⊕ C(f_{2}^{n_{2}}) ⊕ ⋯ ⊕ C(f_{r}^{n_{r}}).

Here f_{1}, …, f_{r} are either the zero polynomial or irreducible monic polynomials in k[t], n_{1}, …, n_{r} are positive integers, and C( ·) denotes taking the companion matrix. (For details see e.g. [Sha, Chapter 11]).

Step 2.4.2: Apply the row operations defined by P^{−1} and the column operations defined by P to the output of Step 1 in the given strips. This replaces the block B by

(6.2)  P^{−1} · B · P = ⨁_{i=1}^{r} (x^{a} · I − y^{b} · C(f_{i}^{n_{i}})).

Now restore the diagonal form of the left x- and y-diagonal parts using the column operations defined by right multiplication with P. Introduce further partitions into C(x, y), according to the decomposition of P^{−1} · B · P and go to Step 2.1.

Step 2.4.3: Suppose that B is of the form x^{a} ·I +y^{b} ·C(f_{i}^{n_{i}}) . If f_{i} has non-zero constant term, then C(f_{i}^{n_{i}}) is invertible. In this case we can use the non-zero yentries of (6.2) to clear out all other y-entries in their rows and columns in C(x, y). Now remove this block as a direct summand from our presentation matrix (5.3).

If f_{i} = t, then transform C(f_{i}^{n_{i}}) into Jordan canonical form. Introduce partitions according to the decomposition into elementary Jordan blocks. For each singular elementary Jordan block introduce further partitions to separate the top row and right-most column. Now go to Step 2.5.

If f_{i} = 0, then go to Step 2.5.

Step 2.5: We return to Steps 2.1 and 2.2 and proceed with the next block B.

Step 3: After one complete round of iterations in Step 2, we have now reached the following situation. The rows and columns of the matrix C(x, y) are partitoned such that

(1) all blocks are square, and each non-zero block has the form X = x^{a} · I or has the form Y = y^{b} · V where a, b are positive integers and V is a non-singular matrix;

(2) each horizontal strip contains at most one non-zero Y -block;

(3) each vertical strip contains exactly one non-zero X-block and one non-zero Y -block.

Furthermore, the x- and y-parts of the matrix (5.3) are still in diagonal form. By permuting blocks, we can transform C(x, y) into a direct sum of matrices of the following two types:

(6.3)  ( \begin{matrix}X & 0 & 0 & ⋯ & 0 & Y \\ Y & X & 0 & ⋯ & 0 & 0 \\ 0 & Y & X & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ... & X & 0 \\ 0 & 0 & 0 & ⋯ & Y & X \end{matrix} );

(6.4)  ( \begin{matrix}X & 0 & 0 & ⋯ & 0 & 0 \\ Y & X & 0 & ⋯ & 0 & 0 \\ 0 & Y & X & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ... & X & 0 \\ 0 & 0 & 0 & ⋯ & Y & X \\ 0 & 0 & 0 & ⋯ & 0 & Y \end{matrix} ) .

Step 4: Consider the case (6.4). By conjugation with a suitable scalar block diagonal matrix, we simultaneously transform all Y -blocks into diagonal matrices of the form y^{b} · I. If any of the blocks are larger than 1 × 1, then we permute the rows and columns to decompose our matrix into a sum of smaller matrices of the same type. If all blocks have size 1 × 1, then the matrix is indecomposable.

Step 5: It remains to consider the matrices of type (6.3). By a conjugation as in Step 4, we can simultaneously diagonalize all Y -blocks except the one in the upper right corner. Once this has been accomplished, the upper right Y -block can be transformed into rational canonical form. The rational canonical form is decomposed into r blocks as in (6.1), and the matrix decomposes accordingly into r indecomposable matrices.

We illustrate this process for the matrix

(6.5)  C(x, y) = ( \begin{matrix}x^{a_{1}} · I & 0 & 0 & y^{b_{1}} · V_{1} \\ y^{b_{2}} · V_{2} & x^{a_{2}} · I & 0 & 0 \\ 0 & y^{b_{3}} · V_{3} & x^{a_{3}} · I & 0 \\ 0 & 0 & y^{b_{4}} · V_{4} & x^{a_{4}} · I \end{matrix} ) .

Let V := V_{1}V_{4}V_{3}V_{2} and define P by the relation (6.1). The transformation matrix

Q := ( \begin{matrix}P & 0 & 0 & 0 \\ 0 & V_{2}P & 0 & 0 \\ 0 & 0 & V_{3}V_{2}P & 0 \\ 0 & 0 & 0 & V_{4}V_{3}V_{2}P \end{matrix} ) gives us

(6.6) Q^{−1} · C(x, y) · Q = ( \begin{matrix}x^{a_{1}} · I & 0 & 0 & y^{b_{1}} · ⨁_{i=1}^{r} C(f_{i}^{n_{i}}) \\ y^{b_{2}} · I & x^{a_{2}} · I & 0 & 0 \\ 0 & y^{b_{3}} · I & x^{a_{3}} · I & 0 \\ 0 & 0 & y^{b_{4}} · I & x^{a_{4}} · I \end{matrix} )

By permuting blocks, we can now decompose (6.6) as a direct sum:

(6.7) Q^{−1} · C(x, y) · Q = ⨁_{i=1}^{r} ( \begin{matrix}x^{a_{1}} · I & 0 & 0 & y^{b_{1}} · C(f_{i}^{n_{i}}) \\ y^{b_{2}} · I & x^{a_{2}} · I & 0 & 0 \\ 0 & y^{b_{3}} · I & x^{a_{3}} · I & 0 \\ 0 & 0 & y^{b_{4}} · I & x^{a_{4}} · I \end{matrix} ) .

Step 6: This step is optional and intended to merge blocks whenever possible. Suppose our matrix (6.3) is indecomposable and has the form as in (6.7). Denote the weight of the i-th vertical strip by a_{i} and the weight of the j-th horizontal strip by b_{j}. In this way, we obtain a sequence of weights (a_{1}, b_{1}), …, (a_{n}, b_{n}). We reorder this sequence so that it is the periodic repetition of the first t weights

(a_{1}, b_{1}), …, (a_{t}, b_{t}); (a_{1}, b_{1}), …; …; (a_{1}, b_{1}), …, (a_{t}, b_{t})

for the smallest possible t ≤ n. If t = n then we call the sequence aperiodic. Let n = tq. Now we rearrange the horizontal and vertical strips of (6.3) in such a way that the sequence of weights becomes aperiodic, by placing the (it + j)-th strip, for 0 ≤ i < q, 0 < j ≤ t, into the position of the (i + 1 + (j − 1)q)-th strip. Then, for each α = 1, …, t, combine the strips q(α − 1) + 1, …, qα, which have equal weight, into one. Observe that the first and the last (horizontal and vertical) strips stay unchanged, so that the type of (6.3) is preserved under these transformations. Now the sequence of weights is aperiodic.

This completes the local normal form algorithm. If all rows and columns have the same weight, then we are in the situation considered by Weierstrass and Kronecker; see [Ga, Ch. 12].

VII. The Classification

We summarize the final output of our normal form algorithm.

Theorem 7.1. Let A(x, y) be an m × n-matrix over R = k[x, y]/⟨xy⟩. Then the algorithm of the previous sections computes invertible matrices U and V over R such that

U · ( \begin{matrix}I & 0 \\ 0 & A(x, y) \end{matrix} ) · V = [f_{i}(x)] ⊕ [g_{j}(y)] ⊕ B_{1}(x, y) ⊕ ⋯ ⊕ B_{r}(x, y),

where ⊕ denotes direct sum of matrices, I is an s × s-identity matrix, with 0 ≤ s ≤ 2m, f_{i}(0) ≠ 0, g_{j}(0) ≠ 0, and each matrix B_{i}(x, y) is either zero or is of one of the following three types:

(7.1)  y^{b} · C(f^{m}) − x^{a} · I,  or

(7.2)  ( \begin{matrix}ϵy^{b_{0}} & x^{a_{1}} & 0 & 0 & … & 0 & 0 \\ 0 & y^{b_{1}} & x^{a_{2}} & 0 & … & 0 & 0 \\ 0 & 0 & y^{b_{2}} & x^{a_{3}} & … & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 & 0 \\ 0 & 0 & 0 & … & y^{b_{n−1}} & x^{a_{n}} & 0 \\ 0 & 0 & 0 & … & 0 & y^{b_{n}} & δx^{a_{n+1}} \end{matrix} ) , or

(7.3)  ( \begin{matrix}x^{a_{1}} · I & 0 & 0 & … & 0 & y^{b_{1}} · C(f^{m}) \\ y^{b_{2}} · I & x^{a_{2}} · I & 0 & … & 0 & 0 \\ 0 & y^{b_{3}} · I & x^{a_{3}} · I & … & 0 & 0 \\ ⋮ & ⋮ & ... & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & … & y^{b_{n}} · I & x^{a_{n}} · I \end{matrix} ) ,

where a_{i}, b_{j} are positive integers, ϵ, δ are zero or one, I stands for identity matrices of various sizes, and C(f^{m}) is the companion matrix of a power of an irreducible polynomial f ∈ k[t] with f(0) ≠ 0. In (7.3) we may assume that the sequence (a_{1}, b_{1}), …, (a_{n}, b_{n}) is aperiodic. Furthermore, each of the matrices (7.1)-(7.3) is indecomposable.

Proof. Let

( [x^{a_{i+1}}] [y^{b_{i+1}}] C)

be the part of matrix (5.3) corresponding to an indecomposable block. If C is a block of form (7.1) or (7.3), then the columns of the first two diagonal parts are multiples of columns of C, so we may delete them. If C is of the form (7.2), with the first and last column deleted, then all but possibly the first column of [x^{a_{i+1}}] and the last column of [y^{b_{i+1}}] are multiples of columns of C. Thus we may delete all but these two columns, which results in matrix (7.2).

The assertion about the indecomposability of (7.1)-(7.3) was shown in [NR2, pp. 643–644]. ■

We rephrase Theorem 7.1 in module-theoretic terms to get the classification of finitely generated R-modules. Theorem 7.2 is a special case of the results of L. Levy [L2].

Theorem 7.2. Every finitely generated module over R = k[x, y]/⟨xy⟩, k a field, can be decomposed as a direct sum of indecomposable modules of the following types:

(1) free modules of rank one;

(2) indecomposable modules over k[x], and indecomposable modules over k[y];

(3) modules presented by indecomposable matrices of types (7.1)-(7.3). This decomposition is unique up to the order of the factors. In other words, the Krull-Schmidt Theorem holds for the ring R = k[x, y]/⟨xy⟩,

Proof. The Krull-Schmidt Theorem holds for R as a consequence of [L2, Theorem 10.2], since the coordinate rings k[x] and k[y] have trivial ideal class group. ■

Two examples might help illustrate how the matrix description translates into a module description. For instance, the matrix

( x^{3} y^{2} x^{2} − 12y)

is of type (7.2) and presents a cyclic module M, obtained from its separated representation M′ = R/⟨x^{3}, y^{2}⟩ by dividing out the submodule R · (x^{2} − 12y). We will see this module reappear in the next section.

The matrix

( \begin{matrix}x^{5} & 0 & y^{4} & 0 & x^{4} \\ 0 & x^{3} & 0 & y^{8} & y^{7} \end{matrix} )

is of type (7.1) and presents the module obtained by taking the sum of the two separated modules R/⟨x^{5}, y^{4}⟩ and R/⟨x^{3}, y^{7}⟩ and “amalgamating” part of their socles by dividing out the submodule generated by (x^{4}, y^{7}). For a detailed description of the structure of R-modules in relation to their presentation see [L2].

VIII. Mutually Annihilating Matrices

In this section we discuss an application of our algorithm to a problem in linear algebra. A pair (C, D) of n × n-matrices with entries in k is called mutually annihilating if CD = DC = 0. The geometric meaning of this condition is best understood by considering a fixed matrix C of rank r. Then CD = DC = 0 holds if and only if the transpose of D is a normal vector at C to the manifold of all rank r matrices. The maximum rank among all such matrices D is precisely n − r. Hence the set of pairs of mutually annihilating matrices is the total conormal variety to the rank stratification of n × n-matrices. (Thanks to Tom Braden for pointing this out to us.) The general linear group GL_{n}(k) acts on this conormal variety via (C, D) ↦ (U^{−1}CU, U^{−1}DU). Our problem is to compute a normal form for mutually annihilating matrices modulo this action.

Any pair of mutually annihilating n × n-matrices (C, D) defines the structure of an R-module on k^{n} as follows: a polynomial p in R = k[x, y]/⟨xy⟩ sends v ∈ k^{n} to p(C, D) · v. We denote this R-module by M_{C,D}. The following three facts are easily verified:

(1) Every artinian R-module M can be written in the form M_{C,D}.

(2) Two pairs (C, D) and (C′, D′) are equivalent under simultaneous conjugation by GL_{n}(k) if and only if the R-modules M_{C,D} and M_{C′,D′} are isomorphic.

(3) The R-module M_{C,D} is isomorphic to the cokernel of the n × 2n-matrix

(8.1)  A(x, y) = ( C − x · I_{n} , D − y · I_{n}).

To prove assertion (1), we simply choose a k-basis of M and define C and D to be the matrices which represent (the k-endomorphisms given by) multiplication by x and y.

These considerations gives rise to the following normal form algorithm for a given pair (C, D) of mutually annihilating n×n-matrices: Apply our normal form algorithm for R-modules to the matrix A(x, y) in (8.1).

A familiar special case of this algorithm occurs when D = 0 and C is an arbitrary n × n-matrix over k. In this case our algorithm computes the Smith normal form over k[x] of the matrix A(x) = (C − x · I_{n}). From the output we can read off the rational canonical form or Jordan canonical form of C; see Chapter 11 in [Sha].

We close with an explicit example for n = 3. Let the input matrices be

C = ( \begin{matrix}16 & 16 & 26 \\ 34 & −20 & −19 \\ −28 & 8 & 4 \end{matrix} )  and  D = ( \begin{matrix}6 & 12 & 18 \\ 33 & 66 & 99 \\ −24 & −48 & −72 \end{matrix} ) .

Our algorithm will generate an identity such as the following:

U · ( C − xI_{3} , D − yI_{3} ) · V = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & x^{2} − 12y & 0 & 0 & 0 \end{matrix} )

where U = ( \begin{matrix}1 & 0 & 0 \\ −1/2 & 0 & 1 \\ x/18 + y/108 + 1/2 & 1 & x/72 − y/54 + 3/2 \end{matrix} )

and V = ( \begin{matrix}0 & 0 & −18 & −18 & 18y & −18y \\ 1/16 & 1/72 & 9 − x & −99 & 63y & 18y \\ 0 & 0 & 0 & 72 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1296 & 0 \\ 0 & −1/54 & 12−x/6 & −3x/2 & −648 & −972 \\ 0 & 0 & 0 & 0 & 0 & 648 \end{matrix} ) .

This shows that M_{C,D} is isomorphic to the indecomposable module M = R/⟨x^{2} − 12y⟩. Choosing the k-basis {1, x, y} for M, we see that (C, D) is equivalent to (C′, D′) where

C′ = ( \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 12 & 0 \end{matrix} )  and  D′ = ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ) .

References

[ALo] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, American Mathematical Society, Graduate Studies in Math. 3, Providence, 1994.

[ALa] D. M. Arnold and R. C. Laubenbacher, Finitely Generated Modules over Pullback Rings, to appear, J. Algebra.

[DK] R. K. Dennis and M. I. Krusemeyer, K_{2}(A[X, Y]/XY), A Problem of Swan, and Related Computations, J. Pure Appl. Algebra 15 (1979), 125–148.

[Ga] F. R. Gantmacher, The Theory of Matrices, Chelsea Publishing Co., New York, 1959.

[GP] I. M. Gel’fand and V. A. Ponomarev, Indecomposable Representations of the Lorentz Groups, Russ. Math. Surveys 23 (1968), 1–58.

[Ka] R. Kannan, Solving Systems of Linear Equations Over Polynomials, Theoretical Computer Science 39 (1985), 69–88.

[Kl] S. Kleiman, r-Special Subschemes and an Argument of Severi’s, Advances in Math 22 (1976), 1–31.

[Kr] H. P. Kraft, Geometric Methods in Representation Theory, Representations of Algebras (M. Auslander and E. Lluis, eds.), Springer Lecture Notes in Math 944, Springer Verlag, 1982, pp. 180–258.

[L1] L. S. Levy, Modules Over Pullbacks and Subdirect Sums, J. Algebra 71 (1981), 50–61.

[L2] , Mixed Modules Over ℤG, G Cyclic of Prime Order, and Over Related Dedekind Pullbacks, J. Algebra 71 (1981), 62–114.

[L3] , Modules Over Dedekind-like Rings, J. Algebra 93 (1985), 1–116.

[NR1] L. A. Nazarova and A. V. Roiter, Finitely Generated Modules Over a Dyad of Two Local Dedekind Rings, and Finite Groups With an Abelian Normal Divisor of Index p, Math. USSR-Izvestija 3 (1969), 65–86.

[NR2] L. A. Nazarova, A. V. Roiter, V. V. Sergeichuk and V. M. Bondarenko, Application of Modules Over a Dyad for the Classification of Finite p-Groups Possessing an Abelian Subgroup of Index p and of Pairs of Mutually Annihilating Operators, J. Soviet Mathematics 3 (1975), 636-653.

[Sha] R.Y. Sharp, Steps in Commutative Algebra, Cambridge University Press, London Math. Soc. Student Texts 19, Cambridge, 1990.

Reinhard C. Laubenbacher, Department of Mathematics, New Mexico State University, Las Cruces, NM 88003

E-mail address: reinhard@nmsu.edu

Bernd Sturmfels, Department of Mathematics, University of California, Berkeley, CA 94720-3840

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