6 FG-module homomorphisms
  
  
  6.1 The FpGModuleHomomorphismGF datatype
  
  Linear  homomorphisms  between free FG-modules (as FpGModuleGF objects - see
  Chapter  5)  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 (6.4-1):
  
  --    source the source FpGModuleGF module for the homomorphism
  
  --    target the target FpGModuleGF module for the homomorphism
  
  --    gens  a  list  of  vectors  that  are the images (in target) under the
        homomorphisms of each of the generators stored in source
  
  
  6.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  5). 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 5.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 (6.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
  
  --    I  =  im(U)  cap  im(V)  is  the intersection of the images of the two
        homomorphisms U and V
  
  --    preim_U(I) the set of all preimages of I under U
  
  --    preim_V(I) the set of all preimages of I under V
  
  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 5.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
  (6.6-3).
  
  
  6.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 (6.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.
  
  
  6.4 Construction functions
  
  
  6.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
  (5.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.
  
  
  6.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
  
  ---------------------------  Example  ----------------------------
    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>
  ------------------------------------------------------------------
  
  
  6.5 Data access functions
  
  6.5-1 SourceModule
  
  > SourceModule( phi ) _____________________________________________operation
  Returns:  FpGModuleGF
  
  Returns the source module for the homomorphism phi, as an FpGModuleGF.
  
  6.5-2 TargetModule
  
  > TargetModule( phi ) _____________________________________________operation
  Returns:  FpGModuleGF
  
  Returns the targetmodule for the homomorphism phi, as an FpGModuleGF.
  
  6.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.
  
  6.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.)
  
  6.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.
  
  6.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
  (6.5-4) method.
  
  
  6.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.
  
  ---------------------------  Example  ----------------------------
    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 5.2). This
  makes  it  efficient  to  compute  the  kernel  of  this  homomorphism using
  KernelOfModuleHomomorphismSplit  (6.6-3), as described in Section 6.2, since
  there  is  only a small intersection between the images generated by the top
  and bottom halves of the generating vectors.
  
  
  6.6 Image and kernel functions
  
  
  6.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 (5.5-9) should be used on
  the result if a minimal set of generators is needed.
  
  
  6.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 (5.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.
  
  6.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:
  
  --    The standard version calculates the kernel by the obvious vector-space
        method.  The  homomorphism's  generators  are  expanded  into  a  full
        vector-space basis and the kernel of that vector space homomorphism is
        found.  The  generators  of  the  returned module are in fact a vector
        space basis for the kernel module.
  
  --    The  Split  version divides the homomorphism into two (using the first
        half  and  the  second  half  of the generating vectors), and uses the
        preimage  of  the  intersection  of  the  images  of the two halves to
        calculate  the kernel (see Section 6.2). If the generating vectors for
        phi  are  in  block echelon form (see Section 5.2), then this approach
        provides a considerable memory saving over the standard approach.
  
  --    The  IndependentSplit  version splits the generating vectors into sets
        that generate vector spaces which have no intersection, and calculates
        the kernel as the sum of the kernels of those independent rows. If the
        generating  vectors  can  be  decomposed  in this manner (i.e. the the
        generator  matrix  is  in  a  diagonal form), this will provide a very
        large memory saving over the standard approach.
  
  --    The  GF  version  performs  column  reduction  and partitioning of the
        generator  matrix  to  enable  a  recursive  approach to computing the
        kernel (see Section 6.3). The level of partitioning is governed by the
        option  MaxFGExpansionSize,  which  defaults  to  10^9, allowing about
        128Mb  of  memory  to  be  used  for  standard  linear  algebra before
        partitioning  starts.  See  'Reference:  Options Stack' for details of
        using options in GAP
  
  None  of these basis versions of the functions guarantee to return a minimal
  set  of generators, and one of the MinimalGeneratorsModule functions (5.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.
  
  
  6.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  (6.6-1) and KernelOfModuleHomomorphism (6.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.
  
  ---------------------------  Example  ----------------------------
    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
  ------------------------------------------------------------------