Zyklen von Permutationen

Sei $\pi$ eine Permutation. Für $i\in\{ 1,\dots,n \}$ heißt $\{ i,\pi(i),\pi^2(i),\dots \}$ die Bahn oder der Zyklus von $\pi$.

$\begin{pmatrix} 1&2&3&4\\3&1&2&4 \end{pmatrix}$ liefert $1\rightarrow 3\rightarrow 2\rightarrow 1\dots$

Je zwei Bahnen sind entweder disjunkt oder gleich.

Seien $i,j\in\{ 1,\dots,n \}$ und $\pi^k(i)=\pi^l(j)$. Wir zeigen dann, dass die Bahnen von $i$ und $j$ gleich sind. Es ist $\pi^m(i)=\pi^{m-k}\circ \pi^k(i)$$=\pi^{m-k}\circ \pi^l(j)=\pi^{m-k+l}(j)$ Damit ist die Bahn durch $i$ Teilmenge der Bahn durch $j$. Die umgekehrte Inklusion zeigt man analog. Damit sind die Bahnen gleich. $\qed$

Satz 16NR liefert die Rechtfertigung für die

Eine Permutation $\pi$ können wir daher als Menge von Zyklen schreiben. Damit die Darstellung eindeutig wird, werden die Bahnelemente in ihrer Reihenfolge geschrieben:

$\pi=\pmatrix{{1 2 3 4 5} \\ {3 1 5 4 2}}=(1 3 5 2)$

$\pi= \begin{pmatrix} 1&2&3&4&5&6&7\\3&5&1&4&6&7&2 \end{pmatrix}=(1\ 3)(2\ 5\ 6\ 7)(4)$

Zyklen der Länge 1 können auch weggelassen werden: $(1\ 3)(2\ 5\ 6\ 7)(4)=(1\ 3)(2\ 5\ 6\ 7)$.

Damit bei der identischen Permutation nicht alle Zyklen wegfallen, schreibt man $(1)$.

Jede Permutation lässt sich als Produkt von elementfremden Zyklen darstellen.

Der Beweis dieser Behauptung ist ziemlich technisch und beruht im Wesentlichen auf dem Konstruktionsprinzip, das wir anhand eines Beispiels darstellen.

Wir wollen die Zyklendarstellung der Permutation $\pi=\pmatrix{{1 2 3 4 5 6}\\ {3 5 1 4 6 2 }}$ ermitteln. Dabei gehen wir von der $1$ aus. Die $1$ wird in die $3$ überführt. Der Zyklus muss also $(1 3 \ldots )$ lauten. Die $3$ wird aber wieder in die $1$ überführt. Damit ist der erste Zyklus abgeschlossen: $(1 3 )$. Jetzt nehmen wir uns das nächste Element, dass bisher in keinem Zyklus vorkommt. Dies ist die $2$. Wenn wir obiges Verfahren anwenden erhalten wir den Zyklus $(2 5 6 )$. Schließlich bleibt die $4$ übrig und wir erhalten: $\pi=(1 3 )(2 5 6 )(4)$. $\qed$

Es ist unmittelbar klar, dass elementfremde Zyklen bei der Multiplikation vertauscht werden können.