Lineare Algebra - Permutation

[Perry3D]

Hallo

ich bin gerade dabei für mein Mathe-Vordiplom zu lernen und bin bei dem Kapitel Permutationen. Leider ist das Skript sehr kompliziert und ich versteh leider nichts alles.

In einer Übungsaufgabe geht es darum, dass man jede Permutation aus S4 als Produkt der Elemente (1,2), (2,3) und (3,4) schreibe.

Ich habe zwar die Lösungen, aber nicht den Lösungsweg.
Ein Beispiel wäre:

(1,3,4,2) = (2,3) * (1,2) * (3,4)
oder (1,4,2) = (2,3) * (3,4) * (2,3) * (1,2)
Wie komme ich darauf?
Hat jemand Ahnung von diesem Thema und kann mir weiterhelfen?

 

[i_hasser]

Schreib die einzelnen Transpositionen mal ordentlich auf, ich komm da auf (3, 1, 4, 2) beim ersten. Die Hintereinanderausführen hast du von hinten nach vorn gemacht?

 

[Perry3D]

Ja, von hinten nach vorne.
Also ich komm auf das richtige Ergebnis. Habe ich ja auch so aus der Lösung abgeschrieben.
Kannst du mir mal kurz erklären was Transpositionen sind? Sind das Permutationen / Zyklen mit der Länge 2?

 

[i_hasser]

Hab gerade festgestellt, dass ich mich verguckt hatte. Schreib die 3 Elemente mal als ordenltiche Permutation auf, kenn die Schreibweise von dir net.

Theoretisch müsstest du aus denen nur jede mögliche Transposition herleiten können, wenn das erfüllt ist kannst du jede Permutation aus S4 als Produkt der 3 Elemente darstellen.

 

[Perry3D]

Sorry, ich habe die Zykelschreibweise benutzt:

So sieht die normale aus:

[FONT=Fixedsys](2,3) = 1 2 3 4       (1,2) = 1 2 3 4        (3,4) = 1 2 3 4
        1 3 2 4               2 1 3 4                1 2 4 3 [/FONT]

Das Beispiel wäre dann:

[FONT=Fixedsys]1 2 3 4  =  1 2 3 4  *   1 2 3 4   *  1 2 3 4
3 1 4 2     1 3 2 4      2 1 3 4      1 2 4 3[/FONT]

Ich habe allerdings noch keine ordentliche Definition für "Transposition" gefunden. Kannst du mir vielleicht kurz erklären um was es sich dabei handelt?

 

[i_hasser]

Eine Transposition ist genau eine Vertauschung. Jede Permutation kannst du als Verkettung von Transpositionen darstellen.

Für Mathe-Sachen sehr zu empfehlen: http://de.wikipedia.org/wiki/Alternierende_Gruppe

Eine recht einfache Methode irgendeine Permutation über Transpositionen auszudrücken, ist jedes Element so zu tauschen, dass es an der richtigen Stelle steht. Also zB:

1 2 3 4  
3 1 4 2  

=

1 2 3 4 * 1 2 3 4 
3 2 1 4   1 3 4 2
          
          ^ ^ 1 auf die richtige
          Position getauscht
^^^^^^^ Transposition, die diese 
        Vertauschung wieder aufhebt         

=

1 2 3 4 * (1 2 3 4 * 1 2 3 4) 
3 2 1 4   (1 3 2 4   1 2 4 3)
                     
                       ^   ^ 2 auf die
                       richtige Position getauscht
                       
           ^^^^^^^ Transposition, die das wieder 
                   aufhebt           
          
=

1 2 3 4 * (1 2 3 4 * (1 2 3 4 * 1 2 3 4)) 
3 2 1 4   (1 3 2 4   (1 2 3 4   1 2 3 4))
                           
                                    ^ ^ 3 auf
                                 die richtige Pos getauscht, 
                                 ist jetzt Identität
                      ^^^^^^^ Transposition, die das
                              wieder aufhebt
                                       
                                       
=>
                                       
1 2 3 4  = 1 2 3 4 * 1 2 3 4 * 1 2 3 4
3 1 4 2    3 2 1 4   1 3 2 4   1 2 3 4

           ^^^^^^^   ^^^^^^^   ^^^^^^^
              alles nur Transpositionen, da 
              ungerader Anzahl ist das signum 
              der Ausgangspermutation -1

Einen einfachen Algorithmus wie du Transpositionen aus den 3 gegebenen Transpositionen herleiten kannst, gibt es afaik nicht. Aber die 6 Transpositionen in S4 ( (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) ) aus den 3 gegebenen herleiten dürfte eigentlich net das Problem sein, vor allem hast du damit gleich bewiesen, dass du jede Permutation aus S4 damit darstellen kannst.

 

[Perry3D]

Vielen Dank i_hasser. Du warst mir eine große Hilfe

Wenn man den Bogen raus hat, ist es echt einfach.

Du hast Recht: Algorithmus gibt es dafür keinen, aber man sieht recht schnell welche der drei Transpositionen man verwenden muss.

Gruß Perry