Permutationen hinzugefügt

6 files changed, 874 insertions, 0 deletions

diff --git a/buch/chapters/50-permutationen/beispiele/perm.m b/buch/chapters/50-permutationen/beispiele/perm.m
new file mode 100644
index 0000000..2e837ef
--- /dev/null
+++ b/buch/chapters/50-permutationen/beispiele/perm.m
@@ -0,0 +1,44 @@
+#
+# perm.m -- find a random permutation
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+N = 8
+M = N+1
+
+function retval = permutation(n)
+	p = (1:n);
+	for i = (1:(n-1))
+		j = i + 1 + floor(rand() * (n-i));
+		s = p(i);
+		p(i) = p(j);
+		p(j) = s;
+	endfor
+	retval = p;
+end
+
+function retval = compose(p,q)
+	n = size(p)(1,2);
+	retval = zeros(1,n);
+	for i = (1:n)
+		retval(i) = q(p(i));
+	end
+end
+
+sigma = permutation(N)
+sigma = compose(sigma, permutation(N))
+sigma = compose(sigma, permutation(N))
+sigma = compose(sigma, permutation(N))
+sigma = compose(sigma, permutation(N))
+sigma = compose(sigma, permutation(N))
+sigma = compose(sigma, permutation(N))
+
+s = zeros(M,N);
+s(1,:) = sigma;
+for i = (2:M)
+	s(i,:) = compose(s(i-1,:), sigma);
+end
+
+s
+
+compose(sigma, permutation(N))
diff --git a/buch/chapters/50-permutationen/chapter.tex b/buch/chapters/50-permutationen/chapter.tex
index c9514b8..842051b 100644
--- a/buch/chapters/50-permutationen/chapter.tex
+++ b/buch/chapters/50-permutationen/chapter.tex
@@ -7,9 +7,24 @@
 \label{buch:chapter:permutationen}}
 \lhead{Permutationen}
 \rhead{}
+Die Berechnung der Determinante einer Matrix macht ausgedehnten
+Gebrauch von der Tatsache, dass die Vertauschung von zwei Zeilen
+oder Spalten das Vorzeichen des Wertes der Determinanten bewirkt.
+In diesem Kapitel sollen die Permutationen der Zeilen abstrakt
+untersucht werden.
+Wir erhalten so eine abstrakte Gruppe, die Permutationsgruppe.
+Ihre Elemente lassen sich auch durch spezielle Matrizen beschreiben,
+eine Darstellung der Gruppe, die auch unmittelbar zu einer 
+Formel für die Determinante einer Matrix führt.
 
 \input{chapters/50-permutationen/endlich.tex}
 \input{chapters/50-permutationen/transpositionen.tex}
 \input{chapters/50-permutationen/matrizen.tex}
 \input{chapters/50-permutationen/determinante.tex}
 
+\section*{Übungsaufgaben}
+\aufgabetoplevel{chapters/50-permutationen/uebungsaufgaben}
+\begin{uebungsaufgaben}
+\uebungsaufgabe{5001}
+\end{uebungsaufgaben}
+
diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex
index 71cc991..9514f88 100644
--- a/buch/chapters/50-permutationen/endlich.tex
+++ b/buch/chapters/50-permutationen/endlich.tex
@@ -6,3 +6,291 @@
 \section{Permutationen einer endlichen Menge
 \label{buch:section:permutationen-einer-endlichen-menge}}
 \rhead{Permutationen}
