Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Transpositionen - Beweis
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Transpositionen - Beweis
 
Autor Nachricht
Shubi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.07.2008
Beiträge: 1193

BeitragVerfasst am: 15 Okt 2008 - 11:59:23    Titel: Transpositionen - Beweis

Es soll hier gezeigt werden, dass jede Transposition aus einer ungeraden Anzahl von Nachbartranspositionen besteht. Hier ist der Beweis:

Sei [;S_n;] die symmetrische Gruppe in n Buchstaben und [;\tau;] eine Transposition mit [;\tau \in S_n;]

[;\tau=\begin{pmatrix} 1 & \cdots & j & \cdots & i & \cdots & n\\ 1 & \cdots & i & \cdots & j & \cdots & n \end{pmatrix};]

Für alle [;j\le k<i;] setze [;\tau_k=\begin{pmatrix} 1 & \cdots & k & k+1 & \cdots & n\\ 1 & \cdots & k+1 & k & \cdots & n \end{pmatrix};]

Dann gilt:

[;\tau=\tau_{i-1} \circ \tau_{i-2}\circ \cdots \circ \tau_{j+1} \circ \tau_j\circ\tau_{j+1}\circ\cdots\circ\tau_{i-1};]

Danach kommt noch ein kleiner erklärender Text, wieso das denn nun so ist und warum damit der Beweis erbracht worden ist - den kann ich aber auch nicht nachvollziehen, deshalb wollte ich hier einmal fragen:

Erstmal bilden wir doch [;\tau_{i-1}=\begin{pmatrix} 1 & \cdots & i-1 & i & \cdots & n\\ 1 & \cdots & i & i-1 & \cdots & n \end{pmatrix};] und [;\tau_{i-2}=\begin{pmatrix} 1 & \cdots & i-2 & i-1 & \cdots & n\\ 1 & \cdots & i-1 & i-2 & \cdots & n \end{pmatrix};]

Sind diese beiden Transpositionen überhaupt richtig?

Dann bilde ich als ersten Schritt (Ausführung von rechts nach links):

[;\tau_{i-2}\circ\tau_{i-1}=\begin{pmatrix} 1 & \cdots & i-1 & i & \cdots & n\\ 1 & \cdots & i & i-1 & \cdots & n \end{pmatrix}\circ \begin{pmatrix} 1 & \cdots & i-2 & i-1 & \cdots & n\\ 1 & \cdots & i-1 & i-2 & \cdots & n \end{pmatrix};]

Wenn ich jetzt die zwei Nachbartranspositionen miteinander verknüpfe, bekomme ich immer [;\tau_{i-1};] als Ergebnis. Eigentlich müssten aber eine art Verschiebung dabei herauskommen oder? Also dass z.B. das Element i-1 auf i abgebildet wird.

Mein intuitives Verständnis des Beweise sieht nämlich wie folgt aus:

Wir verschieben die zwei Element, die die Transposition [;\tau;] vertauscht, mittels Nachbartranspositionen an ihren neuen Platz, das machen wir auf der rechten Hälfte dieser riesigen Verkettung. Die linke Hälfte verschiebt jetzt alle anderen Elemente wieder an ihren ursprünglichen Platz zurück - außer eben diejenigen, die von [;\tau;]vertauscht werden.

Help! Very Happy

(Und ich hoffe es war halbwegs verständlich)
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 15 Okt 2008 - 14:08:59    Titel:

Also erstmal ist diese Art der Schreibweise für Transpositionen schrecklich. Ich benutze lieber die Notation (i, j), die besagt, dass die Elemente i und j vertauscht werden und alle anderen fix bleiben.
Damit kann man deinen Satz übersichtlicher formulieren:

Code:
(i, j) = (i-1, i) (i-2, i-1) ... (j+1, j+2) (j, j+1) (j+1, j+2) ... (i-2, i-1) (i-1, i)


Wir können nun sehen, dass jedes Element z, dass zwischen i und j liegt (j < z < i) auf der rechten Seite auf z+1 abgebildet wird und schließlich auf der linken Seite zurück auf z.

Das Element i wird auf der rechten Seite sukkzessive über i-1, i-2, etc. verschoben auf j. Auf der linken Seite operieren nun alle Transpositionen neutral auf j.

Die Transpositionen auf der rechten Seite operieren neutral auf dem Element j. Schließlich wird es links über j+1, ... auf i verschoben.
Shubi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.07.2008
Beiträge: 1193

BeitragVerfasst am: 15 Okt 2008 - 14:23:58    Titel:

Ah, es wird langsam klarer, ich guck mal, ob ich noch irgendwo eine Frage finde Very Happy

(Wofür braucht man das eigentlich? Angeblich sollen die Permutationen sehr wichtig sein, aber wofür?)

Aber danke schonmal =)
KayC
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 18.08.2008
Beiträge: 24

BeitragVerfasst am: 16 Okt 2008 - 06:24:12    Titel:

Hi Shubi,

irgendwo im Skript steht, dass es später bei Determinanten gebraucht wird?

lg, Katharina
Shubi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.07.2008
Beiträge: 1193

BeitragVerfasst am: 16 Okt 2008 - 08:33:36    Titel:

Ah, tatsächlich Very Happy

Die Passage hatte ich vollkommend übersehen Embarassed

Und ich glaube auch endlich alle beweise verstanden zu haben - fehlt ja nur noch der euklidische Algorithmus. Da finde ich immer s und t nicht Sad
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Transpositionen - Beweis
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum