GENERATORS AND RELATIONS FOR MATRIX ALGEBRAS

JON F. CARLSON^{∗} AND GRAHAM MATTHEWS

Dedicated to Charles Leedham-Green on the occasion of his 65th birthday

1. Introduction

The aim of this paper is to describe algorithms for the extraction of generators and relations for an algebra that is generated by a finite set of matrices. The idea of representing algebras by generators and relations and using noncommutative Gröbner bases to perform computational operations is certainly not new. There are many reasons for wanting to regard an algebra A defined over a field k as the quotients of free algebras or noncommutative polynomial rings with coefficients in k. One of the most important reasons is that such a construction makes it possible to define representations of the algebra A. A representation is a homomorphism \xymatrix{ρ : A \ar[r] & Mat_{n}(k)} of A into the algebra of n × n k-matrices. Computationally, this means the assignment of an n×n matrix to each of the generators of the algebra A. This could be done in almost any setting. However, the only way to be certain that the assignment ρ defines a representation is to verify that the relations among the generators are also satisfied by the matrices assigned to the generators. This means that we must know the relations as polynomials in the generators of A.

For the most part, computer algebra systems that allow for the definition of algebras in terms of generators and relations start with exactly that premise. That is, in these systems, the input for the algebras must be as generators and relations provided by the user. However, in many practical situations, the algebras arise as other structures. Certainly one of the most universal such structures is that of a matrix algebra. By this we mean the subalgebra of Mat_{n}(k), for some n, generated by some finite collection α_{1}, …, α_{t} of n × n matrices. Indeed, given any finite dimensional algebra over a field k, it is often routine to embed it in an algebra of matrices. In general, matrix algebras can be very difficult to analyze and manipulate. Even finding the dimension of such an algebra requires enumerating a basis which must be computed by some means or other.

The main point of this paper is that we can deal with a matrix algebra A by constructing a Wedderburn type decomposition of the algebra. That is we create primitive idempotents to build the semi-simple part of the algebra and then search for generators for the radical of the algebra. Along the way we construct a condensed algebra eAe where e is a sum of orthogonal primitive idempotents, one for each simple A-module. The condensed algebra is Morita equivalent to A and the generators and relations for the radical can be found in eAe. The relations involving the radical generators are created experimentally.

Date: January 31, 2006.

This research was supported in part by a grant from NSF.

We should emphasize that the algorithms avoid computing a basis for the algebra. Computing a basis for a large algebra can be a very difficult calculation in terms of time and memory. In some cases we have seen that the basis for an algebra can be computed far more efficiently by computing the presentation, using the algorithms of this paper and then applying Gröbner basis machinery to get a basis for the algebra.

The analysis has several collateral benefits. For one thing we get a test for membership in the algebra. That is, we can test to see if an n × n matrix is an element of A, and if it is in A, then we can write it as a word in the computed generators for A. The Cartan matrix for A and the dimensions of the projective modules for A are easily found using the output of the programs. We should emphasize that the algorithms avoid

The algorithms described in this paper are for dealing with matrix algebras defined over finite fields. Some of the algorithms may have analogs over infinite fields or fields of characteristic 0. However, we find it very convenient to have a Frobenius automorphism. In addition, the algorithms require a Meataxe program or some substitute for it. The best current implementations for the Meataxe work only for modules over finite fields.

The algorithms that we describe are implemented and available in the current release of the computer algebra system MAGMA [2]. Special thanks are due to John Cannon and Allan Steel of the MAGMA project for their help with the implementation. We offer some remarks on the running times and capabilities of the MAGMA programs in the last section of the paper.

Part of this paper was included in the doctoral dissertation of the second author [7].

Throughout the paper, an algebra will mean an algebra over a field with an identity element. However, a subalgebra will in general not contain the identity element of the parent algebra. Except in a few special circumstances, a module over an algebra will mean a right unital module.

2. Structure of algebras

In this section, we set some notation and discuss a few aspects of the structure of matrix algebras and how they apply to computer modeling. Throughout, we assume that k is a field of characteristic p > 0. Suppose that A is a finite dimensional algebra over k. The radical of A is a two-sided ideal which can be defined in various equivalent ways. It is the unique maximal nilpotent two-sided ideal. It is also the sum of all of the nilpotent right (or left) ideals and also the annihilator of the simple right (or left) A-modules. We denote the radical of A by Rad(A).

Something of the structure of A is expressed in the following theorems. These are the theorems of Wedderburn and proofs can be found in almost any standard text on algebras (for example see [3]). For notation, let Mat_{n}(K) denote the algebra of all n × n-matrices over the field K.

Theorem 2.1. Let A be a finite dimensional k-algebra.

(1) A/ Rad(A) is a semi-simple algebra, i.e. it is a direct sum of simple algebras.

So

A/ Rad(A) ≅ A_{1} ⊕ ⋯ ⊕ A_{r}

where each A_{i} is a simple k-algebra.

(2) A simple k-algebra is a full matrix algebra over a division algebra.

(3) If k is a finite field, then any finite dimensional division algebra over k is a field.

In particular, if B is a simple, finite dimensional k-algebra for k a finite field, then B ≅ Mat_{n}(K) for some n and some finite extension K of k. Another property of algebras over finite fields is the following.

Proposition 2.2. Suppose that A is a finite dimensional algebra defined over a finite field k. Then the sequence

\xymatrix{0 \ar[r] & Rad A \ar[r] & A \ar[r]^{ρ} & A/(Rad A) \ar[r] & 0}

is right split. That is, there is an algebra homomorphism \xymatrix{φ : A/(Rad A) \ar[r] & A} such that ρ ∘ φ is the identity on A/(Rad A), A′ = φ(A/(Rad A)) is a subalgebra of A and A ≅ A′ ⊕ Rad(A) as a direct sum of k-vector spaces.

We emphasize that the subalgebra A′ of the proposition is definitely not an ideal and there is no left splitting. Indeed, by Nakayama’s Lemma, if B ⊆ A were an ideal such that ρ(B) = A/(Rad A) then B = A. The proof of the proposition is known (see Corollary 4.1.11 in Volume 1 of [1]) and the proposition holds as long as the field k is separable. In the course of developing our algorithm we will give another, purely constructive proof. That is, our algorithm will construct the subalgebra A′.

The objects of study in this paper are matrix algebras defined over finite fields. If k is a field, by a matrix algebra over k we mean the algebra generated by a finite set α_{1}, …, α_{t} of matrices in Mat_{n}(k) for some n. We assume that the identity element of Mat_{n}(k) is an element of A.

Our aim is to take a matrix algebra A given as above and to compute its structure. This means computing its semisimple subalgebra A′ as in the proposition, finding generators for the radical of A and finally constructing a presentation of A in terms of generators and relations. To this end we need the following.

Proposition 2.3. Suppose that A is a matrix algebra over k, generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Let V be the restriction of the natural n-dimensional Mat_{n}(k)-module to an A-module. Then every irreducible A-module is isomorphic to a composition factor of V.

Proof. Observe that V is faithful as an A-module. That is, there is no a ∈ A such that va = 0 for all v ∈ V. So suppose that S is a simple A-module. Then there is a primitive idempotent e ∈ A such that eA is the projective indecomposable module covering S. That is there is a map \xymatrix{eA \ar[r] & S} whose kernel is contained in eA ∩ Rad A. The fact that V e ≠ {0} means that this is a nonzero homomorphism of eA to V. Hence V must have a composition factor isomorphic to S. □

3. A presentation for a full matrix algebra

Throughout this section, assume that A ≅ Mat_{n}(K), where K is a finite extension of the base field k which is finite and has characteristic p. In practice, k is usually the prime field k = 𝔽_{p}. However, we do not want this to be a part of our assumptions. We are interested in finding an efficient presentation of A in terms of generators and relations over k. That is, we want to write A as a quotient P/I where P is an algebra of noncommuting polynomials in finitely many variables over k and I is an ideal in P. To this end, we start with the following well known result. Note that we do not depend on the actual isomorphism of A with Mat_{n}(K), though we rely very much on the fact that the two are isomorphic.

Proposition 3.1. Suppose that e_{1}, …, e_{n} is a complete set of mutually orthogonal primitive idempotents in the algebra A and that τ ∈ A is an element with the property that τ^{n} = Id_{A} and for each i such that 1 ≤ i < n, we have τ^{−1}e_{i}τ = e_{i+1}. Let β be an element in e_{1}Ae_{1} ≅ K such that β generates the multiplicative group of nonzero elements of e_{1}Ae_{1}. Then we have the following.

(1) ∑_{i=1}^{n} e_{i} = Id_{A}.

(2) The elements β and τ generate A as a k-algebra.

Proof. The proposition is standard linear algebra and we leave it to the reader to fill in the details. Suppose that V is the natural module for the algebra A which we identify with Mat_{n}(k) under some isomorphism. For each i choose a nonzero element v_{i} in V e_{i}. Now, v_{1}, …, v_{n} is a k-basis for V. Let U be the matrix that has the vectors v_{1}, …, v_{n} as rows. Conjugating by U, we transform the element e_{i} into the standard idempotent matrix with 1 in the (i, i) position and zero everywhere else. Likewise when τ is conjugated by U, it becomes the permutation matrix

