aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--buch/chapters/10-vektorenmatrizen/linear.tex9
-rw-r--r--buch/chapters/50-permutationen/determinante.tex102
-rw-r--r--buch/chapters/50-permutationen/matrizen.tex5
-rw-r--r--buch/chapters/60-gruppen/symmetrien.tex4
-rw-r--r--buch/chapters/70-graphen/wavelets.tex2
-rw-r--r--buch/chapters/90-crypto/Makefile.inc1
-rw-r--r--buch/chapters/90-crypto/arith.tex1
-rw-r--r--buch/chapters/90-crypto/ff.tex53
-rw-r--r--buch/chapters/90-crypto/rs.tex41
-rw-r--r--buch/chapters/95-homologie/Makefile.inc1
-rw-r--r--buch/chapters/95-homologie/chapter.tex2
-rw-r--r--buch/chapters/95-homologie/homologie.tex340
-rw-r--r--buch/chapters/95-homologie/komplex.tex104
-rw-r--r--buch/chapters/95-homologie/simplex.tex2
-rw-r--r--buch/chapters/references.bib7
15 files changed, 612 insertions, 62 deletions
diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex
index 10b5a7e..e368364 100644
--- a/buch/chapters/10-vektorenmatrizen/linear.tex
+++ b/buch/chapters/10-vektorenmatrizen/linear.tex
@@ -1088,6 +1088,15 @@ für die Inverse einer Matrix der Form
\eqref{buch:vektoren-und-matrizen:abeispiel:eqn1}.
\end{beispiel}
+\subsubsection{Produktregel für die Determinante}
+Aus der Charakterisierung der Determinanten kann man auch ableiten,
+dass die Produktregel
+\[
+\det (AB) = \det(A) \cdot \det(B)
+\]
+gilt.
+Daraus folgt auch, dass $\det(A^{-1})=\det(A)^{-1}$.
+
%
% Lineare Abbildungen
%
diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex
index c440caf..805235d 100644
--- a/buch/chapters/50-permutationen/determinante.tex
+++ b/buch/chapters/50-permutationen/determinante.tex
@@ -7,3 +7,105 @@
\section{Determinante
\label{buch:section:determinante}}
\rhead{Determinante}
+Das Signum einer Permutationsmatrizen lässt sich
+gemäss~\eqref{buch:permutationen:determinante}
+mit der Determinanten berechnen.
+Umgekehrt sollte es auch möglich sein, eine Formel
+für die Determinante zu finden.
+Die Basis dafür ist der
+Entwicklungssatz
+\begin{equation}
+\det(A)
+=
+\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij})
+\label{buch:permutationen:entwicklungssatz}
+\end{equation}
+von Laplace für die Determinante.
+In den Produkten $a_{ij}\cdot\det(A_{ij})$ enthält
+die Untermatrix $A_{ij}$ weder Elemente der Zeile $i$ noch der
+Zeile $j$.
+Die Summanden auf der rechten Seite von
+\eqref{buch:permutationen:entwicklungssatz}
+sind daher Produkte der Form
+\[
+a_{1i_1}
+a_{2i_2}
+a_{3i_3}
+\dots
+a_{ni_n},
+\]
+in denen nur Faktoren aus verschiedenen Spalten der Matrix $A$
+vorkommen.
+Das ist gleichbedeutend damit, dass unter den Spaltenindizes
+$i_1,i_2,i_3,\dots,i_n$ keine zwei gleich sind, dass also
+\[
+\sigma
+=
+\begin{pmatrix}
+1&2&3&\dots&n\\
+i_1&i_2&i_3&\dots&i_n
+\end{pmatrix}
+\]
+eine Permutation ist.
+
+Die Determinante muss sich daher als Summe über alle Permutationen
+in der Form
+\begin{equation}
+\det(A)
+=
+\sum_{\sigma\in S_n}
+c(\sigma)
+a_{1\sigma(1)}
+a_{2\sigma(2)}
+\dots
+a_{n\sigma(n)}
+\label{buch:permutationen:cformel}
+\end{equation}
+schreiben lassen, wobei die Koeffizienten $c(\sigma)$ noch zu bestimmen
+sind.
+Setzt man in
+\eqref{buch:permutationen:cformel}
+eine Permutationsmatrix $P_\tau$ ein, dann verschwinden alle
+Terme auf der rechten Seite ausser dem zur Permutation $\tau$,
+also
+\[
+\det(P_\tau)
+=
+\sum_{\sigma \in S_n}
+c(\sigma)
+(P_\tau)_{1\sigma(1)}
+(P_\tau)_{2\sigma(2)}
+\dots
+(P_\tau)_{n\sigma(n)}
+=
+c(\tau)
+1\cdot 1\cdot\dots\cdot 1
+=
+c(\tau).
+\]
+Der Koeffizientn $c(\tau)$ ist also genau das Vorzeichen
+der Permutation $\tau$.
+Damit erhalten wir den folgenden Satz:
+
+\begin{satz}
+Die Determinante einer $n\times n$-Matrix $A$ kann berechnet werden als
+\[
+\det(A)
+=
+\sum_{\sigma\in S_n}
+\operatorname{sgn}(\sigma)
+a_{1\sigma(1)}
+a_{2\sigma(2)}
+\dots
+a_{n\sigma(n)}
+=
+\sum_{\tau\in S_n}
+\operatorname{sgn}(\tau)
+a_{\tau(1)1}
+a_{\tau(2)2}
+\dots
+a_{\tau(n)n}.
+\]
+Insbesondere folgt auch $\det(A)=\det(A^t)$.
+\end{satz}
+
diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex
index 7e55364..f7e9e31 100644
--- a/buch/chapters/50-permutationen/matrizen.tex
+++ b/buch/chapters/50-permutationen/matrizen.tex
@@ -181,7 +181,7 @@ Die Determinante einer solchen Permutationsmatrix ist
Nach der Produktregel für die Determinante folgt für eine Darstellung
der Permutation $\sigma=\tau_1\dots\tau_l$ als Produkt von Transpositionen,
dass
-\[
+\begin{equation}
\det P_{\sigma}
=
\det P_{\tau_1} \dots \det P_{\tau_l}
@@ -189,7 +189,8 @@ dass
(-1)^l
=
\operatorname{sgn}(\sigma).
-\]
+\label{buch:permutationen:determinante}
+\end{equation}
Das Vorzeichen einer Permutation ist also identisch mit der Determinante
der zugehörigen Permutationsmatrix.
diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex
index 7364c85..aee3b41 100644
--- a/buch/chapters/60-gruppen/symmetrien.tex
+++ b/buch/chapters/60-gruppen/symmetrien.tex
@@ -714,8 +714,8 @@ Kurve so zu definieren, dass dabei Längen und Winkel erhalten bleiben.
Dieser Ansatz ist die Basis der Theorie der Krümmung sogenannter
Riemannscher Mannigfaltigkeiten.
-\subsection{Der Satz von Noether
-\label{buch:subsection:noether}}
+%\subsection{Der Satz von Noether
+%\label{buch:subsection:noether}}
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index ef1520e..8baa88c 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -10,7 +10,7 @@ In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde
gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen
Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen
beschreibt, die mit vergleichbarer Amplitude sich über den ganzen
-Graphen entsprechen.
+Graphen erstrecken.
Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen
Knoten fast vollständig.
diff --git a/buch/chapters/90-crypto/Makefile.inc b/buch/chapters/90-crypto/Makefile.inc
index 9543ce1..508add5 100644
--- a/buch/chapters/90-crypto/Makefile.inc
+++ b/buch/chapters/90-crypto/Makefile.inc
@@ -8,5 +8,4 @@ CHAPTERFILES = $(CHAPTERFILES) \
chapters/90-crypto/arith.tex \
chapters/90-crypto/ff.tex \
chapters/90-crypto/aes.tex \
- chapters/90-crypto/rs.tex \
chapters/90-crypto/chapter.tex
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index dcc31b8..b05110f 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -91,6 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient
implementieren.
\begin{algorithmus}
+\label{buch:crypto:teile-und-hersche}
Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$
Multiplikationen
\begin{enumerate}
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index 535b359..a1cb747 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -7,6 +7,15 @@
\section{Kryptographie und endliche Körper
\label{buch:section:kryptographie-und-endliche-koerper}}
\rhead{Kryptographie und endliche Körper}
+In diesem Abschnitt soll illustriert werden, wie die Arithmetik in
+endlichen Körpern Algorithmen zu konstruieren erlaubt, mit denen sich
+zum Beispiel sehr effizient kryptographische Schlüssel aushandeln
+lassen.
+Der klassische Diffie-Hellmann-Algorithmus in einem Galois-Körper
+$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:subsection:elliptische-kurven}
+verallgemeinert auf eine sogenannte elliptische Kurve.
+Diese Version des Algorithmus ist sehr effizient was die Bitlänge der
+Schlüssel betrifft.
\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
\label{buch:subsection:potenzen-diskreter-logarithmus}}
@@ -439,6 +448,7 @@ Das Polynom ist
\[
p(t)
=
+XXX
\]
Nach Division durch $t(t-1)$ erhält man als den Quotienten
\begin{align*}
@@ -652,13 +662,44 @@ Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen
abelschen Gruppe.
\end{satz}
-\subsubsection{Beispiele}
-% XXX
-TODO: elliptische Kurven in IPsec: Oakley Gruppen
-
\subsubsection{Diffie-Hellman in einer elliptischen Kurve}
-% XXX
-TODO: $g^x$ in einer elliptischen Kurve
+Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper
+$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines
+Elementes berechnen kann, und dass es schwierig ist, diese Operation
+umzukehren.
+Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
+nicht benötigt.
+
+In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
+aus der sich mit dem
+Algorithmus~\ref{buch:crypto:teile-und-hersche} eine effizienter
+Potenzieralgorithmus konstruieren lässt.
+
+Die im Internet Key Exchange Protokol
+in RFC 2409
+\cite{buch:rfc2409}
+definierte Oakley-Gruppe 4
+zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$
+mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$
+und den Koeffizienten
+\begin{align*}
+a&=0\\
+b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1,
+\end{align*}
+die die elliptische Kurve definieren.
+
+Als Elemente $g$ für den Diffie-Hellmann-Algorithmus wird ein Punkt
+der elliptischen Kurve verwendet, dessen $X$-Koordinaten durch das
+Polynom $g_x = x^4+x^3$ gegeben ist.
+Der Standard spezifiziert die $Y$-Koordinate nicht, diese kann aus
+den gegebenen Daten abgeleitet werden.
+Die entstehende Gruppe hat etwa $4.9040\cdot10^{55}$ Elemente, die
+für einen brute-force-Angriff durchprobiert werden müssten.
+
+
+
+
+
diff --git a/buch/chapters/90-crypto/rs.tex b/buch/chapters/90-crypto/rs.tex
deleted file mode 100644
index ec8ec8c..0000000
--- a/buch/chapters/90-crypto/rs.tex
+++ /dev/null
@@ -1,41 +0,0 @@
-%
-% rs.tex -- Reed-Solomon-Code
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-\section{Fehlerkorrigierende Codes nach Reed-Solomon
-\label{buch:section:reed-solomon}}
-\rhead{Fehlerkorrigierende Codes}
-Jede Art von Datenübertragung muss sich mit dem Problem der Fehler befassen,
-die auf dem Übertragungskanal entstehen können.
-Die einfachste Lösung dieses Problem versucht, Fehler zu erkennen und
-dann eine erneute Übermittelung zu veranlassen.
-Dies ist zum Beispiel bei der Datenübertragung von einer Raumsonde
-wie Voyager~1 nicht möglich, die Signallaufzeit von der Sonde und wieder
-zurück ist über 40 Stunden.
-Es ist auch nicht sinnvoll beim Lesen eines optischen Mediums wie einer
-CD oder DVD, wenn ein Fehler durch eine Beschädigung der Oberfläche
-des Mediums verursacht wird.
-Erneutes Lesen würde das Resultat auch nicht ändern.
-Es wird also eine Möglichkeit gesucht, die Daten so zu codieren, dass
-ein Fehler nicht nur erkannt sondern auch korrigiert werden kann.
-
-In diesem Abschnitt werden die algebraisch besonders interessanten
-Reed-Solmon-Codes beschrieben.
-Ihren ersten Einsatz hatten Sie bei den Voyager-Raumsonden, die 1977
-gestartet wurden.
-Sie befinden sich im Moment in einer Entfernung von
-Zum ersten mal kommerziell verwendet wurden sie für die optischen
-Medien CD und DVD.
-
-% https://www.youtube.com/watch?v=uOLW43OIZJ0
-% https://www.youtube.com/watch?v=4BfCmZgOKP8
-
-\subsection{Was ist ein Code?
-\label{buch:subsection:was-ist-ein-code}}
-
-\subsection{Reed-Solomon-Code
-\label{buch:subsection:reed-solomon-code}}
-
-\subsection{Decodierung
-\label{buch:subsection:decodierung}}
diff --git a/buch/chapters/95-homologie/Makefile.inc b/buch/chapters/95-homologie/Makefile.inc
index 7e6f1e7..41b1569 100644
--- a/buch/chapters/95-homologie/Makefile.inc
+++ b/buch/chapters/95-homologie/Makefile.inc
@@ -8,7 +8,6 @@ CHAPTERFILES = $(CHAPTERFILES) \
chapters/95-homologie/simplex.tex \
chapters/95-homologie/komplex.tex \
chapters/95-homologie/homologie.tex \
- chapters/95-homologie/mayervietoris.tex \
chapters/95-homologie/fixpunkte.tex \
chapters/95-homologie/chapter.tex
diff --git a/buch/chapters/95-homologie/chapter.tex b/buch/chapters/95-homologie/chapter.tex
index eaa56c4..994c400 100644
--- a/buch/chapters/95-homologie/chapter.tex
+++ b/buch/chapters/95-homologie/chapter.tex
@@ -38,7 +38,7 @@ Damit wird es möglich, das Dreieck vom Rand des Dreiecks zu unterschieden.
\input{chapters/95-homologie/simplex.tex}
\input{chapters/95-homologie/komplex.tex}
\input{chapters/95-homologie/homologie.tex}
-\input{chapters/95-homologie/mayervietoris.tex}
+%\input{chapters/95-homologie/mayervietoris.tex}
\input{chapters/95-homologie/fixpunkte.tex}
diff --git a/buch/chapters/95-homologie/homologie.tex b/buch/chapters/95-homologie/homologie.tex
index 2b80a17..905ecc3 100644
--- a/buch/chapters/95-homologie/homologie.tex
+++ b/buch/chapters/95-homologie/homologie.tex
@@ -6,13 +6,349 @@
\section{Homologie
\label{buch:section:homologie}}
\rhead{Homologie}
+Die Idee der Trangulation ermöglicht, komplizierte geometrische
+Objekte mit einem einfachen ``Gerüst'' auszustatten und so zu
+analysieren.
+Projiziert man ein mit einer Kugel konzentrisches Tetraeder auf die
+Kugel, entsteht eine Triangulation der Kugeloberfläche.
+Statt eine Kugel zu studieren, kann man also auch ein Tetraeder untersuchen.
+
+Das Gerüst kann natürlich nicht mehr alle Eigenschaften des ursprünglichen
+Objektes wiedergeben.
+Im Beispiel der Kugel geht die Information darüber, dass es sich um eine
+glatte Mannigfaltigkeit handelt, verloren.
+Was aber bleibt, sind Eigenschaften des Zusammenhangs.
+Wenn sich zwei Punkte mit Wegen verbinden lassen, dann gibt es auch eine
+Triangulation mit eindimensionalen Simplices, die diese Punkte als Ecken
+enthalten, die sich in der Triangulation mit einer Folge von Kanten
+verbinden lassen.
+Algebraisch bedeutet dies, dass die beiden Punkte der Rand eines
+Weges sind.
+Fragen der Verbindbarkeit von Punkten mit Wegen lassen sich also
+dadurch studieren, dass man das geometrische Objekt auf einen Graphen
+reduziert.
+
+In diesem Abschnitt soll gezeigt werden, wie diese Idee auf höhere
+Dimensionen ausgedehnt werden.
+Es soll möglich werden, kompliziertere Fragen des Zusammenhangs, zum
+Beispiel das Vorhandensein von Löchern mit algebraischen Mitteln
+zu analysieren.
\subsection{Homologie eines Kettenkomplexes
\label{buch:subsection:homologie-eines-kettenkomplexes}}
+Wegzusammenhang lässt sich untersuchen, indem man in der Triangulation
+nach Linearkombinationen von Kanten sucht, die als Rand die beiden Punkte
+haben.
+Zwei Punkte sind also nicht verbindbar und liegen damit in verschiedenen
+Komponenten, wenn die beiden Punkte nicht Rand irgend einer
+Linearkombination von Kanten sind.
+Komponenten können also identifiziert werden, indem man unter allen
+Linearkombinationen von Punkten, also $C_0$ all diejenigen ignoriert,
+die Rand einer Linearkombinationv on Kanten sind, also $\partial_1C_1$.
+Der Quotientenraum $H_0=C_0/\partial_1C_1$ enthält also für jede Komponente
+eine Dimension.
+
+Eine Dimension höher könnten wir danach fragen, ob sich ein geschlossener
+Weg zusammenziehen lässt.
+In der Triangulation zeichnet sich ein geschlossener Weg dadurch aus,
+dass jedes Ende einer Kante auch Anfang einer Folgekante ist, dass also
+der Rand der Linearkombination von Kanten 0 ist.
+Algebraisch bedeutet dies, dass wir uns für diejenigen Linearkombinationen
+$z\in C_1$ interessieren, die keinen Rand haben, für die also $\partial_1z=0$
+gilt.
+
+\begin{definition}
+Die Elemente von
+\[
+Z_k
+=
+Z_k^C
+=
+\{z\in C_k\;|\; \partial_k z = 0\}
+=
+\ker \partial_k
+\]
+heissen die {\em ($k$-dimensionalen) Zyklen} von $C_*$.
+\end{definition}
+
+In einem Dreieck ist der Rand ein geschlossener Weg, der sich zusammenziehen
+lässt, indem man ihn durch die Dreiecksfläche deformiert.
+Entfernt man aber die Dreiecksfläche, ist diese Deformation nicht mehr
+möglich.
+Einen zusammenziehbaren Weg kann man sich also als den Rand eines Dreiecks
+einer vorstellen.
+``Löcher'' sind durch geschlossene Wege erkennbar, die nicht Rand eines
+Dreiecks sein können.
+Wir müssen also ``Ränder'' ignorieren.
+
+\begin{definition}
+Die Elemente von
+\[
+B_k
+=
+B_k^C
+=
+\{\partial_{k+1}z\;|\; C_{k+1}\}
+=
+\operatorname{im} \partial_{k+1}
+\]
+heissen die {\em ($k$-dimensionalen) Ränder} von $C_*$.
+\end{definition}
+
+Algebraisch ausgedrückt interessieren uns also nur Zyklen, die selbst
+keine Ränder sind.
+Der Quotientenraum $Z_1/B_1$ ignoriert unter den Zyklen diejenigen, die
+Ränder sind, drückt also algebraisch die Idee des eindimensionalen
+Zusammenhangs aus.
+Wir definieren daher
+
+\begin{definition}
+Die $k$-dimensionale Homologiegruppe des Kettenkomplexes $C_*$ ist
+\[
+H_k(C) = Z_k/B_k = \ker \partial_k / \operatorname{im} \partial_{k+1}.
+\]
+Wenn nur von einem Kettenkomplex die Rede ist, kann auch $H_k(C)=H_k$
+abgekürzt werden.
+\end{definition}
+
+Die folgenden zwei ausführlichen Beispiele sollen zeigen, wie die
+Homologiegruppe $H_2$ die Anwesenheit eines Hohlraumes detektieren kann,
+der entsteht, wenn man aus einem Tetraeder das innere entfernt.
+
+\begin{beispiel}
+\begin{figure}
+\centering
+XXX Bild eines Tetraeders mit Bezeichnung der Ecken und Kanten
+\caption{Triangulation eines Tetraeders, die Orientierung von Kanten
+und Seitenflächen ist immer so gewählt, dass die Nummern der Ecken
+aufsteigend sind.
+\label{buch:homologie:tetraeder:fig}}
+\end{figure}
+Ein Tetraeder ist ein zweidmensionales Simplex, wir untersuchen seinen
+Kettenkomplex und bestimmen die zugehörigen Homologiegruppen.
+Zunächst müssen wir die einzelnen Mengen $C_k$ beschreiben und verwenden
+dazu die Bezeichnungen gemäss Abbildung~\ref{buch:homologie:tetraeder:fig}.
+$C_0$ ist der vierdimensionale Raum aufgespannt von den vier Ecken
+$0$, $1$, $2$ und $3$ des Tetraeders.
+$C_1$ ist der sechsdimensionale Vektorraum der Kanten
+\[
+k_0 = [0,1],\quad
+k_1 = [0,2],\quad
+k_2 = [0,3],\quad
+k_3 = [1,2],\quad
+k_4 = [1,3],\quad
+k_5 = [2,3]
+\]
+Der Randoperator $\partial_1$ hat die Matrix
+\[
+\partial_1
+=
+\begin{pmatrix*}[r]
+-1&-1&-1& 0& 0& 0\\
+ 1& 0& 0&-1&-1& 0\\
+ 0& 1& 0& 1& 0&-1\\
+ 0& 0& 1& 0& 1& 1
+\end{pmatrix*}.
+\]
+
+Wir erwarten natürlich, dass sich zwei beliebige Ecken verbinden lassen,
+dass es also nur eine Komponente gibt und dass damit $H_1=\Bbbk$ ist.
+Dazu beachten wir, dass das Bild von $\partial_1$ genau aus den Vektoren
+besteht, deren Komponentensumme $0$ ist.
+Das Bild $B_0$ von $\partial_1$ ist daher die Lösungsmenge der einen
+Gleichung
+\(
+x_0+x_1+x_2+x_3=0.
+\)
+Der Quotientenraum $H_0=Z_0/B_0 = C_0/\operatorname{im}\partial_1$
+ist daher wie erwartet eindimensional.
+
+Wir bestimmen jetzt die Homologiegruppe $H_1$.
+Da sich im Tetraeder jeder geschlossene Weg zusammenziehen lässt,
+erwarten wir $H_1=0$.
+
+Die Menge der Zyklen $Z_1$ wird bestimmt, indem man die Lösungsmenge
+des Gleichungssystems $\partial_1z=0$ bestimmt.
+Der Gauss-Algorithmus für die Matrix $\partial_1$ liefert das
+Schlusstableau
+\[
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+k_0&k_1&k_2&k_3&k_4&k_5\\
+\hline
+ 1& 0& 0& -1& -1& 0\\
+ 0& 1& 0& 1& 0& -1\\
+ 0& 0& 1& 0& 1& 1\\
+ 0& 0& 0& 0& 0& 0\\
+\hline
+\end{tabular}
+\]
+Daraus lassen sich drei linear unabhängig eindimensionale Zyklen ablesen,
+die zu den Lösungsvektoren
+\[
+z_1
+=
+\begin{pmatrix*}[r]
+1\\
+-1\\
+0\\
+1\\
+0\\
+0
+\end{pmatrix*},
+\qquad
+z_2
+=
+\begin{pmatrix*}[r]
+1\\
+0\\
+-1\\
+0\\
+1\\
+0
+\end{pmatrix*},
+\qquad
+z_3
+=
+\begin{pmatrix*}[r]
+0\\
+1\\
+-1\\
+0\\
+0\\
+1
+\end{pmatrix*}
+\]
+gehören.
+
+$C_2$ hat die vier Seitenflächen
+\[
+f_0=[0,1,2],\quad
+f_1=[0,1,3],\quad
+f_2=[0,2,3],\quad
+f_3=[1,2,3]
+\]
+als Basis.
+Der zweidimensionale Randoperator ist die $6\times 4$-Matrix
+\[
+\partial_2
+=
+\begin{pmatrix*}[r]
+ 1& 1& 0& 0\\
+-1& 0& 1& 0\\
+ 0&-1&-1& 0\\
+ 1& 0& 0& 1\\
+ 0& 1& 0&-1\\
+ 0& 0& 1& 1
+\end{pmatrix*}.
+\]
+Man kann leicht nachrechnen, dass $\partial_1\partial_2=0$ ist, wie es
+für einen Kettenkomplex sein muss.
+
+Um nachzurechnen, dass die Homologiegruppe $H_1=0$ ist, müssen wir jetzt
+nachprüfen, ob jeder Zyklus in $Z_1$ auch Bild der Randabbildung $\partial_2$
+ist.
+Die ersten drei Spalten von $\partial_2$ sind genau die drei Zyklen
+$z_1$, $z_2$ und $z_3$.
+Insbesondere lassen sich alle Zyklen als Ränder darstellen, die
+Homologiegruppe $H_1=0$ verschwindet.
+
+Die Zyklen in $C_2$ sind die Lösungen von $\partial_2z=0$.
+Der Gauss-Algorithmus für $\partial_2$ liefert das -Tableau
+\[
+\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
+\hline
+f_0&f_1&f_2&f_3\\
+\hline
+1&0&0& 1\\
+0&1&0&-1\\
+0&0&1& 1\\
+0&0&0& 0\\
+0&0&0& 0\\
+0&0&0& 0\\
+\hline
+\end{tabular}
+\]
+Daraus liest man ab, dass es genau einen Zyklus nämlich
+\[
+z
+=
+\begin{pmatrix}
+-1\\1\\-1\\1
+\end{pmatrix}
+\]
+$Z_2$ besteht also aus Vielfachen des Vektors $z$.
+
+Da es nur ein zweidimensionales Simplex gibt, ist $C_3$ eindimensional.
+Die Randabbildung $\partial_3$ hat die Matrix
+\[
+\partial_3
+=
+\begin{pmatrix}
+1\\
+-1\\
+1\\
+-1
+\end{pmatrix}.
+\]
+Die Zyklen $Z_2$ und die Ränder $B_2$ bilden also dieselbe Menge, auch
+die Homologie-Gruppe $H_2$ ist $0$.
+
+Da es keine vierdimensionalen Simplizes gibt, ist $B_3=0$.
+Die Zyklen $Z_3$ bestehen aus den Lösungen von $\partial_3w=0$, da
+aber $\partial_3$ injektiv ist, ist $Z_3=0$.
+Daher ist auch $H_3=0$.
+\end{beispiel}
+
+\begin{beispiel}
+Für dieses Beispiel entfernen wir das Innere des Tetraeders, es entsteht
+ein Hohlraum.
+Am Kettenkomplex der Triangulation ändert sich nur, dass $C_3$ jetzt
+nur noch den $0$-Vektor enthält.
+Das Bild $B_2=\operatorname{im}\partial_3$ wird damit auch $0$-dimensional,
+während es im vorigen Beispiel eindimensional war.
+Die einzige Änderung ist also in der Homologiegruppe
+$H_2 = Z_2/B_2 = Z_2 / \{0\} \simeq \Bbbk$.
+Die Homologiegruppe $H_2$ hat jetzt Dimension $1$ und zeigt damit den
+Hohlraum an.
+\end{beispiel}
\subsection{Induzierte Abbildung
\label{buch:subsection:induzierte-abbildung}}
+Früher haben wurde eine Abbildung $f_*$ zwischen Kettenkomplexen $C_*$ und
+$D_*$ so definiert,
+dass sie mit den Randoperatoren verträglich sein muss.
+Diese Forderung bewirkt, dass sich auch eine lineare Abbildung
+\[
+H_k(f) \colon H_k(C) \to H_k(D)
+\]
+zwischen den Homologiegruppen ergibt, wie wir nun zeigen wollen.
+
+Um eine Abbildung von $H_k(C)$ nach $H_k(D)$ zu definieren, müssen wir
+zu einem Element von $H_k(C)$ ein Bildelement konstruieren.
+Ein Element in $H_k(C)$ ist eine Menge von Zyklen in $Z^C_k$, die sich
+nur um einen Rand in $B_k$ unterscheiden.
+Wir wählen also einen Zyklus $z\in Z_k$ und bilden ihn auf $f_k(z)$ ab.
+Wegen $\partial^D_kf(z)=f\partial^C_kz = f(0) =0 $ ist auch $f_k(z)$
+ein Zyklus.
+Wir müssen jetzt aber noch zeigen, dass eine andere Wahl des Zyklus
+das gleiche Element in $H_k(D)$ ergibt.
+Dazu genügt es zu sehen, dass sich $f(z)$ höchstens um einen Rand
+ändert, wenn man $z$ um einen Rand ändert.
+Sei also $b\in B^C_k$ ein Rand, es gibt also ein $w\in C_{k+1}$ mit
+$\partial^C_{k+1}w=b$.
+Dann gilt aber auch
+\[
+f_k(z+b)
+=
+f_k(z) + f_k(b)
+=
+f_k(z) + f_k(\partial^C_{k+1}w)
+=
+f_k(z) + \partial^D_{k+1}(f_k(w)).
+\]
+Der letzte Term ist ein Rand in $D_k$, somit ändert sich $f_k(z)$ nur
+um diesen Rand, wenn man $z$ um einen Rand ändert.
+$f_k(z)$ und $f_k(z+b)$ führen auf die selbe Homologieklasse.
-\subsection{Homologie eines simplizialen Komplexes
-\label{buch:subsection:simplizialekomplexe}}
diff --git a/buch/chapters/95-homologie/komplex.tex b/buch/chapters/95-homologie/komplex.tex
index 6dd8efb..fa2d8e1 100644
--- a/buch/chapters/95-homologie/komplex.tex
+++ b/buch/chapters/95-homologie/komplex.tex
@@ -6,9 +6,105 @@
\section{Kettenkomplexe
\label{buch:section:komplex}}
\rhead{Kettenkomplexe}
+Die algebraische Struktur, die in Abschnitt~\ref{buch:subsection:triangulation}
+konstruiert wurde, kann noch etwas abstrakter konstruiert werden.
+Es ergibt sich das Konzept eines Kettenkomplexes.
+Die Triangulation gibt also Anlass zu einem Kettenkomplex.
+So lässt sich zu einem geometrischen Objekt ein algebraisches
+Vergleichsobjekt konstruieren.
+Im Idealfall lassens ich anschliessend geometrische Eigenschaften mit
+algebraischen Rechnungen zum Beispiel in Vektorräumen mit Matrizen
+beantworten.
-\subsection{Randoperator von Simplexen
-\label{buch:subsection:randoperator-von-simplexen}}
+\subsection{Definition
+\label{buch:subsection:kettenkomplex-definition}}
+Die Operation $\partial$, die für Simplizes konstruiert worden ist,
+war linear und hat die Eigenschaft $\partial^2$ gehabt.
+Diese Eigenschaften reichen bereits für Definition eines Kettenkomplexes.
+
+\begin{definition}
+Eine Folge $C_0,C_1,C_2,\dots$ von Vektorräumen über dem Körper $\Bbbk$
+mit einer Folge von linearen Abbildungen
+$\partial_k\colon C_k \to C_{k-1}$, dem {\em Randoperator},
+heisst ein Kettenkomplex, wenn $\partial_{k-1}\partial_k=0$ gilt
+für alle $k>0$.
+\end{definition}
+
+Die aus den Triangulationen konstruieren Vektorräme von
+Abschnitt~\ref{buch:subsection:triangulation} bilden einen
+Kettenkomplex.
+
+XXX nachrechnen: $\partial^2 = 0$ ?
+
+\subsection{Abbildungen
+\label{buch:subsection:abbildungen}}
+Wenn man verschiedene geometrische Objekte mit Hilfe von Triangulationen
+vergleichen will, dann muss man auch das Konzept der Abbildungen zwischen
+den geometrischen Objekten in die Kettenkomplexe transportieren.
+
+Eine Abbildung zwischen Kettenkomplexen muss einerseits eine lineare
+Abbildung der Vektorräume $C_k$ sein, andererseits muss sich eine
+solche Abbildung mit dem Randoperator vertragen.
+Wir definieren daher
+
+\begin{definition}
+Eine Abbildung $f_*$ zwischen zwei Kettenkomplexe $(C_*,\partial^C_*)$ und
+$(D_*,\partial^D_*)$ heisst eine Abbildung von Kettenkomplexen, wenn
+für jedes $k$
+\begin{equation}
+\partial^D_k
+\circ
+f_{k}
+=
+f_{k+1}
+\circ
+\partial^C_k
+\label{buch:komplex:abbildung}
+\end{equation}
+gilt.
+\end{definition}
+
+Die Beziehung~\eqref{buch:komplex:abbildung} kann übersichtlich als
+kommutatives Diagramm dargestellt werden.
+\begin{equation}
+\begin{tikzcd}
+0
+ & C_0 \arrow[l, "\partial_0^C"]
+ \arrow[d, "f_0"]
+ & C_1 \arrow[l,"\partial_1^C"]
+ \arrow[d, "f_1"]
+ & C_2 \arrow[l,"\partial_2^C"]
+ \arrow[d, "f_2"]
+ & \dots \arrow[l]
+ \arrow[l, "\partial_{k-1}^C"]
+ & C_k
+ \arrow[l, "\partial_k^C"]
+ \arrow[d, "f_k"]
+ & C_{k+1}\arrow[l, "\partial_{k+1}^C"]
+ \arrow[d, "f_{k+1}"]
+ & \dots
+\\
+0
+ & D_0 \arrow[l, "\partial_0^D"]
+ & D_1 \arrow[l,"\partial_1^D"]
+ & D_2 \arrow[l,"\partial_2^D"]
+ & \dots \arrow[l]
+ \arrow[l, "\partial_{k-1}^D"]
+ & D_k
+ \arrow[l, "\partial_k^D"]
+ & D_{k+1}\arrow[l, "\partial_{k+1}^D"]
+ & \dots
+\end{tikzcd}
+\label{buch:komplex:abbcd}
+\end{equation}
+Die Relation~\eqref{buch:komplex:abbildung} drückt aus, dass man jeden
+den Pfeilen im Diagram~\eqref{buch:komplex:abbcd} folgen kann und
+dabei zwischen zwei Vektorräumen unabhängig vom Weg die gleiche Abbildung
+resultiert.
+
+Die Verfeinerung einer Triangulation erzeugt eine solche Abbildung von
+Komplexen.
+
+
+% XXX simpliziale Approximation
-\subsection{Kettenkomplexe und Morphismen
-\label{buch:subsection:kettenkomplex}}
diff --git a/buch/chapters/95-homologie/simplex.tex b/buch/chapters/95-homologie/simplex.tex
index 5ca2ca8..397ba07 100644
--- a/buch/chapters/95-homologie/simplex.tex
+++ b/buch/chapters/95-homologie/simplex.tex
@@ -233,6 +233,6 @@ Vorzeichen zu, die Matrix ist
\subsection{Triangulation
-\label{buch:subsection:}}
+\label{buch:subsection:triangulation}}
diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib
index 59a8376..977bf81 100644
--- a/buch/chapters/references.bib
+++ b/buch/chapters/references.bib
@@ -39,6 +39,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc
year = {2016},
}
+@online{buch:rfc2409,
+ title = {The Internet Key Exchange (IKE)},
+ author = { D. Harkins and D. Carrel},
+ url = {https://datatracker.ietf.org/doc/html/rfc2409},
+ year = {1998}
+}
+
@online{buch:fftw,
title = {Fastest Fourier Transform in the West},
url = {http://www.fftw.org/},