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

4 FG-module homomorphisms
 4.1 The FpGModuleHomomorphismGF datatype
 4.2 Calculating the kernel of a FG-module homorphism by splitting into two homomorphisms
 4.3 Calculating the kernel of a FG-module homorphism by column reduction and partitioning
 4.4 Construction functions
 4.5 Data access functions
 4.6 Image and kernel functions

4 FG-module homomorphisms

4.1 The FpGModuleHomomorphismGF datatype

Linear homomorphisms between free FG-modules (as FpGModuleGF objects - see Chapter 3) are represented in HAPprime using the FpGModuleHomomorphismGF datatype. This represents module homomorphisms in a similar manner to FG-modules, using a set of generating vectors, in this case vectors that generate the images in the target module of the generators of the source module.

Three items need to be passed to the constructor function FpGModuleHomomorphismGF (4.4-1):

4.2 Calculating the kernel of a FG-module homorphism by splitting into two homomorphisms

HAPprime represents a homomorphism between two FG-modules as a list of generators for the image of the homomorphism. Each generator is given as an element in the target module, represented as a vector in the same manner as used in the FpGModuleGF datatype (see Chapter 3). Given a set of such generating vectors, an F-generating set for the image of the homomorphism (as elements of the target module's vector space) is given by taking all G-multiples of the generators. Writing the vectors in this expanded set as a matrix, the kernel of the boundary homomorphism is the (left) null-space of this matrix. As with FpGModuleGFs, the block structure of the generating vectors (see Section 3.2-1) allows this null-space to be calculated without necessarily expanding the whole matrix.

This basic algorithm is implemented in the HAPprime function KernelOfModuleHomomorphismSplit (4.6-3). The generating vectors for a module homomorphism H are divided in half, with the homomorphism generated by the first half of the generating vectors being called U and that by the second half being called V. Given this partition the kernel of H can be defined as

ker(H) = intersection of preim_U(I) with [-preim_V(I)]

where

Rather than computing the complete set of preimages, instead the implementation takes a preimage representative of each generator for I and adds the kernel of the homomorphisms U and V. The means that instead of calculating the null-space of the full expanded matrix, we can compute the answer by calculating the kernels of two homomorphisms with fewer generators, as well as the intersection of two modules, and some preimage representatives. Each of these operations takes less memory than the naive null-space calculation. The intersection of two FG-modules can be compactly calculated using the generators' block structure (see Section 3.2-4), while the kernels of U and V can be computed recursively using these same algorithm. The block structure can also help in calculating the preimage, but at a considerable cost in time, so this is not done. However, since U and V have fewer generators than the original homomorphism H, a space saving is still made.

In the case where the problem is seperable, i.e. a U and V can be found for which there is no intersection, this approach can give a large saving. The separable components of the homomorphism can be readily identified from the block structure of the generators (they are the rows which share no blocks or heads with other rows), and the kernels of these can be calculated independently, with no intersection to worry about. This is implemented in the alternative algorithm KernelOfModuleHomomorphismIndependentSplit (4.6-3).

4.3 Calculating the kernel of a FG-module homorphism by column reduction and partitioning

The list of generators of the image of a FG-module homomorphism can be interpreted as the rows of a matrix A with elements in FG, and it is the kernel of this matrix which must be found (i.e. the solutions to xA=0. If column reduction is performed on this matrix (by adding FG-multiples of other columns to a column), the kernel is left unchanged, and this process can be performed to enable the kernel to be found by a recursive algorithm similar to standard back substitution methods.

Given the matrix A = (a_ij), take the FG-module generated by the first row (a_1j) and find a minimal (or small) subset of elements {a_1j}_j in J that generate this module. Without altering the kernel, we can permute the columns of A such that J = {1 ... t}. Taking F and G-multiples of these columns from the remaining columns, the first row of these columns can be reduced to zero, giving a new matrix A'. This matrix can be partitioned as follows:

[ B 0 ] [ C D ]

where B is 1x t, C is (m-1)x t and D is (m-1)x (n-t). It is assumed that B and C are `small' and operations on these can can be easily handled in memory using standard linear algebra, while D may still be large.

Taking the FG-module generated by the t columns which form the BC partition of the matrix, we compute E, a set of minimal generators for the submodule of this which is zero in the first row. These are added as columns at the end of A', giving a matrix

[ B 0 0 ] [ C D E ]

The kernel of this matrix can be shown to be

[ ker(B) 0 ] [ L ker(DE) ]

where

L = preim_B((\ker (DE)) C)

The augmentation of D with E guarantees that this preimage always exists. Since B and C are small, both ker B and L are easy to compute using linear algebra, while ker (DE) can be computed by recursion.

Unfortunately, E can be large, and the accumulated increase of size of the matrix over many recursions negates the time and memory saving that this algorithm might be expected to give. Testing indicates that it is currently no faster than the KernelOfModuleHomomorphismSplit (4.6-3) method, and does not save much memory over the full expansion using linear algebra. An improved version of this algorithm would reduce E by D before augmentation, thus adding a smaller set of generators and restricting the explosion in size. If D were already in echelon form, this would also be time-efficient.

4.4 Construction functions

4.4-1 FpGModuleHomomorphismGF construction functions
> FpGModuleHomomorphismGF( S, T, gens )( operation )
> FpGModuleHomomorphismGFNC( S, T, gens )( operation )

Returns: FpGModuleHomomorphismGF

Creates and returns an FpGModuleHomomorphismGF module homomorphism object. This represents the homomorphism from the module S to the module T with a list of vectors gens whose rows are the images in T of the generators of S. The modules must (currently) be over the same group.

The standard constructor checks that the homomorphism is compatible with the modules, i.e. that the vectors in gens have the correct dimension and that they lie within the target module T. It also checks whether the generators of S are minimal. If they are not, then the homomorphism is created with a copy of S that has minimal generators (using MinimalGeneratorsModuleRadical (3.5-9)), and gens is also copied and converted to agree with the new form of S. If you wish to skip these checks then use the NC version of this function.

IMPORTANT: The generators of the module S and the generator matrix gens must be remain consistent for the lifetime of this homomorphism. If the homomorphism is constructed with a mutable source module or generator matrix, then you must be careful not to modify them while the homomorphism is needed.

4.4-2 Example: Constructing a FpGModuleHomomorphismGF

In this example we construct the module homomorphism phi: (FG)^2 -> FG which maps both generators of (FG)^2 to the generator of FG

gap> G := SmallGroup(8, 4);;
gap> im := [1,0,0,0,0,0,0,0]*One(GF(2));
[ Z(2)^0, 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2) ]
gap> phi := FpGModuleHomomorphismGF(
>              FpGModuleGF(G, 2),
>              FpGModuleGF(G, 1),
>              [im, im]);
<Module homomorphism>

4.5 Data access functions

4.5-1 SourceModule
> SourceModule( phi )( operation )

Returns: FpGModuleGF

Returns the source module for the homomorphism phi, as an FpGModuleGF.

4.5-2 TargetModule
> TargetModule( phi )( operation )

Returns: FpGModuleGF

Returns the targetmodule for the homomorphism phi, as an FpGModuleGF.

4.5-3 ModuleHomomorphismGeneratorMatrix
> ModuleHomomorphismGeneratorMatrix( phi )( operation )

Returns: List of vectors

Returns the generating vectors gens of the representation of the homomorphism phi. These vectors are the images in the target module of the generators of the source module.

4.5-4 DisplayBlocks
> DisplayBlocks( phi )( method )

Returns: nothing

Prints a detailed description of the module in human-readable form, with the module generators and generator matrix shown in block form. The standard GAP methods View (Reference: View), Print (Reference: Print) and Display (Reference: Display) are also available.)

4.5-5 DisplayModuleHomomorphismGeneratorMatrix
> DisplayModuleHomomorphismGeneratorMatrix( phi )( method )

Returns: nothing

Prints a detailed description of the module homomorphism generating vectors gens in human-readable form. This is the display method used in the Display (Reference: Display) method for this datatype.

4.5-6 DisplayModuleHomomorphismGeneratorMatrixBlocks
> DisplayModuleHomomorphismGeneratorMatrixBlocks( phi )( method )

Returns: nothing

Prints a detailed description of the module homomorphism generating vectors gens in human-readable form. This is the function used in the DisplayBlocks (4.5-4) method.

4.5-7 Example: Accessing data about a FpGModuleHomomorphismGF

A free FG resolution is a chain complex of FG-modules and homomorphisms, and the homomorphisms in a HAPResolution (see Chapter 2) can be extracted as a FpGModuleHomomorphismGF using the function BoundaryFpGModuleHomomorphismGF (2.4-6). We construct a resolution R and then examine the third resolution in the chain complex, which is a FG-module homomorphism d_3 : (FG)^7 -> (FG)^5.

gap> R := ResolutionPrimePowerGroupRadical(SmallGroup(64, 141), 3);;
#I  Dimension 2: rank 5
#I  Dimension 3: rank 7
gap> d3 := BoundaryFpGModuleHomomorphismGF(R, 3);;
gap> SourceModule(d3);
Full canonical module FG^7 over the group ring of <pc group of size 64 with
6 generators> in characteristic 2

gap> TargetModule(d3);
Full canonical module FG^5 over the group ring of <pc group of size 64 with
6 generators> in characteristic 2

gap> ModuleHomomorphismGeneratorMatrix(d3);
<an immutable 7x320 matrix over GF2>
gap> DisplayBlocks(d3);
Module homomorphism with source:
Full canonical module FG^7 over the group ring of Group(
[ f1, f2, f3, f4, f5, f6 ] )
 in characteristic 2

and target:
Full canonical module FG^5 over the group ring of Group(
[ f1, f2, f3, f4, f5, f6 ] )
 in characteristic 2

and generator matrix:
[*.*.*]
[*****]
[.**..]
[.**..]
[..**.]
[...**]
[...*.]

Note that the module homomorphism generating vectors in a resolution calculated using HAPprime are in block-echelon form (see Section 3.2). This makes it efficient to compute the kernel of this homomorphism using KernelOfModuleHomomorphismSplit (4.6-3), as described in Section 4.2, since there is only a small intersection between the images generated by the top and bottom halves of the generating vectors.

4.6 Image and kernel functions

4.6-1 ImageOfModuleHomomorphism
> ImageOfModuleHomomorphism( phi )( operation )
> ImageOfModuleHomomorphism( phi, M )( operation )
> ImageOfModuleHomomorphism( phi, elm )( operation )
> ImageOfModuleHomomorphism( phi, coll )( operation )
> ImageOfModuleHomomorphismDestructive( phi, elm )( operation )
> ImageOfModuleHomomorphismDestructive( phi, coll )( operation )

Returns: FpGModuleGF, vector or list of vectors depending on argument

For a module homomorphism phi, the one-argument function returns the module that is the image of the homomorphism, while the two-argument versions return the result of mapping of an FpGModuleGF M, a module element elm (given as a vector), or a collection of module elements coll through the homomorphism. This uses standard linear algebra to find the image of elements from the source module.

The Destructive versions of the function will corrupt the second parameter, which must be mutable as a result. The version of this operation that returns a module does not guarantee that the module will be in minimal form, and one of the MinimalGeneratorsModule functions (3.5-9) should be used on the result if a minimal set of generators is needed.

4.6-2 PreImageRepresentativeOfModuleHomomorphism
> PreImageRepresentativeOfModuleHomomorphism( phi, elm )( operation )
> PreImageRepresentativeOfModuleHomomorphism( phi, coll )( operation )
> PreImageRepresentativeOfModuleHomomorphism( phi, M )( operation )
> PreImageRepresentativeOfModuleHomomorphismGF( phi, elm )( operation )
> PreImageRepresentativeOfModuleHomomorphismGF( phi, coll )( operation )

For an element elm in the image of phi, this returns a representative of the set of preimages of elm under phi, otherwise it returns fail. If a list of vectors coll is provided then the function returns a list of preimage representatives, one for each element in the list (the returned list can contain fail entries if there are vectors with no solution). For an FpGModuleGF module M, this returns a module whose image under phi is M (or fail). The module returned will not necessarily have minimal generators, and one of the MinimalGeneratorsModule functions (3.5-9) should be used on the result if a minimal set of generators is needed.

The standard functions use linear algebra, expanding the generator matrix into a full matrix and using SolutionMat (Reference: SolutionMat) to calculate a preimage of elm. In the case where a list of vectors is provided, the matrix decomposition is only performed once, which can save significant time.

The GF versions of the functions can give a large memory saving when the generators of the homomorphism phi are in echelon form, and operate by doing back-substitution using the generator form of the matrices.

4.6-3 KernelOfModuleHomomorphism
> KernelOfModuleHomomorphism( phi )( operation )
> KernelOfModuleHomomorphismSplit( phi )( operation )
> KernelOfModuleHomomorphismIndependentSplit( phi )( operation )
> KernelOfModuleHomomorphismGF( phi )( operation )

Returns: FpGModuleGF

Returns the kernel of the module homomorphism phi, as an FpGModuleGF module. There are three independent algorithms for calculating the kernel, represented by different versions of this function:

None of these basis versions of the functions guarantee to return a minimal set of generators, and one of the MinimalGeneratorsModule functions (3.5-9) should be used on the result if a minimal set of generators is needed. All of the functions leave the input homomorphism phi unchanged.

4.6-4 Example: Kernel and Image of a FpGModuleHomomorphismGF

A free FG-resolution of a module is an exact sequence of module homomorphisms. In this example we use the functions ImageOfModuleHomomorphism (4.6-1) and KernelOfModuleHomomorphism (4.6-3) to check that one of the sequences in a resolution is exact, i.e. that in the sequence

M_3 -> M_2 -> M_1

the image of the first homomorphism d_3: M_3 -> M_2 is the kernel of the second homomorphism d_2: M_2 -> M_1

We also demonstrate that we can find the image and preimage of module elements under our module homomorphisms. We take an element e of M_2, in this case by taking the first generating element of the kernel of d_2, and map it up to M_3 and back.

Finally, we compute the kernel using the other available methods, and check that the results are the same.

gap> R := ResolutionPrimePowerGroupRadical(SmallGroup(8, 3), 3);;
gap> d2 := BoundaryFpGModuleHomomorphismGF(R, 2);;
gap> d3 := BoundaryFpGModuleHomomorphismGF(R, 3);;
gap> #
gap> I := ImageOfModuleHomomorphism(d3);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 4 generators in FG^3.

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

gap> I = K;
true
gap> #
gap> e := ModuleGenerators(K)[1];;
gap> PreImageRepresentativeOfModuleHomomorphism(d3, e);
<a GF2 vector of length 32>
gap> f := PreImageRepresentativeOfModuleHomomorphism(d3, e);
<a GF2 vector of length 32>
gap> ImageOfModuleHomomorphism(d3, f);
<a GF2 vector of length 24>
gap> last = e;
true
gap> #
gap> L := KernelOfModuleHomomorphismSplit(d2);
Module over the group ring of <pc group of size 8 with
3 generators> in characteristic 2 with 5 generators in FG^3.

gap> K = L;
true
gap> M := KernelOfModuleHomomorphismGF(d2);
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> K = M;
true
 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 6 Ind

generated by GAPDoc2HTML