Symmetrische Gruppe

Die symmetrische Gruppe Sym_n oder S_n ist eine Gruppe, die aus allen Permutationen einer Menge mit n Elementen besteht. Gruppenoperation ist die Verkettung der Permutationen. Das neutrale Element ist die Identität id.

Sym_n besitzt n! ( n Fakultät ) Elemente. Für n > 2 ist Sym_n nicht kommutativ.

Verkettung

Die Verkettung zweier n-stelliger Permutationen $p_2 \circ p_1$ besagt, dass die Permutation $p 2$ nach $p 1$ ausgeführt wird, d. h. $p 2$ wird auf das Ergebnis von $p 1$ ausgeführt. Das Ergebnis der Verkettung ist erneut eine n-stellige Permutation.

Beispiel:

$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4\end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix}$

Zunächst bildet die „rechte“ Permutation die 4 auf die 1 ab, anschließend bildet die „linke“ Permutation die 1 auf die 2 ab. Die gesamte Verkettung bildet also die 4 auf die 2 ab.

Rechenschema

Das Ergebnis einer Verkettung lässt sich u.a. nach folgendem Schema ermitteln:

Ordnen der Spalten der linken Permutation, so dass die obere Zeile der linken Permutation gleich der unteren Zeile der rechten Permutation ist.
Das Ergebnis der Verkettung besteht nun aus der oberen Zeile der rechten und der unteren Zeile der linken Permutation.

Beispiel:

$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4\end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix} = \begin{pmatrix} 3 & 2 & 4 & 1 \\ 1 & 3 & 4 & 2\end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2\end{pmatrix}$

Gruppeneigenschaften

Verkettungen sind generell assoziativ.

Für jede n-stellige Permutation $p$ gilt: $p \circ \mathrm{id} = \mathrm{id} \circ p = p$ , wobei $id$ die identische Permutation $(1)$ bezeichnet.

Zu jeder n-stelligen Permutation $p$ gibt es eine Permutation $p - 1$ mit $p \circ p^{-1} = p^{-1} \circ p = \mathrm{id}$ .

$p - 1$ lässt sich aus $p$ generieren, indem obere und untere Zeile vertauscht werden.

Man kann per vollständiger Induktion zeigen, dass man jede Permutation als Produkt von Zyklen der Länge zwei darstellen kann. Dieser Satz spielt eine theoretische Rolle in der Informatik. Er sagt aus, dass man durch sukzessives Vertauschen von jeweils lediglich zwei Elementen eine unsortierte Folge von Elementen sortieren kann.

Beispiele

$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix}\circ \begin{pmatrix} 3 & 2 & 4 & 1 \\ 1 & 2 & 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 2 & 4 & 1 \\ 1 & 2 & 3 & 4\end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4\end{pmatrix}$

Für n > 2 ist die symmetrische Gruppe Sym_n nicht kommutativ:

$\begin{pmatrix}1&2&3&\ldots\\2&3&1&\ldots\end{pmatrix}\circ \begin{pmatrix}1&2&3&\ldots\\2&1&3&\ldots\end{pmatrix}= \begin{pmatrix}1&2&3&\ldots\\3&2&1&\ldots\end{pmatrix}$
$\begin{pmatrix}1&2&3&\ldots\\2&1&3&\ldots\end{pmatrix}\circ \begin{pmatrix}1&2&3&\ldots\\2&3&1&\ldots\end{pmatrix}= \begin{pmatrix}1&2&3&\ldots\\1&3&2&\ldots\end{pmatrix}$