<html><head><title>[ref] 67 The MeatAxe</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP066.htm">Previous</a>] [<a href ="CHAP068.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>67 The MeatAxe</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP067.htm#SECT001">MeatAxe Modules</a> <li> <A HREF="CHAP067.htm#SECT002">Module Constructions</a> <li> <A HREF="CHAP067.htm#SECT003">Selecting a Different MeatAxe</a> <li> <A HREF="CHAP067.htm#SECT004">Accessing a Module</a> <li> <A HREF="CHAP067.htm#SECT005">Irreducibility Tests</a> <li> <A HREF="CHAP067.htm#SECT006">Finding Submodules</a> <li> <A HREF="CHAP067.htm#SECT007">Induced Actions</a> <li> <A HREF="CHAP067.htm#SECT008">Module Homomorphisms</a> <li> <A HREF="CHAP067.htm#SECT009">Invariant Forms</a> <li> <A HREF="CHAP067.htm#SECT010">The Smash MeatAxe</a> <li> <A HREF="CHAP067.htm#SECT011">Smash MeatAxe Flags</a> </ol><p> <p> The MeatAxe <a href="biblio.htm#Par84"><cite>Par84</cite></a> 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. <p> <font face="Gill Sans,Helvetica,Arial">GAP</font> uses the improved MeatAxe of Derek Holt and Sarah Rees, and also incorporates further improvements of Ivanyos and Lux. <p> <p> <h2><a name="SECT001">67.1 MeatAxe Modules</a></h2> <p><p> <a name = "SSEC001.1"></a> <li><code>GModuleByMats( </code><var>gens</var><code>, </code><var>field</var><code> )</code> <li><code>GModuleByMats( </code><var>emptygens</var><code>, </code><var>dim</var><code>, </code><var>field</var><code> )</code> <p> creates a MeatAxe module over <var>field</var> from a list of invertible matrices <var>gens</var> which reflect a group's action. If the list of generators is empty, the dimension must be given as second argument. <p> MeatAxe routines are on a level with Gaussian elimination. Therefore they do not deal with <font face="Gill Sans,Helvetica,Arial">GAP</font> modules but essentially with lists of matrices. For the MeatAxe, a module is a record with components <p> <dl compact> <dt><code>generators</code><dd>A list of matrices which represent a group operation on a finite dimensional row vector space. <p> <dt><code>dimension</code><dd>The dimension of the vector space (this is the common length of the row vectors (see <a href="CHAP059.htm#SSEC008.6">DimensionOfVectors</a>)). <p> <dt><code>field</code><dd>The field over which the vector space is defined. </dl> Once a module has been created its entries may not be changed. A MeatAxe may create a new component <var>NameOfMeatAxe</var> in which it can store private information. By a MeatAxe ``submodule'' or ``factor module'' we denote actually the <strong>induced action</strong> on the submodule, respectively factor module. Therefore the submodules or factor modules are again MeatAxe modules. The arrangement of <code>generators</code> 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. <p> <p> <h2><a name="SECT002">67.2 Module Constructions</a></h2> <p><p> <a name = "SSEC002.1"></a> <li><code>PermutationGModule( </code><var>G</var><code>, </code><var>F</var><code> ) F</code> <p> Called with a permutation group <var>G</var> and a finite field <var>F</var>, <code>PermutationGModule</code> returns the natural permutation module <i>M</i> over <var>F</var> for the group of permutation matrices that acts on the canonical basis of <i>M</i> in the same way as <var>G</var> acts on the points up to its largest moved point (see <a href="CHAP040.htm#SSEC002.2">LargestMovedPoint</a>). <p> <a name = "SSEC002.2"></a> <li><code>TensorProductGModule (</code><var>m1</var><code>,</code><var>m2</var><code>) F</code> <p> TensorProductGModule calculates the tensor product of the modules <var>m1</var> and <var>m2</var>. They are assumed to be modules over the same algebra so, in particular, they should have the same number of generators. <p> <a name = "SSEC002.3"></a> <li><code>WedgeGModule (</code><var>module</var><code>)</code> <p> WedgeGModule calculates the wedge product of a <var>G</var>-module. That is the action on antisymmetric tensors. <p> <p> <h2><a name="SECT003">67.3 Selecting a Different MeatAxe</a></h2> <p><p> All MeatAxe routines are accessed via the global variable <code>MTX</code>, 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 <code>MTX</code> to this variable selects the corresponding MeatAxe. <p> <p> <h2><a name="SECT004">67.4 Accessing a Module</a></h2> <p><p> 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: <p> <a name = "SSEC004.1"></a> <li><code>MTX.Generators( </code><var>module</var><code> )</code> <p> returns a list of matrix generators of <var>module</var>. <p> <a name = "SSEC004.2"></a> <li><code>MTX.Dimension( </code><var>module</var><code> )</code> <p> returns the dimension in which the matrices act. <p> <a name = "SSEC004.3"></a> <li><code>MTX.Field( </code><var>module</var><code> )</code> <p> returns the field over which <var>module</var> is defined. <p> <p> <h2><a name="SECT005">67.5 Irreducibility Tests</a></h2> <p><p> <a name = "SSEC005.1"></a> <li><code>MTX.IsIrreducible( </code><var>module</var><code> ) AST</code> <p> tests whether the module <var>module</var> is irreducible (i.e. contains no proper submodules.) <p> <a name = "SSEC005.2"></a> <li><code>MTX.IsAbsolutelyIrreducible( </code><var>module</var><code> ) AST</code> <p> A module is absolutely irreducible if it remains irreducible over the algebraic closure of the field. (Formally: If the tensor product <i>L</i>⊗<sub><i>K</i></sub> <i>M</i> is irreducible where <i>M</i> is the module defined over <i>K</i> and <i>L</i> is the algebraic closure of <i>K</i>.) <p> <a name = "SSEC005.3"></a> <li><code>MTX.DegreeSplittingField( </code><var>module</var><code> )</code> <p> returns the degree of the splitting field as extension of the prime field. <p> <p> <h2><a name="SECT006">67.6 Finding Submodules</a></h2> <p><p> <a name = "SSEC006.1"></a> <li><code>MTX.SubmoduleGModule( </code><var>module</var><code>, </code><var>subspace</var><code> ) F</code> <a name = "SSEC006.1"></a> <li><code>MTX.SubGModule( </code><var>module</var><code>, </code><var>subspace</var><code> ) F</code> <p> <var>subspace</var> should be a subspace of (or a vector in) the underlying vector space of <var>module</var> i.e. the full row space of the same dimension and over the same field as <var>module</var>. A normalized basis of the submodule of <var>module</var> generated by <var>subspace</var> is returned. <p> <a name = "SSEC006.2"></a> <li><code>MTX.ProperSubmoduleBasis( </code><var>module</var><code> ) F</code> <p> returns the basis of a proper submodule of <var>module</var> and <code>fail</code> if no proper submodule exists. <p> <a name = "SSEC006.3"></a> <li><code>MTX.BasesSubmodules( </code><var>module</var><code> ) F</code> <p> returns a list containing a basis for every submodule. <p> <a name = "SSEC006.4"></a> <li><code>MTX.BasesMinimalSubmodules( </code><var>module</var><code> ) F</code> <p> returns a list of bases of all minimal submodules. <p> <a name = "SSEC006.5"></a> <li><code>MTX.BasesMaximalSubmodules( </code><var>module</var><code> ) F</code> <p> returns a list of bases of all maximal submodules. <p> <a name = "SSEC006.6"></a> <li><code>MTX.BasisRadical( </code><var>module</var><code> ) F</code> <p> returns a basis of the radical of <var>module</var>. <p> <a name = "SSEC006.7"></a> <li><code>MTX.BasisSocle( </code><var>module</var><code> ) F</code> <p> returns a basis of the socle of <var>module</var>. <p> <a name = "SSEC006.8"></a> <li><code>MTX.BasesMinimalSupermodules( </code><var>module</var><code>, </code><var>sub</var><code> ) F</code> <p> returns a list of bases of all minimal supermodules of the submodule given by the basis <var>sub</var>. <p> <a name = "SSEC006.9"></a> <li><code>MTX.BasesCompositionSeries( </code><var>module</var><code> ) F</code> <p> returns a list of bases of submodules in a composition series in ascending order. <p> <a name = "SSEC006.10"></a> <li><code>MTX.CompositionFactors( </code><var>module</var><code> ) F</code> <p> returns a list of composition factors of <var>module</var> in ascending order. <p> <a name = "SSEC006.11"></a> <li><code>MTX.CollectedFactors( </code><var>module</var><code> ) F</code> <p> returns a list giving all irreducible composition factors with their frequencies. <p> <p> <h2><a name="SECT007">67.7 Induced Actions</a></h2> <p><p> <a name = "SSEC007.1"></a> <li><code>MTX.NormedBasisAndBaseChange(</code><var>sub</var><code>)</code> <p> returns a list <code>[</code><var>bas</var><code>,change]</code> where <var>bas</var> is a normed basis (i.e. in echelon form with pivots normed to 1) for <var>sub</var> and change is the base change from <var>bas</var> to <var>sub</var> (the basis vectors of <var>bas</var> expressed in coefficients for <var>sub</var>) <p> <a name = "SSEC007.2"></a> <li><code>MTX.InducedActionSubmodule( </code><var>module</var><code>, </code><var>sub</var><code> ) F</code> <a name = "SSEC007.2"></a> <li><code>MTX.InducedActionSubmoduleNB( </code><var>module</var><code>, </code><var>sub</var><code> ) F</code> <p> creates a new module corresponding to the action of <var>module</var> on <var>sub</var>. In the <code>NB</code> version the basis <var>sub</var> must be normed. (That is it must be in echelon form with pivots normed to 1. See <code>MTX.NormedBasisAndBaseChange</code>) <p> <a name = "SSEC007.3"></a> <li><code>MTX.InducedActionFactorModule( </code><var>module</var><code>, </code><var>sub</var><code>[, </code><var>compl</var><code>] ) F</code> <p> creates a new module corresponding to the action of <var>module</var> on the factor of <var>sub</var>. If <var>compl</var> is given, it has to be a basis of a (vector space-)complement of <var>sub</var>. The action then will correspond to <var>compl</var>. <p> The basis <var>sub</var> has to be given in normed form. (That is it must be in echelon form with pivots normed to 1. See <code>MTX.NormedBasisAndBaseChange</code>) <p> <a name = "SSEC007.4"></a> <li><code>MTX.InducedActionMatrix(</code><var>mat</var><code>,</code><var>sub</var><code>)</code> <a name = "SSEC007.4"></a> <li><code>MTX.InducedActionMatrixNB(</code><var>mat</var><code>,</code><var>sub</var><code>)</code> <a name = "SSEC007.4"></a> <li><code>MTX.InducedActionFactorMatrix( </code><var>mat</var><code>, </code><var>sub</var><code>[, </code><var>compl</var><code>] ) F</code> <p> work the same way as the above functions for modules, but take as input only a single matrix. <p> <a name = "SSEC007.5"></a> <li><code>MTX.InducedAction( </code><var>module</var><code>, </code><var>sub</var><code>[, </code><var>type</var><code>] ) F</code> <p> Computes induced actions on submodules or factormodules and also returns the corresponding bases. The action taken is binary encoded in <var>type</var>: 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 (<var>sub</var>,<var>quot</var>,<var>both</var>,<var>basis</var>) where <var>basis</var> is a basis for the whole space, extending <var>sub</var>. (Actions which are not computed are omitted, so the returned list may be shorter.) If no <var>type</var> is given, it is assumed to be 7. The basis given in <var>sub</var> must be normed! <p> All these routines return <code>fail</code> if <var>sub</var> is not a proper subspace. <p> <p> <h2><a name="SECT008">67.8 Module Homomorphisms</a></h2> <p><p> <a name = "SSEC008.1"></a> <li><code>MTX.IsEquivalent( </code><var>module1</var><code>, </code><var>module2</var><code> ) F</code> <p> tests two irreducible modules for equivalence. <p> <a name = "SSEC008.2"></a> <li><code>MTX.Isomorphism( </code><var>module1</var><code>, </code><var>module2</var><code> ) F</code> <p> returns an isomorphism from <var>module1</var> to <var>module2</var> (if one exists) and <code>fail</code> 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 <i>M</i>, 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 <var>module2</var> with <i>M</i> yields the generators of <var>module1</var>. <p> <a name = "SSEC008.3"></a> <li><code>MTX.Homomorphism( </code><var>module1</var><code>, </code><var>module2</var><code>, </code><var>mat</var><code> ) F</code> <p> <var>mat</var> should be a <var>dim1</var> × <var>dim2</var> matrix defining a homomorphism from <var>module1</var> to <var>module2</var>. This function verifies that <var>mat</var> 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. <p> <a name = "SSEC008.4"></a> <li><code>MTX.Homomorphisms( </code><var>module1</var><code>, </code><var>module2</var><code> ) F</code> <p> returns a basis of all homomorphisms from the irreducible module <var>module1</var> to <var>module2</var>. <p> <a name = "SSEC008.5"></a> <li><code>MTX.Distinguish( </code><var>cf</var><code>, </code><var>nr</var><code> ) F</code> <p> Let <var>cf</var> be the output of <code>MTX.CollectedFactors</code>. This routine tries to find a group algebra element that has nullity zero on all composition factors except number <var>nr</var>. <p> <p> <h2><a name="SECT009">67.9 Invariant Forms</a></h2> <p><p> The functions in this section can only be applied to an absolutely irreducible MeatAxe module <var>module</var>. <p> <a name = "SSEC009.1"></a> <li><code>MTX.InvariantBilinearForm(</code><var>module</var><code>) F</code> <p> returns an invariant bilinear form, which may be symmetric or anti-symmetric, of <var>module</var>, or <code>fail</code> if no such form exists. <p> <a name = "SSEC009.2"></a> <li><code>MTX.InvariantSesquilinearForm(</code><var>module</var><code>) F</code> <p> returns an invariant hermitian (= self-adjoint) sesquilinear form of <var>module</var>, which must be defined over a finite field whose order is a square, or <code>fail</code> if no such form exists. <p> <a name = "SSEC009.3"></a> <li><code>MTX.InvariantQuadraticForm(</code><var>module</var><code>) F</code> <p> returns an invariant quadratic form of <var>module</var>, or <code>fail</code> if no such form exists. If the characteristic of the field over which <var>module</var> 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. <p> <a name = "SSEC009.4"></a> <li><code>MTX.BasisInOrbit(</code><var>module</var><code>) F</code> <p> returns a basis of the underlying vector space of <var>module</var> which is contained in an orbit of the action of the generators of module on that space. This is used by <code>MTX.InvariantQuadraticForm</code> in characteristic 2. <p> <a name = "SSEC009.5"></a> <li><code>MTX.OrthogonalSign(</code><var>module</var><code>) F</code> <p> for an even dimensional module, returns 1 or -1, according as <code>MTX.InvariantQuadraticForm(</code><var>module</var><code>)</code> is of + or - type. For an odd dimensional module, returns 0. For a module with no invariant quadratic form, returns <code>fail</code>. This calculation uses an algorithm due to Jon Thackray. <p> <p> <h2><a name="SECT010">67.10 The Smash MeatAxe</a></h2> <p><p> The standard MeatAxe provided in the <font face="Gill Sans,Helvetica,Arial">GAP</font> library is is based on the MeatAxe in the <font face="Gill Sans,Helvetica,Arial">GAP</font> 3 package <font face="Gill Sans,Helvetica,Arial">Smash</font>, originally written by Derek Holt and Sarah Rees <a href="biblio.htm#HR94"><cite>HR94</cite></a>. It is accessible via the variable <code>SMTX</code> to which <code>MTX</code> is assigned by default. For the sake of completeness the remaining sections document more technical functions of this MeatAxe. <p> <a name = "SSEC010.1"></a> <li><code>SMTX.RandomIrreducibleSubGModule( </code><var>module</var><code> ) F</code> <p> returns the module action on a random irreducible submodule. <p> <a name = "SSEC010.2"></a> <li><code>SMTX.GoodElementGModule( </code><var>module</var><code> ) F</code> <p> finds an element with minimal possible nullspace dimension if <var>module</var> is known to be irreducible. <p> <a name = "SSEC010.3"></a> <li><code>SMTX.SortHomGModule( </code><var>module1</var><code>, </code><var>module2</var><code>, </code><var>homs</var><code> ) F</code> <p> Function to sort the output of <code>Homomorphisms</code>. <p> <a name = "SSEC010.4"></a> <li><code>SMTX.MinimalSubGModules( </code><var>module1</var><code>, </code><var>module2</var><code>[, </code><var>max</var><code>] )</code> <p> returns (at most <var>max</var>) bases of submodules of <var>module2</var> which are isomorphic to the irreducible module <var>module1</var>. <p> <a name = "SSEC010.5"></a> <li><code>SMTX.Setter( </code><var>string</var><code> )</code> <p> returns a setter function for the component <code>smashMeataxe.(string)</code>. <p> <a name = "SSEC010.6"></a> <li><code>SMTX.Getter( </code><var>string</var><code> )</code> <p> returns a getter function for the component <code>smashMeataxe.(string)</code>. <p> <a name = "SSEC010.7"></a> <li><code>SMTX.IrreducibilityTest( </code><var>module</var><code> )</code> <p> 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. <p> <a name = "SSEC010.8"></a> <li><code>SMTX.AbsoluteIrreducibilityTest( </code><var>module</var><code> )</code> <p> Tests for absolute irreducibility and sets splitting field degree. It neither sets an absolute irreducibility flag, nor tests it. <p> <a name = "SSEC010.9"></a> <li><code>SMTX.MinimalSubGModule( </code><var>module</var><code>, </code><var>cf</var><code>, </code><var>nr</var><code> )</code> <p> returns the basis of a minimal submodule of <var>module</var> containing the indicated composition factor. It assumes <code>Distinguish</code> has been called already. <p> <a name = "SSEC010.10"></a> <li><code>SMTX.MatrixSum( </code><var>matrices1</var><code>, </code><var>matrices2</var><code> )</code> <p> creates the direct sum of two matrix lists. <p> <a name = "SSEC010.11"></a> <li><code>SMTX.CompleteBasis( </code><var>module</var><code>, </code><var>pbasis</var><code> )</code> <p> extends the partial basis <var>pbasis</var> to a basis of the full space by action of <var>module</var>. It returns whether it succeeded. <p> <p> <h2><a name="SECT011">67.11 Smash MeatAxe Flags</a></h2> <p><p> The following getter routines access internal flags. For each routine, the appropriate setter's name is prefixed with <code>Set</code>. <p> <a name = "SSEC011.1"></a> <li><code>SMTX.Subbasis</code> <p> Basis of a submodule. <p> <a name = "SSEC011.2"></a> <li><code>SMTX.AlgEl</code> <p> list <code>[newgens,coefflist]</code> giving an algebra element used for chopping. <p> <a name = "SSEC011.3"></a> <li><code>SMTX.AlgElMat</code> <p> matrix of <code>SMTX.AlgEl</code>. <p> <a name = "SSEC011.4"></a> <li><code>SMTX.AlgElCharPol</code> <p> minimal polynomial of <code>SMTX.AlgEl</code>. <p> <a name = "SSEC011.5"></a> <li><code>SMTX.AlgElCharPolFac</code> <p> uses factor of <code>SMTX.AlgEl</code>. <p> <a name = "SSEC011.6"></a> <li><code>SMTX.AlgElNullspaceVec</code> <p> nullspace of the matrix evaluated under this factor. <p> <a name = "SSEC011.7"></a> <li><code>SMTX.AlgElNullspaceDimension</code> <p> dimension of the nullspace. <p> <a name = "SSEC011.8"></a> <li><code>SMTX.CentMat</code> <p> <a name = "SSEC011.9"></a> <li><code>SMTX.CentMatMinPoly</code> <p> <p> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP066.htm">Previous</a>] [<a href ="CHAP068.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
209
