COUNTING EQUIVALENCE CLASSES

OF IRREDUCIBLE REPRESENTATIONS

Edward S. Letzter

June 2001.

Abstract. Let n be a positive integer, and let R be a (possibly infinite dimensional) finitely presented algebra over a computable field of characteristic zero. We describe an algorithm for deciding (in principle) whether R has at most finitely many equivalence classes of ndimensional irreducible representations. When R does have only finitely many such equivalence classes, they can be effectively counted (assuming that k[x] posesses a factoring algorithm).

1. Introduction

Let n be a positive integer, fixed throughout. In [5] we observed that the existence of ndimensional irreducible representations of finitely presented noncommutative algebras can be algorithmically decided. In this note we outline a procedure for effectively “counting” the number of such irreducible representations, up to equivalence, in characteristic zero. Our approach combines standard computational commutative algebra with results from [1] and [9].

1.1. Assume that k is a computable field of characteristic zero, and that \overline{k} is the algebraic closure of k.

Henceforth, let

R = k{X_{1}, …, X_{s}}/⟨f_{1}, …, f_{t}⟩,

for some fixed choice of f_{1}, …, f_{t} in the free associative k-algebra k{X_{1}, …, X_{s}}. In a slight abuse of notation, “X_{ℓ}” will also denote its image in R, for 1 ≤ ℓ ≤ s.

By an n-dimensional representation of R we will always mean a unital k-algebra homomorphism from R into the k-algebra M_{n}(\overline{k}) of n×n matrices over \overline{k}. Representations ρ, ρ′: R → M_{n}(\overline{k}) are equivalent if there exists a matrix Q ∈ GL_{n}(\overline{k}) such that

ρ′(X) = Qρ(X)Q^{−1},

Typeset by AMS-TEX

The author’s research was supported in part by NSF grant DMS-9970413. Also, a part of this research was completed while the author was a participant (February 2000) in the MSRI program on noncommutative algebra.

for all X ∈ R.

We will say that the representation ρ: R → M_{n}(\overline{k}) is irreducible when \overline{k}ρ(R) = M_{n}(\overline{k}) (cf. [1, §9]). Observe that ρ is irreducible if and only if ρ⊗1: R ⊗_{k} \overline{k} → M_{n}(\overline{k}) is surjective, if and only if ρ ⊗ 1 is irreducible in the more common use of the term. (In particular, our approach below will use calculations over the computable field k to study representations over the algebraically closed field \overline{k}.)

1.2. The existence of an n-dimensional representation of R depends only on the consistency of a system of algebraic equations, over k, in (t.n^{2})-many variables. Consequently, the existence of n-dimensional representations of R is decidable (in principle) using Groebner basis methods. This idea is extended in [5] to give a procedure for deciding the existence of n-dimensional irreducible representations. On the other hand, posessing a nonzero finite dimensional representation is a Markov property, and so the existence – in general – of a finite dimensional representation of R cannot be effectively decided, by [3].

We now state our main result; the proof will be presented in §2.

Theorem. Having at most most finitely many equivalence classes of irreducible n-dimen-sional representations is an algorithmically decidable property of R.

1.3. Assume that k[x] is equipped with a factoring algorithm. If it has been determined that R has at most finitely many equivalence classes of n-dimensional irreducible representations, these equivalence classes can (in principle) be effectively counted; see (2.9).

2. Proof of Theorem

2.1. (i) Set

B = k[x_{ij}(ℓ) : 1 ≤ i, j ≤ n, 1 ≤ ℓ ≤ s].

For 1 ≤ ℓ ≤ s, let x_{ℓ} denote the n×n generic matrix (x_{ij}(ℓ)), in M_{n}(B). For g ∈ k{X_{1}, …, X_{s}}, let g(x) denote the image of g, in M_{n}(B), under the canonical map

k{X_{1}, …, X_{s}} ⟶^{X_{ℓ}⟼x_{ℓ}} M_{n}(B).

Identify B with the center of M_{n}(B).

