%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A smash.tex GAP documentation Derek Holt %A Charles Leedham-Green %A Eamonn O'Brien %A Sarah Rees %% %A @(#)$Id: smash.tex,v 3.6 1994/06/21 12:46:01 vfelsch Rel $ %% %Y Copyright 1994 -- School of Mathematical Sciences, ANU %% %% This file describes certain matrix group and G-module functions. %% %H $Log: smash.tex,v $ %H Revision 3.6 1994/06/21 12:46:01 vfelsch %H altered an example %H %H Revision 3.5 1994/06/17 19:04:18 vfelsch %H examples adjusted to version 3.4 %H %H Revision 3.4 1994/05/22 12:42:09 fceller %H initial GAP 3.2 revision %H %% \Chapter{Smash, Matrix Groups and $G$-Modules} This chapter describes functions which may be used to construct and investigate the structure of matrix groups defined over finite fields. These functions permit the user to construct certain types of matrix groups and $G$-modules; to test whether a $G$-module is irreducible; to decide whether a group has certain decomposition with respect to a normal subgroup; and to select random elements with certain properties. Descriptions of most of the algorithms used in these functions can be found in \cite{HR94}, \cite{HLOR94a} and \cite{HLOR94b}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{GModule} 'GModule( )' \\ 'GModule( , )' \\ 'GModule( )' \\ 'GModule( )' 'GModule' constructs a $G$-module record from a list of matrices or from a matrix group . The underlying field may be specified as an optional argument; otherwise, it is taken to be the field generated by the entries of the given matrices. The $G$-module record returned contains components 'field', 'dim', 'matrices' and 'isGModule'. In using the functions described in this chapter, other components of the $G$-module record may be set, which describe the nature of the action of the group on the module. A description of these components is given in Section "Components of a $G$-module record". This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsGModule} 'IsGModule( )' If is a record with component 'isGModule' set to 'true', 'IsGModule' returns 'true'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DualGMod} 'DualGMod( )' is a $G$-module. The dual module (obtained by inverting and transposing the generating matrices) is calculated and returned. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{InducedGMod} 'InducedGMod( , )' is a transitive permutation group $G$, and an $H$-module, where $H$ is the subgroup of $G$ returned by the function 'Stabilizer( , 1 )'. (That is, the matrix generators for should correspond to the permutations generators for $H$ returned by this function call.) The induced $G$-module is calculated and returned. If the action of $H$ on is trivial, then 'PermGMod' should be used instead. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PermGMod} 'PermGMod( , , )' \\ 'PermGMod( , )' is a permutation group, and a finite field. If is supplied, it should be an integer in the permutation domain of ; by default, it is 1. The permutation module of on the orbit of over the field is calculated and returned. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{TensorProductGMod} 'TensorProductGMod( , )' The tensor product of the $G$-modules and is calculated and returned. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{WedgeGMod} 'WedgeGMod( )' The wedge product of the $G$-module -- that is, the action on antisymmetric tensors -- is calculated and returned. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{WreathProd} 'WreathProd( , )' is a matrix group, a $G$-module, a list of matrices, a permutation group or a list of permutations, and can be a permutation group or a list of permutations. Let $G$ be the permutation or matrix group specified or generated by the first argument, $P$ the permutation group specified or generated by the second argument. The wreath product of $G$ and $P$ is calculated and returned. This is a matrix group or a permutation group of dimension or degree $dt$, where $d$ is the dimension or degree of $G$ and $t$ the degree of $P$. (If $G$ is a permutation group, this function has the same effect as 'WreathProduct( $G$, $P$ )'.) This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{WreathPower} 'WreathPower( , )' is a matrix group, a $G$-module, a list of matrices, a permutation group or a list of permutations, and can be a permutation group or a list of permutations. Let $G$ be the permutation or matrix group specified or generated by the first argument, and $P$ the permutation group specified or generated by the second argument. The wreath power of $G$ and $P$ is calculated and returned. This is a matrix group or a permutation group of dimension or degree $d^t$, where $d$ is the dimension or degree of $G$ and $t$ the degree of $P$. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsIrredGMod} 'IsIrredGMod( )' is a $G$-module. 'IsIrredGMod' tests for irreducibility, and returns 'true' or 'false'. It also sets a number of components of the record , which are assumed to be set in other functions described here. If is reducible, a sub- and quotient-module can be constructed by using the functions in the next section. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SubQuotGMod} 'SubGMod( , )' \\ 'QuotGMod( , )' \\ 'SubQuotGMod( , )' All of these functions take a $G$-module as input, together with a basis for a proper submodule, which is assumed to be normalised, in the weak sense that the first nonzero component of each vector in the basis is 1, and no two vectors in the basis have their first nonzero components in the same position. The basis is given as an $r \times n$ matrix, where $r$ is the length of the basis. Normally, one runs 'IsIrredGMod()' first, and (assuming it returns 'false') then runs these functions using 'SubbasisFlag()' as the second argument. 'SubGMod' returns the submodule having as basis, 'QuotGMod' the corresponding quotient module, and 'SubQuotGMod' returns a 3-element list containing the submodule, the quotient module, and also the original matrices rewritten with respect to a basis in which a basis for the submodule comes first. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SpinBasis} 'SpinBasis( , )' The input is a vector, , and a list of $n \times n$ matrices, , where $n$ is the length of the vector. A normalised basis of the submodule generated by the action of the matrices (acting on the right) on the vector is calculated and returned. It is returned as an $r \times n$ matrix, where $r$ is the dimension of this submodule. 'SpinBasis' is used by 'IsIrredGMod'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsAbsIrredGMod} 'IsAbsIrredGMod( )' This function can only be run if 'IsIrredGMod()' has returned 'true'. The $G$-module is tested for absolute irreducibility, and 'true' or 'false' is returned. If the result is 'false', then the dimension $e$ of the centralising field of can be accessed by 'FieldExtDegFlag()'. A matrix which centralises (that is, it centralises the generating matrices 'MatricesFlag()') and which has minimal polynomial of degree $e$ over the ground field can be accessed as 'CentMatFlag()'. If such a matrix is required with multiplicative order $q^e-1$, where $q$ is the order of the ground field, then 'FieldGenCentMat' can be called. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{FieldGenCentMat} 'FieldGenCentMat( )' This function can only be run if the function 'IsIrredGMod()' has returned 'true', and if 'IsAbsIrredGMod()' has returned 'false'. A matrix which centralises the $G$-module and which has multiplicative order $q^e-1$, where $q$ is the order of the ground field and $e$ is the dimension of the centralising field of , is calculated and stored. It can be accessed as 'CentMatFlag()'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsomGMod} 'IsomGMod( , )' This function tests the $G$-modules and for isomorphism. Both $G$-modules must be defined over the same field with the same number of defining matrices, and at least one of them must be known to be irreducible (that is, 'IsIrredGMod()' has returned 'true'). Otherwise the function will exit with an error. If they are not isomorphic, then 'false' is returned. If they are isomorphic, then a $d \times d$ matrix is returned (where $d$ is the dimension of the modules) whose rows give the images of the standard basis vectors of in an isomorphism to . This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{HomGMod} 'HomGMod( , )' This function can only be run if 'IsIrredGMod()' has returned 'true'. and are assumed to be $G$-modules for the same group $G$, and a basis of the space of $G$-homomorphisms from to is calculated and returned. Each homomorphism in this list is given as a $d_1 \times d_2$ matrix, where $d_1$ and $d_2$ are the dimensions of and ; the rows of the matrix are the images of the standard basis of in under the homomorphism. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MinSubGMods} 'MinSubGMods( , )' \\ 'MinSubGMods( , , )' This function can only be run if 'IsIrredGMod()' has returned 'true'. and are assumed to be $G$-modules for the same group $G$. 'MinSubGMods' computes and returns a list of the normalised bases of all of the minimal submodules of that are isomorphic to . (These can then be constructed as $G$-modules, if required, by calling 'SubGMod(, )' where is one of these bases.) The optional parameter should be a positive integer. If the number of submodules exceeds , then the procedure is aborted. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ChopGMod} 'ChopGMod( )' is a $G$-module. This function returns a list, each component of which is itself a 2-element list [, ], where is an irreducible composition factor of , and is the multiplicity of this factor in . The elements correspond to nonisomorphic irreducible modules. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SmashGMod} 'SmashGMod( , )' \\ 'SmashGMod( , , )' 'SmashGMod' seeks to find a decomposition of a module with respect to a normal subgroup. is a module for a finite group $G$ of matrices over a finite field. is a set of matrices, generating a subgroup of $G$. The only permitted value for the optional parameter is the string '\"tensorprod\"'. 'SmashGMod' attempts to find some way of decomposing the module with respect to the normal subgroup $\langle S \rangle ^G$. It returns 'true' if some decomposition is found, 'false' otherwise. $G$ is assumed to act irreducibly and absolutely irreducibly. is assumed to contain at least one non-scalar matrix. The function returns 'true' if it succeeds in verifying that either $G$ acts imprimitively, or semilinearly, or preserves a tensor product, or preserves a symmetric tensor product (that is, permutes the tensor factors) or $G$ normalises a group which is extraspecial or a 2-group of symplectic type. Each of these decompositions, if found, involves $\langle S \rangle ^G$ in a natural way. Components are added to the record which indicate the nature of a decomposition. Details of these components can be found in Section "Components of a $G$-module record". If no decomposition is found, the function returns 'false'. In general, the answer 'false' indicates that there is no such decomposition with respect to $\langle S \rangle ^G$. However, 'SmashGMod' may fail to detect a symmetric tensor product decomposition, since the detection of such a decomposition relies on the choice of random elements. 'SmashGMod' adds conjugates to the set until a decomposition of the underlying vector space can be found as a sum of irreducible $\langle S \rangle$-modules. Decompositions are searched for using the functions 'SemiLinearDecomp', 'TensorProductDecomp', 'SymTensorProductDecomp', 'ExtraSpecialDecomp' and 'MinBlocks'. At the end of the call to 'SmashGMod', may be larger than at the start (but its normal closure has not changed). If the optional argument is supplied, some short cuts are taken, and 'false' is returned as soon as it is clear that $G$ preserves no tensor product decomposition with respect to $\langle S \rangle^G$. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SemiLinearDecomp} 'SemiLinearDecomp( , , , )' is a module for a finite matrix group $G$ over a finite field $GF(q)$. The function returns 'true' if $G$ is found to act semilinearly. $G$ is assumed to act absolutely irreducibly. is a set of invertible matrices, generating a subgroup of $G$, and assumed to act irreducibly but not absolutely irreducibly on the underlying vector space of . The matrix centralises the action of on the underlying vector space and so acts as multiplication by a field generator $x$ of $GF(q^e)$ for some embedding of a $d/e$-dimensional vector space over $GF(q^e)$ in the $d$-dimensional space. If centralises the action of the normal subgroup $\langle S \rangle ^G$ of $G$, then $\langle S \rangle ^G$ embeds in $GL(d/e,q^e)$, and $G$ embeds in $\Gamma L(d/e,q^e)$, the group of semilinear automorphisms of the $d/e$-dimensional space. This is verified by the construction of a map from $G$ to $Aut(GF(q^e))$. If the construction is successful, the function returns 'true'. Otherwise a conjugate of an element of is found which does not commute with . This conjugate is added to and the function returns 'false'. 'SemiLinearDecomp' is called by 'SmashGMod'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{TensorProductDecomp} 'TensorProductDecomp( , , , )' is a module for a matrix group $G$, is a basis of the underlying vector space, and are two integers whose product is the dimension of that space. 'TensorProductDecomp' returns 'true' if can be decomposed as a tensor product of spaces of dimensions and with respect to the given basis, and 'false' otherwise. The matrices which represent the action of the generators of $G$ with respect to the appropriate basis are computed. 'KroneckerFactors( , , )' \\ 'KroneckerFactors( , , , )' For each generating matrix , 'KroneckerFactors' tests whether or not it can be written as the Kronecker product of matrices $A$ and $B$. If the field $F$ is not supplied, it is taken to be 'Field()'. It returns either the pair [$A$, $B$] or 'false'. 'TensorProductDecomp' is called by 'SmashGMod'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{SymTensorProductDecomp} 'SymTensorProductDecomp( , )' is a module for a finite matrix group $G$ over a finite field. is the module corresponding to the action of a subgroup $H$ of $G$ on the same vector space. Both $G$ and $H$ are assumed to act absolutely irreducibly. The function returns 'true' if can be decomposed as a tensor product of two or more $H$-modules, all of the same dimension, where these tensor factors are permuted by the action of $G$. In this case, components of record the tensor decomposition and the action of $G$ in permuting the factors. If no such decomposition is found, 'SymTensorProductDecomp' returns 'false'. A negative answer cannot be 100\% reliable, since decomposition of as a tensor product is investigated using randomly generated elements. 'SymTensorProductDecomp' is called by 'SmashGMod'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ExtraSpecialDecomp} 'ExtraSpecialDecomp( , )' is a module for a finite matrix group $G$ over a finite field where $G$ is assumed to act absolutely irreducibly. is a set of invertible matrices, assumed to act absolutely irreducibly on the underlying vector space of . 'ExtraSpecialDecomp' returns 'true' if (modulo scalars) $\langle S \rangle$ is an extraspecial $r$-group, for some prime $r$, or a 2-group of symplectic type (that is, the central product of an extraspecial 2-group with a cyclic group of order 4), normalised by $G$. Otherwise it returns 'false'. 'ExtraSpecialDecomp' attempts to prove that $\langle S \rangle$ is extraspecial or of symplectic type by construction. It tries to find generators $x_1, \ldots, x_k, y_1, \ldots, y_k, z$ for $\langle S \rangle$, with $z$ central of order $r$, each $x_i$ commuting with all other generators except $y_i$, each $y_i$ commuting with all other generators except $x_i$, and $[x_i, y_i] = z$. If it succeeds, it checks that conjugates of these generators are also in . 'ExtraSpecialDecomp' is called by 'SmashGMod'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPrimitiveGMod} 'IsPrimitiveMatrixGroup( )' \\ 'IsPrimitiveGMod( )' 'IsPrimitiveGMod' takes as input a module, , for a finite matrix group $G$ over a finite field and seeks to decide whether or not $G$ acts primitively. If the function returns 'false', then $G$ is imprimitive and 'BlockSystemFlag()' returns a block system (described in 'MinBlocks'). 'IsPrimitiveMatrixGroup' takes as input and seeks to decide whether or not acts primitively. The function returns a list containing two values\:\ a boolean and the $G$-module, , for $G$. If the boolean is 'false', then is imprimitive and 'BlockSystemFlag ()' returns a block system. If either function discovers that acts semilinearly, it cannot decide whether acts primitively and returns '\"unknown\"'. 'SmashGMod' is called by 'IsPrimitiveMatrixGroup'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MinBlocks} 'MinBlocks( , )' 'MinBlocks' finds the smallest block containing the echelonised basis under the action of the $G$-module . The block system record returned has three components\:\ the number of blocks, a block containing the supplied basis , and a permutation group which describes the action of $G$ on the blocks. 'MinBlocks' is called by 'IsPrimitiveMatrixGroup'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{BlockSystemFlag} 'BlockSystemFlag( )' If the $G$-module record has a block system component, then 'BlockSystemFlag' returns this component, which has the structure described in 'MinBlocks', else it returns 'false'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{InitialiseSeed} 'InitialiseSeed( , , )' \\ 'InitialiseSeed( , , )' \\ 'InitialiseSeed( , , )' 'InitialiseSeed' takes as input either a list of matrices or a matrix group , or a $G$-module . It constructs and returns a list (or seed) of elements which can be used to generate random elements of the matrix group or $G$-module. It generates a seed of words and performs a total of matrix multiplications to obtain this list. The quality of the seed is controlled closely by the value of . For many applications, = 10 and = 50 seem to suffice. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RandomElement} 'RandomElement( )' It takes as input (which can be generated using 'InitialiseSeed') and returns a random element. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ChooseRandomElements} 'ChooseRandomElements( , )' It takes as input (which can be generated using 'InitialiseSeed'). It returns random elements. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ElementOfOrder} 'ElementOfOrder( , , )' It takes as input (which can be generated using 'InitialiseSeed') and seeks to find an element of order . It examines at most elements before returning 'false'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ElementWithCharPol} 'ElementWithCharPol( , , , )' It takes as input (which can be generated using 'InitialiseSeed'). It seeks to find element of order with characteristic polynomial . It examines at most random elements before returning 'false'. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LargestPrimeOrderElement} 'LargestPrimeOrderElement( , )' It takes as input (which can be generated using 'InitialiseSeed'). It generates random elements and determines which elements of prime order can be obtained from powers of each; it returns the largest found and its order as a list. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LargestPrimePowerOrderElement} 'LargestPrimePowerOrderElement( , )' It takes as input (which can be generated using 'InitialiseSeed'). It generates random elements and determines which elements of prime power order can be obtained from powers of each; it returns the largest found and its order as a list. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MatrixOrder} 'MatrixOrder( )' 'MatrixOrder' computes and returns the order of , a matrix defined over a finite field, using the Celler and Leedham-Green algorithm. 'MatrixProjectiveOrder( )' 'MatrixProjectiveOrder' computes the least postive integer $n$ such that $g^n$ is scalar; it returns as a list $n$ and $z$, where $g^n$ is scalar in $z$. This function requires the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Other matrix functions} 'Commutators( )' It returns a list containing the commutators of all pairs of matrices in . 'IsDiagonalMatrix( )' If a matrix, , is diagonal, it returs 'true', else 'false'. 'IsScalarMatrix( )' If a matrix, , is scalar, it returs 'true', else 'false'. 'PrintMat( )'\\ 'PrintMat( )' It converts the entries of a matrix defined over a finite field into integers and ``pretty-prints\"\ the result. All matrices in must be defined over the same finite field. These functions require the package \"smash\"\ (see "RequirePackage"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Components of a $G$-module record} A $G$-module is defined by the action of a group $G$, generated by a set of matrices, on a $d$-dimensional vector space over a field, $F = GF(q)$. The function 'GModule' returns a $G$-module record , where the component 'field' is set to $F$, 'dim' to $d$, 'matrices' to the set of generating matrices for $G$, and 'isGModule' to 'true'. These components are set for any $G$-module record constructed using 'GModule'. Additional components describe the nature of the action of the underlying group $G$ on the module, and are set by functions described in this chapter. Some of these carry information which is essentially private to these functions but others may be of more general use. These components are described briefly below. They need not appear in , or may be set to the value '\"unknown\"'. In general, a component 'component' is accessed via the function 'ComponentFlag' and its value is set with the function 'SetComponentFlag', where the first letter of the component is capitalised in the function names. For example, the component 'tensorBasis' is set by the function 'SetTensorBasisFlag' and accessed by 'TensorBasisFlag'. The component 'reducible' is set to be 'true' if is known to be reducible, and to 'false' if it is known not to be. This component is set by the function 'IsIrredGMod' which may also set the components 'subbasis', 'algEl', 'algElMat', 'algElCharPol', 'algElCharPolFac', 'algElNullspaceVec' and 'algElNullspaceDim'. If has been proved reducible, then 'subbasis' gives a basis for a submodule. Alternatively, if has been proved to be irreducible, 'algEl' is set to the random element $el$ of the group algebra which has been successfully used by the algorithm to prove irreducibility, represented abstractly, essentially as a sum of words in the generators, and 'algElMat' to the actual matrix $X$ that represents that element. The component 'algElCharPol' is set to the characteristic polynomial $p$ of $X$ and 'algElCharPolFac' to the factor $f$ of $X$ used by the algorithm. (Essentially irreducibility is proved by applying Norton\'s irreducibility criterion to the matrix $f(X)$; see \cite{HR94} for further details.) The component 'algElNullspaceVec' is set to an arbitrary vector of the nullspace $N$ of $f(X)$, and 'algElNullspaceDim' to the dimension of $N$. The component 'absReducible' is set to 'false' if is known to be absolutely irreducible, and to 'true' if it is known not to be. This component is set by the function 'IsAbsIrredGMod', which also sets the components 'fieldExtDeg', 'centMat', 'centMatMinPoly' if is not absolutely irreducible. In that case, 'fieldExtDeg' is set to the dimension $e$ of the centralising field of . The component 'centMat' is set to a matrix $C$, which both centralises each of the matrices in '.matrices' generating the group action of and has minimal polynomial $f$ of degree $e$. The component 'centMatMinPoly' is set equal to $f$. The component 'semiLinear' is set to 'true' in the function 'SemiLinearDecomp' if $G$ acts absolutely irreducibly on but embeds in a group of semilinear automorphisms over an extension field of degree $e$ over the field $F$. Otherwise it is not set. At the same time, 'fieldExtDeg' is set to $e$, 'linearPart' is set to a list of matrices $S$ which are normal subgroup generators for the intersection of $G$ with the general linear group in dimension $d/e$ over $GF(q^e)$, and 'centMat' is set to a matrix $C$ which commutes with each of those matrices. Here, $C$ corresponds to scalar multiplication in the module by an element of the extension field $GF(q^e)$. The component 'frobeniusAutos' is set to a list of integers $i$, one corresponding to each of the generating matrices $g$ for $G$ in the list 'matrices', such that $Cg = gC^{q^{i(g)}}$. Thus the generator $g$ acts on the field $GF(q^e)$ as the Frobenius automorphism $x \rightarrow x^{q^{i(g)}}$. The component 'tensorProd' is set to 'true' in the function 'TensorProductDecomp' if can be written as a tensor product of two $G$-modules with respect to an appropriate basis. Otherwise it is not set. At the same time, 'tensorBasis' is set to the appropriate basis of that space, and 'tensorFactors' to the pair of $G$-modules whose tensor product is isomorphic to written with respect to that basis. The component 'symTensorProd' is set to 'true' in the function 'SymTensorProductDecomp' if can be written as a symmetric tensor product whose factors are permuted by the action of $G$. Otherwise it is not set. At the same time, 'symTensorBasis' is set to the basis with respect to which this decomposition can be found, 'symTensorFactors' to the list of tensor factors, and 'symTensorPerm' to the list of permutations corresponding to the action of each of the generators of $G$ on those tensor factors. The component 'extraSpecial' is set to 'true' in the function 'ExtraSpecialDecomp' if $G$ has been shown to have a normal subgroup $H$ which is an extraspecial $r$-group for an odd prime $r$ or a 2-group of symplectic type, modulo scalars. Otherwise it is not set. At the same time, 'extraSpecialPart' is set to a list of generators for the subgroup $H$, and 'extraSpecialPrime' is set to $r$. The component 'imprimitive' is set to 'true' if $G$ has been shown to act imprimitively and to 'false' if $G$ is primitive. Otherwise it is not set. This component is set in the function 'IsPrimitiveGMod'. If $G$ has been shown to act imprimitively, then has a component 'blockSystem' which has the structure described in 'BlockSystemFlag'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Examples} We illustrate some of these functions in the following examples. | gap> RequirePackage( "smash" ); gap> # First set up the natural permutation module for the alternating gap> # group $A_5$ over the field $GF(2)$. gap> P := Group ((1,2,3), (3,4,5));; gap> M := PermGMod (P, GF(2)); rec( field := GF(2), dim := 5, matrices := [ [ [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ], [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ] ], [ [ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ], [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ] ] ], isGModule := true ) gap> # Now test for irreducibility, and calculate a proper submodule. gap> IsIrredGMod (M); false gap> SM := SubGMod (M, SubbasisFlag (M));; gap> DimFlag (SM); 4 gap> # Test to see if SM is self-dual. gap> DSM := DualGMod (SM);; gap> IsomGMod (SM, DSM); Error, Neither module is known to be irreducible. in IsomGMod( SM, DSM ) called from main loop brk> quit; gap> # We must prove irreducibility first! gap> IsIrredGMod (SM); true gap> IsAbsIrredGMod (SM); true gap> IsomGMod (SM, DSM); [ [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0 ], [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] ] gap> # This is an explicit isomorphism. gap> # Now form a tensor product and decompose it into composition gap> # factors. gap> TM := TensorProductGMod (SM, SM);; gap> cf := ChopGMod (TM);; gap> Length (cf); 3 gap> DimFlag(cf[1][1]); cf[1][2]; 1 4 gap> DimFlag(cf[2][1]); cf[2][2]; 4 2 gap> DimFlag(cf[3][1]); cf[3][2]; 4 1 gap> # This tells us that TM has three composition factors, of dimensions gap> # 1, 4 and 4, with multiplicities 4, 2 and 1, respectively. gap> # Is one of the 4-dimensional factors isomorphic to TM? gap> IsomGMod (SM, cf[2][1]); false gap> IsomGMod (SM, cf[3][1]); [ [ 0*Z(2), Z(2)^0, 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] ] gap> IsAbsIrredGMod (cf[2][1]); false gap> FieldExtDegFlag(cf[2][1]); 2 gap> # If we extend the field of cf[2][1] to $GF(4)$, it should gap> # become reducible. Let\'s try it! gap> MM := GModule (MatricesFlag (cf[2][1]), GF(4));; gap> CF2 := ChopGMod (MM);; gap> Length (CF2); 2 gap> DimFlag (CF2[1][1]); CF2[1][2]; 2 1 gap> DimFlag (CF2[2][1]); CF2[2][2]; 2 1 gap> # It reduces into two non-isomorphic 2-dimensional factors.| In the next example, we investigate the structure of a matrix group using 'SmashGMod' and access some of the stored information about the computed decomposition. | gap> # First set up the field. gap> F:= GF (2);; gap> gap> # Now the generating matrices. gap> a := [ > [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]] * Z(2)^0;; gap> b := [ > [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], > [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], > [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], > [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]] * Z(2)^0;; gap> c := [ > [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], > [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], > [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]] * Z(2)^0;; gap> gens := [a, b, c];; gap> gap> # Next we define the module. gap> M := GModule (gens);; gap> gap> # So far only the basic components have been set. gap> RecFields (M); [ "field", "dim", "matrices", "isGModule" ] gap> gap> # First we check for irreducibility and absolute irreducibility. gap> IsIrredGMod (M); true gap> gap> IsAbsIrredGMod (M); true gap> gap> # A few more components have been set during these two function gap> # calls. gap> RecFields(M); [ "field", "dim", "matrices", "isGModule", "algEl", "algElMat", "algElCharPol", "algElCharPolFac", "algElNullspaceVec", "algElNullspaceDim", "reducible", "fieldExtDeg", "absReducible" ] gap> gap> # The function Commutators forms the list of commutators of gap> # generators. gap> S := Commutators(gens);; gap> gap> InfoSmashGMod := Print;; gap> # Setting InfoSmashGMod to Print means that SmashGMod prints out gap> # intermediate output to tell us what it is doing. If we gap> # read this output it tells us what kind of decomposition SmashGMod gap> # has found. Otherwise the output is only a true or false. gap> # But all the relevant information is contained in the components gap> # of M which are set by this function, anyway. gap> gap> SmashGMod (M, S); Starting call to SmashGMod. At top of main SmashGMod loop. S has 2 elements. Translates of W aren't modules. At top of main SmashGMod loop. S has 3 elements. Translates of W aren't modules. At top of main SmashGMod loop. S has 4 elements. Translates of W aren't modules. At top of main SmashGMod loop. S has 5 elements. Group embeds in GammaL(4,GF(2)^3). SmashGMod returns true. true gap> InfoSmashGMod := Ignore;; gap> gap> # Additional components are set during the call to SmashGMod. gap> RecFields(M); [ "field", "dim", "matrices", "isGModule", "algEl", "algElMat", "algElCharPol", "algElCharPolFac", "algElNullspaceVec", "algElNullspaceDim", "reducible", "fieldExtDeg", "absReducible", "semiLinear", "linearPart", "centMat", "frobeniusAutos" ] gap> gap> # We can access the components either directly or through functions. gap> gap> SemiLinearFlag (M); true gap> # This flag tells us G that acts semilinearly. gap> gap> FieldExtDegFlag (M); 3 gap> # This flag tells us the relevant extension field is GF(2\^3) gap> gap> Length (LinearPartFlag (M)); 5 gap> # gap> # M.linearPart is a set of normal subgroup generators for the gap> # intersection of G with the GL(4, GF(2\^3)). It is also the value gap> # of the set S at the end of the call to SmashGMod is bigger than gap> # the set S which was input (which had 3 elements) since conjugates gap> # have been added. The matrices are rather big, so we do not print gap> # them out. gap> gap> FrobeniusAutosFlag (M); [ 0, 0, 1 ] gap> # The first two generators of G act linearly, the last induces the gap> # field automorphism which maps x to x\^2 (= x\^(2\^1)) on GF(2\^3) gap>| In our final example, we demonstrate how to test whether a matrix group is primitive and also how to select random elements. | gap> # gap> # Read in 18-dimensional representation of L(2, 17) over GF(41). gap> # gap> Read("l217.gap"); gap> # Initialise a seed for random element generation. gap> Seed := InitialiseSeed (G, 10, 50);; gap> # Now select a random element. gap> g := RandomElement (Seed);; gap> MatrixOrder (g); 4 gap> h := ElementOfOrder (Seed, 8, 10);; gap> MatrixOrder (h); 8 gap> # Is the group primitive? gap> R := IsPrimitiveMatrixGroup (G);; Input G-module has dimension 18 over GF(41) Number of blocks is 18 Group primitive? false Time taken is 46 seconds gap> # Examine the boolean returned. gap> R[1]; false gap> M := R[2];; gap> # What is the block system found? gap> BlockSystemFlag (M); rec( nmrBlocks := 18, block := [ [ 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), Z(41)^0, 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41) ] ], permGroup := Group( ( 1, 2)( 4, 6)( 5, 9)( 7,10)( 8,13)(12,15) (14,16)(17,18), ( 1, 3, 6, 7,12,17,15, 9, 8,11,16, 4, 2, 5,10,14, 13), ( 1, 4, 8,14,16,13, 6, 2)( 3, 7,12, 5,11, 9,15,10) ), isBlockSystem := true ) gap> v := > [ 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), > Z(41)^0, 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), > 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41) ];; gap> # Illustrate use of MinBlocks gap> B := MinBlocks (M, [v]); rec( nmrBlocks := 18, block := [ [ 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), Z(41)^0, 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41), 0*Z(41) ] ], permGroup := Group( ( 1, 2)( 4, 6)( 5, 9)( 7,10)( 8,13)(12,15) (14,16)(17,18), ( 1, 3, 6, 7,12,17,15, 9, 8,11,16, 4, 2, 5,10,14, 13), ( 1, 4, 8,14,16,13, 6, 2)( 3, 7,12, 5,11, 9,15,10) ), isBlockSystem := true )|