fpgmodulehom.xml.in

<!-- 
  HAPPRIME - fpgmodulehom.xml.in
  Function documentation template file for HAPprime
  Paul Smith

  Copyright (C)  2007-2008
  Paul Smith
  National University of Ireland Galway

  $Id: functions.xml.in 200 2008-02-05 14:29:47Z pas $
-->

<!-- ********************************************************** -->
<Chapter Label="FpGModuleGFHom">
  <Heading>&FG;-module homomorphisms</Heading>

  <Section Label="FpGModuleHomGFdatatype">
    <Heading>The <K>FpGModuleHomomorphismGF</K> datatype</Heading>
    
    Linear homomorphisms between free &FG;-modules (as <K>FpGModuleGF</K> objects 
     - see Chapter <Ref Chap="FpGModuleGF"/>) are represented in
    &HAPprime; using the <K>FpGModuleHomomorphismGF</K> 
    datatype. This represents module homomorphisms in a similar manner to 
    <M>\mathbb{F}G</M>-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. 
    <P/>
    Three items need to be passed to the constructor function 
    <Ref Oper="FpGModuleHomomorphismGF"/>:
    <List>
    <Item><C>source</C> the source <K>FpGModuleGF</K> module for the 
    homomorphism
    </Item>
    <Item><C>target</C> the target <K>FpGModuleGF</K> module for the 
    homomorphism
    </Item>
    <Item><C>gens</C> a list of vectors that are the images (in <C>target</C>)
    under the homomorphisms of each of the generators stored in <C>source</C>
    </Item>
    </List>
  </Section>
  
  <Section Label="FpGModuleHomGFkernel">
    <Heading>Calculating the kernel of a &FG;-module homorphism by splitting
      into two homomorphisms</Heading>

    &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 <K>FpGModuleGF</K> datatype (see Chapter 
    <Ref Chap="FpGModuleGF"/>). Given a set of such generating vectors, an
    &FF;-generating set for the image of the homomorphism (as elements of the 
    target module's vector space) is given by taking all <M>G</M>-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 <K>FpGModuleGF</K>s, the block structure of the generating
    vectors (see Section <Ref Subsect="FpGModuleGFalgoblock"/>) allows this 
    null-space to be calculated without necessarily expanding the whole matrix.
    <P/>
    This basic algorithm is implemented in the &HAPprime; function
    <Ref Oper="KernelOfModuleHomomorphismSplit"/>.
    The generating vectors for a module homomorphism <M>H</M> are divided in 
    half, with the homomorphism generated by the first half of the generating
    vectors being called <M>U</M> and that by the second half being
    called <M>V</M>. Given this partition the kernel of <M>H</M> can 
    be defined as
    <Alt Only="LaTeX">
      <Display>
        ker(H) = preim_U(I) \cap [-preim_V(I)]
      </Display>
    </Alt>
    <Alt Not="LaTeX">
      <Display>
        ker(H) = intersection of preim_U(I) with [-preim_V(I)]
      </Display>
    </Alt>
    where 
    <List>
      <Item> <M>I = im(U) \cap im(V)</M> is the intersection of the images 
      of the two homomorphisms <M>U</M> and <M>V</M></Item>
      <Item> <M>preim_U(I)</M> the set of all preimages of <M>I</M> under <M>U</M></Item>
      <Item> <M>preim_V(I)</M> the set of all preimages of <M>I</M> under <M>V</M></Item>
    </List>
    Rather than computing the complete set of preimages, instead the 
    implementation takes a preimage representative of each generator for 
    <M>I</M> and adds the kernel of the homomorphisms <M>U</M> and <M>V</M>.
    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 <Ref Subsect="FpGModuleGFalgoint"/>), while the
    kernels of <M>U</M> and <M>V</M> 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 <M>U</M> and <M>V</M> have fewer generators than the original 
    homomorphism <M>H</M>, a space saving is still made. 
    <P/>
    In the case where the problem is seperable, i.e. a <M>U</M> and <M>V</M> 
    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 <Ref Oper="KernelOfModuleHomomorphismIndependentSplit"/>.
  </Section>

  <Section Label="FpGModuleHomGFkernel2">
    <Heading>Calculating the kernel of a &FG;-module homorphism by column
      reduction and partitioning</Heading>
      
    The list of generators of the image of a &FG;-module homomorphism can be
    interpreted as the rows of a matrix <M>A</M> with elements in &FG;, and it 
    is the kernel of this matrix which must be found (i.e. the solutions to
    <M>xA=0</M>. 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.
    <P/>
    Given the matrix <M>A = (a_{ij})</M>, take the &FG;-module generated by the 
    first row <M>(a_{1j})</M> and find a minimal (or small) subset of elements
    <M>\{a_{1j}\}_{j \in J}</M> that generate this module. Without altering
    the kernel, we can permute  the columns of <M>A</M> such that 
    <M>J = \{1 \ldots t\}</M>. Taking &FF; 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 <M>A'</M>. This matrix can be partitioned as 
    follows:
    <Alt Only="LaTeX">
      <Display><![CDATA[
        \begin{pmatrix} B & 0 \\ C & D \end{pmatrix}
      ]]></Display>
    </Alt>
    <Alt Not="LaTeX">
      <Display>
        [ B  0 ]
        [ C  D ]
      </Display>
    </Alt>
    where <M>B</M> is <M>1\times t</M>, <M>C</M> is <M>(m-1)\times t</M> and 
    <M>D</M> is <M>(m-1)\times (n-t)</M>. It is assumed that <M>B</M> and 
    <M>C</M> are `small' and operations on these can can be easily handled in 
    memory using standard linear algebra, while <M>D</M> may still be large.
    <P/>
    Taking the &FG;-module generated by the <M>t</M> columns which form the 
    <M>BC</M> partition of the matrix, we compute <M>E</M>, 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 <M>A'</M>, giving a matrix 
    <Alt Only="LaTeX">
      <Display><![CDATA[
        \begin{pmatrix} B & 0 & 0\\ C & D & E\end{pmatrix}
      ]]></Display>
    </Alt>
    <Alt Not="LaTeX">
      <Display>
        [ B  0  0 ]
        [ C  D  E ]
      </Display>
    </Alt>
    <P/>
    The kernel of this matrix can be shown to be
    <Alt Only="LaTeX">
      <Display><![CDATA[
        \begin{pmatrix} \ker B & 0\\ L & \ker (DE)\end{pmatrix}
      ]]></Display>
    </Alt>
    <Alt Not="LaTeX">
      <Display>
        [ ker(B)    0    ]
        [   L    ker(DE) ]
      </Display>
    </Alt>
    where
    <Display>
        L = preim_B((\ker (DE)) C)
    </Display>
    The augmentation of <M>D</M> with <M>E</M> guarantees that this preimage 
    always exists. Since <M>B</M> and <M>C</M> are small, both <M>\ker B</M>
    and <M>L</M> are easy to compute using linear algebra, while 
    <M>\ker (DE)</M> can be computed by recursion. 
    <P/>
    Unfortunately, <M>E</M> 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 <Ref Oper="KernelOfModuleHomomorphismSplit"/>
    method, and does not save much memory over the full expansion using linear
    algebra. An improved version of this algorithm would reduce <M>E</M> by
    <M>D</M> before augmentation, thus adding a smaller set of generators and 
    restricting the explosion in size. If <M>D</M> were already in echelon form,
    this would also be time-efficient.
    
  </Section>
  
  <Section>
    <Heading>Construction functions</Heading>
    <!-- GAPDocSourceSuffix="_DTmanFpGModuleHom_Con" -->

    <Subsection Label="FPGModuleHomExample0">
      <Heading>Example: Constructing a <K>FpGModuleHomomorphismGF</K></Heading>
      In this example we construct the module homomorphism 
      <M>\phi: (\mathbb{F}G)^2 \to \mathbb{F}G</M> which maps both generators
      of <M>(\mathbb{F}G)^2</M> to the generator of &FG;
<!--
gap> G := SmallGroup(8, 4);;
gap> im := [1,0,0,0,0,0,0,0]*One(GF(2));
gap> phi := FpGModuleHomomorphismGF(
             FpGModuleGF(G, 2),
             FpGModuleGF(G, 1),
             [im, im]);
-->
<Example><![CDATA[
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>
]]></Example>
    </Subsection>
  </Section>

  <Section>
    <Heading>Data access functions</Heading>
    <!-- GAPDocSourceSuffix="_DTmanFpGModuleHom_Dat" -->

    <Subsection Label="FPGModuleHomExample1">
      <Heading>Example: Accessing data about a <K>FpGModuleHomomorphismGF</K></Heading>

      A free &FG; resolution is a chain complex of &FG;-modules and 
      homomorphisms, and the homomorphisms in a <K>HAPResolution</K> 
      (see Chapter <Ref Chap="Resolution"/>) can be extracted as a
      <K>FpGModuleHomomorphismGF</K> using the function 
      <Ref Oper="BoundaryFpGModuleHomomorphismGF"/>. We construct a resolution
      <C>R</C> and then examine the third resolution in the chain complex, which
      is a &FG;-module homomorphism 
      <M>d_3 : (\mathbb{F}G)^7 \to (\mathbb{F}G)^5</M>.
<!--
gap> R := ResolutionPrimePowerGroupRadical(SmallGroup(64, 141), 3);;
gap> d3 := BoundaryFpGModuleHomomorphismGF(R, 3);;
gap> SourceModule(d3);
gap> TargetModule(d3);
gap> ModuleHomomorphismGeneratorMatrix(d3);
gap> DisplayBlocks(d3);
-->
<Example><![CDATA[
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:
[*.*.*]
[*****]
[.**..]
[.**..]
[..**.]
[...**]
[...*.]

]]></Example>
      <P/>
      Note that the module homomorphism generating vectors in a resolution
      calculated using &HAPprime; are in block-echelon form (see Section 
      <Ref Sect="FpGModuleGFalgo"/>). This makes it efficient
      to compute the kernel of this homomorphism using 
      <Ref Oper="KernelOfModuleHomomorphismSplit"/>, as described in 
      Section <Ref Sect="FpGModuleHomGFkernel"/>, since there is only a 
      small intersection between the images generated by the top and
      bottom halves of the generating vectors.
    </Subsection>
  </Section>

  <Section>
    <Heading>Image and kernel functions</Heading>
    <!-- GAPDocSourceSuffix="_DTmanFpGModuleHom_Ima" -->

    <Subsection Label="FPGModuleHomExample2">
      <Heading>Example: Kernel and Image of a <K>FpGModuleHomomorphismGF</K></Heading>
      
      A free &FG;-resolution of a module is an exact sequence of module 
      homomorphisms. In this example we use the functions 
      <Ref Oper="ImageOfModuleHomomorphism" Label="image of homomorphism"/> and 
      <Ref Oper="KernelOfModuleHomomorphism"/> 
      to check that one of the sequences
      in a resolution is exact, i.e. that in the sequence
      <Alt Only="LaTeX">
        <Display>
          M_3 \to M_2 \to M_1
        </Display>
      </Alt>
      <Alt Not="LaTeX">
        <Display>
          M_3 -> M_2 -> M_1
        </Display>
      </Alt>
      the image of the first homomorphism <M>d_3: M_3 \to M_2</M> is the
      kernel of the second homomorphism <M>d_2: M_2 \to M_1</M>
      <P/>
      We also demonstrate that we can find the image and preimage of module 
      elements under our module homomorphisms. We take an element <C>e</C> of 
      <M>M_2</M>, in this case by taking the first generating element of the 
      kernel of <M>d_2</M>, and map it up to <M>M_3</M> and back.
      <P/>
      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);
gap> K := KernelOfModuleHomomorphism(d2);
gap> I = K;
gap> #
gap> e := ModuleGenerators(K)[1];;
gap> PreImageRepresentativeOfModuleHomomorphism(d3, e);
gap> f := PreImageRepresentativeOfModuleHomomorphism(d3, e);
gap> ImageOfModuleHomomorphism(d3, f);
gap> last = e;
gap> #
gap> L := KernelOfModuleHomomorphismSplit(d2);
gap> K = L;
gap> M := KernelOfModuleHomomorphismGF(d2);
gap> K = M;
-->
<Example><![CDATA[
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
]]></Example>
    </Subsection>
  </Section>

</Chapter>