Permutationen als Produkt elementarer Transpositionen

Neue Frage »

14.04.2016, 13:56	Transposition	Auf diesen Beitrag antworten »
Permutationen als Produkt elementarer Transpositionen Meine Frage: Schreiben Sie alle Permutationen $\begin{eqnarray} \sigma\in S_{3} \end{eqnarray}$ als Produkt von elementaren Transpositionen. Meine Ideen: Ich würde es so versuchen: $\begin{eqnarray} \sigma_{1}=(1,2,3)=(2,1)(2,1)(3,2)(3,2) \end{eqnarray}$ So vertausch ich immer zwei und machs dann wieder rückgängig, sodass ich auf (1,2,3) komme. $\begin{eqnarray} \sigma_{2}=(2,1,3)=(2,1)(3,2)(3,2) \end{eqnarray}$ $\begin{eqnarray} \sigma_{3}=(2,3,1)=(2,1)(3,2) \end{eqnarray}$ $\begin{eqnarray} \sigma_{4}=(1,3,2)=(2,1)(2,1)(3,2) \end{eqnarray}$ $\begin{eqnarray} \sigma_{5}=(3,1,2)=(2,1)(2,1)(3,2)(2,1) \end{eqnarray}$ $\begin{eqnarray} \sigma_{6}=(3,2,1)=(2,1)(3,2)(2,1) \end{eqnarray}$ Oder versteh ich das falsch? Danke, wenn sich jemand die Mühe macht, dass durchzuschauen, ist ja recht verwirrend am Anfang!
14.04.2016, 14:22	Elvis	Auf diesen Beitrag antworten »
Du machst es verwirrender als nötig. Für völlige Verwirrung hast Du gesorgt, indem du die Zykelschreibweise anstelle der Matrixschreibweise für die Permutationen verwendet hast. Die $\begin{eqnarray} S_3 \end{eqnarray}$ besteht aus 3 Transpositionen und einem 3-er-Zyklus der Ordnung 3 : $\begin{eqnarray} \sigma=(1,2,3)=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \end{eqnarray}$ , d.h. $\begin{eqnarray} \sigma^3=id \end{eqnarray}$ . Also musst du nur die Transpositionen aufschreiben, eine Transposition ist das Produkt aus Transpositionen, nämlich genau einer, die Identität ist das Produkt aus Transpositionen, nämlich genau 0. $\begin{eqnarray} \sigma \end{eqnarray}$ und $\begin{eqnarray} \sigma^2 \end{eqnarray}$ sind das Produkt aus 2 Transpositionen.
14.04.2016, 14:28	Transposition	Auf diesen Beitrag antworten »
Die Zykelschreibweise haben wir noch gar nicht durchgenommen, ich habe eigentlich die Tupelschreibweise gemeint, also immer die untere Zeile aus der Matrix. Mit den Zykeln ginge es natürlich leichter, aber ich glaube kaum, dass wir das so machen sollen. Außerdem ging es auch um elementare Transpositionen, also mit zwei aufeinanderfolgenden Zahlen. Wäre toll, wenn du trotz dieser Einschränkungen noch mal drüberschauen könntest
14.04.2016, 18:12	Elvis	Auf diesen Beitrag antworten »
Hab ich doch gemacht, und ich habe auch die Lösung vorweggenommen. $\begin{eqnarray} S_3=\{id=(1,2)^0,(1,2),(1,3),(2,3),\sigma=(1,2,3)=(1,2)(1,3),\sigma^2=(1,3)(1,2) \} \end{eqnarray}$ Wenn Du keinen 3-er-Zykel schreiben willst, dann lass (1,2,3) weg.
14.04.2016, 18:40	Transposition	Auf diesen Beitrag antworten »
Sorry, aber da blick ich überhaupt nicht durch. Für mich waren in S3 immer Tupel enthalten, keine Transpositionen, und wie gesagt ist mir die Zykel-Schreibweise neu/fremd. Was $\begin{eqnarray} \sigma^{2} \end{eqnarray}$ damit zu tun hat, erschließt sich mir auch nicht. Und wo sind jetzt die elementaren Transpositionen? Bitte bringe Licht in mein Dunkel Danke
14.04.2016, 18:51	Elvis	Auf diesen Beitrag antworten »
Eine elementare Transposition ist eine Transposition. Eine Transposition ist ein 2-er-Zykel $\begin{eqnarray} \tau=(a,b)=\begin{pmatrix} a & b \\ b & a \end{pmatrix} \end{eqnarray}$ . Übrigens hattest Du eingangs Produkte aus Transpositionen geschrieben, da dachte ich, Du weißt, was das ist.
Anzeige

