Lektion 1.6

Die symmetrische Gruppe

25 min Lesezeit

Wir haben bereits in der Lektion über Gruppenbeispiele die symmetrische Gruppe $S_n$ kennengelernt – die Gruppe aller Bijektionen einer endlichen Menge auf sich selbst. Jetzt wollen wir diese Gruppe genauer studieren.

Warum ist $S_n$ so wichtig? Aus mehreren Gründen:

1. Universalität: Der Satz von Cayley besagt, dass jede endliche Gruppe isomorph zu einer Untergruppe einer geeigneten symmetrischen Gruppe ist. $S_n$ enthält also "alle" endlichen Gruppen als Teilstrukturen.

2. Anwendungen: Die Elemente von $S_n$ – die Permutationen – treten überall auf: in der Kombinatorik, bei der Definition der Determinante, in der Physik (Vertauschung identischer Teilchen).

3. Konkretheit: $S_n$ ist eine endliche Gruppe, deren Elemente wir explizit aufschreiben und miteinander verknüpfen können.

Die Grundidee:

Wir betrachten eine Menge $D$ mit $n$ Elementen. Da die Namen der Elemente keine Rolle spielen, wählen wir die Standardmenge:

$D = \{1, 2, 3, \ldots, n\}$

Eine Permutation von $D$ ist eine bijektive Abbildung $\sigma: D \to D$ . Sie ordnet jedem Element von $D$ ein eindeutiges Bild in $D$ zu, und jedes Element von $D$ wird genau einmal getroffen.

Die Menge aller Permutationen von $D$ mit der Komposition als Verknüpfung bildet eine Gruppe – die symmetrische Gruppe $S_n$ .

Definition

Symmetrische Gruppe

Für eine natürliche Zahl $n \geq 1$ ist die symmetrische Gruppe $S_n$ definiert als:

$S_n := \text{Sym}(\{1, 2, \ldots, n\})$

Das heißt: $S_n$ ist die Menge aller bijektiven Abbildungen von $\{1, \ldots, n\}$ nach sich selbst, versehen mit der Komposition $\circ$ als Gruppenverknüpfung.

Gruppenstruktur:
- Verknüpfung: $(\sigma \circ \tau)(i) := \sigma(\tau(i))$ (erst $\tau$ , dann $\sigma$ )
- Neutrales Element: Die Identität $\text{Id}$ , die jedes Element auf sich selbst abbildet
- Inverses zu $\sigma$ : Die Umkehrabbildung $\sigma^{-1}$

|S_n| = n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1

Warum hat $S_n$ genau $n!$ Elemente?

Um eine Permutation $\sigma$ festzulegen, müssen wir für jedes $i \in \{1, \ldots, n\}$ den Wert $\sigma(i)$ wählen – aber so, dass $\sigma$ bijektiv bleibt.

Für $\sigma(1)$ haben wir $n$ Möglichkeiten
Für $\sigma(2)$ bleiben $n-1$ Möglichkeiten (da $\sigma(1)$ schon "vergeben" ist)
Für $\sigma(3)$ bleiben $n-2$ Möglichkeiten
...und so weiter

Insgesamt: $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 = n!$

Die symmetrische Gruppe wächst also sehr schnell: $|S_3| = 6$ , $|S_4| = 24$ , $|S_5| = 120$ , $|S_{10}| = 3.628.800$ .

Beispiel

Die symmetrische Gruppe $S_3$

Die Gruppe $S_3$ besteht aus allen Bijektionen von $\{1, 2, 3\}$ . Sie hat $3! = 6$ Elemente.

Wir können jede Permutation durch eine Wertetabelle angeben:

Die Identität $\text{Id}$ :
$1 \mapsto 1, \quad 2 \mapsto 2, \quad 3 \mapsto 3$

