Transposition/Permutation < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:52 Do 11.11.2010 | | Autor: | Crizz |
| Aufgabe | Aufgabe 3: Eine Permutation [mm] \varphi\in\Sn\sub [/mm] Sn heißt eine Transposition, falls es i, j mit i [mm] \ne [/mm] j gibt, derart, dass
[mm] \varphi(i) [/mm] = j [mm] \varphi(j) [/mm] = i [mm] \varphi(k) [/mm] = k für k [mm] \ne [/mm] i, j.
Beachten Sie, dass jede Transposition ihr eigenes Inverses ist.
a) Sei [mm] \varphi\in\Sn\sub [/mm] Sn eine Permutation mit [mm] \varphi(n) \ne [/mm] n. Zeigen Sie, dass es eine Transposition
[mm] \Gamma\in\Sn\sub [/mm] mit folgender Eigenschaft gibt: [mm] \varphi [/mm] * [mm] \Gamma(n) [/mm] = n.
b) Schreiben Sie die Permutationen
[mm] \begin{pmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1 \end{pmatrix} [/mm] und [mm] \begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 4 & 5 & 2 & 1 & 3 \end{pmatrix} [/mm] als Produkte von Transpositionen.
c) Zeigen Sie – etwa per Induktion über n –, dass jede Permutation in Sn sich
als ein Produkt von Transpositionen schreiben lässt. |
Hallo Leute,
ich hoffe ihr könnt mir bei dieser Aufgabe helfen, da ich leider überhaupt nicht weiß wie ich an diese herangehen soll. Transposition sagt mir auch nur bedingt was, soweit ich weiß vertauscht man einfach 2 Elemente einer Permutation oder? (also in der 2. Zeile) Ich wäre eucht sehr dankbar wenn ihr mir für jede Teilaufgabe Denkanstöße/Lösungsansätze geben würdet, das wäre echt hilfreich!
Schon mal Danke im Vorraus,
Crizz
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.onlinemathe.de/forum/TranspositionPermutation
Aufgabe wurde schon auf onlinemathe.de gestellt, allerdings noch keine einzige Antwort. Werde sie rausnehmen wenn ihr mir helfen könnt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:05 Do 11.11.2010 | | Autor: | Aurelie |
Hallo Crizz,
Eine Permutation [mm]\phi\in S_n[/mm] ist eine bijektive Abbildung [mm]\phi: \{1,\dots,n\}\to\{1,\dots,n\}[/mm]
und eine Transposition ist eine spezielle Permutation nämlich eine bei der jedes Element auf sich selbst abgebildet wird bis auf genau zwei, die aufeinander abgebildet werden: [mm]\exists \;i,j\in\{1,\dots,n\}, i\neq j \text{ mit } \phi(i)=j \text{ und } \phi(j)=i \text{ und sonst } \phi(k)=k[/mm]
Beispiel für eine Transposition ist: [mm]\pmat{ 1& 2&3 &4\\
4&2&3&1 }[/mm]
Wobei diese Schreibweise bedeutet dass die 1 auf die 4, die 2 auf die 2 usw. abgebildet wird. Oder anders gesehenn stehen oben die Zahlen 1-4 in geordneter Reihenfolge und unten drunter in einer neuen Reihenfolge , es wurden nämlich die 1 und die 4 "vertauscht". So zu deinen Aufgaben:
(a)Wenn [mm]\phi(n)\neq n[/mm] dann existiert ein [mm]i\in\{a,\dots,n-1\} \text{ mit }\phi(i)=n[/mm]
Sei [mm]\Gamma[/mm] die Transposition die i und n vertauscht also mit [mm]\Gamma(i)=n \text{ und } \Gamma(n)=i[/mm] dann ist [mm](\phi*\Gamma)(n)=\phi(\Gamma(n))=\phi(i)=n[/mm]
(b) Zu dem zugehörigen Produkt von Transpositionen kommst du zum Beispiel so: In [mm]\pmat{ 1 & 2&3&4 \\
2&3&4&1 } [/mm] vertauscht du nacheinander jeweils 2 Zahlen (was einer Transposition entspricht) bis du bei der Identität [mm]\pmat{ 1 & 2&3&4 \\
1&2&3&4 } [/mm] ankommst:
[mm]\pmat{ 1 & 2&3&4 \\
2&3&4&1 } \to \pmat{ 1 & 2&3&4 \\
1&3&4&2 } \to \pmat{ 1 & 2&3&4 \\
1&2&4&3 } \to \pmat{ 1 & 2&3&4 \\
1&2&3&4 }[/mm] die Transpositionen die du durchgeführt hast schreibst du dann in umgekehrter Reihenfolge auf, hier: <span class="math">[mm]\pmat{ 1 & 2&3&4 \\
2&3&4&1 } = \tau_{1,2}+\tau_{2,3}*\tau_{4,3}[/mm]
Für den Beweis in der (c) musst du im Grunde dieses Prinzip aufschreiben
</span>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:41 So 14.11.2010 | | Autor: | Crizz |
Okey, ich glaube ich habe es soweit verstanden, Dankeschön!
|
|
|
|
