Goto Chapter: Top 1 2 3 4 5 6 Ind
 Top of Book   Previous Chapter   Next Chapter 

3 FG-modules
 3.1 The FpGModuleGF datatype
 3.2 Implementation details: Block echelon form
 3.3 Construction functions
 3.4 Data access functions
 3.5 Generator and vector space functions
 3.6 Block echelon functions
 3.7 Sum and intersection functions
 3.8 Miscellaneous functions

3 FG-modules

Let FG be the group ring of the group G over the field F. In this package we only consider the case where G is a finite p-groups and F = F_p is the field of p elements. In addition, we only consider free FG-modules.

3.1 The FpGModuleGF datatype

Modules and submodules of free FG-modules are represented in HAPprime using the FpGModuleGF datatype, where the `GF' stands for `Generator Form'. This defines a module using a group G and a set of G-generating vectors for the module's vector space, together with a group action which operates on those vectors. A free FG-module FG can be considered as a vector space F^|G| whose basis is the elements of G. An element of (FG)^n is the direct sum of n copies of FG and, as an element of FpGModuleGF, is represented as a vector of length n|G| with coefficients in F. Representing our FG-module elements as vectors is ideal for our purposes since GAP's representation and manipulation of vectors and matrices over small prime fields is very efficient in both memory and computation time.

The HAP package defines a FpGModule object, which is similar but stores a vector space basis rather than a G-generating set for the module's vector space. Storing a G-generating set saves memory, both in passive storage and in allowing more efficient versions of some computation algorithms.

There are a number of construction functions for FpGModuleGFs: see 3.3-1 for details. A FG-module is defined by the following:

The group, action and block size are internally wrapped up into a record groupAndAction, with entries group, action and actionBlockSize. This is used to simplify the passing of parameters to some functions.

Some additional information is sometimes needed to construct particular classes of FpGModuleGF:

3.2 Implementation details: Block echelon form

3.2-1 Generating vectors and their block structure

Consider the vector representation of an element in the FG-module (FG)^2, where G is a group of order four:

v in (FG)^2 = (g_1 + g_3, g_1 + g_2 + g_4) = [1 0 1 0 | 1 1 0 1]

The first block of four entries in the vector correspond to the first FG summand and the second block to the second summand (and the group elements are numbered in the order provided by the GAP function Elements (Reference: Elements)).

Given a G-generating set for a FG-module, the usual group action permutes the group elements, and thus the effect on the vector is to permute the equivalent vector elements. Each summand is independent, and so elements are permuted within the blocks (normally of size |G|) seen in the example above. A consequence of this is that if any block (i.e. summand) in a generator is entirely zero, then it remains zero under group (or F) multiplication and so that generator contributes nothing to that part of the vector space. This fact enables some of the structure of the module's vector space to be inferred from the G-generators, without needing a full vector space basis . A desirable set of G-generators is one that has many zero blocks, and what we call the `block echelon' form is one that has this property.

3.2-2 Matrix echelon reduction and head elements

The block echelon form of a FG-module generating set is analagous to the echelon form of matrices, used as a first stage in many matrix algorithms, and we first briefly review matrix echelon form. In a (row) echelon-form matrix, the head element in each row (the first non-zero entry) is the identity, and is to the right of the head in the previous row. A consequence of this is that the values below each head are all zero. All zero rows are at the bottom of the matrix (or are removed). GAP also defines a semi-echelon form, in which it is guaranteed that all values below each head is zero, but not that each head is to the right of those above it.

Matrices can be converted into (semi-)echelon form by using Gaussian elimination to perform row reduction (for example the GAP function SemiEchelonMat (Reference: SemiEchelonMat)). A typical algorithm gradually builds up a list of matrix rows with unique heads, which will eventually be an echelon-form set of basis elements for the row space of the matrix. This set is initialised with the first row of the matrix, and the algorithm is then applied to each subsequent row in turn. The basis rows in the current set are used to reduce the next row of the matrix: if, after reduction, it is non-zero then it will have a unique head and is added to the list of basis rows; if it is zero then it may be removed. The final set of vectors will be a semi-echelon basis for the row space of the original matrix, which can then be permuted to give an echelon basis if required.

3.2-3 Echelon block structure and minimal generators