(\begin{matrix}0 & 1 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & 1 & 0 & ⋯ & 0 \\ 0 & 0 & 0 & 0 & ⋯ & 1 \\ 1 & 0 & 0 & 0 & ⋯ & 0 \end{matrix}) ,

and when β is conjugated by U it becomes the matrix

(\begin{matrix}a & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 \end{matrix})

where a is a generator for the multiplicative group of nonzero elements in the field K.

From this analysis, both statements of the proposition should be obvious. Note here that if q = |K| then β^{q−1} = e_{1}. Moreover, the matrix with 1 in the (i, j)-position and zeros elsewhere is the conjugate under U of the element τ^{i−1}β^{q−1}τ^{j−1}. □

With the associations in the proof of the proposition we can prove the following. Let h(t) ∈ k[t] be the minimal polynomial of the element a ∈ K and let q be the number of elements of K.

Theorem 3.2. Suppose that A ≅ Mat_{n}(K) with n > 1 and K as above. Then A has a presentation as a k-algebra as F/I, where F = k⟨B, T ⟩ is the free k-algebra in noncommuting variables B and T, and I is the ideal in F generated by the elements:

(1) T^{n} − 1_{F},

(2) Bh(B),

(3) BT^{k}B for all 1 ≤ k ≤ n − 1 and

(4) ∑_{j=1}^{n} T^{n−j}B^{q−1}T^{j} − 1_{F}.

Proof. Define a map ϑ : F → A by letting ϑ(B) = β and ϑ(T) = τ. Then it should be clear from the representation of A in the proof of the proposition, that ϑ is surjective and that the ideal I is contained in the kernel of ϑ. Let J denote the kernel of ϑ. It remains only to show that J ⊆ I.

First we note that if m ∈ F is a monomial, then modulo I, m has the form T^{a}B^{b}T^{c} for some values of a, b and c such that 0 ≤ a, c ≤ n − 1. Because h(t) divides t^{q−1} − 1, we can assume that 0 ≤ b ≤ q − 1. Indeed, if b > 0, then modulo I, m has the form

m ≡ T^{a}B(a_{0} + a_{1}B + ⋯ + a_{u−1}B^{u−1})T^{b}

where u is the degree of h(t) and a_{0}, …, a_{u−1} are elements of k. This all follows from relations implied by (1), (2) and (3). On the other hand if b = 0, then modulo I, m is congruent to T^{a} for 0 ≤ a ≤ n − 1. In this case, using relations implied by (4), we can assume that

m = m · 1_{F} ≡ T^{a} ∑_{j=1}^{n} T^{n−j}B^{q−1}T^{j}

which again can be written as a k-linear combination of monomials of the form T^{a}B^{b}T^{c} for 0 ≤ a, c ≤ n − 1 and 1 ≤ b ≤ u.

It follows that F/I has k-dimension at most un^{2} which is the dimension of A ≅ F/J. Since I ⊆ J we must have that I = J as desired. □

Remark 3.3. In the case that n = 1 and hence A = K, then we know that A ≅ k[B]/(h(B)). This presentation is consistent with the one given above. That is, when n = 1, the relations implied by (2) and (4) in the theorem become Bh(B) = 0 and B^{q−1} = 1. But notice that

h(B) = (Bh(B))B^{q−2} − (B^{q−1} − 1)h(B).

Hence the ideal generated by these two relations coincides with the ideal generated by h(B).

4. A presentation for a semi-simple algebra

Using Theorem 3.2 and Remark 3.3 we can give a standard presentation for a semisimple algebra over a field of finite characteristic. Assume that k has characteristic p > 0.

Theorem 4.1. Suppose that A is a finite dimensional semisimple algebra over k. Then A ≅ ∑_{i=1}^{r} Mat_{n_{i}}(K_{i}) for some integers n_{1}, …, n_{r} and extensions K_{1}, …, K_{r} of the base field k. Assume that r > 1. For each i, let q_{i} = |K_{i}|, and let h_{i}(X) be the minimal polynomial in k[X] of a generator for the multiplicative group of nonzero elements in K_{i}. If for some i, n_{i} = 1, then we renumber so that n_{i} > 1 for i = 1, …, s and n_{s+1} = ⋯ = n_{r} = 1. Then A has a presentation as a k-algebra as F/I, where

F = k⟨B_{1}, …, B_{r}, T_{1}, …, T_{s}⟩

is the free k-algebra in noncommuting variables, and I is the ideal in F generated by the elements:

(1) T_{i}^{n_{i}+1} − T_{i} for i = 1, …, s,

(2) T_{i}^{n_{i}}B_{i} − B_{i}, B_{i}T_{i}^{n_{i}} − B_{i} for i = 1, …, s,

(3) B_{i}h_{i}(B_{i}), for i = 1, …, r,

(4) B_{i}T_{i}^{j}B_{i} for all 1 ≤ j ≤ n_{i} − 1 and i = 1, …, s.

(5) ∑_{j=1}^{n_{i}} T_{i}^{n_{i}−j}B_{i}^{q−1}T_{i}^{j} − T_{i}^{n_{i}},

(6) ∑_{j=1}^{s} T_{i}^{n_{i}} + ∑_{j=s+1}^{r} B_{i}^{q_{i}−1} − 1_{F},

(7) B_{i}B_{j}, T_{i}T_{j}, B_{i}T_{j}, T_{i}B_{j} for all i ≠ j.

Proof. The relations implied by (7) are the consequence of the direct sum decomposition. The relation in (6) is a consequence of the fact that the identity of A is a sum of the identities of the summand algebras. Everything else comes from the results of the last section. □

Remark 4.2. There is some redundancy in the relations. For example, the fact that the relations in (2) are in I follows from the inclusion of elements (6) and (7).

5. Algorithmic beginnings

We can now describe the first step in the presentation algorithm. The aim of the first step is to compute the structure of the semisimple part of the matrix algebra A.

Algorithm 5.1. Suppose that k is a finite field of characteristic p.

Input: A matrix algebra A generated by α_{1}, …, α_{t} ∈ Mat_{n}(k).

Output: A sequence of simple matrix algebras A_{1}, …, A_{r} which are the summands of A/(Rad A), together with the sequence of maps \xymatrix{φ_{i} : A \ar[r] & A_{i}} and the sequence of degrees of the centers of the matrix algebras as extensions of k.

Description. The basic tool here is the Meataxe, which is implemented in both MAGMA [2] and GAP [4] as well as having a stand-alone implementation called the C-Meataxe [8]. The Meataxe finds submodules of a module and by successive application, it computes composition series and composition factors. Hence by Proposition 2.3 we get all of the simple A-modules S_{1}, …, S_{r}. The simple quotient algebras of A are the images of the homomorphisms \xymatrix{φ_{i} : A \ar[r] & End_{k}(S_{i})} , and the radical of A is the intersection of the kernels of these maps. The Meataxe also computes the degrees of the extension over k of the commuting ring of ϕ_{i}(A) in End_{k}(S_{i}).

Remark 5.2. Note that the Meataxe actually returns the modules S_{i} for i = 1, …, r. The data for the module S_{i} is a sequence of matrices α_{i,1}, …, α_{i,t} ∈ Mat_{n_{i}}(k) where n_{i} is the k-dimension of S_{i}. For each j, the matrix α_{i,j} is the matrix of the action of α_{j} on S_{i}. The matrix algebra A_{i} is the subalgebra of Mat_{n_{i}}(k) generated by α_{i,1}, …, α_{i,t}, and the map φ_{i} takes α_{j} to α_{i,j}.

Remark 5.3. The maps \xymatrix{φ_{i} : A \ar[r] & A_{i}} are defined only on the generators. That is, for each α_{j} ∈ A we know that φ_{i}(α_{j}) = α_{i,j}. In practice we handle this situation by creating a free algebra P = k⟨X_{1}, …, X_{t}⟩, and maps \xymatrix{ϕ : P \ar[r] & A} , and \xymatrix{ϕ_{i} : P \ar[r] & A_{i}} such that ϕ(X_{j}) = α_{j} and ϕ_{i}(X_{j}) = α_{i,j} for all i = 1, …, r and j = 1, …, t. Then if have an element β ∈ A, to get its image under φ_{i} we must write β = ϕ(ω) for some ω ∈ P and then φ_{i}(β) = ϕ_{i}(ω).

We end this section with a note on random elements.

Remark 5.4. From time to time in the computations it is necessary to find a “random” element of the algebra A. In general, all we know about A is its generators and computing a basis for A could be an expensive exercise. In addition, we often want to be able to apply a homomorphism outlined in Remark 5.3. For this reason what we really want is to create a “random” word in the free algebra P then apply the map ϕ as in the remark. The “random” we use is random in the same sense as in early implementations of the Meataxe algorithm. That is, we simply add or multiply a few of the variables X_{1}, …, X_{t}. The variables, the operations and the number of operations are randomly chosen from a small set of options.

