Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/Sources/formale Sprachen/GAP/pkg/hap/tutorial/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 19.6.2025 mit Größe 25 kB

Quelle chap10_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/hap/tutorial/chap10_mj.html

<?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>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (HAP commands) - Chapter 10: Chain Complexes</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" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap10" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap9_mj.html">[Previous Chapter]</a> <a href="chap11_mj.html">[Next Chapter]</a> </div>

<a href="chap10.html">[MathJax off]</a>
<a id="X7A06103979B92808" name="X7A06103979B92808"></a>
<div class="ChapSects"><a href="chap10_mj.html#X7A06103979B92808">10 Chain Complexes</a>
<div class="ContSect"> <a href="chap10_mj.html#X782DE78884DD6992">10.1 Chain complex of a simplicial complex and simplicial pair</a>

</div>
<div class="ContSect"> <a href="chap10_mj.html#X79E7A13E7DE9C412">10.2 Chain complex of a cubical complex and cubical pair</a>

</div>
<div class="ContSect"> <a href="chap10_mj.html#X86C38E87817F2EAD">10.3 Chain complex of a regular CW-complex</a>

</div>
<div class="ContSect"> <a href="chap10_mj.html#X7F9662EF83A1FA76">10.4 Chain Maps of simplicial and regular CW maps</a>

</div>
<div class="ContSect"> <a href="chap10_mj.html#X8127E17383F45359">10.5 Constructions for chain complexes</a>

</div>
<div class="ContSect"> <a href="chap10_mj.html#X7AAAB26682CD8AC4">10.6 Filtered chain complexes</a>

</div>
<div class="ContSect"> <a href="chap10_mj.html#X856F202D823280F8">10.7 Sparse chain complexes</a>

</div>
</div>

<h3>10 Chain Complexes</h3>

HAP uses implementations of chain complexes of free \(\mathbb K\)-modules for each of the rings \(\mathbb K = \mathbb Z\), \(\mathbb K = \mathbb Q\), \(\mathbb K = \mathbb F_p\) with \(p\) a prime number, \(\mathbb K = \mathbb ZG\), \(\mathbb K = \mathbb F_pG\) with \(G\) a group. The implemented chain complexes have the form

\( C_n \stackrel{d_n}{\longrightarrow } C_{n-1} \stackrel{d_{n-1}}{\longrightarrow } \cdots \stackrel{d_2}{\longrightarrow } C_1 \stackrel{d_1}{\longrightarrow } C_0 \stackrel{d_0}{\longrightarrow } 0\ .\)

Such a complex is said to have length \(n\) and the rank of the free \(\mathbb K\)-module \(C_k\) is referred to as the dimenion of the complex in degree \(k\).

For the case \(\mathbb K = \mathbb ZG\) (resp. \(\mathbb K = \mathbb F_pG\)) the main focus is on free chain complexes that are exact at each degree \(k\), i.e. \({\rm im}(d_{k+1})={\rm ker}(d_k)\), for \(0 < k < n\) and with \(C_0/{\rm im}(d_1) \cong \mathbb Z\) (resp. \(C_0/{\rm im}(d_1) \cong \mathbb F_p\)). We refer to such a chain complex as a resolution of length \(n\) even though \(d_n\) will typically not be injective. More correct terminology would refer to such a chain complex as the first \(n\) degrees of a free resolution.

The following sections illustrate some constructions of chain complexes. Constructions for resolutions are described in the next chapter <a href="chap11_mj.html#X7C0B125E7D5415B4">11</a>.

<a id="X782DE78884DD6992" name="X782DE78884DD6992"></a>

<h4>10.1 Chain complex of a simplicial complex and simplicial pair</h4>

The following example constructs the Quillen simplicial complex \(Q={\mathcal A}_p(G)\) for \(p=2\) and \(G=A_8\); this is the order complex of the poset of non-trivial elementary \(2\)-subgroups of \(G\). The chain complex \(C_\ast = C_\ast(Q)\) is then computed and seen to have the same number of free generators as \(Q\) has simplices. (To ensure indexing of subcomplexes is consistent with that of the large complex it is best to work with vertices represented as integers.)

<div class="example"><pre>
gap> Q:=QuillenComplex(AlternatingGroup(8),2);
Simplicial complex of dimension 3.

gap> C:=ChainComplex(Q);
Chain complex of length 3 in characteristic 0 .

gap> Size(Q);
55015
gap> Size(C);
55015

</pre></div>

