8.3 Permutationen

In diesem Abschnitt beschäftigen wir uns genauer mit der Struktur der symmetrischen Gruppe $S_n$, also der Gruppe aller bijektiven Abbildungen $\{ 1, \dots , n\} \to \{ 1, \dots , n\} $, wo die Gruppenstruktur durch die Verknüpfung von Abbildungen gegeben ist. Wir schreiben meistens $\sigma \tau $ statt $\sigma \circ \tau $. Die symmetrischen Gruppen sind wichtige Beispiele von endlichen Gruppen. Zudem ist das Material aus diesem Abschnitt auch wichtig für das Studium der Determinante im Kapitel 9.

Anstelle von Bijektionen von $\{ 1, \dots , n\} $ kann man natürlich ebenso gut Bijektionen irgendeiner $n$-elementigen Menge mit sich selbst betrachten. (Ganz formal gesagt erhält man dann eine zu $S_n$ isomorphe Gruppe.) Man spricht daher auch von Permutationen »von $n$ Symbolen« oder von der »symmetrischen Gruppe auf $n$ Buchstaben«. Die Anzahl der Elemente von $S_n$ ist $n! = 1\cdot 2\cdot \cdots \cdot n$.

Definition 8.35

Eine bijektive Abbildung $\{ 1, \dots , n\} \to \{ 1, \dots , n\} $, also ein Element von $S_n$, nennen wir auch Permutation.

Um eine Permutation $\sigma $ konkret anzugeben, können wir die Werte $\sigma (1)$ bis $\sigma (n)$ der Reihe nach auflisten. Dazu schreibt man die Permutation in der Regel als zweizeilige Matrix, in deren erster Zeile die Zahlen $1$ bis $n$, und in deren zweiten Zeile der jeweilige Wert eingetragen ist. Zum Beispiel können wir für $n=7$ die folgende Permutation betrachten:

\[ \sigma = \left( \begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 5 & 3 & 2 & 4 & 7 & 1 & 6 \end{array} \right) \]

(Also $\sigma (1) = 5$, $\sigma (2) = 3$, usw.)

Eine andere Möglichkeit, eine Permutation darzustellen, ist mit Diagrammen der nebenstehenden Form. Die eingezeichneten Pfeile geben die Zuordnungsvorschrift der Abbildung $\{ 1, \dots , n\} \to \{ 1, \dots , n\} $ an. Die gezeigten Beispiele entsprechen den Permutationen

\[ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 6 & 1 & 2 & 5 & 3 \end{pmatrix} \]

und

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 5 & 2 & 6 & 4 \end{pmatrix}. \]

$\includegraphics[width=5.9cm]{figures/permutation1}$
.
$\includegraphics[width=5.9cm]{figures/permutation6}$

Wenn man die Permutationen so »aufschreibt«, dann erhält man die Verkettung $\tau \sigma $, indem man die beiden Abbildungen einfach direkt untereiander zeichnet.

\[ \sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 3 & 6 & 5 \end{pmatrix} \]

$\includegraphics[width=5.9cm]{figures/permutation3}$

Definition 8.36

Ein Zykel der Ordnung $l$ (oder: ein $l$-Zykel) ist eine Permutation $\sigma \in S_n$, so dass eine Teilmenge $I=\{ i_1, \dots , i_l \} \subseteq \{ 1,\dots , n\} $ mit $l$ Elementen existiert, so dass

\[ \sigma (i_1)=i_2,\quad \sigma (i_2)=i_3,\quad \dots ,\quad \sigma (i_{l-1})=\sigma (i_l),\quad \sigma (i_l)=i_1 \]

und $\sigma (j) = j$ für alle $j \not \in \{ i_1, \dots , i_l\} $ gilt. Die Menge $I$ heißt dann der Träger des Zykels $\sigma $.

Wir schreiben dann $\sigma = (i_1, i_2, \dots , i_l)$ (wenn keine Missverständnisse zu befürchten sind, schreibt man die Einträge $i_\lambda $ auch ohne Kommata nebeneinander).