In some of the algorithms we need to compute random words in a subalgebra eAe where e is some idempotent in A. The problem here is that the subalgebra eAe is not, in general, generated by the elements eα_{1}e, …, eα_{t}e even though A is generated by α_{1}, …, α_{t}. So a “random” word in eAe is found by first computing a random word x in A, as above, and then replacing x by exe.

6. Idempotent decompositions: The algorithms.

In this section we describe the algorithms used for getting the generators for the semisimple part of a matrix algebra. We begin with an algebra A defined by matrices α_{1}, …, α_{t} ∈ Mat_{n}(k). Our aim is to construct the algebra A′ ≅ A/(Rad A) as described in Proposition 2.2. We pick up with the output of Algorithm 5.1. That is we have the algebra structure:

A′ ≅ ⨁_{i=1}^{r} A_{i}

where each A_{i} = Mat_{n_{i}}(K_{i}) is a simple algebra. Let d_{i} be the degree of the extension d_{i} = |K_{i} : k|. Remember that each A_{i} is a matrix algebra generated by elements α_{i,1}, …, α_{i,t} ∈ Mat_{d_{i}n_{i}}(k). In particular, the rank of any element of A_{i} must be a multiple of d_{i}. We also have the maps \xymatrix{φ_{i} : A \ar[r] & A_{i}} (see Remark 5.3).

We begin by decomposing the identity of A into idempotents corresponding to the simple quotient algebras. Algorithm 6.1. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k).

Input: The algebra A and the output of Algorithm 5.1.

Output: A sequence of orthogonal idempotent elements E_{1}, …, E_{r} such that for each i, φ_{j}(E_{i}) = δ_{i,j} Id_{A_{i}} and E_{1} + ⋯ + E_{r} = Id_{A}.

Description. The elements are chosen one by one and the orthogonality is assured by the choices. Beginning with i = 1, we do the following for each i.

(a). If i = r, then let E_{r} = Id_{A} − ∑_{j=1}^{r−1} E_{j}, and skip the remaining steps. (If

r = 1, then let E_{1} = Id_{A}.) Otherwise, we assume that i < r. (b). Choose a random element x in A as in Remark 5.4. (c). If i > 1, then replace x by uxu where u = Id_{A} − ∑_{j=1}^{i−1} E_{i}. Notice that this

assures that φ_{j}(x) = 0 for j < i. (d). For each j > i, compute g_{j}(X), the minimal polynomial for φ_{j}(x). Now

replace x by xg_{j}(x). Then the element x has the property that φ_{j}(x) = 0 for all j > i.

(e). If φ_{i}(x) is not invertible, then repeat starting at step (b). (f). Compute the minimum polynomial g(X) of φ_{i}(x). Note that g(X) must

have the form g(X) = h(X) + a where a ∈ k, a ≠ 0, and h(X) has no constant term. Replace x by q(x) where q(X) = −h(X)/a. Now we have that φ_{i}(x) = Id_{A_{i}}.

(g). At this point we know that x is an idempotent modulo the radical of A. That is, φ_{j}(x^{2} − x) = 0 for all j. So x^{2} − x is in Rad(A). If x^{2} − x ≠ 0 then replace x by x^{p}, so that (x^{p})^{2} − x^{p} = (x^{2} − x)^{p}. Repeat until x^{2} = x. Then let E_{i} = x.

We leave it to the reader to check that the algorithm performs the task that it claimed. ♠

Next we turn our attention to obtaining primitive idempotents in A corresponding to the primitive idempotents in each A_{i}. That is, for each A_{i} we want to find the elements β_{i} and τ_{i} as in Proposition 3.1. The reader might note that we give a proof of Proposition 2.2 in the process.

Fix i such that 1 ≤ i ≤ r. The next algorithm creates a complete set of orthogonal primitive idempotents for the subalgebra of A′ ⊆ A that is isomorphic to A_{i}. The algorithm is similar to that in 6.1. Algorithm 6.2. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k).

Input: The algebra A and the output of Algorithms 5.1 and 6.1.

Output: A sequence of orthogonal primitive idempotent elements f_{1}, …, f_{n_{i}} such that for each φ_{j}(f_{i}) = 0 for j ≠ i and ∑_{j=1}^{n_{i}} f_{j} = E_{i}.

Description. The elements are chosen one by one and the orthogonality is assured by the choices. For each j, beginning with j = 1, we do the following.

(a). If j = n_{i}, then let f_{j} = E_{i} − ∑_{ℓ=1}^{n_{i}−1} f_{ℓ}, and skip the remaining steps. In

particular, if n_{i} = 1, then we let f_{1} = E_{i}. Otherwise, we assume that j < n_{i}. (b). Choose a random element x in A as in Remark 5.4. (c). If j > 1, then replace x by uxu where u = E_{i} − ∑_{ℓ=1}^{j−1} f_{ℓ}. If j = 1, then

replace x by E_{i}xE_{i}. (d). Compute g(X), the minimal polynomial for φ_{i}(x). If g(X) has an irreducible

factor p(X) of degree d_{i}, then let q(X) = g(X)/p(X) and replace x by q(x) (note that q(X) must be divisible by X).

(e). If φ_{i}(x) has rank greater than d_{i} then repeat beginning at Step (b). Otherwise, we can use it to get a primitive idempotent in A_{i}. That is, we multiply x by random elements on the left or right until x is not nilpotent. Then replace x by a suitable power of itself which is idempotent.

(f). Let f_{j} = x. We now have orthogonal primitive idempotents f_{1}, …, f_{j}. Let j = j + 1 and repeat.

If at any point in the calculation we get φ_{i}(x) = 0, then go back to step (b) and repeat. ♠

In the previous algorithm, the index i was fixed. In future references, we call the element f_{j} constructed in the algorithm by the name e_{i,j}. In addition, to save notation, we let e_{i} = e_{i,1} (= f_{1}), the first primitive idempotent computed for A_{i} using the algorithm.

Now it is an easy search to find an element playing the role of β in Proposition 3.1, for the algebra A_{i} ⊆ A′. The algorithm is as follows. Again, the index i is fixed.

Algorithm 6.3. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k).

Input: The algebra A and the output of Algorithms 5.1, 6.1 and 6.2.

Output: An element β_{i} ∈ e_{i}Ae_{i} such that β_{i}^{q_{i}} = β_{i} but β_{i}^{m} ≠ β_{i} for all 1 < m < q_{i}.

Description. Notice that if p = 2 and d_{i} = 1 then we can let β_{i} = e_{i}. Otherwise, we perform the following task.

(a). Choose a random element y ∈ A and let x = e_{i}ye_{i}. If n_{i} > 1, then repeat until an element is found such that the minimal polynomial of φ_{i}(x) has the form Xg(X) where g(X) is irreducible of degree d_{i} in k[X]. In the case that n_{i} = 1, we repeat until the minimal polynomial of φ_{i}(x) is irreducible with degree d_{i} and with nonzero constant term. Note that if n_{i} > 1, then x is not invertible and its minimal polynomial must be divisible by X.

(b). Now find a linear combination of powers of x such that φ_{i}(x)^{q_{i}} = φ_{i}(x), but φ_{i}(x)^{m} ≠ φ_{i}(x) for all 1 < m < q_{i}. We know that x^{q_{i}} − x ∈ Rad(A). So replace x by x^{p} as necessary until x^{q_{i}} − x = 0. Then let β_{i} = x. ♠

We continue to assume that i is fixed. To finish the construction of the algebra A_{i} as a subalgebra of A, we need to construct the permutation matrix τ_{i} playing the role of τ in Proposition 3.1. Note that if n_{i} = 1 then this step is skipped. For notation let f_{j} = e_{i,j} be the primitive idempotent computed using Algorithm 6.2.

Algorithm 6.4. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithms 5.1, 6.1, 6.2 and 6.3

Output: A element τ_{i} ∈ E_{i}AE_{i} such that τ_{i}^{n_{i}−1}f_{j}τ_{i} = f_{j+1}, for j = 1, …, n_{i} − 1, τ_{i}^{n_{i}−1}f_{n_{i}}τ_{i} = f_{1}, and τ_{i}^{n_{i}} = E_{i}.

Description.

(a). We begin by choosing random elements b_{1}, …, b_{n_{i}} such that b_{j} ∈ f_{j}Af_{j+1} for j = 1, …, n_{i} − 1 and b_{n_{i}} ∈ f_{n_{i}}Af_{1} and such that φ_{i}(b_{j}) ≠ 0 for all j. This is accomplished, for example in the case that j = 1, by choosing a random element (in the sense of 5.4) b_{1} in A and replacing it by f_{1}b_{1}f_{2} until an element such that φ_{i}(b_{j}) ≠ 0 is found.

(b). Notice that φ_{i}(b_{1}b_{2} ⋯ b_{n_{i}}) is a nonzero element of φ_{i}(f_{1})A_{i}φ_{i}(f_{1}). Hence this element is equal to φ_{i}(β_{i})^{m} where β_{i} is the field generator constructed in 6.3 and for some m. So now replace b_{n_{i}} by b_{n_{i}}β_{i}^{q_{i}−m−1}. Then we have that

φ_{i}(b_{1}b_{2} ⋯ b_{n_{i}}) = φ_{i}(f_{1}).

