path: root/buch/chapters/50-permutationen/endlich.tex

%
% endlich.tex -- Permutationen einer endlichen Menge
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\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
\label{buch: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$ derart, dass
$\sigma_1=\gamma\sigma_2\gamma^{-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.