Die drei Transpositionen (Vertauschungen zweier Elemente):
$\tau_1 = (2\;3)$ : $1 \mapsto 1, \; 2 \mapsto 3, \; 3 \mapsto 2$
$\tau_2 = (1\;3)$ : $1 \mapsto 3, \; 2 \mapsto 2, \; 3 \mapsto 1$
$\tau_3 = (1\;2)$ : $1 \mapsto 2, \; 2 \mapsto 1, \; 3 \mapsto 3$

Die zwei Dreizykel (zyklische Vertauschungen):
$\zeta_1 = (1\;2\;3)$ : $1 \mapsto 2, \; 2 \mapsto 3, \; 3 \mapsto 1$
$\zeta_2 = (1\;3\;2)$ : $1 \mapsto 3, \; 2 \mapsto 1, \; 3 \mapsto 2$

Das sind genau 6 Elemente: $S_3 = \{\text{Id}, \tau_1, \tau_2, \tau_3, \zeta_1, \zeta_2\}$ .

Beachte: $S_3$ ist nicht abelsch! Zum Beispiel: $\tau_1 \circ \tau_2 \neq \tau_2 \circ \tau_1$ .

Definition

Zykelschreibweise

Die Wertetabelle wird bei größeren Permutationen unübersichtlich. Die Zykelschreibweise ist kompakter und zeigt die Struktur besser.

Ein $k$ -Zykel $(x_1\; x_2\; \ldots\; x_k)$ ist die Permutation, die:
- $x_1 \mapsto x_2$
- $x_2 \mapsto x_3$
- ...
- $x_{k-1} \mapsto x_k$
- $x_k \mapsto x_1$ (der "Kreis schließt sich")
- alle anderen Elemente fest lässt

Eine Transposition ist ein 2-Zykel, also eine Vertauschung zweier Elemente.

(x_1\; x_2\; \ldots\; x_k): \quad x_i \mapsto x_{i+1} \text{ für } i < k, \quad x_k \mapsto x_1

Beispiel

Zykelschreibweise konkret

Betrachten wir die Permutation $\sigma \in S_7$ mit der Wertetabelle:

$\sigma(1)=2, \; \sigma(2)=5, \; \sigma(3)=4, \; \sigma(4)=7, \; \sigma(5)=1, \; \sigma(6)=3, \; \sigma(7)=6$

Wir finden die Zykel, indem wir "Ketten" verfolgen:
- Beginne bei 1: $1 \to 2 \to 5 \to 1$ (zurück zum Start) $\Rightarrow$ 3-Zykel $(1\;2\;5)$
- Beginne bei 3: $3 \to 4 \to 7 \to 6 \to 3$ $\Rightarrow$ 4-Zykel $(3\;4\;7\;6)$

Damit: $\sigma = (1\;2\;5) \circ (3\;4\;7\;6)$

Diese Zykel sind disjunkt (keine gemeinsamen Elemente), daher ist die Reihenfolge egal.

Satz

Zerlegung in disjunkte Zykel

Jede Permutation $\sigma \in S_n$ lässt sich eindeutig (bis auf Reihenfolge) als Produkt disjunkter Zykel schreiben.

Diese Darstellung heißt die Zykelzerlegung von $\sigma$ .

Satz

$S_n$ wird von Transpositionen erzeugt

Jede Permutation $\sigma \in S_n$ lässt sich als Produkt von Transpositionen schreiben.

Mit anderen Worten: Die Transpositionen erzeugen die gesamte Gruppe $S_n$ .

Definition

Das Signum einer Permutation

Das Signum (oder Vorzeichen) einer Permutation $\sigma \in S_n$ ist definiert als:

$\text{sign}(\sigma) := \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i}$

Da Zähler und Nenner bis auf Vorzeichen dieselben Faktoren enthalten, ist $\text{sign}(\sigma) \in \{+1, -1\}$ .

Eine Permutation heißt gerade, wenn $\text{sign}(\sigma) = +1$ , und ungerade, wenn $\text{sign}(\sigma) = -1$ .

\text{sign}: S_n \to \{\pm 1\}, \quad \text{sign}(\sigma \circ \tau) = \text{sign}(\sigma) \cdot \text{sign}(\tau)