(c). Let b = b_{1}b_{2} ⋯ b_{n_{i}}. A consequence of the above is that b − f_{1} ∈ Rad(A) and because b ∈ f_{1}Af_{1}, b and f_{1} commute. So for some integer m, b^{p^{m}} = f_{1}.

Now we replace b_{n_{i}} by b_{n_{i}}b^{p^{m}−1}. We get that b = b_{1}b_{2} ⋯ b_{n_{i}} = f_{1}.

(d). Finally, we let τ_{i} = b_{1} + ⋯ + b_{n_{i}}. ♠

Proposition 6.5. The elements β_{i} and τ_{i} constructed in 6.3 and 6.4 generate a subalgebra 𝔄_{i} of A that is isomorphic to A_{i} under the map φ_{i}. (Notice here that if r > 1, then we are not including Id_{A} in 𝔄_{i}).

Proof. The first thing that must be shown is that the element τ_{i} satisfies all of the properties claimed in the statement of output in 6.4. We assume the notation in the description of the algorithm. Remember that b_{j} ∈ f_{j}Af_{j+1} where the subscripts can be taken modulo n_{i}. We know that f_{1} = b_{1}b_{2} … b_{n_{i}}. From this is follows that the element b_{2} ⋯ b_{n_{i}}b_{1} is an idempotent in f_{2}Af_{2}. Since f_{2} is primitive, it must be that f_{2} = b_{2} ⋯ b_{n_{i}}b_{1}. Similarly, we can show that for any j,

f_{j} = b_{j} ⋯ b_{n_{i}}b_{1} ⋯ b_{j−1}.

Thus we have that

τ_{i}^{n_{i}−1}f_{j}τ_{i} = (b_{j−1} ⋯ b_{n_{i}}b_{1} ⋯ b_{j−1})(b_{j} ⋯ b_{n_{i}}b_{1} ⋯ b_{j−1})b_{j} = f_{j+1}.

Likewise it can be seen that τ_{i}^{n_{i}} = f_{1} + f_{2} + ⋯ + f_{n_{i}} = E_{i}, as desired.

From the above it follows that the elements φ_{i}(β_{i}) and φ_{i}(τ_{i}) satisfy the properties of the elements called ′′β′′ and ′′τ′′ in Proposition 3.1. Therefore, φ_{i} takes the subalgebra 𝔄_{i} surjectively onto A_{i}. Let F = k⟨B, T ⟩ be a free noncommuting algebra on two variables. Define \xymatrix{θ : F \ar[r] & A} be defined by θ(1_{F}) = E_{i}, θ(B) = β_{i} and θ(T) = τ_{i}. This is well defined since E_{i} is in 𝔄_{i} and is an identity for 𝔄_{i}. The proof is completed by noting that the kernel of θ is exactly the ideal I of theorem 3.2. □

By performing these operations for each i = 1, … r, we succeed in constructing the subalgebra A′ ≅ A/(Rad A).

Algorithm 6.6. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithms 5.1 and 6.1.

Output: Elements β_{i}, τ_{j}, i = 1, …, r, j = 1, …, s that generate a subalgebra of A that is isomorphic to A/(Rad A).

Description. For each i = 1, …, r, run Algorithms 6.2, 6.3, and 6.4 to get elements β_{i} and τ_{i} (if i ≤ s) such that β_{i}, τ_{i} ∈ E_{i}AE_{i} and β_{i}, τ_{i} generate a subalgebra 𝔄_{i} ⊆ A which is isomorphic to A_{i} under the map φ_{i}. ♠

Thus, we only need to show the following.

Theorem 6.7. The elements β_{i}, τ_{j}, for i = 1, …, r, j = 1, …, s, generate a subalgebra A′ ⊆ A which is isomorphic to A/(Rad A).

Proof. The only thing left to note is that since E_{i}E_{j} = 0 for i ≠ j and since 𝔄_{i} ⊆ E_{i}AE_{i}, the sum A′ = ∑_{i=1}^{r} 𝔄_{i} is direct and hence it is a subalgebra isomorphic to A/(Rad A) ≅ ∑_{i=1}^{r} A_{i} as asserted. □

7. Generators for the radical

At this point, we have seen how to construct the algebra A′ ≅ A/(Rad A) as a subalgebra of the algebra A. The next step is to find generators for the radical of A. In this case, “generators” should be taken to mean generators as an ideal. Together, the generators of A′ and the generators of Rad(A) will form a complete set of generators for the entire algebra A. One of the key points in this step is that a set of generators for the radical can be found in the condensed algebra eAe where e = ∑_{i=1}^{r} e_{i} is a sum of primitive idempotents, one for each of the simple quotient algebras A_{i}, i = 1, …, r. Here e_{i} (called f_{1} in Algorithm 6.2), is the first primitive idempotent corresponding to the quotient algebra A_{i}. We have the following proposition. The proof is well known [1], and we do not repeat it here.

Proposition 7.1. For each i = 1, …, r, let e_{i} be a primitive idempotent in A such that φ_{i}(e_{i}) is a primitive idempotent in A_{i} while φ_{j}(e_{i}) = 0 for j ≠ i. (In practice, we choose e_{i} = β_{i}^{q_{i}−1} in the notation of the last section.) Let e = ∑_{i=1}^{r} e_{i}. Then the subalgebra eAe is Morita equivalent to A.

We remind the reader that even though A is generated by α_{1}, …, α_{t}, it is not in general true that eAe is generated by eα_{1}e, …, eα_{t}e(for example, see [6]). Hence, the arguments that follow are necessary.

From here on we shall call the algebra eAe the (natural) condensed algebra of A. When the field is extended, it might be possible to obtain smaller subalgebras of A that are Morita equivalent to A. But eAe seems to be the optimal choice without some change in the coefficient ring for A.

Our major theorem on the generators of the radical is the following. For convenience of notation we introduce the following conventions

Notation 7.2. We continue the same notation as before. In order to prevent the notation from getting out of hand, we adopt the following exceptional conventions.

(a) For each i = 1, … r, let

β_{i}^{0} = β_{i}^{q_{i}−1} = e_{i},

be the first primitive idempotent constructed for the algebra 𝔄_{i} ⊆ A′, generated by β_{i} and τ_{i}, as a subalgebra of A.

(b) For each i = 1, …, r, let

τ_{i}^{0} = τ_{i}^{n_{i}} = E_{i}

Note that if s < i ≤ r, (in which case n_{i} = 1), then we are assuming that τ_{i} = E_{i} = e_{i} = β_{i}^{q_{i}−1}.

With these conventions in mind, let e_{i,j} = τ_{i}^{n_{i}+1−j}e_{i}τ_{i}^{j−1}. Thus e_{i,1} = e_{i} and E_{i} = ∑_{j=1}^{n_{i}} e_{i,j}. In addition, let \xymatrix{ψ_{i} : A_{i} \ar[r] & A} be the algebra homomorphism that is a right splitting for the map \xymatrix{φ_{i} : A \ar[r] & A_{i}} and such that ψ(A_{i}) = 𝔄_{i} ⊆ A′.

Theorem 7.3. The algebra A is generated by elements of the form (i). β_{i}, for i = 1, …, r, (ii). τ_{i}, for i = 1, …, s, (iii). e_{i}τ_{i}^{a}α_{u}τ_{j}^{b}e_{j}, for 0 ≤ a < n_{i}, 1 ≤ u ≤ t, 0 ≤ b < n_{j}, 1 ≤ i, j ≤ r and i ≠ j, (iv). e_{i}τ_{i}^{a}(α_{u} − ψ_{i}φ_{i}(α_{u}))τ_{i}^{b}e_{i}. for 0 ≤ a, b < n_{i}, 1 ≤ u ≤ t and i = 1, …, r.

The elements of types (iii) and (iv) are in the radical and generate the radical as an ideal.

Proof. We have that

Id_{A} = ∑_{i=1}^{r} E_{i} = ∑_{i=1}^{r} ∑_{j=1}^{n_{i}} e_{i,j}.

Consequently,

A = ∑_{i,j=1,1}^{r,r} ∑_{ℓ=1}^{n_{i}} ∑_{m=1}^{n_{j}} e_{i,ℓ}Ae_{j,m}.

where this sum is direct. For any element α ∈ A. we have that α = ∑ e_{i,ℓ}αe_{j,m}. Notice that if i ≠ j then e_{i,ℓ}αe_{j,m} ∈ Rad(A) since by construction the image of this element under φ_{v} is zero for any v.

Any element of A must be a linear combination of monomials in the elements α_{1}, …, α_{t}. Each of these monomials is a sum of monomials in the variables e_{i,ℓ}α_{u}e_{j,m} by the argument of the previous paragraph. So we see that the algebra A is generated by elements of the form e_{i,ℓ}α_{u}e_{j,m}. Now notice that

e_{i,ℓ}α_{u}e_{j,m} = τ_{i}^{n_{i}−ℓ+1}(e_{i}τ_{i}^{ℓ−1}α_{u}τ_{j}^{n_{j}−m+1}e_{j})τ_{j}^{m−1}.