In the same way that the echelon form is useful for vector space generators, we can convert a set of FG-module generators into echelon form. However, unlike multiplication by a field element, the group action on generating vectors also permutes the vector elements, so a strict echelon form is less useful. Instead, we define a `block echelon' form, treating the blocks in the vector (see example above) as the FG-elements to be converted into echelon form. In block-echelon form, the first non-zero block in each row is as far to the right as possible. Often, the first non-zero block in a row will be to the right of the first non-zero block in the row above, but when several generating vectors are needed in a block, this may not be the case. The following example creates a random submodule of (FG)^n by picking five generating vectors at random. This module is first displayed with the original generators, and then they are converted to block echelon form using the the HAPprime function EchelonModuleGenerators (3.6-1). The two generating sets both span the same vector space (i.e. the same FG module), but the latter representation is much more useful.

gap> M := FpGModuleGF(RandomMat(5, 32, GF(2)), DihedralGroup(8));;
gap> Display(M);
Module over the group ring of Group( [ f1, f2, f3 ] )
 in characteristic 2 with 5 generators in FG^4.
[.1..1.1.|.1....1.|1111.11.|11.1111.]
[11.1..1.|1....11.|1...111.|1...11..]
[11..1.1.|1.1.1...|11...1..|.11.11..]
[11111111|111...1.|.11...1.|.1..1111]
[.1111111|1.1.111.|..1..1..|1.111...]
gap> echM := EchelonModuleGenerators(M);
rec( module := Module over the group ring of <pc group of size 8 with
    3 generators> in characteristic 2 with 4 generators in FG^
    4. Generators are in minimal echelon form., headblocks := [ 1, 2, 3, 4 ] )
gap> Display(echM.module);
Module over the group ring of Group( [ f1, f2, f3 ] )
 in characteristic 2 with 4 generators in FG^4.
[.1..1.1.|.1....1.|1111.11.|11.1111.]
[........|.1111..1|111.1...|.11.11.1]
[........|........|.1..1.1.|.1.1.111]
[........|........|........|..1111.1]
Generators are in minimal echelon form.gap>
gap> M = echM.module;
true

The main algorithm for converting a set of generators into echelon form is SemiEchelonModuleGeneratorsDestructive (3.6-1). The generators for the FG module are represented as rows of a matrix, and (with the canonical action) the first |G| columns of this matrix correspond to the first block, the next |G| columns to the second block, and so on. The first block of the matrix is taken and the vector space V_b spanned by the rows of that block is found (which will be a a subspace of F^|G|). Taking the rows in the first block, find (by gradually leaving out rows) a minimal subset that generates V_b. The rows of the full matrix that correspond to this minimal subset form the first rows of the block-echelon form generators. Taking those rows, and all G-multiples of them, now calculate a semi-echelon basis for the vector space that they generate (using SemiEchelonMatDestructive (Reference: SemiEchelonMatDestructive)). This is used to reduce all of the other generators. Since the rows we have chosen span the space of the first block, the first block in all the other rows will be reduced to zero. We can now move on to the second block.

We now look at the rows of the matrix that start (have their first non-zero entry) in the second block. In addition, some of the generators used for the first block might additionally give rise to vector space basis vectors with head elements in the second blocks. The rows need to be stored during the first stage and reused here. We find a minimal set of the matrix rows with second-block heads that, when taken with any second-block heads from the first stage, generate the entire space spanned by the second block. The vector-space basis from this new minimal set is then used to reduce the rest of the generating rows as before, reducing all of the other rows' second blocks to zero. The process is then repeated for each other block. Any generators that are completely zero are then removed. The algorithm is summarised in the following pseudocode:


Let X be the list of generators still to convert (initially all the generators)
Let Xe = [] be the list of generators already in block-echelon form
Define X{b} to represent the $b$th block from generators X
Define V(X) to represent the vector space generated by generators X
-------------------------------------------------------------------------------
for b in [1..blocks] 
  1. Find a minimal set of generators Xm from X such that 
     V(Xm{b} + Xe{b}) = V(X{b} + Xe{b})
  2. Remove Xm from X and add them to Xe
  3. Find a semi-echelon basis for V(Xe) and use this to reduce the elements 
     of block b in remaining vectors of X to zero
end for
      

The result of this algorithm is a new generating set for the module that is minimal in the sense that no vector can be removed from the set and leave it still spanning the same vector space. In the case of a FG-module with F=GF(2), this is a globally minimal set: there is no possible alternative set with fewer generators.

3.2-4 Intersection of two modules

Knowing the block structure of the modules enables the intersection of two modules to be calculated more efficiently. Consider two modules U and V with the block structure as given in this example:

gap> DisplayBlocks(U);
[*..]
[**.]
[.*.]
gap> DisplayBlocks(V);
[.**]
[.**]
[..*]

To calculate the intersection of the two modules, it is normal to expand out the two modules to find the vector space U_F and V_F of the two modules and calculate the intersection as a standard vector-space intersection. However, in this case, since U has no elements in the last block, and V has no elements in the first block, the intersection must only have elements in the middle block. This means that the first generator of U and the last generator of V can not be in the intersection and can be ignored for the purposes of the intersection calculation. In general, rather than expanding the entirety of U and V into an F-basis to calculate their intersection, one can expand U and V more intelligently into F-bases U'_F and V'_F which are smaller than U_F and V_F but have the same intersection.

Having determined (by comparing the block structure of U and V) that only the middle block in our example contributes to the intersection, we only need to expand out the rows of U and V that have heads in that block. The first generator of U generates no elements in the middle block, and trivially be ignored. The second row of U may or may not contribute to the intersection: this will need expanding out and echelon reduced. The expanded rows that don't have heads in the central block can then be discarded, with the other rows forming part of the basis of U'_F. Likewise, the third generator of U is expanded and echelon reduced to give the rest of the basis for U'_F. To find V'_F, the first two generators are expanded, semi-echelon reduced and the rows with heads in the middle block kept. The third generator can be ignored. Finally, the intersection of U'_F and V'_F can found using, for example, SumIntersectionMatDestructive (HAPprime Datatypes: SumIntersectionMatDestructive).

This algorithm, implemented in the function IntersectionModulesGF (3.7-3), will (for modules whose generators have zero columns) use less memory than a full vector-space expansion, and in the case where U and V have no intersection, may need to perform no expansion at all. In the worst case, both U and V will need a full expansion, using no more memory than the naive implementation. Since any full expansion is done row-by-row, with echelon reduction each time, it will in general still require less memory (but will be slower).

3.3 Construction functions

3.3-1 FpGModuleGF construction functions
> FpGModuleGF( gens, G[, action, actionBlockSize] )( operation )
> FpGModuleGF( gens, groupAndAction )( operation )
> FpGModuleGF( ambientDimension, G[, action, actionBlockSize] )( operation )
> FpGModuleGF( ambientDimension, groupAndAction )( operation )
> FpGModuleGF( G, n )( operation )
> FpGModuleGF( groupAndAction, n )( operation )
> FpGModuleGF( HAPmod )( operation )
> FpGModuleGFNC( gens, G, form, action, actionBlockSize )( operation )
> FpGModuleGFNC( ambientDimension, G, action, actionBlockSize )( operation )
> FpGModuleGFNC( gens, groupAndAction[, form] )( operation )

Returns: FpGModuleGF

Creates and returns a FpGModuleGF module object. The most commonly-used constructor requires a list of generators gens and a group G. The group action and block size can be specified using the action and actionBlockSize parameters, or if these are omitted then the canonical action is assumed. These parameters can also be wrapped up in a groupAndAction record (see 3.1).

An empty FpGModuleGF can be constructed by specifying a group and an ambientDimension instead of a set of generators. A module spanning (FG)^n with canonical generators and action can be constructed by giving a group G and a rank n. A FpGModuleGF can also be constructed from a HAP FpGModule HAPmod.

The generators in a FpGModuleGF do not need to be a minimal set. If you wish to create a module with minimal generators, construct the module from a non-minimal set gens and then use one of the MinimalGeneratorsModule functions (3.5-9). When constructing a FpGModuleGF from a FpGModule, the HAP function GeneratorsOfFpGModule (HAP: GeneratorsOfFpGModule) is used to provide a set of generators, so in this case the generators will be minimal.

Most of the forms of this function perform a few (cheap) tests to make sure that the arguments are self-consistent. The NC versions of the constructors are provided for internal use, or when you know what you are doing and wish to skip the tests. See Section 3.3-5 below for an example of usage.

3.3-2 FpGModuleFromFpGModuleGF
> FpGModuleFromFpGModuleGF( M )( operation )

Returns: FpGModule

Returns a HAP FpGModule that represents the same module as the FpGModuleGF M. This uses ModuleVectorSpaceBasis (3.5-7) to find the vector space basis for M and constructs a FpGModule with this vector space and the same group and action as M See Section 3.3-5 below for an example of usage.

TODO: This currently constructs an FpGModule object explicitly. It should use a constructor once one is provided

3.3-3 MutableCopyModule
> MutableCopyModule( M )( operation )

Returns: FpGModuleGF

Returns a copy of the module M where the generating vectors are fully mutable. The group and action in the new module is identical to that in M - only the list of generators is copied and made mutable. (The assumption is that this function used in situations where you just want a new generating set.)

3.3-4 CanonicalAction
> CanonicalAction( G )( attribute )
> CanonicalActionOnRight( G )( attribute )
> CanonicalGroupAndAction( G )( attribute )

Returns: Function action(g,v) or a record with elements (group, action, actionOnRight, actionBlockSize)

Returns a function of the form action(g,v) that performs the canonical group action of an element g of the group G on a vector v (acting on the left by default, or on the right with the OnRight version). The GroupAndAction version of this function returns the actions in a record together with the group and the action block size. Under the canonical action, a free module FG is represented as a vector of length |G| over the field F, and the action is a permutation of the vector elements.

Note that these functions are attributes of a group, so that the canonical action for a particular group object will always be an identical function (which is desirable for comparing and combining modules and submodules).

3.3-5 Example: Constructing a FpGModuleGF

The example below constructs four different FG-modules, where G is the quaternion group of order eight, and the action is the canonical action in each case:

  1. M is the module (FG)^3

  2. S is the submodule of (FG)^3 with elements only in the first summand

  3. T is a random submodule M generated by five elements

  4. U is the trivial (zero) submodule of (FG)^4

We check whether S, T and U are submodules of M, examine a random element from M, and convert S into a HAP FpGModule. For the other functions used in this example, see Section 3.8.

gap> G := SmallGroup(8, 4);;
gap> M := FpGModuleGF(G, 3);
Full canonical module FG^3 over the group ring of <pc group of size 8 with
3 generators> in characteristic 2
gap> gen := ListWithIdenticalEntries(24, Zero(GF(2)));;
gap> gen[1] := One(GF(2));;
gap> S := FpGModuleGF([gen], G);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 1 generator in FG^
3. Generators are in minimal echelon form.
gap> T := RandomSubmodule(M, 5);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 5 generators in FG^3.
gap> U := FpGModuleGF(32, CanonicalGroupAndAction(G));
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 0 generators in FG^
4. Generators are in minimal echelon form.
gap>
gap> IsSubModule(M, S);
true
gap> IsSubModule(M, T);
true
gap> IsSubModule(M, U);
false
gap>
gap> e := RandomElement(M);
<a GF2 vector of length 24>
gap> Display([e]);
 . 1 1 . . 1 . . . . . 1 . . 1 1 . . 1 . 1 . . 1
gap> IsModuleElement(S, e);
false
gap> IsModuleElement(T, e);
true
gap>
gap> FpGModuleFromFpGModuleGF(S);
Module of dimension 8 over the group ring of <pc group of size 8 with
3 generators> in characteristic 2

3.4 Data access functions

3.4-1 ModuleGroup
> ModuleGroup( M )( operation )

Returns: Group

Returns the group of the module M. See Section 3.4-11 below for an example of usage.

3.4-2 ModuleGroupOrder
> ModuleGroupOrder( M )( operation )

Returns: Integer

Returns the order of the group of the module M. This function is identical to Order(ModuleGroup(M)), and is provided for convenience. See Section 3.4-11 below for an example of usage.

3.4-3 ModuleAction
> ModuleAction( M )( operation )

Returns: Function

Returns the group action function of the module M. This is a function action(g, v) that takes a group element g and a vector v and returns a vector w that is the result of w = gv. See Section 3.4-11 below for an example of usage.

3.4-4 ModuleActionBlockSize
> ModuleActionBlockSize( M )( operation )

Returns: Integer

Returns the block size of the group action of the module M. This is the length of vectors (or the factor of the length) upon which the group action function acts. See Section 3.4-11 below for an example of usage.

3.4-5 ModuleGroupAndAction
> ModuleGroupAndAction( M )( operation )

Returns: Record with elements (group, action, actionOnRight, actionBlockSize)

Returns details of the module's group and action in a record with the following elements:

This function is provided for convenience, and is used by a number of internal functions. The canonical groups and action can be constructed using the function CanonicalGroupAndAction (3.3-4). See Section 3.4-11 below for an example of usage.

3.4-6 ModuleCharacteristic
> ModuleCharacteristic( M )( operation )

Returns: Integer

Returns the characteristic of the field F of the FG-module M. See Section 3.4-11 below for an example of usage.

3.4-7 ModuleField
> ModuleField( M )( operation )

Returns: Field

Returns the field F of the FG-module M. See Section 3.4-11 below for an example of usage.

3.4-8 ModuleAmbientDimension
> ModuleAmbientDimension( M )( operation )

Returns: Integer

Returns the ambient dimension of the module M. The module M is represented as a submodule of FG^n using generating vectors for a vector space. This function returns the dimension of this underlying vector space. This is equal to the length of each generating vector, and also nxactionBlockSize. See Section 3.4-11 below for an example of usage.

3.4-9 AmbientModuleDimension
> AmbientModuleDimension( M )( operation )

Returns: Integer

The module M is represented a submodule embedded within the free module FG^n. This function returns n, the dimension of the ambient module. This is the same as the number of blocks. See Section 3.4-11 below for an example of usage.

3.4-10 DisplayBlocks
> DisplayBlocks( M )( operation )

Returns: nothing

Displays the structure of the module generators gens in a compact human-readable form. Since the group action permutes generating vectors in blocks of length actionBlockSize, any block that contains non-zero elements will still contain non-zero elements after the group action, but a block that is all zero will remain all zero. This operation displays the module generators in a per-block form, with a * where the block is non-zero and . where the block is all zero.

The standard GAP methods View (Reference: View), Print (Reference: Print) and Display (Reference: Display) are also available.) See Section 3.6-3 below for an example of usage.

3.4-11 Example: Accessing data about a FpGModuleGF

In the following example, we construct three terms of a (minimal) resolution of the dihedral group of order eight, which is a chain complex of FG-modules.

(FG)^3 -> (FG)^2 -> FG -> F -> 0

We obtain the last homomorphism in this chain complex and calculate its kernel, returning this as a FpGModuleGF. We can use the data access functions described above to extract information about this module.

See Chapters 4 and 2 respectively for more information about FG-module homomorphisms and resolutions in HAPprime

gap> R := ResolutionPrimePowerGroupRadical(DihedralGroup(8), 2);
Resolution of length 2 in characteristic 2 for <pc group of size 8 with
3 generators> .
No contracting homotopy available.
A partial contracting homotopy is available.

gap> phi := BoundaryFpGModuleHomomorphismGF(R, 2);
<Module homomorphism>

gap> M := KernelOfModuleHomomorphism(phi);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 15 generators in FG^3.

gap> # Now find out things about this module M
gap> ModuleGroup(M);
<pc group of size 8 with 3 generators>
gap> ModuleGroupOrder(M);
8
gap> ModuleAction(M);
function( g, v ) ... end
gap> ModuleActionBlockSize(M);
8
gap> ModuleGroupAndAction(M);
rec( group := <pc group of size 8 with 3 generators>,
  action := function( g, v ) ... end,
  actionOnRight := function( g, v ) ... end, actionBlockSize := 8 )
gap> ModuleCharacteristic(M);
2
gap> ModuleField(M);
GF(2)
gap> ModuleAmbientDimension(M);
24
gap> AmbientModuleDimension(M);
3

3.5 Generator and vector space functions

3.5-1 ModuleGenerators
> ModuleGenerators( M )( operation )

Returns: List of vectors

Returns, as the rows of a matrix, a list of the set of currently-stored generating vectors for the vector space of the module M. Note that this set is not necessarily minimal. The function ModuleGeneratorsAreMinimal (3.5-2) will return true if the set is known to be minimal, and the MinimalGeneratorsModule functions (3.5-9) can be used to ensure a minimal set, if necessary. See Section 3.5-11 below for an example of usage.

3.5-2 ModuleGeneratorsAreMinimal
> ModuleGeneratorsAreMinimal( M )( operation )

Returns: Boolean

Returns true if the module generators are known to be minimal, or false otherwise. Generators are known to be minimal if the one of the MinimalGeneratorsModule functions (3.5-9) have been previously used on this module, or if the module was created from a HAP FpGModule. See Section 3.5-11 below for an example of usage.

3.5-3 ModuleGeneratorsAreEchelonForm
> ModuleGeneratorsAreEchelonForm( M )( operation )

Returns: Boolean

Return true if the module generators are known to be in echelon form, or (i.e. EchelonModuleGenerators (3.6-1) has been called for this module), or false otherwise. Some algorithms work more efficiently if (or require that) the generators of the module are in block-echelon form, i.e. each generator in the module's list of generators has its first non-zero block in the same location or later than the generator before it in the list. See Section 3.5-11 below for an example of usage.

3.5-4 ModuleIsFullCanonical
> ModuleIsFullCanonical( M )( operation )

Returns: Boolean

Returns true if the module is known to represent the full module FG^n, with canonical generators and group action, or false otherwise. A module is only known to be canonical if it was constructed using the canonical module FpGModuleGF constructor (FpGModuleGF (3.3-1)). If this is true, the module is displayed in a concise form, and some functions have a trivial implementation. See Section 3.5-11 below for an example of usage.

3.5-5 ModuleGeneratorsForm
> ModuleGeneratorsForm( M )( operation )

Returns: String

Returns a string giving the form of the module generators. This may be one of the following:

See Section 3.5-11 below for an example of usage.

3.5-6 ModuleRank
> ModuleRank( M )( operation )
> ModuleRankDestructive( M )( operation )

Returns: Integer

Returns the rank of the module M, i.e. the number of minimal generators. If the module is already in minimal form (according to ModuleGeneratorsAreMinimal (3.5-2)) then the number of generators is returned with no calculation. Otherwise, MinimalGeneratorsModuleGF (3.5-9) or MinimalGeneratorsModuleGFDestructive (3.5-9) respectively are used to find a set of minimal generators. See Section 3.5-11 below for an example of usage.

3.5-7 ModuleVectorSpaceBasis
> ModuleVectorSpaceBasis( M )( operation )

Returns: List of vectors

Returns a matrix whose rows are a basis for the vector space of the FpGModuleGF module M. Since FpGModuleGF stores modules as a minimal G-generating set, this function has to calculate all G-multiples of this generating set and row-reduce this to find a basis. See Section 3.5-11 below for an example of usage.

TODO: A GF version of this one

3.5-8 ModuleVectorSpaceDimension
> ModuleVectorSpaceDimension( M )( operation )

Returns: Integer

Returns the dimension of the vector space of the module M. Since FpGModuleGF stores modules as a minimal G-generating set, this function has to calculate all G-multiples of this generating set and row-reduce this to find the size of the basis. See Section 3.5-11 below for an example of usage.

TODO: A GF version of this function

3.5-9 MinimalGeneratorsModule
> MinimalGeneratorsModuleGF( M )( operation )
> MinimalGeneratorsModuleGFDestructive( M )( operation )
> MinimalGeneratorsModuleRadical( M )( operation )

Returns: FpGModuleGF

Returns a module equal to the FpGModuleGF M, but which has a minimal set of generators. Two algorithms are provided:

See Section 3.5-11 below for an example of usage.

3.5-10 RadicalOfModule
> RadicalOfModule( M )( operation )

Returns: FpGModuleGF

Returns radical of the FpGModuleGF module M as another FpGModuleGF. The radical is the module generated by the vectors v-gv for all v in the set of generating vectors for M and all g in a set of generators for the module's group.

The generators for the returned module will not be in minimal form: the MinimalGeneratorsModule functions (3.5-9) can be used to convert the module to a minimal form if necessary. See Section 3.5-11 below for an example of usage.

3.5-11 Example: Generators and basis vectors of a FpGModuleGF

Starting with the same module as in the earlier example (Section 3.4-11), we now investigate the generators of the module M. The generating vectors (of which there are 15) returned by the function KernelOfModuleHomomorphism (4.6-3) are not a minimal set, but the function MinimalGeneratorsModuleGF (3.5-9) creates a new object N representing the same module, but now with only four generators. The vector space spanned by these generators has 15 basis vectors, so representing the module by a G-generating set instead is much more efficient. (The original generating set in M was in fact an F-basis, so the dimension of the vector space should come as no surprise.)

We can also find the radical of the module, and this is used internally for the faster, but more memory-hungry, MinimalGeneratorsModuleRadical (3.5-9).

gap> R := ResolutionPrimePowerGroupRadical(DihedralGroup(8), 2);;
gap> phi := BoundaryFpGModuleHomomorphismGF(R, 2);;
gap> M := KernelOfModuleHomomorphism(phi);;
gap> #
gap> ModuleGenerators(M);
[ <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24> ]
gap> ModuleGeneratorsAreMinimal(M);
false
gap> ModuleGeneratorsForm(M);
"unknown"
gap> #
gap> N := MinimalGeneratorsModuleGF(M);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 4 generators in FG^
3. Generators are in minimal echelon form.

gap> M = N;    # Check that the new module spans the same space
true
gap> ModuleGeneratorsAreEchelonForm(N);
true
gap> ModuleIsFullCanonical(N);
false
gap> M = N;
true
gap> ModuleVectorSpaceBasis(N);
[ <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24>, <a GF2 vector of length 24>,
  <a GF2 vector of length 24> ]
gap> ModuleVectorSpaceDimension(N);
15
gap> #
gap> N2 := MinimalGeneratorsModuleRadical(M);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 4 generators in FG^
3. Generators are minimal.

gap> #
gap> R := RadicalOfModule(M);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 120 generators in FG^3.

gap> N2 = N;
true

3.6 Block echelon functions

3.6-1 EchelonModuleGenerators
> EchelonModuleGenerators( M )( operation )
> EchelonModuleGeneratorsDestructive( M )( operation )
> SemiEchelonModuleGenerators( M )( operation )
> SemiEchelonModuleGeneratorsDestructive( M )( operation )
> EchelonModuleGeneratorsMinMem( M )( operation )
> EchelonModuleGeneratorsMinMemDestructive( M )( operation )
> SemiEchelonModuleGeneratorsMinMem( M )( operation )
> SemiEchelonModuleGeneratorsMinMemDestructive( M )( operation )

Returns: Record (module, headblocks)

Returns a record with two components:

In block-echelon form. each generator is row-reduced using Gg-multiples of the other other generators to produce a new, equivalent generating set where the first non-zero block in each generator is as far to the right as possible. The resulting form, with many zero blocks, can allow more memory-efficient operations on the module. See Section 3.2 for details. In addition, the standard (non-MinMem) form guarantees that the set of generators are minimal in the sense that no generator can be removed from the set while leaving the spanned vector space the same. In the GF(2) case, this is the global minimum.

Several versions of this algorithm are provided. The SemiEchelon versions of these functions do not guarantee a particular generator ordering, while the Echelon versions sort the generators into order of increasing initial zero blocks. The non-Destructive versions of this function return a new module and do not modify the input module; the Destructive versions change the generators of the input module in-place, and return this module. All versions are memory-efficient, and do not need a full vector-space basis. The MinMem versions are guaranteed to expand at most two generators at any one time, while the standard version may, in the (unlikely) worst-case, need to expand half of the generating set. As a result of this difference in the algorithm, the MinMem version is likely to return a greater number of generators (which will not be minimal), but those generators typically have a greater number of zero blocks after the first non-zero block in the generator. The MinMem operations are currently only implemented for GF(2) modules. See Section 3.6-3 below for an example of usage.

3.6-2 ReverseEchelonModuleGenerators
> ReverseEchelonModuleGenerators( M )( operation )
> ReverseEchelonModuleGeneratorsDestructive( M )( operation )

Returns: FpGModuleGF

Returns an FpGModuleGF module whose vector space spans the same space as the input module M, but whose generating vectors are modified to try to get as many zero blocks as possible at the end of each vector. This function performs echelon reduction of generating rows in a manner similar to EchelonModuleGenerators (3.6-1), but working from the bottom upwards. It is guaranteed that this function will not change the head block (the location of the first non-zero block) in each generating row, and hence if the generators are already in an upper-triangular form (e.g. following a call to EchelonModuleGenerators (3.6-1)) then it will not disturb that form and the resulting generators will be closer to a diagonal form.

The Destructive version of this function modifies the input module's generators in-place and then returns that module; the non-Destructive version works on a copy of the input module and so will not modify the original module.

This operation is currently only implemented for GF(2) modules. See Section 3.5-11 below for an example of usage.

3.6-3 Example: Converting a FpGModuleGF to block echelon form

We can construct a larger module than in the earlier examples (Sections 3.4-11 and 3.5-11) by taking the kernel of the third boundary homomorphism of a minimal resolution of a group of order 32, which as returned by the function KernelOfModuleHomomorphism (4.6-3) has a generating set with many redundant generators. We display the block structure of the generators of this module after applying various block echelon reduction functions.

gap> R := ResolutionPrimePowerGroupRadical(SmallGroup(32, 10), 3);;
gap> phi := BoundaryFpGModuleHomomorphismGF(R, 3);;
gap> #
gap> M := KernelOfModuleHomomorphism(phi);
Module over the group ring of <pc group of size 32 with
5 generators> in characteristic 2 with 65 generators in FG^4.

gap> #
gap> N := SemiEchelonModuleGenerators(M);
rec( module := Module over the group ring of <pc group of size 32 with
    5 generators> in characteristic 2 with 5 generators in FG^
    4. Generators are in minimal semi-echelon form.
    , headblocks := [ 2, 3, 1, 1, 3 ] )
gap> DisplayBlocks(N.module);
Module over the group ring of Group( [ f1, f2, f3, f4, f5 ] )
 in characteristic 2 with 5 generators in FG^4.
[.*.*]
[..**]
[***.]
[****]
[..**]
Generators are in minimal semi-echelon form.
gap> N2 := SemiEchelonModuleGeneratorsMinMem(M);
rec( module := Module over the group ring of <pc group of size 32 with
    5 generators> in characteristic 2 with 9 generators in FG^4. 
    , headblocks := [ 2, 1, 3, 1, 1, 4, 1, 3, 4 ] )
gap> DisplayBlocks(N2.module);
Module over the group ring of Group( [ f1, f2, f3, f4, f5 ] )
 in characteristic 2 with 9 generators in FG^4.
[.*..]
[**..]
[..**]
[****]
[****]
[...*]
[****]
[..**]
[...*]

gap> #
gap> EchelonModuleGeneratorsDestructive(M);;
gap> DisplayBlocks(M);
Module over the group ring of Group( [ f1, f2, f3, f4, f5 ] )
 in characteristic 2 with 5 generators in FG^4.
[***.]
[****]
[.*.*]
[..**]
[..**]
Generators are in minimal echelon form.
gap> ReverseEchelonModuleGeneratorsDestructive(M);
Module over the group ring of <pc group of size 32 with
5 generators> in characteristic 2 with 5 generators in FG^
4. Generators are in minimal echelon form.

gap> DisplayBlocks(M);
Module over the group ring of Group( [ f1, f2, f3, f4, f5 ] )
 in characteristic 2 with 5 generators in FG^4.
[***.]
[****]
[.*..]
[..*.]
[..**]
Generators are in minimal echelon form.

3.7 Sum and intersection functions

3.7-1 DirectSumOfModules
> DirectSumOfModules( M, N )( operation )
> DirectSumOfModules( coll )( operation )
> DirectSumOfModules( M, n )( operation )

Returns: FpGModule

Returns the FpGModuleGF module that is the direct sum of the specified modules (which must have a common group and action). The input can be either two modules M and N, a list of modules coll, or one module M and an exponent n specifying the number of copies of M to sum. See Section 3.7-5 below for an example of usage.

If the input modules all have minimal generators and/or echelon form, the construction of the direct sum guarantees that the output module will share the same form.

3.7-2 DirectDecompositionOfModule
> DirectDecompositionOfModule( M )( operation )
> DirectDecompositionOfModuleDestructive( M )( operation )

Returns: List of FpGModuleGFs

Returns a list of FpGModuleGFs whose direct sum is equal to the input FpGModuleGF module M. The list may consist of one element: the original module.

This function relies on the block structure of a set of generators that have been converted to both echelon and reverse-echelon form (see EchelonModuleGenerators (3.6-1) and ReverseEchelonModuleGenerators (3.6-2)), and calls these functions if the module is not already in echelon form. In this form, it can be possible to trivially identify direct summands. There is no guarantee either that this function will return a decomposition if one is available, or that the modules returned in a decomposition are themselves indecomposable. See Section 3.7-5 below for an example of usage.

The Destructive version of this function uses the Destructive versions of the echelon functions, and so modifies the input module and returns modules who share generating rows with the modified M. The non-Destructive version operates on a copy of M, and returns modules with unique rows.

3.7-3 IntersectionModules
> IntersectionModules( M, N )( operation )
> IntersectionModulesGF( M, N )( operation )
> IntersectionModulesGFDestructive( M, N )( operation )
> IntersectionModulesGF2( M, N )( operation )

Returns: FpGModuleGF

Returns the FpGModuleGF module that is the intersection of the modules M and N. This function calculates the intersection using vector space methods (i.e. SumIntersectionMatDestructive (HAPprime Datatypes: SumIntersectionMatDestructive)). The standard version works on the complete vector space bases of the input modules. The GF version considers the block structure of the generators of M and N and only expands the necessary rows and blocks. This can lead to a large saving and memory if M and N are in echelon form and have a small intersection. See Section 3.2-4 for details. See Section 3.7-5 below for an example of usage. The GF2 version computes the intersection by a G-version of the standard vector space algorithm, using EchelonModuleGenerators (3.6-1) to perform echelon reduction on an augmented set of generators. This is much slower than the GF version, but may use less memory.

The vector spaces in FpGModuleGFs are assumed to all be with respect to the same canonical basis, so it is assumed that modules are compatible if they have the same group and the same ambient dimension.

The Destructive version of the GF function corrupts or permutes the generating vectors of M and N, leaving it invalid; the non-destructive version operates on copies of them, leaving the original modules unmodified. The generating vectors in the module returned by this function are in fact also a vector space basis for the module, so will not be minimal. The returned module can be converted to a set of minimal generators using one of the MinimalGeneratorsModule functions (3.5-9).

This operation is currently only defined for GF(2).

3.7-4 SumModules
> SumModules( M, N )( operation )

Returns: FpGModuleGF

Returns the FpGModuleGF module that is the sum of the input modules M and N. This function simply concatenates the generating vectors of the two modules and returns the result. If a set of minimal generators are needed then use one of the MinimalGeneratorsModule functions (3.5-9) on the result. See Section 3.7-5 below for an example of usage.

The vector spaces in FpGModuleGF are assumed to all be with respect to the same canonical basis, so it is assumed that modules are compatible if they have the same group and the same ambient dimension.

3.7-5 Example: Sum and intersection of FpGModuleGFs

We can construct the direct sum of FG-modules, and (attempt to) calculate a direct decomposition of a module. For example, we can show that

(FG)^2 (+) FG = FG (+) FG (+) FG

gap> G := CyclicGroup(64);;
gap> FG := FpGModuleGF(G, 1);
Full canonical module FG^1 over the group ring of <pc group of size 64 with
6 generators> in characteristic 2

gap> FG2 := FpGModuleGF(G, 2);
Full canonical module FG^2 over the group ring of <pc group of size 64 with
6 generators> in characteristic 2

gap> M := DirectSumOfModules(FG2, FG);
Full canonical module FG^3 over the group ring of <pc group of size 64 with
6 generators> in characteristic 2

gap> DirectDecompositionOfModule(M);
[ Module over the group ring of <pc group of size 64 with
    6 generators> in characteristic 2 with 1 generator in FG^
    1. Generators are in minimal echelon form.
    , Module over the group ring of <pc group of size 64 with
    6 generators> in characteristic 2 with 1 generator in FG^
    1. Generators are in minimal echelon form.
    , Module over the group ring of <pc group of size 64 with
    6 generators> in characteristic 2 with 1 generator in FG^
    1. Generators are in minimal echelon form.
     ]

We can also compute the sum and intersection of FG-modules. In the example below we construct two submodules of FG, where G is the dihedral group of order four: M is the submodule generated by g_1 + g_2, and N is the submodule generated by g_1 + g_2 + g_3 + g_4. We calculate their sum and intersection. Since N is in this case a submodule of M it is easy to check that the correct results are obtained.

gap> G := DihedralGroup(4);;
gap> M := FpGModuleGF([[1,1,0,0]]*One(GF(2)), G);
Module over the group ring of <pc group of size 4 with
2 generators> in characteristic 2 with 1 generator in FG^
1. Generators are in minimal echelon form.

gap> N := FpGModuleGF([[1,1,1,1]]*One(GF(2)), G);
Module over the group ring of <pc group of size 4 with
2 generators> in characteristic 2 with 1 generator in FG^
1. Generators are in minimal echelon form.

gap> #
gap> S := SumModules(M,N);
Module over the group ring of <pc group of size 4 with
2 generators> in characteristic 2 with 2 generators in FG^1.

gap> I := IntersectionModules(M,N);
Module over the group ring of <pc group of size 4 with
2 generators> in characteristic 2 with 1 generator in FG^1.

gap> #
gap> S = M and I = N;
true

3.8 Miscellaneous functions

3.8-1 =
> =( M, N )( operation )

Returns: Boolean

Returns true if the modules are equal, false otherwise. This checks that the groups and actions in each module are equal (i.e. identical), and that the vector space spanned by the two modules are the same. (All vector spaces in FpGModuleGFs of the same ambient dimension are assumed to be embedded in the same canonical basis.) See Section 3.5-11 above for an example of usage.

3.8-2 IsModuleElement
> IsModuleElement( M, elm )( operation )
> IsModuleElement( M, coll )( operation )

Returns: Boolean

Returns true if the vector elm can be interpreted as an element of the module M, or false otherwise. If a collection of elements is given as the second argument then a list of responses is returned, one for each element in the collection. See Section 3.3-5 above for an example of usage.

3.8-3 IsSubModule
> IsSubModule( M, N )( operation )

Returns: Boolean

Returns true if the module N is a submodule of M. This checks that the modules have the same group and action, and that the generators for module N are elements of the module M. (All vector spaces in FpGModuleGFs of the same ambient dimension are assumed to be embedded in the same canonical basis.) See Section 3.3-5 above for an example of usage.

3.8-4 RandomElement
> RandomElement( M[, n] )( operation )

Returns: Vector

Returns a vector which is a random element from the module M. If a second argument, n is give, then a list of n random elements is returned. See Section 3.3-5 above for an example of usage.

3.8-5 Random Submodule
> RandomSubmodule( M, ngens )( operation )

Returns: FpGModuleGF

Returns a FpGModuleGF module that is a submodule of M, with ngens generators selected at random from elements of M. These generators are not guaranteed to be minimal, so the rank of the submodule will not necessarily be equal to ngens. If a module with minimal generators is required, the MinimalGeneratorsModule functions (3.5-9) can be used to convert the module to a minimal form See Section 3.3-5 above for an example of usage.

 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 Ind

generated by GAPDoc2HTML