%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %W meataxe.tex GAP documentation Alexander Hulpke %% %H @(#)$Id: meataxe.tex,v 4.16.2.1 2007/08/29 14:45:19 gap Exp $ %% %Y Copyright 1997, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file contains a description of the MeatAxe functions. %% \Chapter{The MeatAxe} The MeatAxe \cite{Par84} is a tool for the examination of submodules of a group algebra. It is a basic tool for the examination of group actions on finite-dimensional modules. {\GAP} uses the improved MeatAxe of Derek Holt and Sarah Rees, and also incorporates further improvements of Ivanyos and Lux. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{MeatAxe Modules} \>GModuleByMats( <gens>, <field> ) \>GModuleByMats( <emptygens>, <dim>, <field> ) creates a MeatAxe module over <field> from a list of invertible matrices <gens> which reflect a group's action. If the list of generators is empty, the dimension must be given as second argument. MeatAxe routines are on a level with Gaussian elimination. Therefore they do not deal with {\GAP} modules but essentially with lists of matrices. For the MeatAxe, a module is a record with components \beginitems `generators'&A list of matrices which represent a group operation on a finite dimensional row vector space. `dimension'&The dimension of the vector space (this is the common length of the row vectors (see~"DimensionOfVectors")). `field'&The field over which the vector space is defined. \enditems Once a module has been created its entries may not be changed. A MeatAxe may create a new component <NameOfMeatAxe> in which it can store private information. By a MeatAxe ``submodule'' or ``factor module'' we denote actually the *induced action* on the submodule, respectively factor module. Therefore the submodules or factor modules are again MeatAxe modules. The arrangement of `generators' is guaranteed to be the same for the induced modules, but to obtain the complete relation to the original module, the bases used are needed as well. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Module Constructions} \>PermutationGModule( <G>, <F> ) F Called with a permutation group <G> and a finite field <F>, `PermutationGModule' returns the natural permutation module $M$ over <F> for the group of permutation matrices that acts on the canonical basis of $M$ in the same way as <G> acts on the points up to its largest moved point (see~"LargestMovedPoint"). \>TensorProductGModule (<m1>,<m2>) F TensorProductGModule calculates the tensor product of the modules <m1> and <m2>. They are assumed to be modules over the same algebra so, in particular, they should have the same number of generators. \>WedgeGModule (<module>) WedgeGModule calculates the wedge product of a <G>-module. That is the action on antisymmetric tensors. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Selecting a Different MeatAxe} All MeatAxe routines are accessed via the global variable `MTX', which is a record whose components hold the various functions. It is possible to have several implementations of a MeatAxe available. Each MeatAxe represents its routines in an own global variable and assigning `MTX' to this variable selects the corresponding MeatAxe. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Accessing a Module} Even though a MeatAxe module is a record, its components should never be accessed outside of MeatAxe functions. Instead the following operations should be used: \>MTX.Generators( <module> ) returns a list of matrix generators of <module>. \>MTX.Dimension( <module> ) returns the dimension in which the matrices act. \>MTX.Field( <module> ) returns the field over which <module> is defined. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Irreducibility Tests} \>MTX.IsIrreducible( <module> ) AST tests whether the module <module> is irreducible (i.e. contains no proper submodules.) \>MTX.IsAbsolutelyIrreducible( <module> ) AST A module is absolutely irreducible if it remains irreducible over the algebraic closure of the field. (Formally: If the tensor product $L\otimes_K M$ is irreducible where $M$ is the module defined over $K$ and $L$ is the algebraic closure of $K$.) \>MTX.DegreeSplittingField( <module> ) returns the degree of the splitting field as extension of the prime field. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Finding Submodules} \>MTX.SubmoduleGModule( <module>, <subspace> ) F \>MTX.SubGModule( <module>, <subspace> ) F <subspace> should be a subspace of (or a vector in) the underlying vector space of <module> i.e. the full row space of the same dimension and over the same field as <module>. A normalized basis of the submodule of <module> generated by <subspace> is returned. \>MTX.ProperSubmoduleBasis( <module> ) F returns the basis of a proper submodule of <module> and `fail' if no proper submodule exists. \>MTX.BasesSubmodules( <module> ) F returns a list containing a basis for every submodule. \>MTX.BasesMinimalSubmodules( <module> ) F returns a list of bases of all minimal submodules. \>MTX.BasesMaximalSubmodules( <module> ) F returns a list of bases of all maximal submodules. \>MTX.BasisRadical( <module> ) F returns a basis of the radical of <module>. \>MTX.BasisSocle( <module> ) F returns a basis of the socle of <module>. \>MTX.BasesMinimalSupermodules( <module>, <sub> ) F returns a list of bases of all minimal supermodules of the submodule given by the basis <sub>. \>MTX.BasesCompositionSeries( <module> ) F returns a list of bases of submodules in a composition series in ascending order. \>MTX.CompositionFactors( <module> ) F returns a list of composition factors of <module> in ascending order. \>MTX.CollectedFactors( <module> ) F returns a list giving all irreducible composition factors with their frequencies. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Induced Actions} \>MTX.NormedBasisAndBaseChange(<sub>) returns a list `[<bas>,change]' where <bas> is a normed basis (i.e. in echelon form with pivots normed to 1) for <sub> and change is the base change from <bas> to <sub> (the basis vectors of <bas> expressed in coefficients for <sub>) \>MTX.InducedActionSubmodule( <module>, <sub> ) F \>MTX.InducedActionSubmoduleNB( <module>, <sub> ) F creates a new module corresponding to the action of <module> on <sub>. In the `NB' version the basis <sub> must be normed. (That is it must be in echelon form with pivots normed to 1. See~`MTX.NormedBasisAndBaseChange') \>MTX.InducedActionFactorModule( <module>, <sub>[, <compl>] ) F creates a new module corresponding to the action of <module> on the factor of <sub>. If <compl> is given, it has to be a basis of a (vector space-)complement of <sub>. The action then will correspond to <compl>. The basis <sub> has to be given in normed form. (That is it must be in echelon form with pivots normed to 1. See~`MTX.NormedBasisAndBaseChange') \>MTX.InducedActionMatrix(<mat>,<sub>) \>MTX.InducedActionMatrixNB(<mat>,<sub>) \>MTX.InducedActionFactorMatrix( <mat>, <sub>[, <compl>] ) F work the same way as the above functions for modules, but take as input only a single matrix. \>MTX.InducedAction( <module>, <sub>[, <type>] ) F Computes induced actions on submodules or factormodules and also returns the corresponding bases. The action taken is binary encoded in <type>: 1 stands for subspace action, 2 for factor action and 4 for action of the full module on a subspace adapted basis. The routine returns the computed results in a list in sequence (<sub>,<quot>,<both>,<basis>) where <basis> is a basis for the whole space, extending <sub>. (Actions which are not computed are omitted, so the returned list may be shorter.) If no <type> is given, it is assumed to be 7. The basis given in <sub> must be normed! All these routines return `fail' if <sub> is not a proper subspace. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Module Homomorphisms} \>MTX.IsEquivalent( <module1>, <module2> ) F tests two irreducible modules for equivalence. \>MTX.Isomorphism( <module1>, <module2> ) F returns an isomorphism from <module1> to <module2> (if one exists) and `fail' otherwise. It requires that one of the modules is known to be irreducible. It implicitly assumes that the same group is acting, otherwise the results are unpredictable. The isomorphism is given by a matrix $M$, whose rows give the images of the standard basis vectors of module2 in the standard basis of module1. That is, conjugation of the generators of <module2> with $M$ yields the generators of <module1>. \>MTX.Homomorphism( <module1>, <module2>, <mat> ) F <mat> should be a <dim1> $\times$ <dim2> matrix defining a homomorphism from <module1> to <module2>. This function verifies that <mat> really does define a module homomorphism, and then returns the corresponding homomorphism between the underlying row spaces of the modules. This can be used for computing kernels, images and pre-images. \>MTX.Homomorphisms( <module1>, <module2> ) F returns a basis of all homomorphisms from the irreducible module <module1> to <module2>. \>MTX.Distinguish( <cf>, <nr> ) F Let <cf> be the output of `MTX.CollectedFactors'. This routine tries to find a group algebra element that has nullity zero on all composition factors except number <nr>. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Invariant Forms} The functions in this section can only be applied to an absolutely irreducible MeatAxe module <module>. \>MTX.InvariantBilinearForm(<module>) F returns an invariant bilinear form, which may be symmetric or anti-symmetric, of <module>, or `fail' if no such form exists. \>MTX.InvariantSesquilinearForm(<module>) F returns an invariant hermitian (= self-adjoint) sesquilinear form of <module>, which must be defined over a finite field whose order is a square, or `fail' if no such form exists. \>MTX.InvariantQuadraticForm(<module>) F returns an invariant quadratic form of <module>, or `fail' if no such form exists. If the characteristic of the field over which <module> is defined is not 2, then the invariant bilinear form (if any) divided by two will be returned. In characteristic 2, the form returned will be lower triangular. \>MTX.BasisInOrbit(<module>) F returns a basis of the underlying vector space of <module> which is contained in an orbit of the action of the generators of module on that space. This is used by `MTX.InvariantQuadraticForm' in characteristic 2. \>MTX.OrthogonalSign(<module>) F for an even dimensional module, returns 1 or -1, according as `MTX.InvariantQuadraticForm(<module>)' is of + or - type. For an odd dimensional module, returns 0. For a module with no invariant quadratic form, returns `fail'. This calculation uses an algorithm due to Jon Thackray. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The Smash MeatAxe} The standard MeatAxe provided in the {\GAP} library is is based on the MeatAxe in the {\GAP}~3 package \package{Smash}, originally written by Derek Holt and Sarah Rees \cite{HR94}. It is accessible via the variable `SMTX' to which `MTX' is assigned by default. For the sake of completeness the remaining sections document more technical functions of this MeatAxe. \>SMTX.RandomIrreducibleSubGModule( <module> ) F returns the module action on a random irreducible submodule. \>SMTX.GoodElementGModule( <module> ) F finds an element with minimal possible nullspace dimension if <module> is known to be irreducible. \>SMTX.SortHomGModule( <module1>, <module2>, <homs> ) F Function to sort the output of `Homomorphisms'. \>SMTX.MinimalSubGModules( <module1>, <module2>[, <max>] ) returns (at most <max>) bases of submodules of <module2> which are isomorphic to the irreducible module <module1>. \>SMTX.Setter( <string> ) returns a setter function for the component `smashMeataxe.(string)'. \>SMTX.Getter( <string> ) returns a getter function for the component `smashMeataxe.(string)'. \>SMTX.IrreducibilityTest( <module> ) Tests for irreducibility and sets a subbasis if reducible. It neither sets an irreducibility flag, nor tests it. Thus the routine also can simply be called to obtain a random submodule. \>SMTX.AbsoluteIrreducibilityTest( <module> ) Tests for absolute irreducibility and sets splitting field degree. It neither sets an absolute irreducibility flag, nor tests it. \>SMTX.MinimalSubGModule( <module>, <cf>, <nr> ) returns the basis of a minimal submodule of <module> containing the indicated composition factor. It assumes `Distinguish' has been called already. \>SMTX.MatrixSum( <matrices1>, <matrices2> ) creates the direct sum of two matrix lists. \>SMTX.CompleteBasis( <module>, <pbasis> ) extends the partial basis <pbasis> to a basis of the full space by action of <module>. It returns whether it succeeded. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Smash MeatAxe Flags} The following getter routines access internal flags. For each routine, the appropriate setter's name is prefixed with `Set'. \>SMTX.Subbasis Basis of a submodule. \>SMTX.AlgEl list `[newgens,coefflist]' giving an algebra element used for chopping. \>SMTX.AlgElMat matrix of `SMTX.AlgEl'. \>SMTX.AlgElCharPol minimal polynomial of `SMTX.AlgEl'. \>SMTX.AlgElCharPolFac uses factor of `SMTX.AlgEl'. \>SMTX.AlgElNullspaceVec nullspace of the matrix evaluated under this factor. \>SMTX.AlgElNullspaceDimension dimension of the nullspace. \>SMTX.CentMat \>SMTX.CentMatMinPoly