Permutation als Komposition von Transpositionen

Aufrufe: 1670     Aktiv: 05.02.2020 um 10:43

0

 

Hallo,

nehmen wir an ich habe folgende Permuation gegeben:

 

nun  soll die Permuation als Hintereinanderausführung von Transpositionen dargestellt werden. Als Lösung ist dazu das folgende angegeben:

Wenn ich nun jedoch die angegebenen Transpositionen auflöse und wieder in die obige Schreibweise bringe erhalte ich die Inverse Permuation und nicht die Ausgangspermuation. Ist die Lösung einfach falsch und bezieht sich auf die Zerlegung der Inversen Permuation in Transpositionen? Oder wo liegt der Fehler?

Generell: Wie kann ich eine gegebene Permuation in Transpositionen zerlegen?

Danke und viele Grüße

 

 

Diese Frage melden
gefragt

Student, Punkte: 20

 
Kommentar schreiben
1 Antwort
1

Hi, 

bei der Komposition der Transpositionen gilt:

\(1 \mapsto 5 \\ 2 \mapsto 6 \\ 3 \mapsto 1 \\ 4 \mapsto 3 \\ 5 \mapsto 4\\ 6 \mapsto 2\)

Das entspricht auch genau deiner angegebenen Permutaion.

Und für die Zerlegung einer Permutation in Transpositionen gibt es einen einfachen Algorithmus:

Schreibe die Permutation zunächst als Komposition von disjunkten Zykeln, also

\( (1 5 4 3) \circ (2 6) \)

Nun gilt: 

\( (i_1 i_2 ... i_k)  \) = \( (i_1 i_k)\circ (i_1 i_{k-1})\circ ... \circ (i_1 i_2)\)

In diesem Fall wäre es also:

\( (1 5 4 3) \circ (2 6)  =  (1 3) \circ (1 4) \circ (1 5) \circ (2 6)\)

Diese Komposition von Transpositionen entspricht genau deinem \(f\) ;) 

Liebe Grüße :)

Diese Antwort melden
geantwortet

Student, Punkte: 489

 

Danke! Aber die Verknüpfung von Transpositionen funktioniert nur wenn ich sie von links lese, oder? Ich habe irgendwie im Kopf, dass die Verknüpfung von Permuationen von rechts durchgeführt wird.   ─   lukastimmer 04.02.2020 um 16:23

Also ein einzelner Zykel wird von links nach rechts gelesen, zum Beispiel:
(1 4 3 2), schickt die 1 auf die 4 und die 4 auf die 3, die 3 auf die 2 und die 2 auf die 1
(bei einer einzelnen Transposition ist es eigentlich egal, wie man die liest, da die beiden Zahlen ja sowieso nur miteinander getauscht werden)
Eine Komposition wird allerdings von rechts nach links gelesen, zum Beispiel:
(1 3) o (1 4)
Hier gilt:.
1 - > 4
2 - > 2
3 - > 1
4 - > 3
  ─   student201 05.02.2020 um 09:46

Okay, jetzt hab ichs endlich verstanden! :D Vielen Dank!   ─   lukastimmer 05.02.2020 um 10:43

Kommentar schreiben