|
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|