Magma contains broad range of facilities for computing with vector spaces. Let K be a field. In Magma, the standard K-vector space is taken to be the set of n-tuples over the field K, which is written as Kn.
There are two different ways for handling standard vector spaces, depending on how subspaces are presented to the user. Suppose V is the vector space Kn and S is a subspace of V of dimension d. The two ways of representing S are as follows:
The embedded representation is the usual way vector spaces are regarded in elementary linear algebra and is typically more convenient when working with vectors from various subspaces which are all to be related to the original Kn (particularly when working with linear codes and their words). On the other hand, the reduced representation is useful when working in a more abstract setting where operations are relevant to a reduced basis and so every vector space is to be considered simply as Kd (this representation is also necessary when working with modules with matrix action; see below).
To provide the user with the maximum flexibility, Magma supports functions for creating spaces with both forms of presentation: vector spaces with the embedded form are called K-spaces, while those with the reduced form are called K-modules. Usually a calculation commences with the definition of one or two vector spaces from which further spaces are created by the operations of forming subspaces or quotient spaces. Magma provides parallel creation functions which allow the user to choose the form of presentation. Once that choice has been made, all spaces derived from the initial spaces will follow the same presentation convention.
All standard operations on vector spaces are supported by Magma. One non-trivial operation is to compute the intersection of two subspaces; here Magma can use two different methods (depending on the dimensions), both of which map to asymptotically fast matrix multiplication. One can also create a vector space V with a given basis B (not necessarily a standard basis) and then repeatedly ask for the coordinates w.r.t.B of a vector v∈V (expressing v as a linear combination of the elements of B).
Magma also allows the user to construct a vector space V = Kn with an attached inner product matrix F. Here F is an n×n symmetric matrix which is used for computing the inner product of elements of V as follows: (u,v) = u·F·vtr for u,v∈V. This inner product for V is automatically inherited by subspaces of V and automatically used for elements of such by all relevant functions in Magma.
A special type of vector space are the Hom Spaces: These are vector spaces of the form Km×n, consisting of all m×n matrices over K (for any m,n ≥ 0) and their subspaces. A subspace of this type having dimension d is always represented in embedded form (since the reduced form would just be the standard Kd) and the basis consists of d matrices of size m×n. All functions relevant to vector spaces are supported for Hom spaces (sometimes with some subtle modifications because of the form of elements). This includes the ability to express a matrix in terms of a user-provided basis for a Hom space.
Let U and V be K-vector spaces of dimensions m and n, respectively (which may be explicitly embedded in a parent space of higher dimension). The set of all linear transformations with domain U and codomain V is denoted by HomK(U,V). Once bases have been chosen for U and V, HomK(U,V) can be identified with K(m×n). Magma contains a non-trivial algorithm to compute HomK(U,V) for arbitrary U and V. If U,V are reduced then the algorithm is trivial, but if U,V are embedded then the space of matrices which give valid linear mappings from U to V is not easy to construct.
Let R be a general Euclidean ring (not necessarily a field). Magma provides extensive facilities for computing with the scalar R-module Rn, whose elements are just n-tuples over R, where the module action is scalar multiplication by elements of R. This is essentially a generalisation of a vector space where the base ring is no longer assumed to be a field.
As for vector spaces, Magma provides both embedded and reduced representations. All fundamental operations which are applicable to vector spaces are also supported for scalar modules. The most significant difference is that bases of subspaces must be handled differently when R is not a field. If R is a domain (such as ℤ or K[x] for a field K), then the Hermite Normal Form (HNF) is used to compute a basis of a submodule (see the section on matrices over Euclidean rings). This form gives a unique canonical basis for any submodule of Rn. As for vector spaces, the user can also construct a submodule with a given basis so that vectors can be expressed as a linear combination w.r.t. this basis.
If R is a ring with zero divisors (such as the residue class rings ℤm = ℤ/mℤ with m composite, or K[x]/<f> with f reducible), then submodules of Rn may not possess a basis in general (i.e., it may be the case that there does not exist a generating set of minimal cardinality which is linearly independent) and the standard HNF algorithm is inadequate. In this situation, Magma uses an algorithm to compute the Howell Normal Form, which is like the HNF but which potentially adds extra rows related to annihilator ideals; the result yields a unique canonical generating set for a submodule. This special form is needed even for a simple test as to whether a vector is in a submodule and also allows submodules to be compared for equality, etc.
Quotient modules are handled by the Smith Normal Form (SNF) algorithm. The SNF itself gives an abstract presentation of the quotient module and several transformation matrices are kept in the background to facilitate the natural mapping (and its inverse) between the original module and the quotient module. Handling this in general is quite non-trivial, since a quotient module may have both free and torsion parts; even if R is a domain (such as ℤ), a quotient module may have torsion and so be equivalent to a module over a residue class ring with zero divisors.
Similarly to vector spaces, Magma also provides support for Hom Spaces over a Euclidean ring R: these are scalar R-modules of the form Rm×n, consisting of all m×n matrices over R and their subspaces. The user can also compute HomR(U,V) for arbitrary submodules U,V of Rn.
Let A be a subalgebra of the matrix algebra Mn×n(K), where K is a field. An A-module M can be regarded as the vector space Kn equipped with an action by A (multiplication on the right by elements of A). Magma provides a major package for computations with such A-modules. The main feature is a suite of algorithms for structural analysis of A-modules and several types of related finite-dimensional associative algebras. This has very many applications in areas such as representation theory as well as in the theory of algebras and number theory.
Let M be an A-module, where A is a subalgebra of Mn×n(K). A submodule of M is a vector subspace V of Kn which is invariant under the action of A (i.e., such that v·a∈V for all v∈V,a∈A). An A-module M is called simple or irreducible if there are no proper submodules of M (i.e., other than the zero submodule and M itself). If M does possess a proper submodule S then M is called reducible and one can form the quotient module Q = M/S. Proceeding with constructing proper submodules and quotient modules of these derived modules as much as possible, one can form a composition series for M as a chain of submodules:
The fundamental computational tool for analysis of A-modules over fields is the so-called Meataxe algorithm of Parker (1984), which was later improved by Holt & Rees (1994). The Meataxe algorithm takes an A-module M and determines whether M is simple; if M is not simple then the algorithm also returns a proper submodule S of M. The algorithm works by constructing submodules generated by vectors from suitable generalised eigenspaces of random elements of A; either this yields a proper submodule with reasonable probability, or gives information whereby M can be proved to be simple. If the Meataxe shows that a given submodule M is not simple and thus also returns a proper submodule S, then one can reapply the Meataxe recursively on S and the quotient module M/S and so on to construct a complete composition series for M.
Magma contains a highly optimised implementation of the Meataxe algorithm, which carefully minimises the memory usage as it proceeds (several dense matrices need to be managed in large examples). The eigenspaces of elements of A are formed via the asymptotically-fast matrix algorithms for multiplication and echelonisation. Furthermore, a key subroutine of the algorithm computes the invariant submodule of M generated by a given vector (traditionally called the ‘Spin’ algorithm); Magma's novel implementation of this algorithm also maps this problem to matrix multiplication, so this takes advantage of the optimised fast matrix operations for a wide range of fields (see the section on matrix operations). Thus Magma contains the only implementation of the Meataxe algorithm which maps the whole algorithm completely to fast matrix multiplication.
The original Meataxe algorithm was only designed for the case that A is an algebra over a finite field and is technically Las Vegas (with a very small probability of failure) but terminates on virtually all inputs in practice. Magma contains an extension of the Meataxe to fields of characteristic zero; this is not guaranteed to terminate on large examples for general A-modules because of the difficulty of finding singular elements of A when the coefficients are large, but works very well on many classes of inputs (see below).
Suppose M1 and M2 are A-modules (for the same fixed algebra A). The module of homomorphisms H = HomA(M1, M2) can be viewed as the set of all homomorphisms from the underlying vector space of M1 to the underlying vector space of M2 which are compatible with the action of A (i.e., H is the set of all homomorphisms h from M1 to M2 such that h(v·a) = h(v)·a for all v∈M1,a∈A). The endomorphism ring of an A-module M is simply HomA(M,M); i.e., the set of homomorphisms of M into itself which are compatible with A.
An important problem in module theory is the testing of two modules for isomorphism. Suppose M1 and M2 are A-modules. If one of the modules is irreducible (which is easily determined first by the Meataxe) then Magma uses a straight-forward algorithm of Holt and Rees, using some information computed by the Meataxe for the irreducible module. Otherwise, Magma uses an advanced algorithm based on the general Hom-algorithm above, which searches for an invertible homomorphism or proves non-isomorphism via various criteria.
Suppose that an A-module M possesses a proper submodule S. If there also exists a direct summand T such that M = S⊕T, then M is called decomposable. Conversely, if M cannot be written as a direct sum of proper submodules, then M is called indecomposable. Magma contains an algorithm developed by C. Leedham-Green and A. Steel for determining whether such a module is decomposable or not. This algorithm depends on an analysis of the endomorphism ring of M (which is first computed by the above Hom-module).
The characteristic-zero Meataxe algorithm is used heavily in the number theory package of Magma when decomposing an ideal of an order O of a number field K = ℚ(α) into the product of prime ideals of O.