10 Associative Algebras

10.1 Finitely Presented Associative Algebras

Finitely-presented (FP) associative algebras (or noncommutative polynomial rings) are defined by taking R-linear combinations of elements of a semigroup, where R is some ring. Since V2.11, these are handled by an extension of the commutative algebra machinery to noncommutative data structures and algorithms, where applicable. These include a noncommutative analogue for Gröbner bases.

• Construction of free algebras over arbitrary fields

• Arithmetic

• Mappings into other associative algebras

• Definition of left, right, two-sided ideals

• Noncommutative Gröbner bases of ideals, with specialized algorithms for different coefficient fields (fraction-free methods for the rational field and rational function fields)

• Gröbner bases of ideals over finite fields and rationals, using noncommutative extension of the Faugère F₄ algorithm

• Construction of degree-d (truncated) Gröbner bases

• Normal form of a polynomial with respect to an ideal

• Construction of FP-algebras as quotient rings

• Enumeration of the basis of finite-dimensional FP algebras

• Matrix and structure-constant representations of finite-dimensional FP algebras

• Construction of a matrix representation (Linton's vector enumerator)

There are two major tools for computing with these algebras. The main approach is to apply a noncommutative version of Buchberger's algorithm to construct a Gröbner basis for an ideal. This technique has been developed chiefly by Teo Mora in Genova and Ed Green in Virginia. An extension of Faugère's F₄ algorithm, due to Allan Steel, works by sparse linear algebra and is often much quicker.

Linton's vector enumerator uses the Todd-Coxeter algorithm in an attempt to construct a matrix representation. If the user has some idea as to how to select ideals that might give rise to matrix representations of reasonable degree, this approach is very successful.

10.2 Exterior Algebras

A special type is provided for working with an exterior algebra. Such an algebra is a special kind of FP algebra which is skew-commutative and is represented as a quotient of the free algebra K < x₁,…, x_n > by the relations x_i² = 0 and x_i x_j = -x_j x_i for 1 ≤ i,j ≤ n, i ≠ j.

Because of the above relations, elements of an exterior algebra can be written in terms of commutative monomials in the variables (via a collection algorithm), and the associated algorithms are much more efficient than for the general noncommutative case. Gröbner bases of ideals can be computed very efficiently (the Faugere F₄ algorithm has been specially adapted for this). Furthermore, the extensive module theory also works over exterior algebras.

10.3 General Finite-Dimensional Algebras

These algebras are presented in terms of a basis for a free module M together with a set of structure constants defining the multiplication of these basis elements. It is assumed that we have an echelonization algorithm for M so that standard bases may be constructed for submodules.

• Creation of algebras in terms of structure constants

• Direct sum

• Arithmetic including Lie bracket operation

• Identities: associative, commutative, Lie, etc

• Properties of elements: idempotent, unit, zero-divisor, nilpotent

• Trace and minimal polynomial

• Creation of subalgebras, ideals and quotient algebras

• Ideal arithmetic: Sum, product, powers, intersection

• Ideal structure: Jacobson radical, maximal (minimal) left, right, two-sided ideals

• Decomposition: Simplicity, semi-simplicity, composition series

10.4 Finite-Dimensional Associative Algebras

These algebras are presented in terms of a basis for a free module M together with a set of structure constants defining the multiplication of these basis elements. It is assumed that we have an echelonization algorithm for M so that standard bases may be constructed for submodules. We shall refer to these algebras as ASC-algebras.

10.5 Matrix Algebras

Matrix algebras arise naturally as the endomorphism ring of a module and consequently are a fundamental structure in mathematics. Much effort has been invested into developing highly efficient code for working with these algebras and their elements in Magma. A description of generic matrix operations may be found in the section on Vector Spaces and Matrices and will not be repeated in this section.

While a matrix algebra may be defined over any ring R, most non-trivial operations require R to be an Euclidean Domain.

10.6 Group Algebras

A group algebra may be created for a finite group of moderate order over a Euclidean Domain.

• Creation of group algebras: a vector and term representation are provided allowing the construction of algebras for groups of arbitrary size.

• Arithmetic including Lie bracket operation

• Properties of elements: idempotent, unit, zero-divisor, nilpotent

• Trace and minimal polynomial

• Creation of subalgebras, ideals and quotient algebras

• Ideal arithmetic: Sum, product, powers, intersection

• Centralizer, idealizer

• Augmentation ideal, augmentation map

• Characteristic ideals: Centre, commutator ideal, Jacobson radical

• Ideal structure: Maximal (minimal) left, right, two-sided ideals

• Decomposition: Simplicity, semi-simplicity, composition series

• Construction of the (left, right) regular matrix representation

10.7 Quaternion Algebras

A quaternion algebra is a central, simple algebra of dimension four over a field. Basic functions are provided for quaternion algebras over an arbitrary field. Higher level routines are available for algebras over ℚ, number fields, and rational function fields k(x), where k is a finite field. This includes support for orders and ideals, in particular enumeration of left, right and two-sided ideal classes.

• Arithmetic of elements

• Norm, trace, and conjugation

• Minimal polynomial of elements

• Discriminant, ramified primes and ramified places

• Construction of maximal orders

• Recognition of quaternion algebras

• Computation of an isomorphism to the matrix algebra, in particular over completions of the base field

• Embedding subfields into quaternion algebras

• Left and right orders of ideals

• Isomorphism testing for ideals and orders

• Construction and recognition of Eichler orders

• Enumeration of left, right and two-sided ideal classes of Eichler orders

• Enumeration of conjugacy classes of orders

• Unit groups of orders in definite algebras

10.8 Basic Algebras

A basic algebra is a finite dimensional algebra A over a field, all of whose simple modules have dimension one. In the literature such an algebra is known as a "split" basic algebra. Every finite dimensional algebra is Morita equivalent to a basic algebra, meaing that the algebra and its basic algebra have equivalent module categories and hence the same representation theory. So, for example, a cohomology calculation involving modules over an algebra is often most easily done by condensing to the basic algebra. Magma has the capabilility of constructing the basic algebra of a matrix algebra defined over a finite field. In some cases it is necessary to extend the field in order to split the irreducible modules over the matrix algebra. The basic algebra type in Magma is optimized for the purposes of doing homological calculations.