Hence, together with the elements of type (i) and (ii) in the theorem, the elements of the form e_{i}τ_{i}^{a}α_{u}τ_{j}^{b}e_{j} for 1 ≤ i, j ≤ r and 1 ≤ u ≤ t generate A. When i ≠ j these element are of type (iii). In the case that i = j we have that

e_{i}τ_{i}^{a}α_{u}τ_{i}^{b}e_{i} ≡ e_{i}τ_{i}^{a}(α_{u} − ψ_{i}(φ_{i}(α_{u})))τ_{i}^{b}e_{i}

modulo the subalgebra A′ generated by the elements of type (i) and (ii). That is, ψ_{i}(φ_{i}(α_{u})) is in the subalgebra generated by β_{i} and τ_{i}. Hence, A is generated by elements as listed in the theorem. □

The following is now obvious.

Corollary 7.4. The k-algebra A is generated by elements of type (i) and (ii) and by elements in eAe where e = ∑_{i=1}^{r} e_{i}.

So now we have the main theorem of the section. Recall the Notation 7.2.

Theorem 7.5. The space Rad(eAe)/ Rad^{2}(eAe) is spanned as a k-vector space by classes modulo Rad^{2}(A) of elements of the form (iii′). β_{i}^{a}τ_{i}^{b}α_{u}τ_{j}^{c}β_{j}^{d} for 0 ≤ a < |K_{i} : k|, 0 ≤ b < n_{i}, 1 ≤ u ≤ t, 0 ≤ c < n_{j},

0 ≤ d < |K_{j} : k|, and 1 ≤ i, j ≤ r where i ≠ j, (iv′). β_{i}^{a}τ_{i}^{b}(α_{u} − ψ_{i}(ϕ_{i}(α_{u})))τ_{i}^{c}e_{i} for 0 ≤ a < |K_{i} : k|, 0 ≤ b, c < n_{i}, 1 ≤ u ≤ t, and

i := 1, …, r

Proof. We know from Theorem 7.3 that every element of A is a linear combination of monomials in the elements of type (i), (ii), (iii) and (iv). Moreover we know that the space of all monomials in the elements of types (i) and (ii) span the subalgebra A′ which is a complementary k-subspace to Rad(A) in the space A. It follows that if ω is in Rad(A) then ω can be written as a linear combinations of monomials in the elements of type (i), (ii), (iii) and (iv) such that every monomial in that linear combination has at least one factor an element of type (iii) or of type (iv). On the other hand, because elements of type (iii) and (iv) are in the radical of A, if such a monomial has two factors of type (iii) or (iv), then it is in Rad^{2}(A). Consequently, ω + Rad^{2}(A) can be written as a linear combination of cosets of the form γ_{1}αγ_{2} + Rad^{2}(A) where α is of type (iii) or (iv) and γ_{1}, γ_{2} are in A′. Now assume also that ω is in e(Rad A)e and that α is in e_{i}Ae_{j}. Then

γ_{1}αγ_{2} = eγ_{1}e_{i}αe_{j}γ_{2}e = (e_{i}γ_{1}e_{i})α(e_{j}γ_{2}e_{j}).

This is because, for x in A′, e_{ℓ}xe_{m} = 0 unless ℓ = m. Therefore we can assume that γ_{1} = e_{i}γ_{1}e_{i} = β_{i}^{g} and γ_{2} = e_{j}γ_{2}e_{j} = β_{j}^{h} for some g and h. The result now follows from the fact that β_{i}^{g} can be expressed as a linear combination of the elements β_{i}^{a} for 0 ≤ a < |K_{i} : k|. □

We immediately have the following.

Corollary 7.6. The algebra A is generated by elements of types (i), (ii), (iii′) and (iv′)

And we have the algorithm:

Algorithm 7.7. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k).

Input: The algebra A and the output of Algorithms 5.1 and 6.6.

Output: A set of generators for the radical as an ideal of A in the form of a k-spanning set for the space Rad eAe/(Rad^{2} eAe). The output is given in the form of a set of sets {W_{i,j}}, where W_{i,j} is the set of generators for the radical in e_{i}Ae_{j}.

Description. Compute W_{i,j} as the set of all of the elements of types (iii′) and (iv′), having i and j as the indicated indices. This done by straightforward matrix multiplication. Note that there are only a finite number of these elements. Then replace each W_{i,j} by a basis of the space spanned by its elements. ♠

It remains to get an actual basis for the radical of eAe. Such a basis will be important when we wish to find minimal set of generators of Rad(A) as well the relations among those generators of the algebra. It is clear that, for any u, Rad^{u}(A) = ∑ e_{i,ℓ} Rad^{u}(A)e_{j,m} as a direct sum of vector spaces. One of the main points of the following is that e_{i,ℓ} Rad^{u}(A)e_{j,m} = Rad^{u}(A) ∩ e_{i,ℓ}Ae_{j,m}. As in Algorithm 7.7, let W_{i,j} be the subspace of e_{i} Rad Ae_{j} spanned by the elements of type (iii′) and (iv′) for the specified i and j. What we know is that

(W_{i,j}+(Rad^{2}(A)∩e_{i}Ae_{j}))/(Rad^{2}(A)∩e_{i}Ae_{j}) = (Rad(A)∩e_{i}Ae_{j})/(Rad^{2}(A)∩e_{i}Ae_{j}).

Let W_{i,j}^{(2)} = W_{i,j} + ∑_{u=1}^{r} W_{i,u}W_{u,j} for any i and j. Inductively, let

W_{i,j}^{(v)} = W_{i,j}^{(v−1)} + ∑_{u=1}^{r} W_{i,u}^{(v−1)}W_{u,j}.

We need the following.

Lemma 7.8. For v ≥ 2 and any i and j, we have that

(W_{i,j}^{(v)} + (Rad^{v+1}(A) ∩ e_{i}Ae_{j}))/(Rad^{v+1}(A) ∩ e_{i}Ae_{j}) =
(Rad(A) ∩ e_{i}Ae_{j})/(Rad^{v+1}(A) ∩ e_{i}Ae_{j}).

Proof. We prove the case that v = 2 and leave the rest as an exercise. Clearly W_{i,j}^{(2)} ⊆ Rad(A) ∩ e_{i}Ae_{j}. So suppose that xy is in Rad^{2}(A) ∩ e_{i}Ae_{j} for x and y in Rad(A). Thus

xy = e_{i}xye_{j} = e_{i}x ( ∑_{ℓ,m=1,1}^{r,n_{ℓ}} e_{ℓ,m}) ye_{j}

= e_{i}x ∑_{ℓ=1}^{r} ∑_{m=1}^{n_{ℓ}} τ_{ℓ}^{n_{ℓ}+1−m}e_{ℓ}τ_{ℓ}^{m−1}ye_{j}

= ∑_{ℓ=1}^{r} ∑_{m=1}^{n_{ℓ}}(e_{i}xτ_{ℓ}^{n_{ℓ}+1−m}e_{ℓ})(e_{ℓ}τ_{ℓ}^{m−1}ye_{j})

Hence, xy = ∑_{ℓ=1}^{r} x_{ℓ}y_{ℓ} where x_{ℓ} ∈ e_{i}Ae_{ℓ} ∩ Rad(A) and y_{ℓ} ∈ e_{ℓ}Ae_{j} ∩ Rad(A). We have noted that for any ℓ, x_{ℓ} ≡ x′_{ℓ} and y_{ℓ} ≡ y′_{ℓ} modulo Rad^{2}(A) for some x′_{ℓ} ∈ W_{i,ℓ} and some y′_{ℓ} ∈ W_{ℓ,j}. It follows that xy ≡ ∑ x′_{ℓ}y′_{ℓ} modulo Rad^{3}(A). This combined with the fact that the classes of the elements in W_{i,j} modulo Rad^{2}(A) span the space (Rad(A) ∩ e_{i}Ae_{j})/(Rad^{2}(A) ∩ e_{i}Ae_{j}) is enough to prove the lemma in the case that v = 2. □

We can now compute a minimal set of generators for the radical of the algebra A.

Algorithm 7.9. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithms 5.1, 6.6 and 7.7.

Output: A set of generators for the radical of A and for each i and j, a k-basis for the coset space (e_{i}Ae_{j} ∩ Rad(A))/(e_{i}Ae_{j} ∩ Rad^{2}(A)).

Description. The output of Algorithm 7.7 is the sequence of sets W_{i,j} for 1 ≤ i, j ≤ r.

(a). Compute the spaces U_{i,j}^{(2)} = ∑_{ℓ=1}^{r} W_{i,ℓ}W_{ℓ,j}, U_{i,j}^{(3)} = ∑_{ℓ=1}^{r} U_{i,ℓ}^{(2)}W_{ℓ,j}, etc., until we get the zero space for all i and j. That is, we compute until U_{i,j}^{(m)} = {0} for all i and j.

(b). By Lemma 7.8, we have that

Rad(A) ∩ e_{i}Ae_{j} = W_{i,j} + U_{i,j}^{(2)} + U_{i,j}^{(3)} + …,

while

Rad^{2}(A) ∩ e_{i}Ae_{j} = U_{i,j}^{(2)} + U_{i,j}^{(3)} + …