Next the simplicial complex \(Q\) is converted to one whose vertices are represented by integers and a contactible subcomplex \(L < Q\) is computed. The chain complex \(D_\ast=C_\ast(Q,L)\) of the simplicial pair \((Q,L)\) is constructed and seen to have the correct size.

<div class="example"><pre>
gap> Q:=IntegerSimplicialComplex(Q);
Simplicial complex of dimension 3.

gap> L:=ContractibleSubcomplex(Q);
Simplicial complex of dimension 3.

gap> D:=ChainComplexOfPair(Q,L);
Chain complex of length 3 in characteristic 0 .

gap> Size(D)=Size(Q)-Size(L);
true
gap> Size(D);
670
gap>

</pre></div>

The next commands produce a smalled chain complex \(B_\ast\) chain homotopy equivalent to \(D_\ast\) and compute the homology \(H_k(Q,\mathbb Z) \cong H_k(B_\ast)\) for \(k=1,2,3\).

<div class="example"><pre>
gap> B:=ContractedComplex(D);
Chain complex of length 3 in characteristic 0 .

gap> Size(B);
64
gap> Homology(B,1);
[ ]
gap> Homology(B,2);
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
gap> Homology(B,3);
[ ]

</pre></div>

<a id="X79E7A13E7DE9C412" name="X79E7A13E7DE9C412"></a>

<h4>10.2 Chain complex of a cubical complex and cubical pair</h4>

The following example reads in the digital image

<img src="images/bw_image.bmp" align="center" height="300" alt="a digital image"/>

as a \(2\)-dimensional pure cubical complex \(M\) and constructs the chain complex \(C_\ast=C_\ast(M)\).

<div class="example"><pre>
gap> K:=ReadImageAsPureCubicalComplex(file,400);
Pure cubical complex of dimension 2.

gap> C:=ChainComplex(K);
Chain complex of length 2 in characteristic 0 .

gap> Size(C); 
173243

</pre></div>

Next an acyclic pure cubical subcomplex \(L < M\) is computed and the chain complex \(D_\ast=C_\ast(M,L)\) of the pair is constructed.

<div class="example"><pre>
gap> L:=AcyclicSubcomplexOfPureCubicalComplex(K);
Pure cubical complex of dimension 2.

gap> D:=ChainComplexOfPair(K,L);
Chain complex of length 2 in characteristic 0 .

gap> Size(D);
618

</pre></div>

Finally the chain complex \(D_\ast\) is simplified to a homotopy equivalent chain complex \(B_\ast\) and the homology \(H_1(M,\mathbb Z) \cong H_1(B_\ast)\) is computed.

<div class="example"><pre>
gap> B:=ContractedComplex(D);
Chain complex of length 2 in characteristic 0 .

gap> Size(B);
20
gap> Homology(B,1);
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]

</pre></div>

<a id="X86C38E87817F2EAD" name="X86C38E87817F2EAD"></a>

<h4>10.3 Chain complex of a regular CW-complex</h4>

The next example constructs a \(15\)-dimensional regular CW-complex \(Y\) that is homotopy equivalent to the \(2\)-dimensional torus.

<div class="example"><pre>
gap> Circle:=PureCubicalComplex([[1,1,1,1,1],[1,1,0,1,1],[1,1,1,1,1]]);
Pure cubical complex of dimension 2.

gap> Torus:=DirectProductOfPureCubicalComplexes(Circle,Circle);
Pure cubical complex of dimension 4.

gap> CTorus:=CechComplexOfPureCubicalComplex(Torus);
Simplicial complex of dimension 15.

gap> Y:=RegularCWComplex(CTorus);
Regular CW-complex of dimension 15

</pre></div>