Satz

Eigenschaften des Signums

Das Signum hat folgende wichtige Eigenschaften:

a) Das Signum ist ein Gruppenhomomorphismus: $\text{sign}(\sigma \circ \tau) = \text{sign}(\sigma) \cdot \text{sign}(\tau)$

b) Jede Transposition hat Signum $-1$ : $\text{sign}((a\;b)) = -1$

c) Ein $k$ -Zykel hat Signum $(-1)^{k-1}$

d) Wenn $\sigma$ als Produkt von $l$ Transpositionen geschrieben ist, dann: $\text{sign}(\sigma) = (-1)^l$

Die Anzahl $l$ ist zwar nicht eindeutig, aber ihre Parität (gerade/ungerade) ist es!

Zusammenfassung

$S_n$ ist die Gruppe aller Permutationen von $\{1, \ldots, n\}$ mit $|S_n| = n!$
Die Zykelschreibweise ist kompakter als Wertetabellen: $(1\;2\;3)$ bedeutet $1 \to 2 \to 3 \to 1$
Jede Permutation lässt sich eindeutig in disjunkte Zykel zerlegen
Jede Permutation ist ein Produkt von Transpositionen
Das Signum ist ein Homomorphismus $\text{sign}: S_n \to \{\pm 1\}$
Transpositionen haben Signum $-1$ , ein $k$ -Zykel hat Signum $(-1)^{k-1}$

Übungen

Aufgabe 1Numerisch

Wie viele Elemente hat die symmetrische Gruppe $S_5$ ?

Aufgabe 2Freitext

Bestimme die Zykelzerlegung der Permutation $\sigma \in S_6$ mit $\sigma(1)=3, \sigma(2)=1, \sigma(3)=2, \sigma(4)=6, \sigma(5)=5, \sigma(6)=4$ .

Aufgabe 3Multiple Choice

Welches Signum hat der 5-Zykel $(1\;2\;3\;4\;5)$ ?

$+1$ (gerade)

$-1$ (ungerade)

$0$

Das hängt von der konkreten Menge ab

Lektion 1.6 · Gruppen

• • •

Die symmetrische Gruppe

Warum ist $S_n$ so wichtig? Aus mehreren Gründen:

2. Anwendungen: Die Elemente von $S_n$ – die Permutationen – treten überall auf: in der Kombinatorik, bei der Definition der Determinante, in der Physik (Vertauschung identischer Teilchen).

3. Konkretheit: $S_n$ ist eine endliche Gruppe, deren Elemente wir explizit aufschreiben und miteinander verknüpfen können.

Die Grundidee:

Wir betrachten eine Menge $D$ mit $n$ Elementen. Da die Namen der Elemente keine Rolle spielen, wählen wir die Standardmenge:

$D = \{1, 2, 3, \ldots, n\}$

Eine Permutation von $D$ ist eine bijektive Abbildung $\sigma: D \to D$ . Sie ordnet jedem Element von $D$ ein eindeutiges Bild in $D$ zu, und jedes Element von $D$ wird genau einmal getroffen.

Die Menge aller Permutationen von $D$ mit der Komposition als Verknüpfung bildet eine Gruppe – die symmetrische Gruppe $S_n$ .

Definition

Symmetrische Gruppe

Für eine natürliche Zahl $n \geq 1$ ist die symmetrische Gruppe $S_n$ definiert als:

$S_n := \text{Sym}(\{1, 2, \ldots, n\})$

Das heißt: $S_n$ ist die Menge aller bijektiven Abbildungen von $\{1, \ldots, n\}$ nach sich selbst, versehen mit der Komposition $\circ$ als Gruppenverknüpfung.

|S_n| = n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1

Warum hat $S_n$ genau $n!$ Elemente?

Um eine Permutation $\sigma$ festzulegen, müssen wir für jedes $i \in \{1, \ldots, n\}$ den Wert $\sigma(i)$ wählen – aber so, dass $\sigma$ bijektiv bleibt.