Return the sets B_{i,j} for all i and j, where B_{i,j} is a complementary basis to Rad^{2}(A) ∩ e_{i}Ae_{j} in Rad(A) ∩ e_{i}Ae_{j}.

The union of the B_{i,j}’s is a k basis for Rad(A)/ Rad^{2}(A). ♠

8. Constructing the relations

To this point we have a collection of algorithms for the construction of a complete set of generators for the algebra A. The primary remaining task is to construct the relations among those generators. We continue the notation of the previous section. In particular, our list of generators consists of β_{i} for i = 1, …, r, and τ_{j} for j = 1, …, s, which generated the semisimple subalgebra A′, and generators z_{ℓ} for ℓ = 1, … m, which generate the radical. Note that every z_{ℓ} is in e_{i}Ae_{j} for some i and some j. In addition, for each i and j we have a basis B_{i,j} for the space e_{i}Ae_{j} ∩ Rad(A). Of course, in the case that i ≠ j we have that e_{i}Ae_{j} ⊆ Rad(A) and hence B_{i,j} is a basis for e_{i}Ae_{j}. Otherwise, we have that B_{i,i} together with the set {β_{i}^{ℓ}|ℓ = 0, …, d_{i} − 1} is a basis for e_{i}Ae_{i}. Here we recall that d_{i} = |K_{i} : k|. We continue the convention that β_{i}^{0} = e_{i}.

There are three types of relations that we need to compute. They are

(1) relations among the variables β_{1}, …, β_{r} and τ_{1}, …, τ_{s},

(2) relations among the variables z_{1}, …, z_{m}, and

(3) relations between the sets of variable {β_{1}, …, β_{r}} and {z_{ℓ}|z_{ℓ} ∈ e_{i}Ae_{j}} for all i and j.

The first type is easily dealt with. Fortunately, there is not even any computation to be done. That is, we have the following.

Lemma 8.1. The relations among the variables β_{1}, …, β_{r} and τ_{1}, …, τ_{s} are given as the images ψ(x) = 0 of the generators x of the ideal I in Theorem 4.1 under the map \xymatrix{ψ : P \ar[r] & A} such that ψ(B_{i}) = β_{i} and ψ(T_{i}) = τ_{i}.

The proof of the lemma is clear from the construction of the elements. That is, the Algorithms 6.2, 6.3 and 6.6 construct elements satisfying precisely these relations.

Next we consider the relations of type (2), relations among the generators of the radical. This is one of the more delicate of our algorithms. The objective is to obtain a set of relators that approximates a Gröbner basis for the ideal of relations. By the vector of an n × n matrix, we mean the vector of length n^{2} which is the concatenation of the rows of the matrix.

Algorithm 8.2. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithm 7.9.

Output: A complete set of generators for the ideal of relations among the generators z_{1}, …, z_{m} for the radical of A, as well as a basis for the radical of Rad(eAe) in the form of monomials in the elements z_{1}, …, z_{m}. The basis is a union of sets C_{i,j}, where C_{i,j} is a k-basis for Rad(A) ∩ e_{i}Ae_{j}.

Description. The classes of the elements z_{1}, …, z_{m} form a basis for the space Rad(eAe)/ Rad^{2}(eAe) and hence they are linearly independent over the base field k. We proceed by taking monomials in the elements z_{1}, …, z_{m} and searching for dependence relations (as k-vectors) of the monomials. We do this one degree at a time until every relation is a consequence of previous relations. That is, we stop at the point that we know that every monomial can be reduced, modulo the ideal generated by previously computed relations, to a linear combination of monomials of lower degree.

There are some important points that should be mentioned. First, recall that each z_{i} is contained in e_{a}Ae_{b} for some a and b. Hence if z_{i} ∈ e_{a}Ae_{b} and z_{j} ∈ e_{c}Ae_{d} with b ≠ c, then z_{i}z_{j} = 0. These relations can be written down without any computation. Moreover, no monomial which is divisible by z_{i}z_{j} need be considered in any further search.

Next, we remember that eAe is a direct sum of the spaces e_{a}Ae_{b}. Consequently, it is only necessary to search for relations among the monomial lying in e_{a}Ae_{b} for all a and b. This partitions the search into smaller pieces. In addition, we can work in the condensed algebra eAe so that the vectors of the matrices are relatively small.

It should be emphasized that the ideal of relations is not a homogeneous ideal. Hence at each step, the monomials in the variables z_{1}, …, z_{m} which have lower degree, must be included in the search. So if we have computed all of the k-dependence relations among the monomial in z_{1}, …, z_{m} up to degree d. Then we have a basis B for the space of matrices in monomials in degrees up to d. The basis B is in the form of vectors of monomials in z_{1}, …, z_{m}. In the next step, we calculate set B′ of vectors of the matrices of monomials in degree d + 1. At this step we must consider the dependence relations among the vectors in B ∪ B′ and not just B′. This is accomplished by creating a matrix N whose rows are the elements of B ∪ B′ and computing the null space of the matrix. The elements of the null space are the vectors of coefficients of the relations. That is, if the monomials corresponding to the element of B ∪ B′ are u_{1}, …, u_{m} and a = (a_{1}, …, a_{m}) is an element of the null space of N, then ∑ a_{i}u_{i} = 0 is a relation. This is because, if we replace each u_{i} by the corresponding matrix of the monomial (or the vector of the matrix), then we get the zero matrix since a is in the null space.

Considerable computing time can be saved by making a good choice of the monomials and by computing parts of the ideal of relations in the process of the calculation. In particular, we order the monomials is a way that is consistent with finding a Gröbner basis for the ideal of relations. Then at each step, as described above, we order the vectors of B ∪ B′ in descending order of the corresponding monomials. Now the null space is returned as an echelonized basis. With the chosen ordering, in each basis element, the first nonzero coefficient is on the leading term u of the corresponding relator. Hence, u, the leading monomial is expressible as a linear combination of terms of lower degree modulo the ideal of relations. It follows that in any relation that is computed in subsequent steps, monomials which are multiples of u can be eliminated by expressing them as linear combinations of terms of lower degree. Therefore, in subsequent steps, it is unnecessary to consider monomials which are multiples of u. That is, what we are doing is creating the ideal of leading monomials of the ideal of relations and thereby reducing the size of the computations of the steps. The monomials which are not in the ideal of leading monomials form a basis for Rad(eAe).

With these ideas in mind, we proceed as follows.

(a). For every i and j, let C_{i,j} be the set of all z_{ℓ} such that z_{ℓ} ∈ e_{i}Ae_{j}. Let

B_{i,j} = C_{i,j}. (b). For each degree d, beginning with d = 2 do the following.

(1) For every i and j, we mutate the set C_{i,j} by letting

C_{i,j} = C_{i,j} ∪_{ℓ} {xy | x ∈ B_{i,ℓ}, y ∈ C_{ℓ,j}, degree(y) = d − 1}

where degree(y) means the degree of y as a monomial in z_{1}, …, z_{m}. The elements of C_{i,j} are reordered in decreasing order in the monomial ordering.

(2) For each i and j, find a basis L_{i,j} for the space of dependence relations among the elements of C_{i,j}. Translate each element of L_{i,j} into a polynomial in z_{1}, …, z_{m}. The polynomial is recorded as one of the relations among the generators of the radical. For each element of L_{i,j}, we remove the leading monomial of that polynomial from the set C_{i,j}. (We emphasize that the basis L_{i,j} is echelonized and because of the ordering on monomial, each polynomial corresponding to an element of L_{i,j} has a different leading monomial!) Now the elements of C_{i,j} are linearly independent over k.

(c). Repeat the above until for all i and j, the set

{xy | x ∈ B_{i,ℓ}, y ∈ C_{ℓ,j}, degree(y) = d − 1} = {0}.

The collection of relations is the union of the sets of polynomials corresponding to the elements of the sets L_{i,j}. ♠

Now we require the relations of type (3). The computation is relatively simple.

Algorithm 8.3. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithm 6.6 and 8.2.

Output: A complete set of relations between the set of variables β_{1}, …, β_{r} and the set of variables z_{1}, …, z_{n}.

Description. From the output of Algorithm 8.2 we have a basis for Rad(eAe) which is a union of sets B_{i,j} ⊂ e_{i}Ae_{j} each consisting of monomials in the elements z_{1}, …, z_{m}. If i ≠ j then B_{i,j} is a basis for e_{i}Ae_{j}, while if i = j then e_{i}Ae_{i} has a basis which is the union of the sets B_{i,i} and {β_{i}^{a}|0 ≤ a < d_{i}}. Then the relations of type (3) come in four types.

(a.) β_{i}z_{j} = 0, whenever z_{j} ∈ e_{k}Ae_{ℓ} for k ≠ i, (b.) z_{j}β_{i} = 0, whenever z_{j} ∈ e_{k}Ae_{ℓ} for ℓ ≠ i, (c.) β_{i}z_{j} = x_{i,j}, whenever z_{j} ∈ e_{i}Ae_{ℓ} and x_{i,j} is a linear combination of the basis