+Eine endliche Anzahl $n$ von Objekten können auf $n!$ Arten angeordnet
+werden.
+Als Objektmenge nehmen wir $[n] = \{ 1,\dots,n\}$.
+Die Operation, die die Objekte in eine bestimmte Reihenfolge bringt,
+ist eine Abbildung $\sigma\colon[n]\to[n]$.
+Eine Permutation ist eine umkehrbare Abbildung $[n]\to[n]$.
+Die Menge $S_n$ aller umkehrbaren Abbildungen $[n]\to[n]$
+mit der Verknüpfung von Abbildungen als Operation heisst die
+die {\em symmetrische Gruppe}.
+Die identische Abbildung $\sigma(x)=x$ ist das {\em neutrale
+Element} der Gruppe $S_n$ und wir auch mit $e$ bezeichnet.
+
+\subsection{Permutationen als $2\times n$-Matrizen}
+Eine Permutation kann als $2\times n$-Matrix geschrieben werden:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\def\sx{0.8}
+\def\sy{1}
+\begin{scope}[xshift=-3cm]
+\foreach \x in {1,...,6}{
+	\node at ({(\x-1)*\sx},\sy) [above] {$\tiny\x$};
+	\fill ({(\x-1)*\sx},\sy) circle[radius=0.05];
+	\fill ({(\x-1)*\sx},0) circle[radius=0.05];
+}
+\draw[->] (0,\sy) to[out=-70,in=110] (\sx,0);
+\draw[<-] (0,0) to[out=70,in=-110] (\sx,\sy);
+\draw[->] ({2*\sx},\sy) -- ({2*\sx},0);
+\draw[->] ({3*\sx},\sy) to[out=-70,in=110] ({4*\sx},0);
+\draw[->] ({4*\sx},\sy) to[out=-70,in=110] ({5*\sx},0);
+\draw[->] ({5*\sx},\sy) to[out=-110,in=70] ({3*\sx},0);
+\end{scope}
+\node at (2.4,{\sy/2}) {$\mathstrut=\mathstrut$};
+\node at (5,{\sy/2}) {$\displaystyle
+\renewcommand{\arraystretch}{1.4}
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}
+$};
+\end{tikzpicture}
+\end{center}
+Das neutrale Element hat die Matrix
+\[
+e = \begin{pmatrix}
+1&2&3&4&5&6\\
+1&2&3&4&5&6
+\end{pmatrix}
+\]
+aus zwei identischen Zeilen.
+
+Die Verknüpfung zweier solcher Permutationen kann leicht graphisch
+dargestellt werden: dazu werden die beiden Permutationen
+untereinander geschrieben und Spalten der zweiten Permutation
+in der Reihen folge der Zahlen in der zweiten Zeile der ersten
+Permutation angeordnet.
+Die zusammengesetzte Permutation kann dann in der zweiten Zeile
+der zweiten Permutation abgelesen werden:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\begin{scope}[xshift=-4.5cm]
+\node at (0,0) {$\displaystyle
+\sigma_1=\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}$};
+\node at (0,-1) {$\displaystyle
+\sigma_2=\begin{pmatrix}
+1&2&3&4&5&6\\
+3&4&5&6&1&2
+\end{pmatrix}
+$};
+\end{scope}
+\begin{scope}
+\node at (0,0) {$\displaystyle
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}$};
+\node at (0,-1) {$\displaystyle
+\begin{pmatrix}
+2&1&3&5&6&4\\
+4&3&5&1&2&6
+\end{pmatrix}
+$};
+
+\end{scope}
+\begin{scope}[xshift=4.5cm]
+\node at (0,-0.5) {$\displaystyle
+\sigma_2\sigma_1=\begin{pmatrix}
+1&2&3&4&5&6\\
+4&3&5&1&2&6
+\end{pmatrix}
+$};
+\end{scope}
+\end{tikzpicture}
+\end{center}
+Die Inverse einer Permutation kann erhalten werden, indem die beiden
+Zeilen vertauscht werden und dann die Spalten wieder so angeordnet werden,
+dass die Zahlen in der ersten Zeile ansteigend sind:
+\[
+\sigma = \begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}
+\qquad\Rightarrow\qquad
+\sigma^{-1}
+=
+\begin{pmatrix}
+2&1&3&5&6&4\\
+1&2&3&4&5&6
+\end{pmatrix}
+=
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&6&4&5
+\end{pmatrix}.
+\]
+
+\subsection{Zyklenzerlegung}
+Eine Permutation $\sigma\in S_n$ kann auch mit sogenanten Zyklenzerlegung
+analysiert werden.
+Zum Beispiel:
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\begin{scope}[xshift=-3cm]
+\node at (0,0) {$\displaystyle
+\sigma=\begin{pmatrix}
+{\color{red}1}&{\color{red}2}&{\color{darkgreen}3}&{\color{blue}4}&{\color{blue}5}&{\color{blue}6}\\
+{\color{red}2}&{\color{red}1}&{\color{darkgreen}3}&{\color{blue}5}&{\color{blue}6}&{\color{blue}4}
+\end{pmatrix}$};
+\end{scope}
+\node at (0,0) {$\mathstrut=\mathstrut$};
+\begin{scope}[xshift=1.5cm]
+\coordinate (A) at (0,0.5);
+\coordinate (B) at (0,-0.5);
+\draw[->,color=red] (A) to[out=-20,in=20] (0,-0.5);
+\draw[->,color=red] (B) to[out=160,in=-160] (0,0.5);
+\node at (A) [above] {$\tiny 1$};
+\node at (B) [below] {$\tiny 2$};
+\fill (A) circle[radius=0.05];
+\fill (B) circle[radius=0.05];
+
+\coordinate (C) at (1.5,0.25);
+\node at (C) [above] {$\tiny 3$};
+\draw[->,color=darkgreen] ({1.5+0.01},0.25) to[out=-10,in=-170] ({1.5-0.01},0.25);
+\draw[color=darkgreen] (1.5,{0.25-0.3}) circle[radius=0.3];
+\fill (C) circle[radius=0.05];
+
+\def\r{0.5}
+\coordinate (D) at ({3.5+\r*cos(90)},{0+\r*sin(90)});
+\coordinate (E) at ({3.5+\r*cos(210)},{0+\r*sin(210)});
+\coordinate (F) at ({3.5+\r*cos(330)},{0+\r*sin(330)});
+\node at (D) [above] {$\tiny 4$};
+\node at (E) [below left] {$\tiny 5$};
+\node at (F) [below right] {$\tiny 6$};
+\draw[->,color=blue] (D) to[out=180,in=120] (E);
+\draw[->,color=blue] (E) to[out=-60,in=-120] (F);
+\draw[->,color=blue] (F) to[out=60,in=0] (D);
+\fill (D) circle[radius=0.05];
+\fill (E) circle[radius=0.05];
+\fill (F) circle[radius=0.05];
+
+\end{scope}
+\end{tikzpicture}
+\end{center}
+
+\begin{definition}
+Ein Zyklus $Z$ ist eine unter $\sigma$ invariante Teilmenge von $[n]$
+minimaler Grösse.
+Die Zyklenzerlegung ist eine Zerlegung von $[n]$ in Zyklen
+\[
+[n]
+=
+\cup_{i=1}^k Z_i,
+\]
+wobei jede Menge $Z_i$ ein Zyklus ist.
+\end{definition}
+
+Der folgende Algorithmus findet die Zyklenzerlegung einer Permutation.
+
+\begin{satz}
+Sei $\sigma\in S_n$ eine Permutation. Der folgende Algorithmus findet
+die Zyklenzerlegung von $\sigma$:
+\begin{enumerate}
+\item
+$i=1$
+\item
+Wähle das erste noch nicht verwendete Element
+\[
+s_i=\min\biggl( [n] \setminus \bigcup_{j< i} Z_j\biggr)
+\]
+\item
+Bestimme alle Elemente, die aus $s_i$ durch Anwendung von $\sigma$
+entstehen:
+\[
+Z_i
+=
+\{ s_i, \sigma(s_i), \sigma(\sigma(s_i)), \dots \}
+=
+\{\sigma^k(s_i)\;|\; k\ge 0\}.
+\]
+\item
+Falls $\bigcup_{j\le i} Z_j\ne [n]$, erhöhe $i$ um $1$ und fahre 
+weiter bei 2.
+\end{enumerate}
+\end{satz}
+
+Mit Hilfe der Zyklenzerlegung von $\sigma$ lassen sich auch
+gewisse Eigenschaften von $\sigma$ ableiten.
+Sei also $[n] = Z_1\cup\dots\cup Z_k$ die Zyklenzerlegung.
+Für jedes Element $x\in S_i$ gilt $\sigma^{|S_i|}(x) = x$.
+Die kleinste Zahl $m$, für die $\sigma^m=e$ ist, das kleinste
+gemeinsame Vielfache der Zyklenlängen:
+\[
+m = \operatorname{kgV} (|Z_1|,|Z_2|,\dots,|Z_k|).
+\]
+
+\subsection{Konjugierte Elemente in $S_n$}
+Zwei Elemente $g_1,g_2\in G$ einer Gruppe heissen konjugiert, wenn
+es ein Element $c\in G$ gibt derart, dass $cg_1c^{-1}=g_2$.
+Bei Matrizen hat dies bedeutet, dass die beiden Matrizen durch
+Basiswechsel auseinander hervorgehen.
+Dasselbe lässt sich auch im Kontext der symmetrischen Gruppe sagen.
+
+Seien $\sigma_1$ und $\sigma_2$ zwei konjugierte Permutationen in $S_n$.
+Es gibt also eine Permutation $\gamma\in S_n$ derat, dass
+$\sigma_1=\gamma\sigma_2\sigma^{-1}$ oder $\gamma^{-1}\sigma_1\gamma=\sigma_2$.
+Dann gilt auch für die Potenzen
+\begin{equation}
+\sigma_1^k = \gamma\sigma_2^k\gamma^{-1}.
+\label{buch:permutationen:eqn:konjpot}
+\end{equation}
+Ist $Z_i$ ein Zyklus von $\sigma_2$ und $x\in Z_i$, dann ist
+$Z_i = \{ x,\sigma_2(x),\sigma_2^2(x),\dots\}$.
+Die Menge $\gamma(Z_i)$ besteht dann aus dem Elementen
+$\gamma(Z_i)=\{\gamma(x),\gamma(\sigma_2(x)),\gamma(\sigma_2^2(x)),\dots\}$.
+Aus der Formel~\eqref{buch:permutationen:eqn:konjpot} folgt
+$\sigma_1^k\gamma = \gamma\sigma_2^k$, also
+\[
+\gamma(Z_i)
+=
+\{\gamma(x),\sigma_1(\gamma(x)),\sigma_1^2(\gamma(x)),\dots\},
+\]
+Also ist $\gamma(Z_i)$ ein Zyklus von $\sigma_1$.
+Die Permutation $\gamma$ bildet also Zyklen von $\sigma_2$ auf Zyklen
+von $\sigma_1$ ab.
+Es folgt daher der folgende Satz:
+
+\begin{satz}
+Sind $\sigma_1,\sigma_2\in S_n$ konjugiert $\sigma_1=\gamma\sigma_2\gamma^{-1}$
+mit dem $\gamma\in S_n$.
+Wenn $Z_1,\dots,Z_k$ die Zyklen von $\sigma_2$ sind, dann sind 
+$\gamma(Z_1),\dots,\gamma(Z_k)$ die Zyklen von $\sigma_1$.
+\end{satz}
+
+Die Zyklenzerlegung kann mit der Jordan-Normalform \ref{XXX}
+einer Matrix verglichen werden.
+Durch einen Basiswechsel, welcher durch eine ``Konjugation''
+von Matrizen ausgedrückt wir, kann die Matrix in eine besonders 
+übersichtliche Form gebracht werden.
+Wenn $\sigma$ die Zyklenzerlegung $Z_1,\dots,Z_k$ mit Zyklenlängen
+$l_i=|Z_i|$, dann kann man die Menge $[n]$ wie folgt in Teilmengen
+\begin{align*}
+X_1 &= \{1,\dots, l_1\},
+\\
+X_2 &= \{l_1+1,\dots,l_1+l_2\},
+\\
+X_i &= \{l_1+\dots+l_{i-1}+1,\dots, l_1+\dots+l_i\}
+\\
+X_k &= \{l_1+\dots+l_{k-1}+1,\dots n\}
+\end{align*}
+zerlegen.
+Sei $\sigma_2$ die Permutation, die in jeder der Mengen $X_i$ durch
+zyklische Vertauschung der Elemente wirkt.
+Indem man die Elemente von $Z_i$ in der Reihenfolge, in der sie durch
+$\sigma_1$ erreicht werden, auf die Elemente $X_i$ abbildet, findet
+man eine Permutation, die Zyklen von $\sigma_1$ in Zyklen von $\sigma_2$
+überführt.
+
+\begin{satz}
+Wenn zwei Elemente $\sigma_1,\sigma_2\in S_n$ Zyklenzerlegungen mit den
+gleichen Zyklenlängen haben, dann sind sie konjugiert.
+\end{satz}
+
+Ein Element $\sigma\in S_n$ ist also bis auf eine Permutation
+vollständig durch die Länge der Zyklen von $\sigma$ charakterisiert.
+
+
diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex
index 3d06b0a..14aba7a 100644
--- a/buch/chapters/50-permutationen/matrizen.tex
+++ b/buch/chapters/50-permutationen/matrizen.tex
@@ -6,4 +6,191 @@
 \section{Permutationsmatrizen
 \label{buch:section:permutationsmatrizen}}
 \rhead{Permutationsmatrizen}