(ii) Let Rel(M_{n}(B)) be the ideal of M_{n}(B) generated by f_{1}(x), …, f_{t}(x).

(iii) Let Rel(B) denote the ideal of B generated by the entries of the matrices f_{1}(x), …, f_{t}(x) ∈ M_{n}(B). Note that

Rel(B) = Rel(M_{n}(B)) ∩ B.

(iv) Let

A = k{x_{1}, …, x_{s}},

the k-subalgebra of M_{n}(B) generated by the generic matrices x_{1}, …, x_{s}. Set

Rel(A) = Rel(M_{n}(B)) ∩ A.

2.2. Every n-dimensional representation of R can be written in the form

R ⟶^{X_{ℓ}⟼x_{ℓ}+Rel(A)} (\frac{A}{Rel(A)}) ⟶^{inclusion} (\frac{M_{n}(B)}{Rel(M_{n}(B))}) ⟶ M_{n}(\overline{k}),

and every k-algebra homomorphism

M_{n}(B)/ Rel(M_{n}(B)) → M_{n}(\overline{k})

is completely determined by the induced map

B/ Rel(B) → \overline{k}.

For each representation ρ: R → M_{n}(\overline{k}), let χ_{ρ}: B → \overline{k} be the homomorphism (with Rel(B) ⊆ ker χ_{ρ}) given by this correspondence.

2.3. Let T be the k-subalgebra of B generated by the coefficients of the characteristic polynomials of elements in A. (Since the characteristic of k is zero, T is in fact generated by the traces, as n×n matrices, of the elements in A.) Set

Rel(T) = Rel(B) ∩ T.

Note, when ρ, ρ′: R → M_{n}(\overline{k}) are equivalent representations, that the restrictions of χ_{ρ} and χ_{ρ′} to T will coincide.

2.4. Let simple_{n}(R) denote the set of equivalence classes of irreducible n-dimensional representations of R. By (2.3) there is a well-defined function

Φ : simple_{n}(R) ⟶ V (Rel(T)),

where V (Rel(T)) denotes the \overline{k}-affine algebraic set of points on which the polynomials in Rel(T) vanish. It follows from [1, pp. 558–559] that Φ is injective.

2.5. (i) Recall the mth standard identity

s_{m} = ∑_{σ∈S_{m}}(sgn σ)Y_{σ(1)} ⋯ Y_{σ(m)} ∈ ℤ{Y_{1}, …, Y_{m}}.

If Λ is a commutative ring, then the Amitsur-Levitzky Theorem ensures that M_{n}(Λ) satisfies s_{m} if and only if m ≥ 2n; see, for example, [6, 13.3.2, 13.3.3].

(ii) Let S denote the finite subset of T (⊆ B) comprised of

trace (M_{0} · s_{2(n−1)}(M_{1}, …, M_{2(n−1)})) ,

for all monic monomials M_{0}, …, M_{2(n−1)}, in the generic matrices x_{1}, …, x_{s}, of length less than

p = n\sqrt{2n^{2}/(n − 1) + 1/4} + n/2 − 2.

(The choice of p will follow from [7]; see [5, 2.2].) Let ρ: R → M_{n}(\overline{k}) be a representation. It now follows from [5, §2] that ρ is irreducible if and only if

S ⊈ ker χ_{ρ}.

(Other sets of polynomials can be substituted for S; see [5, 2.6vi,vii].)

2.6. (i) Set

W = V (Rel(T)) \ V (S).

Combining (2.4) with (2.5ii), we obtain a bijection

Φ : simple_{n}(R) ⟶ W.

(ii) Set

J = ann_{B} (\frac{Rel(B) + B.S}{Rel(B)} ) , and I = J ∩ T = ann_{T} (\frac{Rel(T) + T.S}{Rel(T)} ) .

A finite generating set for J can be specified, using standard methods, and we can identify T/I with its image in B/J. Since V (I) is the Zariski closure of W, to prove the theorem it suffices to find an effective procedure for determining whether or not T/I is finite dimensional. (When not indicated otherwise, “dimension” refers to “dimension as a k-vector space.”)