elements B_{i,ℓ}, and (d.) z_{j}β_{i} = y_{i,j}, whenever z_{j} ∈ e_{ℓ}Ae_{i} and y_{i,j} is a linear combination of the basis

elements B_{ℓ,i}. The relations of the first two types are generated automatically without any computation. The relations of the third sort are found by taking the product of the matrices β_{i}z_{j} and writing that product as a linear combination of the elements in B_{i,ℓ}. The elements of the fourth type are found similarly. The last two processes are straightforward linear algebra applications. ♠

Remark 8.4. The output of algorithm 8.3, is the final step in finding a presentation for the basic algebra eAe.

The above algorithms are summed up in the following.

Algorithm 8.5. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithm 6.6, 8.2 and 8.3.

Output: A presentation for A in the form A ≅ P/I where

P = k⟨B_{1}, …, B_{r}, T_{1}, …, T_{s}, Z_{1}, …, Z_{m}⟩

is a free algebra over k and I is an ideal of relations. The ideal I is specificied by a set S of relators that generated the ideal.

Description. Define the map \xymatrix{ψ : P \ar[r] & A} by letting ψ(B_{i}) = β_{i}, ψ(T_{i}) = τ_{i}, and ψ(Z_{i}) = z_{i}. The ideal I is generated by the relators S given in Theorem 4.1, and computed in Algorithms 8.2 and 8.3. ♠

We can prove the following.

Theorem 8.6. The ideal I is the kernel of ψ and the map \xymatrix{ψ′ : P/I \ar[r] & A} induced by ψ is an isomorphism.

Proof. It is clear from the computation that I is in the kernel of the map ψ. Moreover the relations of type (1), (2) and (3) are sufficient to generate a complete set of the semisimple relations as well as complete set of relations that involve the generators z_{1}, …, z_{m} and β_{1}, …, β_{r}. Hence, the only thing that needs to be noticed is that for any i, j, a and b, the space e_{i}Ae_{j} is isomorphic to the k-space τ_{i}^{a}e_{i}Ae_{j}τ_{j}^{b} and to the space e_{i}τ_{i}^{a}Aτ_{j}^{b}e_{j}. All of this follows because, τ_{i}^{n_{i}} = E_{i} = ∑_{j=1}^{n_{i}} τ_{i}^{n_{i}−j}e_{i}τ_{i}^{j} and E_{i}e_{i} = e_{i}E_{i} = e_{i}. These relations are implied by Theorem 4.1. The result is that there are no new relations that involve the elements τ_{1}, …, τ_{s}. □

9. Solving the word problem

Suppose that A is a matrix algebra in Mat_{n}(k) generated by the matrices α_{1}, …, α_{t}. There are many benefits to computing a presentation for A that go beyond the immediate result. One of these collateral benefits is a membership test for A. That is, if γ ∈ Mat_{n}(k), then it is possible to decide if γ is an element of A and when it is an element of A we can find a polynomial in the free algebra P of the presentation whose image under the map \xymatrix{ψ : P \ar[r] & A} is the element γ. That is, we can solve the word problem of writing arbitrary elements of A as images of elements of P

One of the aims is to make it possible to define homomorphisms from the algebra A and hence representations of the algebra A (A-modules). Specifically, a homomorphism from A to a k-algebra B can be constructed as a homomorphism \xymatrix{σ : P \ar[r] & B} which has the ideal I of relations in its kernel. A homomorphism from P to B consists of an assignment of the free generators of P to elements of B. A representation of A of dimension r has the structure of a homomorphism \xymatrix{σ : P \ar[r] & Mat_{r}(k)} , having I in its kernel. For an element α in A, the representation of α is the element σ(f) where f ∈ P is a polynomial such that ψ(f) = α.

To solve the word problem, we first express the elements of A in a normal form with respect to the computed idempotent decomposition of A. Recall that e_{i,j} = τ_{i}^{n_{i}−j+1}e_{i}τ_{i}^{j−1}. We have that

Id_{A} = ∑_{i=1}^{r} E_{i} = ∑_{i=1}^{r} ∑_{j=1}^{n_{i}} e_{i,j}

is an idempotent decomposition of the identity as a sum of orthogonal primitive idempotents. The normal form expresses an element α of A as a sum of the elements e_{i,j}αe_{k,ℓ} in a way that is easily identifiable from the transformed matrix of α. The next algorithm provides the mechanism.

Algorithm 9.1. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k).

Input: The algebra A and the output of Algorithm 6.6.

Output: An invertible matrix U, conjugation by which moves the elements of A into normal form with respect to the computed idempotent decomposition.

Description. Let V be the right A-module of dimension n which is the restriction to A of the natural module for Mat_{n}(k). Let r_{i} be the rank of the matrix e_{i} = e_{i,1}. Then, r_{i} will also be the rank of e_{i,j} for any j = 1, …, n_{i}.

(a). We construct a basis B for V as follows. For each i select a basis B_{i,1} for V e_{i}. Suppose that B_{i,1} = {v_{i,1}, …, v_{i,r_{i}}} Then a basis for V e_{i,j} is the set

B_{i,j} = {v_{i,ℓ}τ_{i}^{j−1}|ℓ = 1, …, r_{i}}.

It follows that a basis for V E_{i} is

B_{i} = B_{i,1} ∪ ⋯ ∪ B_{i,n_{i}},

and that

B = B_{1} ∪ ⋯ ∪ B_{r}

is a basis for V. It is important that these elements be ordered exactly as indicated in the construction.

(b). Let the matrix U be constructed as the matrix whose rows are the elements

of the basis B taken in exactly the order given. The result of all of this is that for any i = 1, …, r and j = 1, …, n_{i}, the matrix U^{−1}e_{i,j}U is equal to the zero matrix except in the r_{i} × r_{i} beginning at position (w_{i,j}, w_{i,j}) where w_{i,j} = ∑_{k=1}^{i−1} r_{k}n_{k} + (j − 1)r_{i} + 1. In that r_{i} × r_{i} block, it is the identity matrix. ♠

The point of the normal form can be expressed in the following. The proof should be clear from the above.

Lemma 9.2. Suppose that α is in the algebra A. Then

α = ∑_{i,j=1,1}^{r,r} ∑_{k=1}^{n_{i}} ∑_{ℓ=1}^{n_{j}} e_{i,k}αe_{j,ℓ}.

Moreover, all of the entries in the matrix U^{−1}e_{i,k}αe_{j,ℓ}U are zero except for those in the r_{i} × r_{j} block beginning in position (w_{i,k}, w_{j,ℓ}).

Now we have the algorithm for solving the word problem.

Algorithm 9.3. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: A matrix α ∈ Mat_{n}(k) together with the algebra A and the output of Algorithms 8.2, 8.5 and 9.1.

Output: A boolean which is true if the matrix α is an element of the algebra A and false otherwise. In the case that α ∈ A we also get an element f in the free algebra P (from Algorithm 8.5) such that ψ(f) = α.

Description. Let U be the normal form conjugation matrix obtained in the run of Algorithm 9.1. Recall that from Algorithm 8.2 we have a complete k-basis C_{i,j} for e_{i}Ae_{j} and for each element of that basis we know a word in P whose image under ψ is that basis element. Moreover, for such a basis element b we can compute U^{−1}bU and record only the r_{i} × r_{j} submatrix in the nonzero block. That is, in Step (b), below, we work only with the submatrices of size r_{i} × r_{j} for i and j as appropriate.

So we proceed as follows.

(a). Construct the matrix U and replace α by U^{−1}αU. Let f be the zero element

of P. (b). For every tuple i, j, k, ℓ such that 1 ≤ i, j ≤ r, 1 ≤ k ≤ n_{i} and 1 ≤ ℓ ≤ n_{j}

do the following. Take the submatrix of size r_{i} × r_{j} whose upper left hand corner is in the position (w_{i,k}, w_{j,ℓ}). Express this as a linear combination of basis elements C_{i,j}.

(1) If there is no such linear combination, then α is not in A. Return “false” and quit the remainder of the routine.

(2) Otherwise we obtain an element f_{i,j,k,ℓ} ∈ P. Now replace f by the element f + T_{i}^{k−1}f_{i,j,k,ℓ}T_{j}^{n_{j}+1−ℓ}, and continue.

At the end, if no “false” has been returned, then return “true” and the element f.

Note once again, that the order is extremely important here. In particular, if b is a basis element in C_{i,j} represented by an element f in P, then the corresponding element in the basis of e_{i,k}αe_{j,ℓ} must be τ_{i}^{k−1}bτ_{j}^{n_{j}+1−ℓ}. Otherwise, the substitution made in (b), above, is not valid. ♠

10. Condensed algebras and Cartan matrices

Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Assume that we have computed a set of primitive idempotents e_{1}, …, e_{r} in A, such that the modules e_{i}A/(e_{i}A ∩ Rad(A)) are the simple A modules. Let e = ∑ e_{i}. The subalgebra eAe is Morita equivalent to the algebra A as noted in 7.1. This means that A and eAe have equivalent module categories. The information that we have computed allows us to realize eAe as a matrix algebra of (generally) much smaller dimension. The difference in the dimensions of A and eAe is a function of the sizes (n_{1}, …, n_{r}) of the simple quotient algebras of A. The algorithm for realizing eAe is straightforward linear algebra and we give only a summary of the proof. Again, we remind the reader that eAe is not the subalgebra generated by the set of matrices {eα_{i}e|i = 1, …, t}.