Man beachte, dass zum Beispiel $(1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3)$ alle denselben Zykel der Ordnung $4$ bezeichnen.

Sind $\sigma ,\tau \in S_n$ Zykel, deren Träger disjunkt sind, dann gilt $\sigma \tau =\tau \sigma $. Die folgende »Rechenregel« ist oft nützlich und leicht zu überprüfen:

Lemma 8.37

Sei $\pi \in S_n$ und sei $(i_1,\dots , i_l)\in S_n$ ein Zykel der Ordnung $l$. Dann gilt

\[ \pi \, (i_1,\dots , i_l)\, \pi ^{-1} = (\pi (i_1),\dots , \pi (i_l)). \]

Ergänzung 8.38 Zerlegung in Zykel mit disjunkten Trägern

Satz 8.39

Jede Permutation $\sigma \in S_n$ lässt sich als Produkt von Zykeln der Ordnung ${\gt} 1$ mit paarweise disjunkten Trägern schreiben. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig.

Wir verstehen den Satz so, dass die Identität als das leere Produkt geschrieben wird.

Beweis

Sei $\sigma \in S_n$. Wir nennen eine Teilmenge $I\subseteq \{ 1,\dots , n\} $ stabil unter $\sigma $, wenn $\sigma (I)=I$ gilt und nennen (nur in diesem Beweis) eine minimale nicht-leere $\sigma $-stabile Teilmenge eine Komponente von $\sigma $.

Dass eine Komponente aus einem einzigen Element $i$ besteht, bedeutet einfach, dass $\sigma (i)=i$ gilt. Komponenten mit nur einem Element nennen wir trivial.

Ist $i\in \{ 1,\dots n\} $, so ist die Menge $\{ \sigma ^r(i);\ r\in \mathbb N\} $ eine Komponente. Das ist klar, wenn $\sigma (i)=i$ ist. Andernfalls argumentieren wir wie folgt. Da $S_n$ endlich ist, handelt es sich natürlich um eine endliche Menge: Es gibt $r {\lt} r^\prime $ mit $\sigma ^r(i)=\sigma ^{r^\prime }(i)$, also $\sigma ^{r^\prime -r}(i) = i$. Daran sehen wir, dass die Menge $\{ \sigma ^r(i);\ r\in \mathbb N\} $ eine $\sigma $-stabile Menge ist, und auch, dass es sich um eine Komponente von $\sigma $ handelt. Denn ist $j$ irgendein Element dieser Menge, so folgt $\{ \sigma ^r(i); r\in \mathbb N\} = \{ \sigma ^r(j);\ r\in \mathbb N\} $. Die einzige echte $\sigma $-stabile Teilmenge ist also die leere Menge. Es ist dann klar, dass alle Komponenten diese Form haben.

Wir führen nun Induktion nach der Anzahl der nicht-trivialen Komponenten von $\sigma $. Gibt es keine nicht-triviale Komponente, dann ist $\sigma = \operatorname{id}$, und dies ist das leere Produkt von Zykeln.

Sei nun $I$ eine Komponente von $\sigma $ mit $l{\gt}1$ Elementen, und sei $i\in I$. Sei $\tau $ der Zykel $(i, \sigma (i), \sigma ^2(i),\dots , \sigma ^{l-1}(i))$. Dass $\tau $ ein Zykel ist, folgt aus der Beschreibung der Komponenten von $\sigma $, die wir oben gegeben haben.

Dann gilt $\tau ^{-1}\sigma (j) = \sigma (j)$ für $j\not \in I$ und $\tau ^{-1}\sigma (i)=i$ für $i\in I$. Daher hat $\tau ^{-1}\sigma (j)$ eine nicht-triviale Komponente weniger als $\sigma $, ist also nach Induktionsvoraussetzung das Produkt $\sigma _1\cdots \sigma _k$ von Zykeln mit paarweise disjunkten Trägern. Dann ist $\sigma = \tau \sigma _1\cdots \sigma _k$. Weil $\tau ^{-1}\sigma (i)=i$ für $i\in I$, ist $I$ disjunkt zu den Trägern der $\sigma _i$. Daraus folgt die Existenz der Zerlegung als Produkt von Zykeln mit disjunkten Trägern.

