Beweis Permutation in paarweise disjunkte Zyklen |
20.04.2012, 12:56 | rawfood | Auf diesen Beitrag antworten » | ||||||
Beweis Permutation in paarweise disjunkte Zyklen Ich habe ein Verständnisproblem. 2.2.4 Proposition : Jede Permutation sigma lässt sich in paarweise disjunkte Zyklen zerlegen. Beweis. Einen Beweis kann man per Induktion über die Anzahl der Elemente, die keine Fixpunkte von sigma sind angeben. Wenn sigma nicht die identische Abbildung ist, dann startet man bei einem Element a und berechnet sigma(a), anschließend sigma(sigma(a), solange bis sich der Zyklus schließt und sigma(sigma(a)) = a ist. Jetzt steht hier in meinem Skript : Sei nun T die Permutation, die aus Sigma entsteht, wenn wir aus allen Elementen die in dem eben gefundenen Zyklus vorkommen, Fixpunkte machen. Ich verstehe nicht wie der letzte Satz gemeint sein soll. Sei meine Permutation 1 2 3 4 2 1 3 4 Ich hätte folgenden Zyklus sigma1(1,2) Sei nun T die Permutation, die aus Sigma entsteht, wenn wir aus allen Elementen die in dem eben gefunden Zyklus Fixpunkte machen: Bedeutet dies T von sigma ist 1 2 3 4 1 2 3 4 Danke Rawfood |
||||||||
20.04.2012, 12:58 | Mystic | Auf diesen Beitrag antworten » | ||||||
RE: Beweis Permutation in paarweise disjunkte Zyklen Ja. |
||||||||
21.04.2012, 12:52 | rawfood | Auf diesen Beitrag antworten » | ||||||
Okay Super. Jetzt habe ich mit folgender Aussage ein Problem : Jede Permutation / Zyklus läßt sich als Komposition / Produkt von Transpositionen schreiben. Damit komme ich nicht zurecht. Eine Transposition ist eine Permutation die nur zwei Zahlen vertauscht. Bsp: 1 2 3 4 5 1 2 4 3 5 Das ist jetzt nach meinem Verständnis eine Transposition. Nun soll es mir auch Möglich sein, jede andere Permutation als Produkt von Transpotionen zu notieren. Bsp: 1 2 3 4 5 2 3 1 4 5 Ich habe also die Zyklen <1,2,3>°<4>°<5>. Wie notiere ich diese Permutation nun als Transposition? <1,2>°<2,3>°<4>°<5> Ist das nun meine obige Permutation als Transposition ausgedrückt? Wenn nicht, wo liegt mein Denkfehler? 1 2 3 4 5 1 2 3 4 5 2 1 3 4 5 1 3 2 4 5 Kann ich Fixpunkte überhaupt als Komposition einer Transposition notieren? Wenn ja, dann wären es keine Fixpunkte mehr. Also nein? In der Lösung zur Aufgabe steht: Es lässt sich jede Permutation in paarweise disjunkte Zyklen zerlegen. Es genügt also, die Aufgabe für Permutationen zu zeigen, die bis auf Fixpunkte nur einen Zyklus <a1,a2...ak> haben. Warum schließe ich aus der Tatsache, dass jede Permutation sich in paarweise disjunkte Zyklen zerlegen läßt, dass dass ich in meinem Beweis nur für Permutationen mit einem Zyklus sowie Fixpunkte zeigen muss, dass sich jede Permutation als Komposition von Transpositionen schreiben läßt? Danke Rawfood |
||||||||
21.04.2012, 21:40 | Mystic | Auf diesen Beitrag antworten » | ||||||
(1 2)(2 3) wäre ok, dagegen ist in deiner Darstellung (4) und (5) keine Transposition...
Kapier dein Argument hier nicht... Z.B. hat ja das Produkt (12)(12) mindestens die Fixpunkte 1 und 2...
Das ist richtig, denn man muss ja dann für die Zyklen nur mehr die Darstellungen als Produkt von Transpositionen einsetzen... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|