Für $\sigma(1)$ haben wir $n$ Möglichkeiten
Für $\sigma(2)$ bleiben $n-1$ Möglichkeiten (da $\sigma(1)$ schon "vergeben" ist)
Für $\sigma(3)$ bleiben $n-2$ Möglichkeiten
...und so weiter

Insgesamt: $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 = n!$

Die symmetrische Gruppe wächst also sehr schnell: $|S_3| = 6$ , $|S_4| = 24$ , $|S_5| = 120$ , $|S_{10}| = 3.628.800$ .

Beispiel

Die symmetrische Gruppe $S_3$

Die Gruppe $S_3$ besteht aus allen Bijektionen von $\{1, 2, 3\}$ . Sie hat $3! = 6$ Elemente.

Wir können jede Permutation durch eine Wertetabelle angeben:

Die Identität $\text{Id}$ :
$1 \mapsto 1, \quad 2 \mapsto 2, \quad 3 \mapsto 3$

Die zwei Dreizykel (zyklische Vertauschungen):
$\zeta_1 = (1\;2\;3)$ : $1 \mapsto 2, \; 2 \mapsto 3, \; 3 \mapsto 1$
$\zeta_2 = (1\;3\;2)$ : $1 \mapsto 3, \; 2 \mapsto 1, \; 3 \mapsto 2$

Das sind genau 6 Elemente: $S_3 = \{\text{Id}, \tau_1, \tau_2, \tau_3, \zeta_1, \zeta_2\}$ .

Beachte: $S_3$ ist nicht abelsch! Zum Beispiel: $\tau_1 \circ \tau_2 \neq \tau_2 \circ \tau_1$ .

Definition

Zykelschreibweise

Die Wertetabelle wird bei größeren Permutationen unübersichtlich. Die Zykelschreibweise ist kompakter und zeigt die Struktur besser.

Eine Transposition ist ein 2-Zykel, also eine Vertauschung zweier Elemente.

(x_1\; x_2\; \ldots\; x_k): \quad x_i \mapsto x_{i+1} \text{ für } i < k, \quad x_k \mapsto x_1

Beispiel

Zykelschreibweise konkret

Betrachten wir die Permutation $\sigma \in S_7$ mit der Wertetabelle:

$\sigma(1)=2, \; \sigma(2)=5, \; \sigma(3)=4, \; \sigma(4)=7, \; \sigma(5)=1, \; \sigma(6)=3, \; \sigma(7)=6$

Damit: $\sigma = (1\;2\;5) \circ (3\;4\;7\;6)$

Diese Zykel sind disjunkt (keine gemeinsamen Elemente), daher ist die Reihenfolge egal.

Satz

Zerlegung in disjunkte Zykel

Jede Permutation $\sigma \in S_n$ lässt sich eindeutig (bis auf Reihenfolge) als Produkt disjunkter Zykel schreiben.

Diese Darstellung heißt die Zykelzerlegung von $\sigma$ .

Beweis

Die Idee ist einfach: Wir verfolgen die "Bahnen" der einzelnen Elemente.

Starte bei 1 und bilde die Folge $1, \sigma(1), \sigma^2(1), \ldots$ . Da $\{1, \ldots, n\}$ endlich ist, muss irgendwann ein Wert wiederholt werden. Der erste, der sich wiederholt, ist 1 selbst (weil $\sigma$ bijektiv ist).

Sei $k$ minimal mit $\sigma^k(1) = 1$ . Dann ist $(1\; \sigma(1)\; \sigma^2(1)\; \ldots\; \sigma^{k-1}(1))$ ein $k$ -Zykel.

Falls noch Elemente übrig sind, wiederhole den Prozess mit dem kleinsten noch nicht erfassten Element. Da die entstehenden Zykel verschiedene Elemente enthalten, sind sie disjunkt.

q.e.d.

Satz

$S_n$ wird von Transpositionen erzeugt

Jede Permutation $\sigma \in S_n$ lässt sich als Produkt von Transpositionen schreiben.