Die Eindeutigkeit ergibt sich mit ähnlichen Argumenten.

$\begin{tikzpicture} [>=Stealth] \graph [simple necklace layout, nodes={circle,minimum size=.7cm,draw}, node sep=1cm]{ 1,2,3,4,5,6,7,8,9; 1->[ultra thick, green] 4 ->[ultra thick, green] 2 ->[ultra thick, green] 1, 3 ->[ultra thick, blue] 8 ->[ultra thick, blue] 6 ->[ultra thick, blue] 9 ->[ultra thick, blue] 7 ->[ultra thick, blue] 3; 5 ->[ultra thick, loop below] 5; }; \end{tikzpicture}$

Die Zerlegung in Zykel mit disjunktem Träger im Beispiel:

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 1 & 8 & 2 & 5 & 9 & 3 & 6 & 7 \end{pmatrix}\\ & = (142)(38697). \end{align*}

Ein besonders wichtiger Fall ist der der Zykel der Ordnung $2$.

Definition 8.40

Eine Transposition in $S_n$ ist ein Zykel der Ordnung $2$, d.h. eine Permutation, die zwei Zahlen $i\ne j$ vertauscht und alle anderen Zahlen festlässt.

Eine elementare Transposition in $S_n$ ist eine Transposition der Form $(i, i+1)$, $i\in \{ 1, \dots , n-1\} $.

Die Matrix $P_{ij}$ aus Bemerkung 5.37 ist die Permutationsmatrix $P_\tau $ (Definition 8.25) für die Transposition $\tau =(i\, j)$.

Lemma 8.41

Jede Permutation lässt sich als Produkt von Transpositionen schreiben. (Sogar: als Produkt von elementaren Transpositionen. Mit anderen Worten: Die elementaren Transpositionen erzeugen die Gruppe $S_n$.)

Die Aussage des Lemmas ist so zu verstehen, dass dieselbe (elementare) Transposition auch mehrfach vorkommen darf. Zum Beispiel gilt $(1 3) = (1 2) (2 3) (1 2)$.

Beweis

Es genügt natürlich, die Behauptung über elementare Transpositionen zu beweisen. Wir tun das durch Induktion nach $n$. Für $n=1$ (und $n=2$) ist die Sache klar. Nun nehmen wir an, dass sich jede Permutation in $S_{n-1}$ als Produkt elementarer Transpositionen schreiben lässt. Es ist dann klar, dass sich auch jede Permutation $\sigma \in S_n$ mit der Eigenschaft $\sigma (n)=n$ als Produkt der elementaren Transpositionen $(1,2)$, …, $(n-2, n-1)$ schreiben lässt.

Ist $\sigma \in S_n$ eine beliebige Transposition, so können wir $\sigma $ von links mit elementaren Transpositionen multiplizieren um zu erreichen, dass $n$ auf sich selbst abgebildet wird. Damit sind wir in dem bereits abgehandelten Fall.

Definition 8.42

Sei $\sigma \in S_n$ eine Permutation.

Ein Paar $(i,j)$, $1\le i,j\le n$, heißt Fehlstand der Permutation $\sigma $, wenn $i {\lt} j$ und $\sigma (i) {\gt} \sigma (j)$.
Die Länge $l(\sigma )$ von $\sigma $ ist die Anzahl der Fehlstände:

