39.1 More about Finitely Presented Algebras

Free Algebras

Let X be a finite set, and F a field. The free algebra A on X over F can be regarded as the semigroup ring of the free monoid on X over F. Addition and multiplication of elements are performed by dealing with sums of words in abstract generators, with coefficients in F.

Free algebras and also their subalgebras in GAP are always unital, that is, for an element a in a subalgebra A of a free algebra always the element a^0 lies in A (see Algebras and Unital Algebras). Thus the free algebra on the empty set over a field F is defined to consist of all elements f e where f is in F, and e is the multiplicative neutral element, corresponding to the empty word.

Free algebras are useful when dealing with other algebras, like matrix algebras, since they allow to handle expressions in terms of the generators. This is just a generalization of handling words in abstract generators and concrete group elements in parallel, as is done for example in MappedWord (see MappedWord) or functions that construct images and preimages under homomorphisms. This mechanism is also provided for the records representing matrices in the MeatAxe share library (see chapter The MeatAxe).

Finitely Presented Algebras

A finitely presented algebra is defined as quotient A / I of a free algebra A by a two-sided ideal I in A that is generated by a finite set S of elements in F.

Thus computations with finitely presented algebras are similar to those with finitely presented groups. For example, in general it is impossible to decide whether two elements of the free algebra A are equal modulo I.

For finitely presented groups a permutation representation on the cosets of a subgroup of finite index can be computed by the Todd-Coxeter coset enumeration method. An analogue of this method for finitely presented algebras is Steve Linton's VE method that tries to compute a matrix representation of the action on a quotient of a free module of the algebra. This method is available in GAP as a share library (see chapter Vector Enumeration, and the references there), and this makes finitely presented algebra in GAP more than an object one can only use for the obvious arithmetics with elements of free algebras.

GAP only handles the data structures, all the work in done by the standalone program. Thus all functions for finitely presented algebras, like Size, delegate the work to the VE program.

Note that (contrary to the situation in finitely presented groups, and several places in VE) relators are meant to be equal to zero, not to the identity. Two examples for this. If x^2 - a.one is a relator in the presentation of the algebra a, with x a generator, then x is an involution. If x^2 is a relator then x is nilpotent. If the generator x occurs in relators of the form x * v - a.one and w * x - a.one, for v and w elements of the free algebra, then x is known to be invertible.

The VE package is loaded automatically as soon as it is needed. You can also load it explicitly using

gap> RequirePackage( "ve" );

Elements of Finitely Presented Algebras

The elements of finitely presented algebras in GAP are records that store lists of coefficients and of words in abstract generators. Note that the elements of the ground field are not regarded as elements of the algebra, especially the identity and zero element are denoted by a.one and a.zero, respectively. Functions and operators for elements of finitely presented algebras are listed in Elements of Finitely Presented Algebras.

Implementation of Functions for Finitely Presented Algebras

Every question about a finitely presented algebra A that cannot be answered from the presentation directly is delegated to an isomorphic matrix algebra M using the VE share library. This may be impossible because the dimension of an isomorphic matrix algebra is too large. But for small A it seems to be valuable.

For example, if one asks for the size of A, VE tries to find such a matrix algebra M, and then GAP computes its size. M and the isomorphism between A and M are stored in the component A.matAlgebraA, so VE is called only once for A.

Up Top Next
Index

GAP 3.4.4
April 1997