2.7. (i) For the generic matrices x_{1}, …, x_{s}, set Trace =

{trace(y_{1}y_{2} ⋯ y_{u}) : y_{1}, …, y_{u} ∈ {x_{1}, …, x_{s}} and 1 ≤ u ≤ n^{2}} .

In [9] (cf. [4, p. 54]) it is shown that T = k[Trace]. (A larger finite generating set for T was established in [8].)

(ii) By (2.6ii), to prove the theorem it remains to find an algorithm for deciding whether the monomials in Trace (⊆ B) are algebraic over k, modulo J. We accomplish this task using a variant of the subring membership test (cf., e.g., [2, p. 270]): Let C be a commutative polynomial ring, over k, in m variables. Let L be an ideal – equipped with an explicitly given list of generators – in C. Choose f ∈ C. Observe that f is algebraic over k, modulo L, if and only if L ∩ k[f] ≠ {0}. Next, embed C, in the obvious way, as a subalgebra of the polynomial ring C′ = k(t) ⊗_{k} C. Observe that L ∩ k[f] ≠ {0} if and only if 1 is contained in the ideal (t − f).C′ + L.C′ of C′. Hence, the decidability of ideal membership in C′ implies the decidability of algebraicity modulo L in C.

The proof of the theorem follows.

2.8. Roughly speaking, the complexity of the procedure described in (2.1 – 2.7) varies according to the degrees of the polynomials involved in deciding the algebraicity of Trace modulo J. Note, for example, that the degrees of the members of S can be as large as p^{2n−1}, for p as in (2.5ii).

2.9. Assume that it has already been determined that the number (equal to |W |) of equivalence classes of irreducible n-dimensional representations of R is finite. Further assume that k[x] is equipped with a factoring algorithm. We conclude our study by sketching a procedure for calculating – in principal – this number.

Set D = T/I, and identify D with the (finite dimensional) k-subalgebra of B/J generated by the image of Trace. Since B/J can be given a specific finite presentation, finding a k-basis E for D amounts to solving systems of polynomial equations in B, and this task can be accomplished employing elimination methods. Next, using the regular representation of D, and the finite presentation of B/J, we can algorithmically specify E as a set of commuting m×m matrices over k, for some m. Furthermore, the nilradical N(D) will be precisely the set of elements of D whose traces, as m×m matrices, are zero. Consequently, we can effectively compute the dimension of D/N(D). This dimension is equal to |W |.

References

1. M. Artin, On Azumaya algebras and finite dimensional representations of rings, J. Algebra 11 (1969), 532–563.

2. T. Becker and V. Weispfenning, Gröbner Bases: A Computational Approach to Commutative Algebra, Graduate texts in mathematics no. 141, Springer-Verlag, New York, 1993.

3. L. A. Bokut′, Unsolvability of certain algorithmic problems in a class of associative rings, (Russian), Algebra i Logika 9 (1970), 137–144.

4. E. Formanek, The polynomial identites and invariants of n×n matrices, Conference board of the mathematical sciences regional conference series in mathematics no. 78, American Mathematical Society, Rhode Island, 1991.

5. E. S. Letzter, Constructing irreducible representations of finitely presented algebras, J. Symbolic Computation, (to appear).

6. J. C. McConnell and J. C. Robson, Noncommuative noetherian rings, John Wiley and Sons, Chichester, 1987.

7. C. J. Pappacena, An upper bound for the length of a finite-dimensional algebra, J. Algebra 197 (1997), 535–545.

8. C. Procesi, The invariant theory of n × n matrices, Adv. Math. 19 (1976), 306–381.

9. Ju. P. Razmyslov, Identities with trace in full matrix algebras over a field of characteristic zero, (Russian), Izv. Akad. Nauk SSSR 38 (1974), 723–756.

[AMA - Algebra Montpellier Announcements - 01-2001] [July 2001]
Received February 2001, revised June 2001.

Department of Mathematics, Temple University, Philadelphia, PA 19122

  E-mail address: letzter@math.temple.edu