\[ l(\sigma ) = \# \{ (i,j);\ 1\le i {\lt} j \le n,\ \sigma (i) {\gt} \sigma (j) \} . \]
Das Signum $\operatorname{sgn}(\sigma )$ von $\sigma $ ist definiert als

\[ \operatorname{sgn}(\sigma ) := (-1)^{l(\sigma )}, \]

mit anderen Worten: Ist $l(\sigma )$ gerade, so ist $\operatorname{sgn}(\sigma ) = 1$ (und man nennt $\sigma $ dann auch eine gerade Permutation). Ist $l(\sigma )$ ungerade, so ist $\operatorname{sgn}(\sigma ) = -1$ (und man nennt $\sigma $ dann auch eine ungerade Permutation).

Es gilt $l(\operatorname{id})=0$, und die Identität ist die einzige Permutation der Länge $0$. Wir verstehen das Signum einer Permutation, also $1$ bzw. $-1$, als ganze Zahl.

Man beachte: Ist $\sigma $ ein Zykel, so ist die Länge $l(\sigma )$ in der Regel verschieden von der Zykelordnung, und auch nicht allein durch die Zykelordnung bestimmt! Zum Beispiel gilt $l((1 2)) = 1$, $l((1 3)) = 3$.

$\includegraphics[width=5.9cm]{figures/permutation6}$

Die Länge oder Anzahl der Fehlstände einer Permutation ist in einer visuellen Darstellung wie hier gezeigt einfach die Anzahl von Schnittpunkten der Verbindungslinien. Die hier gezeigte Permutation hat also Länge $4$, ihr Signum ist folglich gleich $1$.

Ergänzung 8.43 Länge und reduzierte Darstellungen

Man kann zeigen (und so erklärt sich der Name Länge), dass für eine Permutation $\sigma $ die Länge $l(\sigma )$ die minimale Anzahl von Faktoren ist, die man braucht, um $\sigma $ als Produkt von elementaren Transpositionen darzustellen.

Lemma 8.44

Ist $\sigma $ eine Transposition, $\tau \in S_n$ irgendeine Permutation, so gilt $\operatorname{sgn}(\tau \sigma ) = -\operatorname{sgn}(\tau )$.

Insbesondere gilt $\operatorname{sgn}(\sigma )=-1$: alle Transpositionen sind ungerade Permutationen.

Beweis

Sei zunächst $\sigma $ eine elementare Transposition $(i, i+1)$. Für $j=1,\dots , i-1$ und $j=i+2,\dots , n$ gilt $\tau \sigma (j) = \tau (j)$. Je nachdem, ob $\tau (i) {\lt} \tau (i+1)$ oder $\tau (i){\gt}\tau (i+1)$ hat also $\tau \sigma $ gerade einen Fehlstand mehr oder einen Fehlstand weniger als $\tau $. In beiden Fällen folgt mithin $\operatorname{sgn}(\tau \sigma ) = -\operatorname{sgn}(\tau )$.

Nun behandeln wir den Fall einer beliebigen Transposition $\sigma = (i\, j)$. Nach dem vorherigen Fall genügt es zu zeigen, dass wir $\sigma $ als ein Produkt von elementaren Transpositionen mit einer ungeraden Anzahl von Faktoren schreiben können. Sei ohne Einschränkung $i {\lt} j$. Dann gilt für $\pi = (i, j-1)$ (wegen Lemma 8.37):

\[ (i\, j) = \pi \, (j-1, j)\, \pi ^{-1} \]

Schreiben wir $\pi $ als Produkt von elementaren Transpositionen, so ist die Anzahl der Faktoren in dem Produkt $\pi \, (j-1, j)\, \pi ^{-1}$ offenbar ungerade (denn jede Transposition ist zu sich selbst invers).

Der zweite Teil folgt, indem wir den ersten Teil mit $\tau =\operatorname{id}$ anwenden.

Satz 8.45

Sind $\sigma , \tau \in S_n$, so gilt

\[ \operatorname{sgn}(\sigma \tau ) = \operatorname{sgn}(\sigma )\operatorname{sgn}(\tau ). \]

Beweis

Wir haben gesehen, dass wir $\tau $ als ein Produkt von Transpositionen schreiben können. Ist $r$ die Anzahl der Faktoren, so gilt $\operatorname{sgn}(\tau )=(-1)^r$. Aus dem vorherigen Lemma folgt $\operatorname{sgn}(\sigma \tau ) = (-1)^r\, \operatorname{sgn}(\sigma )$.

Betrachten wir $\{ -1, 1\} $ als Gruppe bezüglich der Multiplikation, so können wir den vorherigen Satz auch wie folgt ausdrücken:

Korollar 8.46

Die Abbildung $\operatorname{sgn}\colon S_n \rightarrow \{ 1, -1 \} $ ist ein Gruppenhomomorphismus.

Wir sehen damit: Schreibt man eine ungerade Permutation als ein Produkt von Transpositionen, so ist die Anzahl der Faktoren ungerade. Schreibt man eine gerade Permutation als ein Produkt von Transpositionen, so ist die Anzahl der Faktoren gerade. Weil $\operatorname{sgn}(\sigma )\operatorname{sgn}(\sigma ^{-1}) = \operatorname{sgn}(\operatorname{id})=1$ ist, folgt auch $\operatorname{sgn}(\sigma ^{-1}) = \operatorname{sgn}(\sigma )$ für alle $\sigma \in S_n$.

$\includegraphics[width=5.9cm]{figures/permutation5}$

Bemerkung 8.47

Anhand des obigen Beispiels kann man sich die Tatsache, dass das Signum mit der Verkettung kompatibel ist, auch folgendermaßen plausibel machen. Wir wollen wissen, ob die Anzahl der Fehlstände einer Verkettung gerade oder ungerade ist. Wenn wir die Verkettung wie nebenstehend zeichnen, gibt es zwar unnötige Überschneidungen; die Länge einer Verkettung $\sigma \tau $ ist üblicherweise nicht gleich der Summe der Längen von $\sigma $ und $\tau $. Wenn man die »Sache aber geradezieht«, dann fallen die unnötigen Überschneidungen immer jeweils in Paaren weg (wie im Bild hier farbig markiert). Ob die Anzahl der Überschneidungen gerade oder ungerade ist, verändert sich also nicht.

Einen Zykel $(i_1, i_2, \dots , i_l)$ kann man als Produkt von $l-1$ Transpositionen schreiben. (Wie?) Das Signum ist daher $(-1)^{l-1}$.

Ergänzung 8.48 Zum Signum einer Permutation

Alternativ kann man das Signum einer Permutation $\sigma $ definieren als

\[ \operatorname{sgn}(\sigma ) = \prod _{1\le i {\lt} j \le n} \frac{\sigma (j) - \sigma (i)}{j-i}. \]

Es ist nicht schwer zu begründen, dass diese Definition mit unserer Definition übereinstimmt. Um die Multiplikativität zu zeigen, kann man dann wie folgt rechnen:

\begin{align*} \operatorname{sgn}(\sigma \tau ) & = \prod _{1\le i {\lt} j \le n} \frac{\sigma \tau (j) - \sigma \tau (i)}{j-i}\\ & = \prod _{1\le i {\lt} j \le n} \left(\frac{\sigma \tau (j) - \sigma \tau (i)}{\tau (j)-\tau (i)}\cdot \frac{\tau (j)-\tau (i)}{j-i}\right)\\ & = \left(\prod _{1\le i {\lt} j \le n} \frac{\sigma (j) - \sigma (i)}{j-i}\right) \cdot \left( \prod _{1\le i {\lt} j\le n} \frac{\tau (j)-\tau (i)}{j-i}\right)\\ & = \operatorname{sgn}(\sigma ) \operatorname{sgn}(\tau ), \end{align*}

wobei im dritten Schritt eine »Indexverschiebung« stattfindet, die ausnutzt, dass für die Permutation $\tau $ die Werte $\tau (1),\dots ,\tau (n)$ die Zahlen $1,\dots , n$ sind. Dabei ist zu beachten, dass

\[ \frac{\sigma (j) - \sigma (i)}{j-i} = \frac{\sigma (i) - \sigma (j)}{i-j} \]

gilt. Es ist daher egal, ob $i {\lt} j$ oder $j {\lt} i$ gilt; Hauptsache, jede zweielementige Teilmenge $\{ i,j\} $ kommt im Produkt genau einmal vor.

Lineare Algebra I, WS 2020/21

Inhalt

8.3 Permutationen