Next the cellular chain complex \(C_\ast=C_\ast(Y)\) is constructed. Also, a minimally generated chain complex \(D_\ast=C_\ast(Y')\) of a non-regular CW-complex \(Y'\simeq Y\) is constructed.

<div class="example"><pre>
gap> C:=ChainComplexOfRegularCWComplex(Y);
Chain complex of length 15 in characteristic 0 .

gap> Size(C);
1172776

gap> D:=ChainComplex(Y);
Chain complex of length 15 in characteristic 0 .

gap> Size(D);
4

</pre></div>

<a id="X7F9662EF83A1FA76" name="X7F9662EF83A1FA76"></a>

<h4>10.4 Chain Maps of simplicial and regular CW maps</h4>

The next example realizes the complement of the first prime knot on \(11\) crossings as a pure permutahedral complex. The complement is converted to a regular CW-complex \(Y\) and the boundary inclusion \(f\colon \partial Y \hookrightarrow Y\) is constructed as a map of regular CW-complexes. Then the induced chain map \(F\colon C_\ast(\partial Y) \hookrightarrow C_\ast(Y)\) is constructed. Finally the homology homomorphism \(H_1(F)\colon H_1(C_\ast(\partial Y)) \rightarrow H_1(C_\ast(Y))\) is computed.

<div class="example"><pre>
gap> K:=PurePermutahedralKnot(11,1);;
gap> M:=PureComplexComplement(K);
Pure permutahedral complex of dimension 3.

gap> Y:=RegularCWComplex(M);
Regular CW-complex of dimension 3

gap> f:=BoundaryMap(Y);
Map of regular CW-complexes

gap> F:=ChainMap(f);
Chain Map between complexes of length 2 .

gap> H:=Homology(F,1);
[ g1, g2 ] -> [ g1^-1, g1^-1 ]

gap> Kernel(H);
Pcp-group with orders [ 0 ]

</pre></div>

The command <code class="code">ChainMap(f)</code> can be used to construct the chain map \(C_\ast(K) \rightarrow C_\ast(K')\) induced by a map \(f\colon K\rightarrow K'\) of simplicial complexes.

<a id="X8127E17383F45359" name="X8127E17383F45359"></a>

<h4>10.5 Constructions for chain complexes</h4>

It is straightforward to implement basic constructions on chain complexes. A few constructions are illustrated in the following example.

<div class="example"><pre>
gap> res:=ResolutionFiniteGroup(SymmetricGroup(5),5);;
gap> C:=TensorWithIntegers(res);
Chain complex of length 5 in characteristic 0 .

gap> D:=ContractedComplex(C);#A chain homotopic complex
Chain complex of length 5 in characteristic 0 .
gap> List([0..5],C!.dimension);
[ 1, 4, 10, 20, 35, 56 ]
gap> List([0..5],D!.dimension);
[ 1, 1, 2, 4, 6, 38 ]

gap> CxC:=TensorProduct(C,C);
Chain complex of length 10 in characteristic 0 .

gap> SC:=SuspendedChainComplex(C);
Chain complex of length 6 in characteristic 0 .

gap> RC:=ReducedSuspendedChainComplex(C);
Chain complex of length 6 in characteristic 0 .

gap> PC:=PathObjectForChainComplex(C);
Chain complex of length 5 in characteristic 0 .

gap> dualC:=HomToIntegers(C);
Cochain complex of length 5 in characteristic 0 .

gap> Cxp:=TensorWithIntegersModP(C,5);
Chain complex of length 5 in characteristic 5 .

gap> CxQ:=TensorWithRationals(C); #The quirky -1/2 denotes rationals
Chain complex of length 5 in characteristic -1/2 .

</pre></div>

<a id="X7AAAB26682CD8AC4" name="X7AAAB26682CD8AC4"></a>

<h4>10.6 Filtered chain complexes</h4>

A sequence of inclusions of chain complexes \(C_{0,\ast} \le C_{1,\ast} \le \cdots \le C_{T-1,\ast} \le C_{T,\ast}\) in which the preferred basis of \(C_{k-1,\ell}\) is the beginning of the preferred basis of \(C_{k,\ell}\) is referred to as a filtered chain complex. Filtered chain complexes give rise to spectral sequences such as the equivariant spectral sequence of a \(G-CW\)-complex with subgroup \(H < G\). A particular case is the Lyndon-Hochschild-Serre spectral sequence for the homology of a group extension \(N \rightarrowtail G \twoheadrightarrow Q\) with \(E^2_{p,q}=H_p(Q,H_q(N, \mathbb Z))\).

The following commands construct the filtered chain complex underlying the Lyndon-Hochschild-Serre spectral sequence for the dihedral group \(G=D_{32}\) of order 64 and its centre \(N=Z(G)\).

<div class="example"><pre>
gap> G:=DihedralGroup(64);;
gap> N:=Center(G);;
gap> R:=ResolutionNormalSeries([G,N],3);;
gap> C:=FilteredTensorWithIntegersModP(R,2);
Chain complex of length 3 in characteristic 2 .

</pre></div>

The differentials \(d^r_{p,q}\) in a given page \(E^r\) of the spectral sequence arise from the induced homology homomorphisms \(\iota^{s,t}_\ell\colon H_{\ell}(C_{s,\ast}) \rightarrow H_{\ell}(C_{t,\ast})\) for \(s\le t\). Textbooks traditionally picture the differential in \(E^r\) as an array of sloping arrows with non-zero groups \(E^r_{p,q}\neq 0\) represented by dots. An alternative representation of this information is as a barcode (of the sort used in Topological Data Analysis). The homomorphisms \(\iota^{\ast,\ast}_2\) in the example, with coefficients converted to mod \(2\), are pictured by the bar code

<img src="images/lhsbc.png" align="center" height="150" alt="a bar code for the LHS spectral sequence"/>

which was produced by the following commands.

<div class="example"><pre>
gap> p:=2;;k:=2;;
gap> P:=PersistentHomologyOfFilteredChainComplex(C,k,p);;
gap> BarCodeDisplay(P);

</pre></div>

<a id="X856F202D823280F8" name="X856F202D823280F8"></a>

<h4>10.7 Sparse chain complexes</h4>

Boundary homomorphisms in all of the above examples of chain complexes are represented by matrices. In cases where the matrices are large and have many zero entries it is better to use sparse matrices.

The following commands demonstrate the conversion of the matrix

\(A=\left(\begin{array}{ccc} 0 &2 &0\\ -3 &0 & 0\\ 0 & 0 &4 \end{array}\right)\)

to sparse form, and vice-versa.

<div class="example"><pre>
gap> A:=[[0,2,0],[-3,0,0],[0,0,4]];;
gap> S:=SparseMat(A);
Sparse matrix with 3 rows and 3 columns in characteristic 0

gap> NamesOfComponents(S);
[ "mat", "characteristic", "rows", "cols" ]
gap> S!.mat;
[ [ [ 2, 2 ] ], [ [ 1, -3 ] ], [ [ 3, 4 ] ] ]

gap> B:=SparseMattoMat(S);
[ [ 0, 2, 0 ], [ -3, 0, 0 ], [ 0, 0, 4 ] ]

</pre></div>

To illustrate the use of sparse chain complexes we consider the data points represented in the following digital image.

<img src="images/data500.png" align="center" height="200" alt="data points samples from an annulus"/>

The following commands read in this image as a \(2\)-dimensional pure cubical complex and store the Euclidean coordinates of the black pixels in a list. Then 200 points are selected at random from this list and used to construct a \(200\times 200\) symmetric matrix \(S\) whose entries are the Euclidean distance between the sample data points.

<div class="example"><pre>
gap> file:=HapFile("data500.png");;
gap> M:=ReadImageAsPureCubicalComplex(file,400);;
gap> A:=M!.binaryArray;;
gap> data:=[];;
gap> for i in [1..Length(A)] do
> for j in [1..Length(A[1])] do
> if A[i][j]=1 then Add(data,[i,j]); fi;
> od;
> od;
gap> sample:=List([1..200],i->Random(data));;
gap> S:=VectorsToSymmetricMatrix(sample,EuclideanApproximatedMetric);;

</pre></div>

The symmetric distance matrix \(S\) is next converted to a filtered chain complex arising from a filtered simplicial complex (using the standard persistent homology pipeline).

<div class="example"><pre>
gap> G:=SymmetricMatrixToFilteredGraph(S,10,100);; 
#Filtration length T=10, distances greater than 100 discarded.
gap> N:=SimplicialNerveOfFilteredGraph(G,2);;
gap> C:=SparseFilteredChainComplexOfFilteredSimplicialComplex(N);;
Filtered sparse chain complex of length 2 in characteristic 0 .

</pre></div>

Next, the induced homology homomorphisms in degrees 1 and 2, with rational coefficients, are computed and displayed a barcodes.

<div class="example"><pre>
gap> P0:=PersistentHomologyOfFilteredSparseChainComplex(C,0);;
gap> P1:=PersistentHomologyOfFilteredSparseChainComplex(C,1);;
gap> BarCodeCompactDisplay(P0);

</pre></div>

<img src="images/barcode0example.png" align="center" height="130" alt="Degree 0 persistent homology barcode"/>

<div class="example"><pre>
gap> BarCodeCompactDisplay(P1);

</pre></div>

<img src="images/barcode1example.png" align="center" height="130" alt="Degree 1 persistent homology barcode"/>

The barcodes are consistent with the data points having been sampled from a space with the homotopy type of an annulus.

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap9_mj.html">[Previous Chapter]</a> <a href="chap11_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chap12_mj.html">12</a> <a href="chap13_mj.html">13</a> <a href="chap14_mj.html">14</a> <a href="chap15_mj.html">15</a> <a href="chap16_mj.html">16</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality99%