Vector enumeration (originally misnamed module enumeration) is an algorithm for converting a finitely-presented module for a finitely-presented algebra into a concrete vector space on which the algebra has explicit matrix action. The algebra may be the group algebra of an fp-group, in which case the resulting module will be a matrix representation of the group, or it might be a more general fp-algebra, such as a Hecke algebra or a quotient of a polynomial ring.

Subsections

• Finitely Presented Modules
• S-algebras
• Finitely Presented Algebras
• Vector Enumeration
• The Isomorphism
• Sketch of the Algorithm
• Weights

For a ring R, let M be an R-module M, generated as an R-module by s elements {m_1, ..., m_s}. There is an R-module epimorphism psi : R^s |-> M, given by (r_1, ..., r_s) |-> m_1r_1 + ... + m_sr_s. This shows that M is isomorphic to A^s/ker psi .

If ker psi is generated as an R-module by a finite set L then we will say that M is presented by s generators and the relators L.

S-algebras

Suppose there is another ring S, equipped with a ring homomorphism phi: S |-> R, such that phi(S) is central in R. In this situation any R-module can be described as an S-module, on which R acts as a ring of S-module endomorphisms. We say that R is an S-algebra. In particular, when S is a field k, any R-module is a k-vector space. If such a module V has finite k-dimension n, then V is characterised by this dimension and R will act on it as a subring of M_n(k).

Finitely Presented Algebras

Given a finite set X, and a ring S, we can define the free S-algebra A generated by X. This can be seen either as the monoid algebra of the free monoid of words in X, or as all expressions in X and k, combined by addition and multiplication.

Given a finite set R subset A we can define P = (A/< ARA >). We say that P is a finitely-presented S-algebra, with generators X and relators R, and write it P = < X | R >.

The monoid algebra of any finitely-presented monoid (or group, of course) is finitely-presented, since k< X | l_1 = r_1, ..., l_k=r_k >_(( monoid)) = < X | l_1 - r_1, ..., l_k - r_k >_(k - algebra). Furthermore, any quotient of a finitely-presented algebra by a finitely-generated two-sided ideal is finitely-presented. This gives us the general form of a finitely-presented algebra in Magma, as the quotient of the monoid algebra of an fp-monoid, by the two-sided ideal generated by some additional relators.

Vector Enumeration

The vector enumeration algorithm explicitly reconciles these two descriptions of an R-module, in the case where R is a finitely presented k-algebra for a field k, and M is a finitely presented R-module, which also has finite k-dimension.

Given the presentation of R as k-algebra, and that of M as R-module, it computes the k-dimension of M and the matrices giving the action of the generators of R on M. If M has infinite k-dimension the algorithm will fail to terminate.

• A permutation module

We know that the group with presentation < a, b | a^4 = b^2 = (ab)^2 = 1 > is the dihedral group of order 8. Its group algebra over any field k is thus the fp-k-algebra < a, b, a', b' | aa' - 1, a'a - 1, bb' - 1, b'b - 1, a^4 - 1, b^2 - 1, (ab)^2 - 1 >. The permutation module of degree 4 of this algebra is presented by 1 generator (as it is transitive) and the submodule generator b - 1.

Applying the algorithm to this case we obtain the matrices

a = [ 0 0 1 0 ]
    [ 1 0 0 0 ]
    [ 0 0 0 1 ]
    [ 0 1 0 0 ]

b = [ 1 0 0 0 ]
    [ 0 0 1 0 ]
    [ 0 1 0 0 ]
    [ 0 0 0 1 ]

• A quotient of a permutation module

a = [  0  0  1 ]
    [  1  0  0 ]
    [ -1 -1 -1 ]

b = [  1  0  0 ]
    [  0  0  1 ]
    [  0  1  0 ]

• A non-cyclic module

As an example we take two copies of the representation constructed in example one, and fuse their one-dimensional submodules. The generators and relators are as before, and now s=2 and the submodule generators are a^2 = {(b - 1, 0), (0, b - 1), (1 + a'(1 + a' + b), - 1 - a'(1 + a' + b))}. We obtain a representation of degree seven, given by

a = [  0  0  0  1  0  0  0 ]
    [  0  0  0  0  0  0  1 ]
    [  1  0  0  0  0  0  0 ]
    [  0  0  0  0  1  0  0 ]
    [  0  0  1  0  0  0  0 ]
    [  0  1  0  0  0  0  0 ]
    [  1 -1  1  1  1 -1 -1 ]

b = [  1  0  0  0  0  0  0 ]
    [  0  1  0  0  0  0  0 ]
    [  0  0  0  1  0  0  0 ]
    [  0  0  1  0  0  0  0 ]
    [  0  0  0  0  1  0  0 ]
    [  0  0  0  0  0  0  1 ]
    [  0  0  0  0  0  1  0 ]

In determining the k-dimension of M, and giving matrices representing the action of R on M, the algorithm is, in effect, constructing a k-vector space, on which R has matrix action, and which is R-module isomorphic to M, which is formally a quotient module of R^s. The algorithm also computes this isomorphism, giving images in the vector space for the s standard generators of R^s and pre-images in R^s of the basis of the vector space.

In example (1) above, we find that the module generator has image (1, 0, 0, 0), while the basis vectors have pre-images 1, a', a'^2 and b.

In example (3) the images of the two module generators are (1, 0, 0, 0, 0, 0, 0) and (0, 1, 0, 0, 0, 0, 0) while the basis vectors are images of (1, 0), (0, 1), (a', 0) ,(a, 0), (a^2, 0), (0, a') and (0, a).

Sketch of the Algorithm

The algorithm is based on the Haselgrove-Leech-Trotter (HLT) version of the Todd-Coxeter algorithm, which we consider as a means of constructing the permutation representation of a finitely-presented group on the cosets of a finitely generated subgroup.

The algorithm proceeds by manipulating a partial action of the free algebra on a vector space. This is represented as a table, with columns indexed by the generators of the algebra, and rows indexed by the basis of the space. Each entry is either a vector or bot, signifying that no action is given.

We can extend this to a "complete action with side-effects", by adding a new row to the table whenever needed. We call this the action with defining.

The action of the fp-algebra P on M gives an action for the free algebra A, and our objective is to modify out partial action until it becomes this action. We know certain things about this action, which drive our modification process:

• It is a complete action.
• The relators of P annihilate every vector.
• The images in the space of the relators of M are zero.
• The space contains images of the R-module generators of M.

We now start to exploit the second fact about M, constructing the action (with defining) of the relators of P, on the basis vectors, and applying the resulting coincidences. This process may not terminate, as we are defining new basis vectors on the one hand, and removing them through coincidences on th other. It is possible to prove, however, that if M is in fact finite-dimensional then the process will terminate.

The first fact is applied by adding the relators x - x for each x in X to the relators of P, so that the image of every basis vector under each x is sure to be defined.

Weights

The above sketch leaves open the question of the order in which the relators are applied to the basis vectors. The proof that the algorithm completes when M is finite-dimensional imposes some rather loose constraints, but within those there is considerable choice.

The implementation in Magma uses a system of weights. Each relator r is assigned a weight w_r by the user, and each basis vector e has a weight w_e. There is a current weight w, which increases as the computation progresses, and at weight w all basis vector, relator pairs (b, r) such that w_b + w_r <= w, which have not been processed already, are processed. New basis vectors defined during this are assigned weight w. The initial basis vectors and those defined during processing of the submodule generators are assigned weight 1. See below for details of how to set the weights, and their default values.