+Die Eigenschaft, dass eine Vertauschung das Vorzeichen kehrt, ist
+eine wohlebekannte Eigenschaft der Determinanten.
+In diesem Abschnitt soll daher eine Darstellung von Permutationen
+als Matrizen gezeigt werden und die Verbindung zwischen dem
+Vorzeichen einer Permutation und der Determinanten hergestellt
+werden.
+
+\subsection{Matrizen}
+Gegeben sei jetzt eine Permutation $\sigma\in S_n$. 
+Aus $\sigma$ lässt sich eine lineare Abbildung $\Bbbk^n\to\Bbbk^n$
+konstruieren, die die Standardbasisvektoren permutiert, also
+\[
+f_{\sigma}\colon
+\Bbbk^n \to \Bbbk^n
+:
+\left\{
+\begin{aligned}
+e_1&\mapsto e_{\sigma(1)} \\
+e_2&\mapsto e_{\sigma(2)} \\
+\vdots&\\
+e_n&\mapsto e_{\sigma(n)}
+\end{aligned}
+\right.
+\]
+Die Matrix $P_\sigma$ der linearen Abbildung $f_{\sigma}$ hat in Spalte $i$
+genau eine $1$ in der Zeile $\sigma(i)$, also
+\[
+(P_\sigma)_{ij} = \delta_{j\sigma(i)}.
+\]
+
+\begin{beispiel}
+Die zur Permutation
+\[
+\begin{pmatrix}
+1&2&3&4&5&6\\
+2&1&3&5&6&4
+\end{pmatrix}
+\]
+gehörige lineare Abbildung $f_\sigma$ hat die Matrix
+\[
+A_\sigma
+=
+\begin{pmatrix}
+0&1&0&0&0&0\\
+1&0&0&0&0&0\\
+0&0&1&0&0&0\\
+0&0&0&0&0&1\\
+0&0&0&1&0&0\\
+0&0&0&0&1&0
+\end{pmatrix}
+\qedhere
+\]
+\end{beispiel}
+
+\begin{definition}
+Eine Permutationsmatrix ist eine Matrix $P\in M_n(\Bbbk)$ 
+derart, die in jeder Zeile und Spalte genau eine $1$ enhalten,
+während alle anderen Matrixelemente $0$ sind.
+\end{definition}
+
+Es ist klar, dass aus einer Permutationsmatrix auch die Permutation
+der Standardbasisvektoren abgelesen werden kann.
+Die Verknüpfung von Permutationen wird zur Matrixmultiplikation
+von Permutationsmatrizen, die Zuordnung $\sigma\mapsto P_\sigma$
+ist also ein Homomorphismus
+$
+S_n \to M_n(\Bbbk^n),
+$
+es ist $P_{\sigma_1\sigma_2}=P_{\sigma_1}P_{\sigma_2}$.
+
+\subsection{Transpositionen}
+Transpositionen sind Permutationen, die genau zwei Elemente von $[n]$
+vertauschen.
+Wir ermitteln jetzt die Permutationsmatrix der Transposition $\tau=\tau_{ij}$
+\[
+P_{\tau_{ij}}
+=
+\begin{pmatrix}
+1&      & &      &     &      & &      & \\
+ &\ddots& &      &     &      & &      & \\
+ &      &1&      &     &      & &      & \\
+ &      & &0     &\dots&1     & &      & \\
+ &      & &\vdots&     &\vdots& &      & \\
+ &      & &1     &\dots&0     & &      & \\
+ &      & &      &     &      &1&      & \\
+ &      & &      &     &      & &\ddots& \\
+ &      & &      &     &      & &      &1
+\end{pmatrix}
+\qedhere
+\]
+
+Die Permutation $\sigma$ mit dem Zyklus $1\to 2\to\dots\to l-1\to l\to 1$
+der Länge $l$ kann aus aufeinanderfolgenden Transpositionen zusammengesetzt
+werden, die zugehörigen Permutationsmatrizen sind
+\begin{align*}
+P_\sigma
+&=
+P_{\tau_{12}}
+P_{\tau_{23}}
+P_{\tau_{34}}\dots
+P_{\tau_{l-2,l-1}}
+P_{\tau_{l-1,l}}
+\\
+&=
+\begin{pmatrix}
+0&1&0&0&\dots\\
+1&0&0&0&\dots\\
+0&0&1&0&\dots\\
+0&0&0&1&\dots\\
+\vdots&\vdots&\vdots&\vdots&\ddots
+\end{pmatrix}
+\begin{pmatrix}
+1&0&0&0&\dots\\
+0&0&1&0&\dots\\
+0&1&0&0&\dots\\
+0&0&0&1&\dots\\
+\vdots&\vdots&\vdots&\vdots&\ddots
+\end{pmatrix}
+\begin{pmatrix}
+1&0&0&0&\dots\\
+0&1&0&0&\dots\\
+0&0&0&1&\dots\\
+0&0&1&0&\dots\\
+\vdots&\vdots&\vdots&\vdots&\ddots
+\end{pmatrix}
+\dots
+\\
+&=
+\begin{pmatrix}
+0&0&1&0&\dots\\
+1&0&0&0&\dots\\
+0&1&0&0&\dots\\
+0&0&0&1&\dots\\
+\vdots&\vdots&\vdots&\vdots&\ddots
+\end{pmatrix}
+\begin{pmatrix}
+1&0&0&0&\dots\\
+0&1&0&0&\dots\\
+0&0&0&1&\dots\\
+0&0&1&0&\dots\\
+\vdots&\vdots&\vdots&\vdots&\ddots
+\end{pmatrix}
+\dots
+\\
+&=
+\begin{pmatrix}
+0&0&0&1&\dots\\
+1&0&0&0&\dots\\
+0&1&0&0&\dots\\
+0&0&1&0&\dots\\
+\vdots&\vdots&\vdots&\vdots&\ddots
+\end{pmatrix}
+\\
+&\vdots\\
+&=
+\begin{pmatrix}
+0&0&0&0&\dots&0&1\\
+1&0&0&0&\dots&0&0\\
+0&1&0&0&\dots&0&0\\
+0&0&1&0&\dots&0&0\\
+\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
+0&0&0&0&\dots&1&0
+\end{pmatrix}
+\end{align*}
+
+\subsection{Determinante und Vorzeichen}
+Die Transpositionen haben Permutationsmatrizen, die aus der Einheitsmatrix
+entstehen, indem genau zwei Zeilen vertauscht werden.
+Die Determinante einer solchen Permutationsmatrix ist
+\[
+\det P_{\tau} = - \det E = -1 = \operatorname{sgn}(\tau).
+\]
+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
+\[
+\det P_{\sigma}
+=
+\det P_{\tau_1} \dots \det P_{\tau_l}
+=
+(-1)^l
+=
+\operatorname{sgn}(\sigma).
+\]
+Das Vorzeichen einer Permutation ist also identisch mit der Determinante
+der zugehörigen Permutationsmatrix.
+
 
diff --git a/buch/chapters/50-permutationen/transpositionen.tex b/buch/chapters/50-permutationen/transpositionen.tex
index f27b20a..426ece4 100644
--- a/buch/chapters/50-permutationen/transpositionen.tex
+++ b/buch/chapters/50-permutationen/transpositionen.tex
@@ -6,3 +6,222 @@
 \section{Permutationen und Transpositionen
 \label{buch:section:permutationen-und-transpositionen}}
 \rhead{Transpositionen}
+Im vorangegangenen Abschnitt haben wir Permutationen durch die
+Zyklenzerlegung charakterisiert.
+Es zeigt sich aber, dass sich eine Permutation in noch elementarere
+Bausteine zerlegen lässt, die Transpositionen.
+
+\begin{definition}
+Einen Transposition $\tau\in S_n$ ist ein Permutation, die genau
+zwei Elemente vertauscht.
+Die Transposition $\tau_{ij}$ ist definiert durch
+\[
+\tau_{ij}(x)
+=
+\begin{cases}
+i&\qquad x=j\\
+j&\qquad x=i\\
+x&\qquad\text{sonst.}
+\end{cases}
+\]
+\end{definition}
+
+Eine Transposition hat genau einen Zyklus der Länge $2$, alle anderen
+Zyklen haben die Länge $1$.
+
+\subsection{Zyklus und Permutationen aus Transpositionen}
+Sei $\sigma$ die zyklische Vertauschung der Elemente $1,\dots,k\in [n]$,
+also die Permutation, die $1\to2\to3\to\dots\to k-2\to k-1\to k\to 1$
+abbildet.
+Dieser Zyklus lässt sich wie folgt aus Transpositionen zusammensetzen:
+\begin{center}
+\def\kreuz#1#2#3{
+	\draw[->] ({(#1)-1},#2) to[out=-90,in=90] ({#1},{#2-1});
+	\draw[->] ({#1},#2) to[out=-90,in=90] ({#1-1},{#2-1});
+	\node at ({(#1)-0.5+0.2},{#2-0.5}) [right] {$#3$};
+}
+\begin{tikzpicture}[>=latex,thick]
+\foreach \x in {1,2,3,6,7,8,9}{
+	\fill ({\x-1},0) circle[radius=0.05];
+}
+\foreach \x in {1,2,3}{
+	\node at ({\x-1},0) [above] {$\tiny \x$};
+}
+\node at (8,0) [above] {$\tiny k$};
+\node at (7,0) [above] {$\tiny k-1$};
+\node at (6,0) [above] {$\tiny k-2$};
+\node at (5,0) [above] {$\tiny k-3$};
+\foreach \x in {1,2,3,4,7,8,9}{
+	\fill ({\x-1},-8) circle[radius=0.05];
+}
+\foreach \x in {1,2,3,4}{
+	\node at ({\x-1},-8) [below] {$\tiny \x$};
+}
+\node at (6,-8) [below] {$k-2$};
+\node at (7,-8) [below] {$k-1$};
+\node at (8,-8) [below] {$k$};
+
+\foreach \x in {3,3.2,...,5}{
+	\fill (\x,{-8+\x}) circle[radius=0.02];
+	\fill ({\x+0.5},-8) circle[radius=0.02];
+	\fill ({\x-0.5},0) circle[radius=0.02];
+}
+
+\kreuz{8}{0}{\tau_{k-1,k}}
+\kreuz{7}{-1}{\tau_{k-2,k-1}}
+\kreuz{6}{-2}{\tau_{k-3,k-2}}
+%\kreuz{5}{-3}{\tau_{56}}
+%\kreuz{4}{-4}{\tau_{45}}
+\kreuz{3}{-5}{\tau_{34}}
+\kreuz{2}{-6}{\tau_{23}}
+\kreuz{1}{-7}{\tau_{12}}
+
+\draw[->,color=gray] (0,0) -- (0,-7);
+\draw[->,color=gray] (1,0) -- (1,-6);
+\draw[->,color=gray] (2,0) -- (2,-5);
+%\draw[->,color=gray] (3,0) -- (3,-4);
+%\draw[->,color=gray] (4,0) -- (4,-3);
+\draw[->,color=gray] (5,0) -- (5,-2);
+\draw[->,color=gray] (6,0) -- (6,-1);
+
+\draw[->,color=gray] (8,-1) -- (8,-8);
+\draw[->,color=gray] (7,-2) -- (7,-8);
+\draw[->,color=gray] (6,-3) -- (6,-8);
+%\draw[->,color=gray] (5,-4) -- (5,-8);
+%\draw[->,color=gray] (4,-5) -- (4,-8);
+\draw[->,color=gray] (3,-6) -- (3,-8);
+\draw[->,color=gray] (2,-7) -- (2,-8);
+	
+\fill (6,-1) circle[radius=0.05];
+\fill (7,-1) circle[radius=0.05];
+\fill (8,-1) circle[radius=0.05];
+
+\fill (5,-2) circle[radius=0.05];
+\fill (6,-2) circle[radius=0.05];
+\fill (7,-2) circle[radius=0.05];
+
+%\fill (4,-3) circle[radius=0.05];
+\fill (5,-3) circle[radius=0.05];
+\fill (6,-3) circle[radius=0.05];
+
+%\fill (3,-4) circle[radius=0.05];
+%\fill (4,-4) circle[radius=0.05];
+%\fill (5,-4) circle[radius=0.05];
+
+\fill (2,-5) circle[radius=0.05];
+\fill (3,-5) circle[radius=0.05];
+%\fill (4,-5) circle[radius=0.05];
+
+\fill (1,-6) circle[radius=0.05];
+\fill (2,-6) circle[radius=0.05];
+\fill (3,-6) circle[radius=0.05];
+
+\fill (0,-7) circle[radius=0.05];
+\fill (1,-7) circle[radius=0.05];
+\fill (2,-7) circle[radius=0.05];
+
+\end{tikzpicture}
+\end{center}
+Es ist also
+\[
+\sigma 
+=
+\tau_{12} \tau_{23} \tau_{34} \dots \tau_{k-3,k-2} \tau_{k-2,k-1} \tau_{k-1,k}.
+\]
+\begin{satz}
+Jede Permutation $\sigma\in S_n$ lässt sich als ein Produkt von 
+Transpositionen schreiben.
+Jeder Zyklus der Länge $k$ lässt sich aus $k-1$ Transpositionen
+zusammensetzen.
+Eine Permutation mit einer Zerlegung in Zyklen der Längen $l_1,\dots,l_p$
+kann als Produkt von $l_1+\dots+l_p-p$ Transpositionen geschrieben werden.
+\end{satz}
+
+\subsection{Signum einer Permutation}
+Die Anzahl Transpositionen, die benötigt werden, um eine Permutation
+zu beschreiben, ist nicht fest. 
+Wenn $\sigma$ mit $k$ Transpositionen geschrieben werden kann und
+$\gamma$ mit $l$, dann hat $\gamma\sigma\gamma^{-1}$ die gleiche
+Zyklenzerlegung, kann aber mit $k+2l$ Transpositionen geschrieben
+werden.
+Die Anzahl Transpositionen, die zur Darstellung einer Permutation
+nötig ist, ändert sich aber immer nur um eine gerade Zahl.
+Die Anzahl ist also keine Invariante einer Permutation, aber ob
+die Anzahl gerade ist oder nicht, ist sehr wohl eine charkterisierende
+Eigenschaft einer Permutation.
+
+\begin{definition}
+Das {\em Vorzeichen} oder {\em Signum} einer Permutation $\sigma$ ist
+die Zahl $\operatorname{sgn}(\sigma)=(-1)^k$, wenn $\sigma$ als Produkt
+von $k$ Transpositionen geschrieben werden kann.
+\end{definition}
+
+Die inverse Permutation $\sigma^{-1}$ hat das gleiche Signum wie $\sigma$.
+Wenn nämlich $\sigma= \tau_1\tau_2\dots\tau_k$ geschrieben werden kann,
+dann ist $\sigma^{-1}=\tau_k\dots\tau_2\tau_1$, sowohl $\sigma$ wie
+$\sigma^{-1}$ können also mit der gleichen Zahl von Transpositionen
+geschrieben werden, sie haben also auch das gleiche Vorzeichen.
+
+Die Abbildung $S_n\to\{\pm\}$, die einer Permutation das Signum zuordnet,
+ist ein Homomorphismus von Gruppen,
+d.~h.
+\[
+\operatorname{sgn}(\sigma_1\sigma_2)
+=
+\operatorname{sgn}(\sigma_1)
+\operatorname{sgn}(\sigma_2)
+\]
+da ganz offensichtlich $\sigma_1\sigma_2$ mit $k_1+k_2$ Transpositionen
+geschrieben kann, wenn $\sigma_i$ mit $k_i$ Transpositionen geschrieben
+werden kann.
+
+Das Signum definiert in der symmetrischen Gruppe eine Teilmenge bestehnd
+aus den Permutationen mit Signum $+1$.
+
+\begin{definition}
+Die Teilmenge
+\[
+A_n
+=
+\{
+\sigma\in S_n\;|\; \operatorname{sgn}(\sigma)=1
+\}
+\subset S_n.
+\]
+heisst die {\em alternierende Gruppe} der Ordnung $n$
+Die Elemente von $A_n$ heissen auch die {\em geraden} Permutationen,
+die
+Elemente von $S_n\setminus A_n$ heissen auch die {\em ungeraden}
+Permutationen.
+\end{definition}
+
+Die alternierende Gruppe $A_n$ ist tatsächlich eine Untergruppe.
+Zunächst ist $\operatorname{sign}(e)=(-1)^0=01$, also ist $e\in A_n$.
+Es wurde schon gezeigt, dass mit jedem Element $\sigma\in A_n$ auch
+das inverse Element $\sigma^{-1}\in A_n$ ist.
+Es muss aber noch sichergestellt sein, dass das Produkt von zwei
+geraden Transpositionen wieder gerade ist:
+\[
+\begin{aligned}
+\sigma_1,\sigma_2&\in A_n
+&\Rightarrow&&
+\operatorname{sign}(\sigma_1)
+&=
+\operatorname{sign}(\sigma_2)
+=
+1
+\\
+&&\Rightarrow&&
+\operatorname{sign}(\sigma_1\sigma_2)
+&=
+\operatorname{sign}(\sigma_1)
+\operatorname{sign}(\sigma_2)
+=
+1\cdot 1=1
+&&\Rightarrow&
+\sigma_1\sigma_2&\in A_n.
+\end{aligned}
+\]
+Damit ist gezeigt, dass die alternierende Gruppe $A_n$ ein Untergruppe von 
+$S_n$ ist.
+
diff --git a/buch/chapters/50-permutationen/uebungsaufgaben/5001.tex b/buch/chapters/50-permutationen/uebungsaufgaben/5001.tex
new file mode 100644
index 0000000..2893adf
--- /dev/null
+++ b/buch/chapters/50-permutationen/uebungsaufgaben/5001.tex
@@ -0,0 +1,121 @@
+Sind die beiden Permutationen
+\[
+\sigma_1
+=
+\begin{pmatrix}
+1&  2&  3&  4&  5&  6&  7&  8\\
+8&  6&  5&  7&  2&  3&  4&  1
+\end{pmatrix}
+\qquad\text{und}\qquad
+\sigma_2
+=
+\begin{pmatrix}
+1&  2&  3&  4&  5&  6&  7&  8\\
+8&  7&  5&  6&  3&  4&  1&  2
+\end{pmatrix}
+\]
+konjugiert in $S_8$?
+Wenn ja, finden Sie eine Permutation $\gamma$ derart, dass
+$\gamma\sigma_1\gamma^{-1}=\sigma_2$
+
+\begin{loesung}
+Die Zyklenzerlegungen von $\sigma_1$ und $\sigma_2$ sind
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\begin{scope}[xshift=-3.3cm]
+\node at (-0.25,1.7) {$\sigma_1$};
+\draw (-3.3,-1.3) rectangle (2.8,1.3);
+\coordinate (A) at (-2.4,0.5);
+\coordinate (B) at (-2.4,-0.5);
+\coordinate (C) at (-0.8,0.5);
+\coordinate (D) at (-0.8,-0.5);
+\coordinate (E) at (0.8,0.5);
+\coordinate (F) at (0.8,-0.5);
+\coordinate (G) at (1.8,0.5);
+\coordinate (H) at (1.8,-0.5);
+
+\draw[->] (E) to[out=-135,in=135] (F);
+\draw[->] (F) to[out=-45,in=-135] (H);
+\draw[->] (H) to[out=45,in=-45] (G);
+\draw[->] (G) to[out=135,in=45] (E);
+
+\draw[->] (A) to[out=-180,in=-180] (B);
+\draw[->] (B) to[out=0,in=0] (A);
+
+\draw[->] (C) to[out=-180,in=-180] (D);
+\draw[->] (D) to[out=0,in=0] (C);
+
+\node at (A) [above] {$1$};
+\node at (B) [below] {$8$};
+\node at (C) [above] {$4$};
+\node at (D) [below] {$7$};
+\node at (E) [above left] {$2$};
+\node at (F) [below left] {$6$};
+\node at (H) [below right] {$3$};
+\node at (G) [above right] {$5$};
+
+\fill (A) circle[radius=0.05];
+\fill (B) circle[radius=0.05];
+\fill (C) circle[radius=0.05];
+\fill (D) circle[radius=0.05];
+\fill (E) circle[radius=0.05];
+\fill (F) circle[radius=0.05];
+\fill (G) circle[radius=0.05];
+\fill (H) circle[radius=0.05];
+\end{scope}
+\begin{scope}[xshift=3.3cm]
+\node at (-0.25,1.7) {$\sigma_2$};
+\draw (-3.3,-1.3) rectangle (2.8,1.3);
+\coordinate (A) at (-2.4,0.5);
+\coordinate (B) at (-2.4,-0.5);
+\coordinate (C) at (-0.8,0.5);
+\coordinate (D) at (-0.8,-0.5);
+\coordinate (E) at (0.8,0.5);
+\coordinate (F) at (0.8,-0.5);
+\coordinate (G) at (1.8,0.5);
+\coordinate (H) at (1.8,-0.5);
+
+\draw[->] (E) to[out=-135,in=135] (F);
+\draw[->] (F) to[out=-45,in=-135] (H);
+\draw[->] (H) to[out=45,in=-45] (G);
+\draw[->] (G) to[out=135,in=45] (E);
+
+\draw[->] (A) to[out=-180,in=-180] (B);
+\draw[->] (B) to[out=0,in=0] (A);
+
+\draw[->] (C) to[out=-180,in=-180] (D);
+\draw[->] (D) to[out=0,in=0] (C);
+
+\node at (A) [above] {$3$};
+\node at (B) [below] {$5$};
+\node at (C) [above] {$4$};
+\node at (D) [below] {$6$};
+\node at (E) [above left] {$7$};
+\node at (F) [below left] {$1$};
+\node at (H) [below right] {$8$};
+\node at (G) [above right] {$2$};
+
+\fill (A) circle[radius=0.05];
+\fill (B) circle[radius=0.05];
+\fill (C) circle[radius=0.05];
+\fill (D) circle[radius=0.05];
+\fill (E) circle[radius=0.05];
+\fill (F) circle[radius=0.05];
+\fill (G) circle[radius=0.05];
+\fill (H) circle[radius=0.05];
+\end{scope}
+\end{tikzpicture}
+\end{center}
+Da die beiden Permutationen die gleiche Zyklenzerlegung haben, müssen
+sie konjugiert sein.
+Die Permutation
+\[
+\gamma
+=
+\begin{pmatrix}
+1&2&3&4&5&6&7&8\\
+6&5&1&4&8&7&2&3
+\end{pmatrix}
+\]
+bildet die Zyklenzerlegung ab, also ist $\gamma\sigma_1\gamma^{-1}=\sigma_2$.
+\end{loesung}