Zyklen von Permutationen

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

Beispiel

(12343124) \begin{pmatrix} 1&2&3&4\\3&1&2&4 \end{pmatrix} liefert 13211\rightarrow 3\rightarrow 2\rightarrow 1\dots

Satz 16NR

Je zwei Bahnen sind entweder disjunkt oder gleich.

Beweis

Seien i,j{1,,n}i,j\in\{ 1,\dots,n \} und πk(i)=πl(j) \pi^k(i)=\pi^l(j). Wir zeigen dann, dass die Bahnen von ii und jj gleich sind. Es ist πm(i)=πmkπk(i) \pi^m(i)=\pi^{m-k}\circ \pi^k(i)=πmkπl(j)=πmk+l(j) =\pi^{m-k}\circ \pi^l(j)=\pi^{m-k+l}(j) Damit ist die Bahn durch ii Teilmenge der Bahn durch jj. Die umgekehrte Inklusion zeigt man analog. Damit sind die Bahnen gleich. \qed
Satz 16NR liefert die Rechtfertigung für die
 
 

Zyklenschreibweise

Eine Permutation π\pi können wir daher als Menge von Zyklen schreiben. Damit die Darstellung eindeutig wird, werden die Bahnelemente in ihrer Reihenfolge geschrieben:
(1=π0(1) π(1) π2(1)πk1(1))(a!=πi(1)i π(a)πl1(a))() \left( \underset{\atop ={\pi^0(1)}}{1}\ \pi(1)\ \pi^2(1)\dots\pi^{k-1}(1) \right) \left( \underset{\atop !={\pi^i(1)\forall i}}{a}\ \pi(a)\dots\pi^{l-1}(a) \right)\left( \dots \right)

Beispiele

π=(1234531542)=(1352)\pi=\pmatrix{{1 2 3 4 5} \\ {3 1 5 4 2}}=(1 3 5 2)
π=(12345673514672)=(1 3)(2 5 6 7)(4)\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)(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)(1).

Satz 5816A

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

Beweisidee anhand eines Beispiels

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 π=(123456351462)\pi=\pmatrix{{1 2 3 4 5 6}\\ {3 5 1 4 6 2 }} ermitteln. Dabei gehen wir von der 11 aus. Die 11 wird in die 33 überführt. Der Zyklus muss also (13)(1 3 \ldots ) lauten. Die 33 wird aber wieder in die 11 überführt. Damit ist der erste Zyklus abgeschlossen: (13)(1 3 ). Jetzt nehmen wir uns das nächste Element, dass bisher in keinem Zyklus vorkommt. Dies ist die 22. Wenn wir obiges Verfahren anwenden erhalten wir den Zyklus (256)(2 5 6 ). Schließlich bleibt die 44 übrig und wir erhalten: π=(13)(256)(4)\pi=(1 3 )(2 5 6 )(4). \qed
Es ist unmittelbar klar, dass elementfremde Zyklen bei der Multiplikation vertauscht werden können.

Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch.

Bertrand Russell

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе