Magma has the capability of constructing a presentation for an algebra A generated by a collection (α1, ..., αt) of n x n matrices over a finite field k. The presentation has the form
A isomorphic to P/ I
where P is a free algebra in noncommuting variable and I is a two-sided ideal in P. The presentation is obtained by computing a set of primitive idempotents for the algebra and extracting generators for the radical of the algebra. For such an algebra there is a sequence
0 -> (Rad)(A) -> A -> A/(Rad)(A) -> 0
which is split in the sense that A/(Rad)(A) is a subalgebra A. Moreover, A/(Rad)(A) is a direct sum of complete matrix algebras Ai over extensions Ki of the field k. Each complete matrix algebra Ai is generated by two elements bi and ti. The element bi has minimal rank and bini - 1 = ei is a primitive idempotent where ni is the number of elements in the field Ki. That is, bi is a generator for the multiplicative group of nonzero elements of eiAiei isomorphic to Ki. The element ti is conjugate to a permutation matrix of degree ni in Ai. The elements z1, ..., zs are generators of the radical of A. These elements are computed so as to lie in the condensed algebra eAe where e = ∑ei.
The calculation produces also a set of generators and relations for the condensed algebra eAe. This algebra is Morita equivalent to A, and hence shares many of the same homological properties of the algebra A.
In the course of obtaining the presentation, several aspects of the algebra are computed.
Returns the map of a free algebra onto the matrix algebra A, such that the variables of the free algebra go to the generators of A.
The simple quotient algebras of the matrix algebra A. The output is a record having the following fields:
- (a)
- The actual simple algebras that are the quotients of the algebra A. The function returns the sequence of mappings from the natural free-algebra cover of A to the quotients. The variable corresponding to a generator of A is mapped to the corresponding generator of the quotient. (field name SimpleQuotients)
- (b)
- The degrees of the quotients as matrix algebras over their centers (field name DegreesOverCenters).
- (c)
- The degrees of the extension of center of the quotient algebra over the base field of A (field name DegreesOfCenters).
- (d)
- The number of elements in the center of the quotient algebra (field name OrdersOfCenters).
The initial data for a decomposition of the matrix algebra A. The output is a sequence of records, one for each simple quotient algebra of A, each consisting of the following fields.
- (a)
- AlgebraIdempotent : An idempotent whose image in the simple quotient is the identity matrix.
- (b)
- PrimitiveIdempotent : A primitive idempotents whose image in the quotient is primitive.
- (c)
- PrimitiveIdempotentOnQuotient : The image of the primitive idempotent in the quotient algebra.
- (d)
- FieldGenerator : A multiple of the primitive idempotent which is a field generator for the center of the algebra.
- (e)
- FieldGeneratorOnQuotient : The image of the field generator in the quotient algebra.
- (f)
- GeneratingPolForCenter : The minimal polynomial for the matrix of the field generator.
A list of primitive idempotent for the matrix algebra A, one idempotent for each irreducible module.
The sequence of ranks of the primitive idempotents for the matrix algebra A.
Returns the map of a free algebra onto the matrix algebra A, such that the variables of the free algebra go the generators of the algebra.
Returns the algebra eAe where e is a sum of primitive idempotents, one for each simple A-module.
We form a matrix algebra over the field with three elements generated by two elements. The algebra is block upper triangular, where the upper left block is a field extension of degree three and the lower block is a filed extension of degree 2.
> a1 := KMatrixSpace(GF(3),3,3)![0,1,0,0,0,1,-1,0,1]; > a2 := KMatrixSpace(GF(3),2,2)![0,1,-1,0]; > z1 := KMatrixSpace(GF(3),5,5)!0; > z2 := InsertBlock(z1,a1,1,1); > z2; [0 1 0 0 0] [0 0 1 0 0] [2 0 1 0 0] [0 0 0 0 0] [0 0 0 0 0] > z3 := InsertBlock(z1,a2,4,4);
z2 and z3 are the matrices of the field extensions. Next, add an entry to z3 that is an extension class between the two algebras.
> z3[1][4] := 1; > z3; [0 0 0 1 0] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 1] [0 0 0 2 0] > A := MatrixAlgebra<GF(3),5|z2,z3>;
We can check to see if the quotients came out as expected.
> SimpleQuotientAlgebras(A);
rec<recformat<SimpleQuotients: SeqEnum, DegreesOverCenters:
SeqEnum, DegreesOfCenters: SeqEnum, OrdersOfCenters: SeqEnum> |
SimpleQuotients := [
Mapping from: Free associative algebra of rank 2 over
GF(3) to Matrix Algebra of degree 3 with 2
generators over GF(3),
Mapping from: Free associative algebra of rank 2 over
GF(3) to Matrix Algebra of degree 2 with 2
generators over GF(3)
],
DegreesOverCenters := [ 1, 1 ],
DegreesOfCenters := [ 3, 2 ],
OrdersOfCenters := [ 27, 9 ]
Here are the idempotents.
> PrimitiveIdempotents(A);
[
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 2]
[0 0 0 0 0]
[0 0 0 0 0],
[0 0 0 0 0]
[0 0 0 0 0]
[0 0 0 0 1]
[0 0 0 1 0]
[0 0 0 0 1]
]
Finally we have the Cartan matrix.
> CartanMatrix(A); [1 3] [0 1]
We use the idempotents as the first step in the presentation process. The generators of the algebra consist of the field generators, each of which is a generator of the center of a simple quotient algebra multiplied by a corresponding primitive idempotent, permutation matrices, one for each simple quotient algebra and generators for the radical, all of which can be taken to be in the subalgebra eAe where e is the sum of one primitive idempotent for each simple quotient algebra.
For display purposes the variables for the free algebra of the presentations are given names. The variables b.i represent field generators, while the t.i's are permutation matrices and the z.i's are the generators of the radical. The reader should be warned that these names are not suitable for input into other function.
The data on the semisimple generators of the algebra A, that is the generators in A of A/Rad(A). Some of the output is intended for use in other functions. The return is a sequence of records, one for each simple quotient algebra. Each record consists of the following fields.
- (a)
- PowersOfFieldGenerators : A record consisting of look-up tables for the powers of the field generators as elements both of the algebra A and the simple quotient algebra.
- (b)
- Permutation : The permutation matrix of the quotient algebra as an element of A.
- (c)
- PermutationOnQuotient : The permutation matrix on the quotient.
- (d)
- FieldGenerator : The matrix of the field generator as an element of A.
- (e)
- FieldGeneratorOnQuotient : The matrix of the field generator as an element of the quotient algebra.
- (f)
- PrimitiveIdempotent : The matrix of the primitive idempotent on A.
- (g)
- PrimitiveIdempotentOnQuotient : The matrix of the primitive idempotent on the quotient algebra.
- (h)
- GeneratingPolForCenter : The Galois polynomial for the extension of the center of the quotient algebra over the base ring.
The standard generators of the matrix algebra A. The output is a record consisting of the following fields.
- (a)
- FieldGenerators : The sequence of matrices of the field generators, one for each simple quotient algebra.
- (b)
- PermutationMatrices : The sequence of permutation matrices for the quotient algebras as elements of A, one for each quotient algebra.
- (c)
- PrimitiveIdempotents : The sequence of primitive idempotents for A, one for each quotient algebra.
- (d)
- RadicalGenerators : A set of generators for the radical of A arranged as a list of lists of generators of the radical of eiAej for ei and ej primitive idempotents.
- (e)
- SequenceRadicalGenerators : A sequence of minimal generators of radical of A.
- (f)
- GeneratingPolynomialsForCenters : The galois polynomials of the centers over the base field.
- (g)
- StandardFormConjugationMatrices : The matrices which conjugate the element of A into the standard form relative to the computed primitive idempotents for A.
The accumulated structure of the matrix algebra A. The return is a record with the following fields. Some of this information is saved to be used in other calculations.
- (a)
- FreeAlgebra : The free algebra in the newly computed variables for the algebra.
- (b)
- RelationsIdeal : The ideal of relations among the new computed generators.
- (c)
- StandardFreeAlgebraCover : The map from the free algebra to A.
- (d)
- FieldGenerators : The matrices in A of the generators of the centers of the simple quotient algebras of A.
- (e)
- PermutationMatrices : The permutation matrices each of which together with the corresponding field generator, generates a simple quotient algebra as a subalgebra of A.
- (f)
- PrimitiveIdempotents : The primitive idempotents, each of which is a power of the corresponding field generator.
- (g)
- RadicalGenerators : A list of lists giving the generators of the radical of A which are in eiAej where { ei} are the primitive idempotents.
- (h)
- CondensedRadicalBasis : The condensed matrices in eAe of a basis for the radical of the algebra. The output is a list of lists giving the basis for eiAej. Each entry in the list of lists is a tuple consisting of a matrix in the condensed algebra and the monomial which expresses this matrix as a product of the generators.
- (i)
- CondensedFieldGenerators : The condensed matrices in eAe of the field generators.
- (j)
- FieldPolynomials : The sequence of minimal polynomials of the field generators.
- (k)
- DegreesOfSimpleModules : The dimensions of the Simple modules of A.
- (l)
- DegreeOfFieldExtensions : The degrees of the centers of simple quotient algebras of A over the base field of A.
- (m)
- SimpleQuotientAlgebras : The simple quotient algebras of A.
- (n)
- StandardFormConjugationMatrices : The matrices which conjugate the algebra A into standard form with respect to the computed system of primitive idempotents.
The presentation in generators and relations of the matrix algebra A. The function returns the free algebra and the relations ideal calculated in the algebra structure program, as well as the map from the free algebra to A.
Returns the pair (M and M - 1) of matrices that conjugate the matrix algebra A into standard form with respect to a chosen set of primitive idempotents.
The matrices, conjugating by which, gives the condensation of A.
The sequence of matrices of elements that generate the radical of A.
The Cartan Matrix of the algebra A.
In this example we form the permutation module M of the symmetric group G on seven letters by the Young subgroup that is the direct product H of two copies of the symmetric group on three letters. The algebra A is the image of the group algebra in the ring of endomorphisms of M.
> G := Sym(7); > H := sub<G| G!(1,2,3),G!(1,2),G!(4,5,6), G!(4,5)>; > M := PermutationModule(G, H, GF(5)); > M; GModule M of dimension 140 over GF(5) > A := Action(M);
We see that A has seven simple quotients.
> SimpleQuotientAlgebras(A);
rec<recformat<SimpleQuotients: SeqEnum, DegreesOverCenters:
SeqEnum, DegreesOfCenters: SeqEnum, OrdersOfCenters: SeqEnum> |
SimpleQuotients := [
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 35 with 2
generators over GF(5),
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 15 with 2
generators over GF(5),
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 13 with 2
generators over GF(5),
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 8 with 2
generators over GF(5),
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 8 with 2
generators over GF(5),
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 6 with 2
generators over GF(5),
Mapping from: Free associative algebra of rank 2 over
GF(5) to Matrix Algebra of degree 1 with 2
generators over GF(5)
],
DegreesOverCenters := [ 35, 15, 13, 8, 8, 6, 1 ],
DegreesOfCenters := [ 1, 1, 1, 1, 1, 1, 1 ],
OrdersOfCenters := [ 5, 5, 5, 5, 5, 5, 5 ]
>
> RanksOfPrimitiveIdempotents(A);
[ 1, 1, 3, 2, 1, 4, 3 ]
The condensed algbra of A is a much smaller object.
> B := CondensedAlgebra(A); > B; Matrix Algebra of degree 15 with 13 generators over GF(5) > CartanMatrix(A); [1 0 0 0 0 0 0] [0 1 0 0 0 0 0] [0 0 2 0 1 0 1] [0 0 0 1 0 1 0] [0 0 1 0 1 0 0] [0 0 0 1 0 2 0] [0 0 1 0 0 0 2]
From the Cartan Matrix we can see that A has four blocks. The first and second simple subalgebras are in blocks by themselves. The subalgebras numbers 3, 5, and 7 form another block as do the subalgebras 4 and 6. Note that B, being Morita equivalent to A, has the same Cartan Matrix and the same block structure.
The presentation machinery also gives a test for membership in a matrix algebra. If A is a subalgebra of the n x n matrices generated by some collection of matrices, Magma can tell if any n x n matrix is an element of A. If the element is in A then Magma can write the element as a polynomial in the polynomial ring of the presentation.
The data needed for the solution to the word problem. The output is a list of lists of basis elements for the radical together with the corresponding monomials in the generators of the free algebra.
Returns true if the matrix x is in the subalgebra A, and if true returns also an expression of the element x as a polynomial in the presentation of A.
In this example we form the permutation module for the symmetric group G acting on the coset space of the normalizer H of Sylow 3-subgroup of G. The coefficients are in the field with two elements. The algebra A is the image of the group algebra in the endomorphism ring of the permutation module.
> G := Sym(5); > H := Normalizer(G,Sylow(G,3)); > M := PermutationModule(G,H, GF(2)); > M; GModule M of dimension 10 over GF(2) > A := Action(M);
Here we get the presentation of A.
> P, I, mu := Presentation(A); > Dimension(P/I); 42
Thus the dimension of A is 42.
> CartanMatrix(A); [1 0 1] [0 1 0] [1 0 2] > B := CondensedAlgebra(A); > Q, J, theta := Presentation(B);
The presentation of B has the form:
> J;
Two-sided ideal of Free associative algebra of rank 5 over GF(2)
Non-commutative Graded Lexicographical Order
Variables: b_1, b_2, b_3, z_1, z_2
Groebner basis:
[
b_2^2 + b_2,
b_2*b_3,
b_2*z_1,
b_2*z_2,
b_3*b_2,
b_3^2 + b_3,
b_3*z_1,
b_3*z_2 + z_2,
z_1*b_2,
z_1*b_3 + z_1,
z_1^2,
z_1*z_2,
z_2*b_2,
z_2*b_3,
z_2^2,
b_1 + b_2 + b_3 + 1
]
The matrix A.1 is the first of the original generators for A. We can check that A.1 is an element of the algebra generated by the computed generators of A.
> boo, y := WordProblem(A,A.1); > boo; true
The element y is the expression of A.1 as a polynomial in the free algebra P in the new computed generators for A.
> y;
t_1^4*b_1*t_1^3 + t_2^4*b_2*t_2^3 + t_1^4*b_1*t_1^2 +
t_2^3*b_2*t_2^3 + t_1^2*b_1*t_1^3 + t_1^4*b_1*t_1 +
t_2^2*b_2*t_2^3 + t_2^3*b_2*t_2^2 + t_2^4*b_2*t_2 +
t_1^2*b_1*t_1^2 + t_1^3*b_1*t_1 + t_1^4*b_1 + t_1^4*z_1 +
t_2*b_2*t_2^3 + t_2^2*b_2*t_2^2 + t_2^3*b_2*t_2 +
t_1*b_1*t_1^2 + t_1^3*b_1 + t_3*z_2*t_1^2 + t_1^2*b_1 +
t_2*b_2*t_2 + t_2^2*b_2 + t_1*b_1 + t_2*b_2 + t_3*b_3 +
t_3*z_2
The mapping mu is the function from the free algebra P into A.
> mu(y); [0 1 0 0 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0] [0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0] [0 0 0 0 0 0 1 0 0 0] [0 0 0 0 0 0 0 0 1 0] [0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 0 1] [1 0 0 0 0 0 0 0 0 0] [0 0 1 0 0 0 0 0 0 0]
The ultimate check of the accuracy of the computation is that the polynomial expressions give back the original generators.
> mu(y) eq A.1; true
Finally we can check whether a random 10 x 10 matrix is an element of A.
> b := Random(Generic(A)); > WordProblem(A,b); false