14.04.2016, 19:00	Transposition	Auf diesen Beitrag antworten »
Ich weiß natürlich, was Produkte aus Transpositionen sind. Elementare Transpositionen haben wir allerdings so definiert, dass es sich um zwei aufeinanderfolgende Zahlen handeln muss - (1,3) ginge dann z.B. ja nicht, oder verstehe ich das falsch? Wie kommst du auf die Zusammensetzung von S3? Für mich sind in S3 die 3er Tupel, die ich in meinem ersten Beitrag als Produkte darzustellen versucht habe. Sind diese Produkte korrekt oder nicht?
14.04.2016, 19:10	Elvis	Auf diesen Beitrag antworten »
Danke für die Mitteilung der Definition. Du weißt mehr als ich und trägst damit zu recht den Ehrentitel "Transposition". Wenn Du weißt, wie man mit Tanspositionen rechnet, warum fragst Du dann ? Vielleicht konnte ich wenigstens zur Vereinfachung deiner Darstellung beitragen, denn immerhin die Hälfte meiner Elemente sind Produkte aus 0 oder einer elementaren Transposition. Deine Ergebnisse scheinen richtig zu sein, Du kannst aber sicher ein paar Transpositionen weglassen, damit wird es übersichtlicher.
14.04.2016, 19:16	Transposition	Auf diesen Beitrag antworten »
Nun ja, ich war mir nicht sicher, es auch richtig verstanden zu haben, darum wollte ich nochmal nachfragen. Welche Transpositionen könnte ich denn beispielsweise weglassen?
14.04.2016, 19:25	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} (1,2,3)=(1,2)^0, (2,1,3)=(1,2), (3,2,1)=(1,2)(2,3)(1,2),(1,3,2)=(2,3),(2,3,1)=(1,2)(2,3),(3,1,2)=(2,3)(1,2)<br /> \end{eqnarray}$ ... und schreibe $\begin{eqnarray} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} \end{eqnarray}$ statt $\begin{eqnarray} (1,2,3) \end{eqnarray}$
14.04.2016, 19:30	Transposition	Auf diesen Beitrag antworten »
Ich kann deine Rechnungen nachvollziehen, aber vermischst du jetzt hier nicht die Tupelschreibweise (bei den 3er Tupeln) mit der Zykelschreibweise (bei den Transpositionen)? Ich hätte jedenfalls bei den Transpositionen die beiden Zahlen immer genau umgedreht geschrieben. Zweite Frage: kann man z.B. bei (2,1,3) =(2,1) die 3 einfach so weglassen? Ich hab dieses umständlich hin und her in meinem ersten Beitrag deshalb gemacht, um auch alle drei Zahlen "einzuführen".
14.04.2016, 19:59	Elvis	Auf diesen Beitrag antworten »
Ich habe deine - falsche - Schreibweise benutzt, damit Du es leichter verstehen kannst. Das sind keine 3-er-Zykel sondern Tupel. Bei einer Transposition ist es egal, wie man sie schreibt, denn (a,b)=(b,a) sagt nur, dass a und b vertauscht werden.
14.04.2016, 22:06	Transposition	Auf diesen Beitrag antworten »
ah, ok, danke aber bei der "falschen" Schreibweise muss ich nochmal einhaken. Das wurde bei uns in der Vorlesung so eingeführt... Hab ich auch in anderen Quellen als mögliche Schreibweisen gefunden Naja egal trotzdem Danke. Nochmal zur 2. Frage: Wenn gefragt ist, (2,1,3) als Produkt von elementaren Transpositionen zu schreiben, reicht es dann wirklich, (1,2) zu schreiben, ohne die 3 zu erwähnen?
15.04.2016, 09:22	Elvis	Auf diesen Beitrag antworten »
Bei Zykeln und insbesondere bei Tupeln schreibt man immer nur die Elemente auf, die zyklisch vertauscht werden. Wenn bei euch in der Vorlesung eine falsche Schreibweise eingeführt wurde, habt ihr ein Problem, weil ihr Zykel nicht von Permutationen unterscheiden könnt. Genau dieses Problem tritt offensichtlich in unserem Dialog auf, was beweist, dass es ein Problem ist. Zum Beispiel ist der Zykel $\begin{eqnarray} (1,2,3)=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \end{eqnarray}$ von der Permutation $\begin{eqnarray} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} \end{eqnarray}$ verschieden. Noch einmal zurück zur Aufgabe. Ich bin sicher, dass Du auch die Definition "elementare Transposition" missverstanden hast. Wenn ich mich recht erinnere an eine Vorlesung Algebra I (ca. 1975), ist eine elementare Transposition eine Transposition benachbarter Elemente. Benachbart sind Elemente in der Ordnung des Tupels, nicht in einer Ordnung der Menge, schon gar nicht in der Ordnung der natürlichen Zahlen ! Zum Beispiel ist $\begin{eqnarray} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 2 & 4 & 5 \\ 1 & 3 & 4 & 2 & 5\end{pmatrix}=(2,3,4)=(2,4)(2,3) \end{eqnarray}$ das Produkt aus zwei elementaren Transpositionen. Die symmetrische Gruppe $\begin{eqnarray} S_n \end{eqnarray}$ wird erzeugt von Transpositionen. Jede Transposition $\begin{eqnarray} (a,b) \end{eqnarray}$ lässt sich als Produkt von elementaren Transpositionen schreiben, indem man a mit dem jeweils rechts stehenden Element vertauscht, bis es die Position von b einnimmt und dann b mit dem jeweils links stehenden Element vertauscht, bis es die ursprüngliche Position von a einnimmt : $\begin{eqnarray} (a,b)=\begin{pmatrix} a & x & y & z & b \\ x & a & y & z & b \\ x & y & a & z & b \\ x & y & z & a & b \\ x & y & z & b & a \\ x & y & b & z & a \\ x & b & y & z & a \\ b & x & y & z & a \end{pmatrix}=(b,x)(b,y)(b,z)(a,b)(a,z)(a,y)(a,x) \end{eqnarray}$ Damit ergibt sich eine vollständige und richtige Darstellung der Gruppe $\begin{eqnarray} S_3 \end{eqnarray}$ durch elementare Transpositionen z. B. so : $\begin{eqnarray} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}=(1,2)^0,\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}=(1,2),\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}=(2,3)(1,3)(1,2),\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}=(2,3),\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}=(1,3)(1,2),\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}=(1,3)(2,3) \end{eqnarray}$ Man sieht auch sehr schön, dass genau die Hälfte der Permutationen aus einer geraden Anzahl von Transpositionen bestehen, das ist die alternierende Gruppe $\begin{eqnarray} A_n<S_n \end{eqnarray}$ , ein Normalteiler vom Index 2. Irgendwann wirst Du lernen, dass die n komplexen Nullstellen eines allgemeinen komplexen Polynoms vom Grad n genau dann durch Radikale berechnet werden können, wenn die $\begin{eqnarray} A_n \end{eqnarray}$ auflösbar ist. Das ist der Fall genau für n<5, und man hat dann die p-q-Formel für quadratische Polynome und die Cardanischen Formeln für Gleichungen 3. und 4. Grades. Für Gleichungen höheren Grades gibt es die Galoistheorie, und dann fängt Algebra an Spaß zu machen.
15.04.2016, 10:01	Transposition	Auf diesen Beitrag antworten »
Hey Elvis, vielen, vielen Dank für diesen fantastischen Beitrag Du hast recht, ich hab die Definition der elementaren Transpositionen falsch verstanden. Das Problem mit der Schreibweise ist mir bewusst, aber ich kann nichts dafür... Wir haben es eindeutig so definiert, in einigen Büchern/Internetquellen ist es auch zum Teil so definiert, auf die Verwechslungsgefahr wird aber deutlich hingewiesen... Scheint keine sehr glücklich gewählte Schreibweise zu sein. Aber das Thema ist mir jetzt klar, da hab ich wirklich was gelernt!! Danke!
15.04.2016, 10:56	Elvis	Auf diesen Beitrag antworten »
Gerne. Denke immer daran, dass Permutationen und insbesondere Zykeln und Transpositionen, so wie alle Abbildungen, von rechts nach links auszuführen sind. Die symmetrischen Gruppen sind ja für n>2 nicht kommutativ, es kommt also auf die Reihenfolge an. Übrigens ist die $\begin{eqnarray} S_3 \end{eqnarray}$ , eine Gruppe der Ordnung 6, die kleinste nichtabelsche Gruppe. (Das ist (oder war ?) eine beliebte Einstiegsfrage bei mündlichen Prüfungen.)

Neue Frage »

Antworten »

Permutationen als Produkt elementarer Transpositionen

Verwandte Themen