%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%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