# Presentations for Matrix Algebras Magma has the capability of constructing a presentation for an algebra $A$ generated by a collection ${\alpha_1, \dots, \alpha_t}$ of $n \times n$ matrices over a finite field $k$. The presentation has the form $$ A \cong 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 \longrightarrow {\rm Rad}(A) \longrightarrow A \longrightarrow A/{\rm Rad}(A) \longrightarrow 0 $$ which is split in the sense that $A/{\rm Rad}(A)$ is a subalgebra $A$. Moreover, $A/{\rm Rad}(A)$ is a direct sum of complete matrix algebras $A_i$ over extensions $K_i$ of the field $k$. Each complete matrix algebra $A_i$ is generated by two elements $b_i$ and $t_i$. The element $b_i$ has minimal rank and $b_i^{n_i-1} = e_i$ is a primitive idempotent where $n_i$ is the number of elements in the field $K_i$. That is, $b_i$ is a generator for the multiplicative group of nonzero elements of $e_iA_ie_i \cong K_i$. The element $t_i$ is conjugate to a permutation matrix of degree $n_i$ in $A_i$. The elements $z_1, \dots, z_s$ are generators of the radical of $A$. These elements are computed so as to lie in the condensed algebra $eAe$ where $e = \sum e_i$. 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. ## Quotients and Idempotents ### `NaturalFreeAlgebraCover(A): AlgMat -> Map` 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$. ### `SimpleQuotientAlgebras(A): AlgMat -> Rec` 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`). ### `PrimitiveIdempotentData(A): AlgMat -> SeqEnum, Map, SeqEnum` 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. ### `PrimitiveIdempotents(A): AlgMat -> SeqEnum` A list of primitive idempotent for the matrix algebra $A$, one idempotent for each irreducible module. ### `RanksOfPrimitiveIdempotents(A): AlgMat -> SeqEnum` The sequence of ranks of the primitive idempotents for the matrix algebra $A$. ### `NaturalFreeAlgebraCover(A): AlgMat -> Map` 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. ### `CondensedAlgebra(A): AlgMat -> AlgMat` Returns the algebra $eAe$ where $e$ is a sum of primitive idempotents, one for each simple $A$-module. ### `Example: Primitive Idempotents (ex-b62a87)` 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. ```magma > 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. ```magma > 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; ``` We can check to see if the quotients came out as expected. ```magma > SimpleQuotientAlgebras(A); rec | 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. ```magma > 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. ```magma > CartanMatrix(A); [1 3] [0 1] ``` ## Generators and Presentations 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. ### `SemisimpleGeneratorData(A): AlgMat -> SeqEnum` 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. ### `AlgebraGenerators(A): AlgMat -> Rec` 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 $e_iAe_j$ for $e_i$ and $e_j$ 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$. ### `AlgebraStructure(A): AlgMat -> Rec` 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 $e_iAe_j$ where $\{ e_i\}$ 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 $e_iAe_j$. 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. ### `Presentation(A): AlgMat -> AlgFr, AlgFr, Map` 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$. ### `StandardFormConjugationMatrices(A): AlgMat -> Tup` 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. ### `CondensationMatrices(A): AlgMat -> Tup` The matrices, conjugating by which, gives the condensation of $A$. ### `SequenceOfRadicalGenerators(A): AlgMat -> SeqEnum` The sequence of matrices of elements that generate the radical of $A$. ### `CartanMatrix(A): AlgMat -> ModMatRngElt` The Cartan Matrix of the algebra $A$. ### `Example: Condensed Algebra (ex-865183)` 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$. ```magma > G := Sym(7); > H := sub; > 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. ```magma > SimpleQuotientAlgebras(A); rec | 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. ```magma > 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. ## Solving the Word Problem The presentation machinery also gives a test for membership in a matrix algebra. If $A$ is a subalgebra of the $n \times n$ matrices generated by some collection of matrices, Magma can tell if any $n \times 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. ### `WordProblemData(A): AlgMat -> List` 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. ### `WordProblem(A, x): AlgMat, AlgMatElt -> BoolElt, AlgFrElt` 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$. ### `Example: Presentation (ex-6d214a)` 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. ```magma > 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$. ```magma > P, I, mu := Presentation(A); > Dimension(P/I); 42 ``` Thus the dimension of $A$ is 42. ```magma > 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: ```magma > 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. ```magma > 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$. ```magma > 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$. ```magma > 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. ```magma > mu(y) eq A.1; true ``` Finally we can check whether a random $10 \times 10$ matrix is an element of $A$. ```magma > b := Random(Generic(A)); > WordProblem(A,b); false ```