aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@othello.ch>2021-01-19 22:08:40 +0100
committerAndreas Müller <andreas.mueller@othello.ch>2021-01-19 22:08:40 +0100
commit45794fb198c8fac02b5c82b6ac3f1e17bac1075e (patch)
tree038f99ee46536f8f46e48358454c5868c429af09 /buch/chapters
parentrepurposing spectral radius section (diff)
downloadSeminarMatrizen-45794fb198c8fac02b5c82b6ac3f1e17bac1075e.tar.gz
SeminarMatrizen-45794fb198c8fac02b5c82b6ac3f1e17bac1075e.zip
Permutationen hinzugefügt
Diffstat (limited to 'buch/chapters')
-rw-r--r--buch/chapters/40-eigenwerte/beispiele/jp.maxima19
-rw-r--r--buch/chapters/40-eigenwerte/beispiele/n.m55
-rw-r--r--buch/chapters/40-eigenwerte/beispiele/n.maxima20
-rw-r--r--buch/chapters/40-eigenwerte/spektralradius.tex351
-rw-r--r--buch/chapters/50-permutationen/beispiele/perm.m44
-rw-r--r--buch/chapters/50-permutationen/chapter.tex15
-rw-r--r--buch/chapters/50-permutationen/endlich.tex288
-rw-r--r--buch/chapters/50-permutationen/matrizen.tex187
-rw-r--r--buch/chapters/50-permutationen/transpositionen.tex219
-rw-r--r--buch/chapters/50-permutationen/uebungsaufgaben/5001.tex121
10 files changed, 1319 insertions, 0 deletions
diff --git a/buch/chapters/40-eigenwerte/beispiele/jp.maxima b/buch/chapters/40-eigenwerte/beispiele/jp.maxima
new file mode 100644
index 0000000..a80a0a2
--- /dev/null
+++ b/buch/chapters/40-eigenwerte/beispiele/jp.maxima
@@ -0,0 +1,19 @@
+/*
+ * jp.maxima -- potenzen von Jordan-Blöcken
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+
+A: matrix(
+[lambda, 1, 0, 0, 0, 0 ],
+[ 0,lambda, 1, 0, 0, 0 ],
+[ 0, 0,lambda, 1, 0, 0 ],
+[ 0, 0, 0,lambda, 1, 0 ],
+[ 0, 0, 0, 0,lambda, 1 ],
+[ 0, 0, 0, 0, 0,lambda ]
+);
+B: A.A;
+B: B.A;
+B: B.A;
+B: B.A;
+B: B.A;
diff --git a/buch/chapters/40-eigenwerte/beispiele/n.m b/buch/chapters/40-eigenwerte/beispiele/n.m
new file mode 100644
index 0000000..af0219b
--- /dev/null
+++ b/buch/chapters/40-eigenwerte/beispiele/n.m
@@ -0,0 +1,55 @@
+#
+# n.m -- Polynome mit dem gleichen Wert von p(A)
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+
+A0 = [
+ 2, 1, 0;
+ 0, 2, 0;
+ 0, 0, 3
+];
+
+# find a 3x3 matrix in SL(3,Z)
+
+function retval = zufallswert()
+ x = round(rand() * 10) - 2;
+ if (x >= 0)
+ x = x + 1;
+ endif
+ retval = x;
+end
+
+function retval = zufallsmatrix(n)
+ retval = zeros(n, n);
+ for i = (1:n)
+ for j = (1:n)
+ retval(i,j) = zufallswert();
+ end
+ end
+end
+
+function retval = regulaer(n)
+ d = 0;
+ do
+ retval = zufallsmatrix(2);
+ d = det(retval);
+ until (d == 1);
+end
+
+function retval = eingebettet(n,k)
+ retval = eye(n);
+ retval(k:k+1,k:k+1) = regulaer(2);
+end
+
+format long
+
+B = eye(3);
+B = B * eingebettet(3,2)
+B = B * eingebettet(3,1)
+
+B
+inverse(B)
+
+A = round(B * A0 * inverse(B))
+
diff --git a/buch/chapters/40-eigenwerte/beispiele/n.maxima b/buch/chapters/40-eigenwerte/beispiele/n.maxima
new file mode 100644
index 0000000..9ed83b6
--- /dev/null
+++ b/buch/chapters/40-eigenwerte/beispiele/n.maxima
@@ -0,0 +1,20 @@
+/*
+ * n.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+A: matrix(
+ [ 1, 9, -4 ],
+ [ -1, 3, 0 ],
+ [ -2, 0, 3 ]
+);
+
+p: expand(charpoly(A,x));
+factor(p);
+
+A.A;
+A.A.A;
+
+A.A - 5*A;
+
+A.A.A -7*A.A +16 *A;
diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex
index 0c99106..3afac18 100644
--- a/buch/chapters/40-eigenwerte/spektralradius.tex
+++ b/buch/chapters/40-eigenwerte/spektralradius.tex
@@ -6,19 +6,365 @@
\section{Funktionen einer Matrix
\label{buch:section:funktionen-einer-matrix}}
\rhead{Funktionen einer Matrix}
+Eine zentrale Motivation in der Entwicklung der Eigenwerttheorie
+war das Bestreben, Potenzen $A^k$ auch für grosse $k$ effizient
+zu berechnen.
+Mit der Jordan-Normalform ist dies auch gelungen, wenigstens über
+einem Körper, in dem das charakteristische Polynom in Linearfaktoren
+zerfällt.
+Die Berechnung von Potenzen war aber nur der erste Schritt, das Ziel
+in diesem Abschnitt ist, $f(A)$ für eine genügend grosse Klasse von
+Funktionen $f$ berechnen zu können.
%
% Polynom-Funktionen von Matrizen
%
\subsection{Polynom-Funktionen
\label{buch:subsection:polynom-funktionen}}
+In diesem Abschnitt ist $B\in M_n(\Bbbk)$ und $\Bbbk'\supset\Bbbk$ ein
+Körper, über dem das charakteristische Polynome $\chi_A(x)$ in
+Linearfaktoren
+\[
+\chi_A(x)
+=
+(\lambda_1-x)^{m_1}(\lambda_2-x)^{m_2}\cdot\ldots\cdot(\lambda_p-x)^{m_p}
+\]
+zerfällt.
+
+Für jedes beliebige Polynome $p(X)=\Bbbk[X]$ der Form
+\[
+p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0
+\]
+kann man auch
+\[
+p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots a_1A + a_0E
+\]
+berechnen.
+In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengstellt
+werden, sobald man die Potenzen von Jordan-Blöcken berechnet hat.
+\begin{satz}
+Die $k$-te Potenz von $J_n(\lambda)$ ist die Matrix mit
+\begin{equation}
+J_n(\lambda)^k
+=
+\begin{pmatrix}
+\lambda^k
+ & \binom{k}{1}\lambda^{k-1}
+ & \binom{k}{2} \lambda^{k-2}
+ & \binom{k}{3} \lambda^{k-3}
+ & \dots
+ &\binom{k}{n-1}\lambda^{k-n+1}
+\\
+0
+ & \lambda^k
+ & \binom{k}{1}\lambda^{k-1}
+ & \binom{k}{2} \lambda^{k-2}
+ & \dots
+ &\binom{k}{n-2}\lambda^{k-n+2}
+\\
+0
+ & 0
+ & \lambda^k
+ & \binom{k}{1}\lambda^{k-1}
+ & \dots
+ &\binom{k}{n-3}\lambda^{k-n+3}
+\\
+\vdots &\vdots &\vdots &\vdots &\ddots & \vdots
+\\
+0 & 0 & 0 & 0 & \dots & \lambda^k
+\end{pmatrix}
+\label{buch:eigenwerte:eqn:Jnkpotenz}
+\end{equation}
+mit den Matrixelementen
+\[
+(J_n(\lambda)^k)_{ij}
+=
+\binom{k}{j-i}\lambda^{k-j+i}
+\]
+Die Binomialkoeffizienten verschwinden für $j<i$ und $j>i+k$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Die Herkunft der Binomialkoeffizienten wird klar, wenn man
+\[
+J_n(\lambda) = \lambda E + N_n
+\]
+schreibt, wobei $N_n$ die Matrix \eqref{buch:eigenwerte:eqn:nnilpotent} ist.
+Die Potenzen von $N_n$ haben die Matrix-Elemente
+\[
+(N_n^k)_{ij}
+=
+\delta_{i,j-k}
+=
+\begin{cases}
+1&\qquad j-i=k\\
+0&\qquad\text{sonst,}
+\end{cases}
+\]
+sie haben also Einsen genau dort, wo in der
+\label{buch:eigenwerte:eqn:Jnkpotenz} die Potenz $\lambda^{k}$ steht.
+Die $kt$-te Potenz von $J_n(\lambda)$ kann dann mit dem binomischen
+Satz berechnet werden:
+\[
+J_n(\lambda)^k
+=
+\sum_{l=0}^k \binom{k}{l}\lambda^l N_n^{k-l},
+\]
+dies ist genau die Form \eqref{buch:eigenwerte:eqn:Jnkpotenz}.
+\end{proof}
+
+Wir haben bereits gesehen, dass $\chi_A(A)=0$, ersetzt man also das
+Polynom $p(X)$ durch $p(X)+\chi_A(X)$, dann ändert sich am Wert
+\[
+(p+\chi_A)(A)
+=
+p(A) + \chi_A(A)
+=
+p(A)
+\]
+nichts.
+Man kann also nicht erwarten, dass verschiedene Polynome
+$p(X)$ zu verschiedenen Matrizen $p(A)$ führen.
+Doch welche Unterschiede zwischen Polynomen wirken sich genau aus?
+
+\begin{satz}
+Für zwei Polynome $p(X)$ und $q(X)$ ist genau dann $p(A)=q(A)$, wenn
+das Minimalpolynom von $A$ die Differenz $p-q$ teilt.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wenn $p(A)=q(A)$, dann ist $h(X)=p(X)-q(X)$ ein Polynom mit $h(A)=0$,
+daher muss $h(X)$ vom Minimalpolynom geteilt werden.
+Ist andererseits $p(X)-q(X)=m(X)t(X)$, dann ist
+$p(A)-q(A)=m(A)t(A)=0\cdot t(A) = 0$, also $p(A)=q(A)$.
+\end{proof}
+
+Über einem Körper $\Bbbk'\supset\Bbbk$, über dem das charakteristische
+Polynom in Linearfaktoren zerfällt, kann man das Minimalpolynom aus
+der Jordanschen Normalform ableiten.
+Es ist
+\[
+m(X)
+=
+(\lambda_1-X)^{q_1}
+(\lambda_2-X)^{q_2}
+\cdot\ldots
+\cdot
+(\lambda_p-X)^{q_p},
+\]
+wobei $q_i$ die Dimension des grössten Jordan-Blocks ist, der in der
+Jordan-Normalform vorkommt.
+Zwei Polynome $p_1(X)$ und $p_2(X)$ haben genau dann den gleichen Wert,
+wenn die Differenz $p_1(X)-p_2(X)$ genau die Nullstellen
+$\lambda_1,\dots,\lambda_p$ mit Vielfachheiten $q_1,\dots,q_p$ hat.
+
+\begin{beispiel}
+Wir betrachten die Matrix
+\[
+A
+=
+\begin{pmatrix}
+ 1& 9& -4\\
+ -1& 3& 0\\
+ -2& 0& 3
+\end{pmatrix}
+\]
+mit dem charakteristischen Polynom
+\[
+\chi_A(x)
+=
+-x^3+7x^2-16 x+12
+=
+-(x-3)(x-2)^2.
+\]
+Daraus kann man bereits ablesen, dass das Minimalpolynom $m(X)$ von $A$
+entweder $(X-2)(X-3)$ oder $(X-2)^2(X-3)$ ist.
+Es genügt also nachzuprüfen, ob $p(A)=0$ für das Polynom
+$p(X)=(X-2)(X-3) = X^2-5X+6$ ist.
+Tatsächlich sind die Potenzen von $A$:
+\[
+A^2=
+\begin{pmatrix}
+ 0& 36& -16 \\
+ -4& 0& 4 \\
+ -8& -18& 17
+\end{pmatrix}
+,\qquad
+A^3=
+\begin{pmatrix}
+ -4& 108& -48\\
+-12& -36& 28\\
+-24&-126& 83
+\end{pmatrix}
+\]
+und daraus kann man jetzt $P(A)$ berechnen:
+\begin{equation}
+p(A)
+=
+\begin{pmatrix}
+ 0& 36& -16 \\
+ -4& 0& 4 \\
+ -8& -18& 17
+\end{pmatrix}
+-5
+\begin{pmatrix}
+ 1& 9& -4\\
+ -1& 3& 0\\
+ -2& 0& 3
+\end{pmatrix}
++
+6
+\begin{pmatrix}
+1&0&0\\
+0&1&0\\
+0&0&1
+\end{pmatrix}
+=
+\begin{pmatrix}
+ 1& -9& 4\\
+ 1& -9& 4\\
+ 2&-18& 8
+\end{pmatrix}
+=
+\begin{pmatrix}1\\1\\2\end{pmatrix}
+\begin{pmatrix}1&-9&4\end{pmatrix}
+\label{buch:eigenwerte:eqn:nichtminimalpolynom}
+\end{equation}
+Also ist tatsächlich $(X-2)^2(X-3)$ das Minimalpolynom.
+
+Das Quadrat des Polynoms $p(X)$ ist $p(X)^2 = (X-2)^2(X-3)^2$, es hat
+das Minimalpolynom als Teiler, also muss $p(A)^2=0$ sein.
+Die Gleichung \eqref{buch:eigenwerte:eqn:nichtminimalpolynom} ermöglicht,
+das Quaddrat $p(A)^2$ leichter zu berechnen:
+\[
+p(A)^2
+=
+\begin{pmatrix}1\\1\\2\end{pmatrix}
+\underbrace{
+\begin{pmatrix}1&-9&4\end{pmatrix}
+\begin{pmatrix}1\\1\\2\end{pmatrix}
+}_{\displaystyle = 0}
+\begin{pmatrix}1&-9&4\end{pmatrix}
+=
+0
+,
+\]
+wie zu erwarten war.
+
+Wenn sich zwei Polynome nur um das charakteristische Polynom unterscheiden,
+dann haben sie den gleichen Wert auf $A$.
+Das Polynom $p_1(X)=X^3$ unterschiedet sich vom Polynom $p_2(X)=7X^2-16X+12$
+um das charakteristische Polynom, welches wir bereits als das Minimalpolynom
+von $A$ erkannt haben.
+Die dritte Potenz $A^3$ von $A$ muss sich daher auch mit $p_2(X)$ berechnen
+lassen:
+\[
+7
+\begin{pmatrix}
+ 0& 36& -16 \\
+ -4& 0& 4 \\
+ -8& -18& 17
+\end{pmatrix}
+-16
+\begin{pmatrix}
+ 1& 9& -4\\
+ -1& 3& 0\\
+ -2& 0& 3
+\end{pmatrix}
++12
+\begin{pmatrix}
+1&0&0\\
+0&1&0\\
+0&0&1
+\end{pmatrix}
+=
+\begin{pmatrix}
+ -4& 108& -48\\
+-12& -36& 28\\
+-24&-126& 83
+\end{pmatrix}
+=
+A^3.
+\qedhere
+\]
+\end{beispiel}
+
+\begin{satz}
+Wenn $A$ diagonalisierbar ist über einem geeignet erweiterten Körper $\Bbbk'$,
+dann haben zwei Polynome $p(X)$ und $q(X)$ in $\Bbbk[X]$ genau dann
+den gleichen Wert auf $A$, also $p(A)=q(A)$, wenn $p(\lambda) = q(\lambda)$
+für alle Eigenwerte $\lambda$ von $A$.
+\end{satz}
+
+Über dem Körper der komplexen Zahlen ist die Bedingung, dass die Differenz
+$d(X)=p_1(X)-p_2(X)$ vom Minimalpolynom geteilt werden muss, gleichbedeutend
+damit, dass $p_1(X)$ und $p_2(X)$ den gleichen Wert und gleiche Ableitungen
+bis zur Ordnung $q_i-1$ haben in allen Eigenwerten $\lambda_i$, wobei
+$q_i$ der Exponent von $\lambda_i-X$ im Minimalpolynom von $A$ ist.
+
+Das Beispiel illustriert auch noch ein weiteres wichtiges Prinzip.
+Schreiben wir das Minimalpolynom von $A$ in der Form
+\[
+m(X)
+=
+X^k + a_{k-1}X^{k-1} + \dots + a_1X + a_0,
+\]
+dann kann man wegen $m(A)=0$ die Potenzen $A^i$ mit $i\ge k$ mit der
+Rekursionsformel
+\[
+A^i
+=
+A^{i-k}A^k
+=
+A^{i-k}(-a_{k-1}A^{k-1}+ \dots + a_1 A + a_0E)
+\]
+in einer Linearkombination kleinerer Potenzen reduzieren.
+Jedes Polynom vom Grad $\ge k$ kann also reduizert werden in
+ein Polynom vom Grad $<k$ mit dem gleichen Wert auf $A$.
+
+\begin{satz}
+\label{buch:eigenwerte:satz:reduktion}
+Sei $A$ eine Matrix über $\Bbbk$ mit Minimalpolynom $m(X)$.
+Zu jedem $p(X)\in\Bbbk[X]$ gibt es ein Polynom $q(X)\in\Bbbk[X]$
+vom Grad $\deg q<\deg m$ mit $p(A)=q(A)$.
+\end{satz}
%
% Approximationen für Funktionswerte f(A)
%
\subsection{Approximation von $f(A)$
\label{buch:subsection:approximation}}
+Die Quadratwurzelfunktion $x\mapsto\sqrt{x}$ lässt sich nicht durch ein
+Polynom darstellen, es gibt also keine direkte Möglichkeit, $\sqrt{A}$
+für eine beliebige Matrix zu definieren.
+Wir können versuchen, die Funktion durch ein Polynom zu approximieren.
+Damit dies geht, müssen wir folgende zwei Fragen klären:
+\begin{enumerate}
+\item
+Wie misst man, ob ein Polynom eine Funktion gut approximiert?
+\item
+Was bedeutet es genau, dass zwei Matrizen ``nahe beeinander'' sind?
+\item
+In welchem Sinne müssen Polynome ``nahe'' beeinander sein, damit
+auch die Werte auf $A$ nahe beeinander sind.
+\end{enumerate}
+
+Wir wissen bereits, dass nur die Werte und gewisse Ableitungen des
+Polynoms $p(X)$ in den Eigenwerten einen Einfluss auf $p(A)$ haben.
+Es genügt also, Approximationspolynome zu verwenden, welche in der Nähe
+der Eigenwerte ``gut genug'' approximieren.
+Solche Polynome gibt es dank dem Satz von Stone-Weierstrass immer:
+
+\begin{satz}[Stone-Weierstrass]
+Ist $I\subset\mathbb{R}$ kompakt, dann lässt sich jede stetige Funktion
+durch eine Folge $p_n(x)$ beliebig genau approximieren.
+\end{satz}
+
+Wir haben schon gezeigt, dass es dabei auf die höheren Potenzen gar nicht
+ankommt, nach Satz~\ref{buch:eigenwerte:satz:reduktion} kann man ein
+approximierendes Polynom immer durch ein Polynom von kleinerem Grad
+als das Minimalpolynom ersetzen.
\begin{definition}
\index{Norm}%
@@ -60,6 +406,11 @@ konvergieren, weil der Fehler nach jedem zweiten Schritt um den
Faktor $\frac23$ kleiner geworden ist.
\end{beispiel}
+\begin{beispiel}
+Wir berechnen die Norm eines Jordan-Blocks.
+
+\end{beispiel}
+
%
% Potenzreihen für Funktionen $f(z)$
%
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}