<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (HAPprime Datatypes) - Chapter 6: FG-module homomorphisms</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<p><a id="X82F28552819A6542" name="X82F28552819A6542"></a></p>
<div class="ChapSects"><a href="chap6.html#X82F28552819A6542">6 <span class="Heading">FG-module homomorphisms</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X85481E577D3BAB8E">6.1 <span class="Heading">The <code class="keyw">FpGModuleHomomorphismGF</code> datatype</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X83FF0EBD81A405A9">6.2 <span class="Heading">Calculating the kernel of a FG-module homorphism by splitting
into two homomorphisms</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X8356C3B680B7110E">6.3 <span class="Heading">Calculating the kernel of a FG-module homorphism by column
reduction and partitioning</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X83D8009086035BCB">6.4 <span class="Heading">Construction functions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8640D133855BB892">6.4-1 <span class="Heading">FpGModuleHomomorphismGF construction functions</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EA7C568836E9730">6.4-2 <span class="Heading">Example: Constructing a <code class="keyw">FpGModuleHomomorphismGF</code></span></a>
</span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7DE3278D7E5DEE03">6.5 <span class="Heading">Data access functions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X835A27F3877D7B04">6.5-1 SourceModule</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X810013F0852729DD">6.5-2 TargetModule</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X81173EB682B5C903">6.5-3 ModuleHomomorphismGeneratorMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EF5C42A79568EAE">6.5-4 DisplayBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7D200588818203D6">6.5-5 DisplayModuleHomomorphismGeneratorMatrix</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X831A8A6485A484D7">6.5-6 DisplayModuleHomomorphismGeneratorMatrixBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7C5F52FE80BB871A">6.5-7 <span class="Heading">Example: Accessing data about a <code class="keyw">FpGModuleHomomorphismGF</code></span></a>
</span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X79444C767921055C">6.6 <span class="Heading">Image and kernel functions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8038F50582425ECA">6.6-1 <span class="Heading">ImageOfModuleHomomorphism</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X850FD5AE80BF6F11">6.6-2 <span class="Heading">PreImageRepresentativeOfModuleHomomorphism</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X86C7D57A825235EE">6.6-3 KernelOfModuleHomomorphism</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X795D4069832F15F8">6.6-4 <span class="Heading">Example: Kernel and Image of a <code class="keyw">FpGModuleHomomorphismGF</code></span></a>
</span>
</div>
</div>
<h3>6 <span class="Heading">FG-module homomorphisms</span></h3>
<p><a id="X85481E577D3BAB8E" name="X85481E577D3BAB8E"></a></p>
<h4>6.1 <span class="Heading">The <code class="keyw">FpGModuleHomomorphismGF</code> datatype</span></h4>
<p>Linear homomorphisms between free FG-modules (as <code class="keyw">FpGModuleGF</code> objects - see Chapter <a href="chap5.html#X820435E87D83DF34"><b>5</b></a>) are represented in <strong class="pkg">HAPprime</strong> using the <code class="keyw">FpGModuleHomomorphismGF</code> 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.</p>
<p>Three items need to be passed to the constructor function <code class="func">FpGModuleHomomorphismGF</code> (<a href="chap6.html#X8640D133855BB892"><b>6.4-1</b></a>):</p>
<ul>
<li><p><code class="code">source</code> the source <code class="keyw">FpGModuleGF</code> module for the homomorphism</p>
</li>
<li><p><code class="code">target</code> the target <code class="keyw">FpGModuleGF</code> module for the homomorphism</p>
</li>
<li><p><code class="code">gens</code> a list of vectors that are the images (in <code class="code">target</code>) under the homomorphisms of each of the generators stored in <code class="code">source</code></p>
</li>
</ul>
<p><a id="X83FF0EBD81A405A9" name="X83FF0EBD81A405A9"></a></p>
<h4>6.2 <span class="Heading">Calculating the kernel of a FG-module homorphism by splitting
into two homomorphisms</span></h4>
<p><strong class="pkg">HAPprime</strong> 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 <code class="keyw">FpGModuleGF</code> datatype (see Chapter <a href="chap5.html#X820435E87D83DF34"><b>5</b></a>). 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 <code class="keyw">FpGModuleGF</code>s, the block structure of the generating vectors (see Section <a href="chap5.html#X79DDD8C37A0B8425"><b>5.2-1</b></a>) allows this null-space to be calculated without necessarily expanding the whole matrix.</p>
<p>This basic algorithm is implemented in the <strong class="pkg">HAPprime</strong> function <code class="func">KernelOfModuleHomomorphismSplit</code> (<a href="chap6.html#X86C7D57A825235EE"><b>6.6-3</b></a>). 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</p>
<p class="pcenter">
ker(H) = intersection of preim_U(I) with [-preim_V(I)]
</p>
<p>where</p>
<ul>
<li><p>I = im(U) cap im(V) is the intersection of the images of the two homomorphisms U and V</p>
</li>
<li><p>preim_U(I) the set of all preimages of I under U</p>
</li>
<li><p>preim_V(I) the set of all preimages of I under V</p>
</li>
</ul>
<p>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 <a href="chap5.html#X86F4852785A509BF"><b>5.2-4</b></a>), 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.</p>
<p>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 <code class="func">KernelOfModuleHomomorphismIndependentSplit</code> (<a href="chap6.html#X86C7D57A825235EE"><b>6.6-3</b></a>).</p>
<p><a id="X8356C3B680B7110E" name="X8356C3B680B7110E"></a></p>
<h4>6.3 <span class="Heading">Calculating the kernel of a FG-module homorphism by column
reduction and partitioning</span></h4>
<p>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.</p>
<p>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:</p>
<p class="pcenter">
[ B 0 ]
[ C D ]
</p>
<p>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.</p>
<p>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</p>
<p class="pcenter">
[ B 0 0 ]
[ C D E ]
</p>
<p>The kernel of this matrix can be shown to be</p>
<p class="pcenter">
[ ker(B) 0 ]
[ L ker(DE) ]
</p>
<p>where</p>
<p class="pcenter">
L = preim_B((\ker (DE)) C)
</p>
<p>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.</p>
<p>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 <code class="func">KernelOfModuleHomomorphismSplit</code> (<a href="chap6.html#X86C7D57A825235EE"><b>6.6-3</b></a>) 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.</p>
<p><a id="X83D8009086035BCB" name="X83D8009086035BCB"></a></p>
<h4>6.4 <span class="Heading">Construction functions</span></h4>
<p><a id="X8640D133855BB892" name="X8640D133855BB892"></a></p>
<h5>6.4-1 <span class="Heading">FpGModuleHomomorphismGF construction functions</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FpGModuleHomomorphismGF</code>( <var class="Arg">S, T, gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FpGModuleHomomorphismGFNC</code>( <var class="Arg">S, T, gens</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">FpGModuleHomomorphismGF</code></p>
<p>Creates and returns an <code class="keyw">FpGModuleHomomorphismGF</code> module homomorphism object. This represents the homomorphism from the module <var class="Arg">S</var> to the module <var class="Arg">T</var> with a list of vectors <var class="Arg">gens</var> whose rows are the images in <var class="Arg">T</var> of the generators of <var class="Arg">S</var>. The modules must (currently) be over the same group.</p>
<p>The standard constructor checks that the homomorphism is compatible with the modules, i.e. that the vectors in <var class="Arg">gens</var> have the correct dimension and that they lie within the target module <var class="Arg">T</var>. It also checks whether the generators of <var class="Arg">S</var> are minimal. If they are not, then the homomorphism is created with a copy of <var class="Arg">S</var> that has minimal generators (using <code class="func">MinimalGeneratorsModuleRadical</code> (<a href="chap5.html#X81C340AD7EE8FA63"><b>5.5-9</b></a>)), and <var class="Arg">gens</var> is also copied and converted to agree with the new form of <var class="Arg">S</var>. If you wish to skip these checks then use the <code class="code">NC</code> version of this function.</p>
<p>IMPORTANT: The generators of the module <var class="Arg">S</var> and the generator matrix <var class="Arg">gens</var> 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.</p>
<p><a id="X7EA7C568836E9730" name="X7EA7C568836E9730"></a></p>
<h5>6.4-2 <span class="Heading">Example: Constructing a <code class="keyw">FpGModuleHomomorphismGF</code></span></h5>
<p>In this example we construct the module homomorphism phi: (FG)^2 -> FG which maps both generators of (FG)^2 to the generator of FG</p>
<table class="example">
<tr><td><pre>
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>
</pre></td></tr></table>
<p><a id="X7DE3278D7E5DEE03" name="X7DE3278D7E5DEE03"></a></p>
<h4>6.5 <span class="Heading">Data access functions</span></h4>
<p><a id="X835A27F3877D7B04" name="X835A27F3877D7B04"></a></p>
<h5>6.5-1 SourceModule</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SourceModule</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">FpGModuleGF</code></p>
<p>Returns the source module for the homomorphism <var class="Arg">phi</var>, as an <code class="keyw">FpGModuleGF</code>.</p>
<p><a id="X810013F0852729DD" name="X810013F0852729DD"></a></p>
<h5>6.5-2 TargetModule</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TargetModule</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>FpGModuleGF</p>
<p>Returns the targetmodule for the homomorphism <var class="Arg">phi</var>, as an <code class="keyw">FpGModuleGF</code>.</p>
<p><a id="X81173EB682B5C903" name="X81173EB682B5C903"></a></p>
<h5>6.5-3 ModuleHomomorphismGeneratorMatrix</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ModuleHomomorphismGeneratorMatrix</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>List of vectors</p>
<p>Returns the generating vectors <code class="code">gens</code> of the representation of the homomorphism <var class="Arg">phi</var>. These vectors are the images in the target module of the generators of the source module.</p>
<p><a id="X7EF5C42A79568EAE" name="X7EF5C42A79568EAE"></a></p>
<h5>6.5-4 DisplayBlocks</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DisplayBlocks</code>( <var class="Arg">phi</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>nothing</p>
<p>Prints a detailed description of the module in human-readable form, with the module generators and generator matrix shown in block form. The standard <strong class="pkg">GAP</strong> methods <code class="func">View</code> (<a href="../../../../../gap4r4/doc/htm/ref/CHAP006.htm#SECT003"><b>Reference: View</b></a>), <code class="func">Print</code> (<a href="../../../../../gap4r4/doc/htm/ref/CHAP006.htm#SECT003"><b>Reference: Print</b></a>) and <code class="func">Display</code> (<a href="../../../../../gap4r4/doc/htm/ref/CHAP006.htm#SECT003"><b>Reference: Display</b></a>) are also available.)</p>
<p><a id="X7D200588818203D6" name="X7D200588818203D6"></a></p>
<h5>6.5-5 DisplayModuleHomomorphismGeneratorMatrix</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DisplayModuleHomomorphismGeneratorMatrix</code>( <var class="Arg">phi</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>nothing</p>
<p>Prints a detailed description of the module homomorphism generating vectors <code class="code">gens</code> in human-readable form. This is the display method used in the <code class="func">Display</code> (<a href="../../../../../gap4r4/doc/htm/ref/CHAP006.htm#SECT003"><b>Reference: Display</b></a>) method for this datatype.</p>
<p><a id="X831A8A6485A484D7" name="X831A8A6485A484D7"></a></p>
<h5>6.5-6 DisplayModuleHomomorphismGeneratorMatrixBlocks</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DisplayModuleHomomorphismGeneratorMatrixBlocks</code>( <var class="Arg">phi</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>nothing</p>
<p>Prints a detailed description of the module homomorphism generating vectors <code class="code">gens</code> in human-readable form. This is the function used in the <code class="func">DisplayBlocks</code> (<a href="chap6.html#X7EF5C42A79568EAE"><b>6.5-4</b></a>) method.</p>
<p><a id="X7C5F52FE80BB871A" name="X7C5F52FE80BB871A"></a></p>
<h5>6.5-7 <span class="Heading">Example: Accessing data about a <code class="keyw">FpGModuleHomomorphismGF</code></span></h5>
<p>A free FG resolution is a chain complex of FG-modules and homomorphisms, and the homomorphisms in a <code class="keyw">HAPResolution</code> (see Chapter <a href="chap2.html#X7C0B125E7D5415B4"><b>2</b></a>) can be extracted as a <code class="keyw">FpGModuleHomomorphismGF</code> using the function <code class="func">BoundaryFpGModuleHomomorphismGF</code> (<a href="chap2.html#X803528CD872A1F4C"><b>2.4-6</b></a>). We construct a resolution <code class="code">R</code> and then examine the third resolution in the chain complex, which is a FG-module homomorphism d_3 : (FG)^7 -> (FG)^5.</p>
<table class="example">
<tr><td><pre>
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:
[*.*.*]
[*****]
[.**..]
[.**..]
[..**.]
[...**]
[...*.]
</pre></td></tr></table>
<p>Note that the module homomorphism generating vectors in a resolution calculated using <strong class="pkg">HAPprime</strong> are in block-echelon form (see Section <a href="chap5.html#X79DF42E686679AFE"><b>5.2</b></a>). This makes it efficient to compute the kernel of this homomorphism using <code class="func">KernelOfModuleHomomorphismSplit</code> (<a href="chap6.html#X86C7D57A825235EE"><b>6.6-3</b></a>), as described in Section <a href="chap6.html#X83FF0EBD81A405A9"><b>6.2</b></a>, since there is only a small intersection between the images generated by the top and bottom halves of the generating vectors.</p>
<p><a id="X79444C767921055C" name="X79444C767921055C"></a></p>
<h4>6.6 <span class="Heading">Image and kernel functions</span></h4>
<p><a id="X8038F50582425ECA" name="X8038F50582425ECA"></a></p>
<h5>6.6-1 <span class="Heading">ImageOfModuleHomomorphism</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageOfModuleHomomorphism</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageOfModuleHomomorphism</code>( <var class="Arg">phi, M</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageOfModuleHomomorphism</code>( <var class="Arg">phi, elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageOfModuleHomomorphism</code>( <var class="Arg">phi, coll</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageOfModuleHomomorphismDestructive</code>( <var class="Arg">phi, elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ImageOfModuleHomomorphismDestructive</code>( <var class="Arg">phi, coll</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">FpGModuleGF</code>, vector or list of vectors depending on argument</p>
<p>For a module homomorphism <var class="Arg">phi</var>, 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 <code class="code">FpGModuleGF</code> <var class="Arg">M</var>, a module element <var class="Arg">elm</var> (given as a vector), or a collection of module elements <var class="Arg">coll</var> through the homomorphism. This uses standard linear algebra to find the image of elements from the source module.</p>
<p>The <code class="code">Destructive</code> 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 <code class="code">MinimalGeneratorsModule</code> functions (<a href="chap5.html#X81C340AD7EE8FA63"><b>5.5-9</b></a>) should be used on the result if a minimal set of generators is needed.</p>
<p><a id="X850FD5AE80BF6F11" name="X850FD5AE80BF6F11"></a></p>
<h5>6.6-2 <span class="Heading">PreImageRepresentativeOfModuleHomomorphism</span></h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PreImageRepresentativeOfModuleHomomorphism</code>( <var class="Arg">phi, elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PreImageRepresentativeOfModuleHomomorphism</code>( <var class="Arg">phi, coll</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PreImageRepresentativeOfModuleHomomorphism</code>( <var class="Arg">phi, M</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PreImageRepresentativeOfModuleHomomorphismGF</code>( <var class="Arg">phi, elm</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PreImageRepresentativeOfModuleHomomorphismGF</code>( <var class="Arg">phi, coll</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>For an element <var class="Arg">elm</var> in the image of <var class="Arg">phi</var>, this returns a representative of the set of preimages of <var class="Arg">elm</var> under <var class="Arg">phi</var>, otherwise it returns <code class="code">fail</code>. If a list of vectors <var class="Arg">coll</var> is provided then the function returns a list of preimage representatives, one for each element in the list (the returned list can contain <code class="code">fail</code> entries if there are vectors with no solution). For an <code class="keyw">FpGModuleGF</code> module <var class="Arg">M</var>, this returns a module whose image under <var class="Arg">phi</var> is <var class="Arg">M</var> (or <code class="code">fail</code>). The module returned will not necessarily have minimal generators, and one of the <code class="code">MinimalGeneratorsModule</code> functions (<a href="chap5.html#X81C340AD7EE8FA63"><b>5.5-9</b></a>) should be used on the result if a minimal set of generators is needed.</p>
<p>The standard functions use linear algebra, expanding the generator matrix into a full matrix and using <code class="func">SolutionMat</code> (<a href="../../../../../gap4r4/doc/htm/ref/CHAP024.htm#SECT006"><b>Reference: SolutionMat</b></a>) to calculate a preimage of <var class="Arg">elm</var>. In the case where a list of vectors is provided, the matrix decomposition is only performed once, which can save significant time.</p>
<p>The <code class="code">GF</code> versions of the functions can give a large memory saving when the generators of the homomorphism <var class="Arg">phi</var> are in echelon form, and operate by doing back-substitution using the generator form of the matrices.</p>
<p><a id="X86C7D57A825235EE" name="X86C7D57A825235EE"></a></p>
<h5>6.6-3 KernelOfModuleHomomorphism</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KernelOfModuleHomomorphism</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KernelOfModuleHomomorphismSplit</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KernelOfModuleHomomorphismIndependentSplit</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KernelOfModuleHomomorphismGF</code>( <var class="Arg">phi</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">FpGModuleGF</code></p>
<p>Returns the kernel of the module homomorphism <var class="Arg">phi</var>, as an <code class="keyw">FpGModuleGF</code> module. There are three independent algorithms for calculating the kernel, represented by different versions of this function:</p>
<ul>
<li><p>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.</p>
</li>
<li><p>The <code class="code">Split</code> 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 <a href="chap6.html#X83FF0EBD81A405A9"><b>6.2</b></a>). If the generating vectors for <var class="Arg">phi</var> are in block echelon form (see Section <a href="chap5.html#X79DF42E686679AFE"><b>5.2</b></a>), then this approach provides a considerable memory saving over the standard approach.</p>
</li>
<li><p>The <code class="code">IndependentSplit</code> 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.</p>
</li>
<li><p>The <code class="code">GF</code> version performs column reduction and partitioning of the generator matrix to enable a recursive approach to computing the kernel (see Section <a href="chap6.html#X8356C3B680B7110E"><b>6.3</b></a>). The level of partitioning is governed by the option <code class="code">MaxFGExpansionSize</code>, which defaults to 10^9, allowing about 128Mb of memory to be used for standard linear algebra before partitioning starts. See <a href="../../../../../gap4r4/doc/htm/ref/CHAP008.htm"><b>Reference: Options Stack</b></a> for details of using options in <strong class="pkg">GAP</strong></p>
</li>
</ul>
<p>None of these basis versions of the functions guarantee to return a minimal set of generators, and one of the <code class="code">MinimalGeneratorsModule</code> functions (<a href="chap5.html#X81C340AD7EE8FA63"><b>5.5-9</b></a>) should be used on the result if a minimal set of generators is needed. All of the functions leave the input homomorphism <var class="Arg">phi</var> unchanged.</p>
<p><a id="X795D4069832F15F8" name="X795D4069832F15F8"></a></p>
<h5>6.6-4 <span class="Heading">Example: Kernel and Image of a <code class="keyw">FpGModuleHomomorphismGF</code></span></h5>
<p>A free FG-resolution of a module is an exact sequence of module homomorphisms. In this example we use the functions <code class="func">ImageOfModuleHomomorphism</code> (<a href="chap6.html#X8038F50582425ECA"><b>6.6-1</b></a>) and <code class="func">KernelOfModuleHomomorphism</code> (<a href="chap6.html#X86C7D57A825235EE"><b>6.6-3</b></a>) to check that one of the sequences in a resolution is exact, i.e. that in the sequence</p>
<p class="pcenter">
M_3 -> M_2 -> M_1
</p>
<p>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</p>
<p>We also demonstrate that we can find the image and preimage of module elements under our module homomorphisms. We take an element <code class="code">e</code> 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.</p>
<p>Finally, we compute the kernel using the other available methods, and check that the results are the same.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1463