Mit anderen Worten: Die Transpositionen erzeugen die gesamte Gruppe $S_n$ .

Beweis

Wir nutzen, dass sich jeder $k$ -Zykel als Produkt von $k-1$ Transpositionen schreiben lässt:

$(x_1\; x_2\; \ldots\; x_k) = (x_1\; x_2) \circ (x_2\; x_3) \circ \ldots \circ (x_{k-1}\; x_k)$

Zur Verifikation: Die rechte Seite bildet $x_i$ auf $x_{i+1}$ ab (für $i < k$ ), und $x_k$ auf $x_1$ .

Da jede Permutation ein Produkt von Zykeln ist und jeder Zykel ein Produkt von Transpositionen, ist jede Permutation ein Produkt von Transpositionen.

q.e.d.

Definition

Das Signum einer Permutation

Das Signum (oder Vorzeichen) einer Permutation $\sigma \in S_n$ ist definiert als:

$\text{sign}(\sigma) := \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i}$

Da Zähler und Nenner bis auf Vorzeichen dieselben Faktoren enthalten, ist $\text{sign}(\sigma) \in \{+1, -1\}$ .

Eine Permutation heißt gerade, wenn $\text{sign}(\sigma) = +1$ , und ungerade, wenn $\text{sign}(\sigma) = -1$ .

\text{sign}: S_n \to \{\pm 1\}, \quad \text{sign}(\sigma \circ \tau) = \text{sign}(\sigma) \cdot \text{sign}(\tau)

Satz

Eigenschaften des Signums

Das Signum hat folgende wichtige Eigenschaften:

a) Das Signum ist ein Gruppenhomomorphismus: $\text{sign}(\sigma \circ \tau) = \text{sign}(\sigma) \cdot \text{sign}(\tau)$

b) Jede Transposition hat Signum $-1$ : $\text{sign}((a\;b)) = -1$

c) Ein $k$ -Zykel hat Signum $(-1)^{k-1}$

d) Wenn $\sigma$ als Produkt von $l$ Transpositionen geschrieben ist, dann: $\text{sign}(\sigma) = (-1)^l$

Die Anzahl $l$ ist zwar nicht eindeutig, aber ihre Parität (gerade/ungerade) ist es!

Beweis

Zu b): Für die Transposition $\tau = (1\;2)$ zählen wir die Faktoren im Produkt, die negativ werden: Nur der Faktor für $(i,j) = (1,2)$ ändert das Vorzeichen. Also $\text{sign}((1\;2)) = -1$ .

Jede andere Transposition $(a\;b)$ ist konjugiert zu $(1\;2)$ : Es gibt ein $\pi$ mit $(a\;b) = \pi^{-1} \circ (1\;2) \circ \pi$ . Da das Signum ein Homomorphismus ist, folgt $\text{sign}((a\;b)) = -1$ .

Zu c): Ein $k$ -Zykel ist das Produkt von $k-1$ Transpositionen, also $\text{sign} = (-1)^{k-1}$ .

q.e.d.

Zusammenfassung

$S_n$ ist die Gruppe aller Permutationen von $\{1, \ldots, n\}$ mit $|S_n| = n!$
Die Zykelschreibweise ist kompakter als Wertetabellen: $(1\;2\;3)$ bedeutet $1 \to 2 \to 3 \to 1$
Jede Permutation lässt sich eindeutig in disjunkte Zykel zerlegen
Jede Permutation ist ein Produkt von Transpositionen
Das Signum ist ein Homomorphismus $\text{sign}: S_n \to \{\pm 1\}$
Transpositionen haben Signum $-1$ , ein $k$ -Zykel hat Signum $(-1)^{k-1}$

—

Die symmetrische Gruppe S3S_3S3​

Zykelschreibweise konkret

Zusammenfassung

Übungen

Die symmetrische Gruppe

Die symmetrische Gruppe S3S_3S3​

Zykelschreibweise konkret

Zusammenfassung

Die symmetrische Gruppe $S_3$

Die symmetrische Gruppe $S_3$