Algorithm 10.1. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithms 6.6 and 8.2.

Output: An algebra 𝔄 ⊆ Mat_{w}(k), isomorphic to the subalgebra eAe of A, where w is the rank of the matrix e ∈ A.

Description. Let V be the natural A-module of dimension n. We proceed as follows.

(a). Find a basis B for the row space of the matrix e and a basis B′ for the row space of Id_{A} −e. Note that B is a basis for the subspace V e of V and likewise, B′ is a basis for V (1 − e). It follows that B ∪ B′ is a basis for V, since e and 1 − e are orthogonal idempotents.

(b). Construct W, the matrix in Mat_{n}(k) whose first w rows are the elements of B and whose last n − w rows are the elements of B′. Let U_{1} be the w × n matrix consisting of the first w rows of W (the elements of B). Let U_{2} be the n × w matrix consisting or the first w columns of W^{−1}. Note that U_{1}U_{2} ∈ Mat_{w}(k) is the identity matrix.

(c). Let 𝔄 be the subalgebra of Mat_{w}(k) generated by

{U_{1}β_{i}U_{2}|i := 1, …, r} ∪ {U_{1}z_{i}U_{2}|i := 1, …, m}.

Then 𝔄 ≅ eAe. ♠

The indecomposable projective modules for the algebra A are isomorphic to the right ideals e_{i}A for i = 1, …, r. Recall that e_{i}A has a unique simple quotient module S_{i} = e_{i}A/(e_{i} Rad(A)), corresponding to the simple quotient algebra A_{i} ≅ Mat_{n_{i}}(K_{i}). The Cartan matrix for A is the matrix C = (c_{i,j}), where c_{i,j} is the multiplicity of S_{j} as a composition factor in the projective module e_{i}A. Thus we have an easy algorithm for computing the Cartan matrix as well as the dimensions of the projective modules of A.

Algorithm 10.2. Let A be a matrix algebra generated by α_{1}, …, α_{t} ∈ Mat_{n}(k). Input: The algebra A and the output of Algorithms 5.1 and 8.2.

Output: The Cartan matrix for A as well as the dimensions of the indecomposable projective modules of A.

Description. From the above description we get that c_{i,j} = (Dim e_{i}Ae_{j})/d_{j} where d_{j} is the degree of K_{j} as an extension of k. Because the dimension of S_{i} is n_{i}d_{i} we have that Dim(e_{i}A) = ∑_{j=1}^{r} c_{i,j}n_{i}d_{i} ♠

11. Current Implementations

As we said in the introduction, the algorithms in this paper are implemented as a package in MAGMA. The package was available with MAGMA Version 2.12 as of the summer of 2005. The implementations have been used to compute the structure of some Hecke algebras. The Hecke algebras that we investigated are the endomorphism rings Hom_{kG}(M, M), where k is a prime field with p-elements, G = Sym(n) is the symmetric group on n letters, and M is a permutation module with point stabilizer a Young subgroup. The results of the computations are published on the first author’s web page.

We make no claim that the method we describe is the best or the most efficient means of computing Hecke algebras. We choose these examples, only for their value in demonstrating the software.

The computations were made in the following steps. First, let A denote the action algebra of M. That is, A is the image of kG in End_{k}(M) = Hom_{k}(M, M). The next step is to obtain a presentation for A and the idempotent decomposition of A. In particular, we want the condensed algebra eAe. Now notice that

Hom_{kG}(M, M) = End_{kG}(M) ≅ End_{A}(M) ≅ End_{eAe}(Me).

Hence, the Hecke algebra can be computed over the condensed algebra.

The table below gives a few of the running times for the calculations. In each calculation, the partition λ = [a_{1}, a_{2}, …, a_{t}] of n, defines a Young subgroup S_{λ} ≅ Sym(a_{1}) × ⋯ × Sym(a_{t}), and the algebra A is the action algebra of Sym(n) on the permutation module M which has dimension |Sym(n) : S_{λ}|. Each of the algebras A is generated by two elements which we denote by α_{1} and α_{2}. The columns in the table indicate the following information. d_{M} is the dimension of M, d_{A} is the dimension of the action algebra A, d_{C} is the dimension of the condensed algebra eAe and p is the number of elements in the field k. The times are t_{1} to find the simple quotient algebras (Meataxe), t_{2} to construct the idempotents, t_{3} to find the generators of the radical, t_{4} to construct the ideal of relations, and t_{5} to solve the word problem, finding α_{1} and α_{2} as polynomials in the new generators for the algebra A. The times are all in seconds. Finally, nt is the total number of terms in the expressions of α_{1} and α_{2} as polynomials in the new generators. Note that the number of terms is often larger than the dimension of the algebra. Perhaps that is to be expected.

part p d_{M}  d_{A} d_{C} t_{1}  t_{2}  t_{3}  t_{4}  t_{5}  nt mem
[3,3,1] 2 140 2124 23 0.05 0.36 1.14 1.63 0.33 2042 8.4M
[3,3,1] 3 140 2319 30 0.08 2.70 10.5 3.20 0.06 3087 12.4 M
[3,3,1] 5 140 2320 16 0.09 6.45 33.4 3.390 0.67 3540 9.4 M
[4,2,2] 2 420 13741 73 0.27 6.74 47.5 10.6 3.38 13558 17 M
[4,2,2] 3 420 14003 46 0.80 140 641 22.9 3.76 18381 28.1 M
[4,2,2] 5 420 14003 21 1.42 234 2357 42.4 8.57 22347 22.5 M
[6,3,1] 2 840 141153 85 1.52 80.9 1909 1088 304 140290 147 M
[6,3,1] 3 840 141152 31 3.10 2738 84K 5016 2135 186881 181 M
[5,3,2] 2 2520 478257 147 35.0 4964 81K 6292 3445 472979 458 M

The computations were run on a Sun Blade 1000 with 8GB. of RAM and two UltraSPARC-III 750 Mhz processors, running the operating system Solaris 5.9. The running times are for a specific run. There does not seem to be much variation in the running times in spite of the Monte Carlo nature of some of the algorithms. We ran every one of the test cases twice, and we ran the seventh one (partition [6, 3, 3] in characteristic 2) ten times. Most of the running times were within 1% of the times in the tables and none was off by more than 8% from those times. It seems to be that the Monte Carlo parts of the algorithms are the parts that run most quickly.

In summary, the current implementation seems to run well for algebras of dimension under a few thousand defined over small fields. We hope that improvements in the code will be reflected in improved capabilities and running times.

Finally, we present some data on the outcomes of these experiments. For the module and algebra structures we refer the reader to the first author’s web page. Some data on the nature of the presentations is give in the table below. These are the presentatons for the action algebra A in each case. For each of the partitions we present, first, the number of computed generators for the action algebra, then the total number of computed relations, the number of terms of the longest relation, and finally, the number of the relators that are monomials. Note that this is only the number or relations that are actually computed by the algorithms and is not the number of elements in a Gröbner basis for the ideal of relations (which in most case should be a much larger number).

partition 3,3,1 3,3,1 3,3,1 4,2,4 4,2,4 4,2,4 6,3,1 6,3,1 5,3,2
characteristic 2 3 5 2 3 5 2 3 2
# variables 19 24 20 26 32 26 27 26 40
# relations 644 834 581 1355 2042 1352 3508 3355 8739
max length 21 21 36 65 36 71 199 280 201
# monomials 598 772 533 1262 1953 1288 3421 3286 8570

References

[1] D. J. Benson, “Representations and Cohomology I, II”, Cambridge Univ. Press, 1991.

[2] W. Bosma and J. Cannon, Handbook of Magma Functions, Magma Computer Algebra, Sydney, 2002.

[3] C. Curtis and I. Reiner, “Representation Theory of Finite Groups and Associative Algebras”, Interscience, New York, 1962.

[4] The GAP Group, GAP – Groups, Algorithms and Programming, 2005,

   (http://www.gap-system.org).

[5] D. J. Green, Gröbner bases and the computation of group cohomology, Lecture Notes in Mathematics 1828, Springer Verlag, Berlin, 2003.

[6] K. Lux and Wiegelmann, M. Condensing Tensor Product Modules The Atlas of Finite Groups: ten years on (Birmingham, 1995), 174-190, London Math Soc. Lecture Note Ser., 249, Cambridge Univ. Press, Cambridge, 1998.

[7] G. Matthews, Computing generators and relations for matrix algebras PhD. Thesis submitted to the University of Georgia, August, 2004.

[8] M. Ringe, The C-Meat-Axe, RWTH, Aachen, 1994.

Department of Mathematics, University of Georgia, Athens, Georgia 30602, USA

E-mail address: jfc@math.uga.edu

Department of Mathematics, University of Georgia, Athens, Georgia 30602, USA, (now at Amgen, 1 Amgen Center Drive, Thousand Oaks, California 91320)

E-mail address: matthews@math.uga.edu