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