Permutation u. Transposition < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Schreiben Sie die Permutationen [mm] \pmat{ 1 & 2 & 3 & 4 \\
2 & 3 & 4 & 1 } [/mm] und [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\
4 & 5 & 2 & 1 & 3 } [/mm] als Produkte von
Transpositionen. |
Ich weiß was Transpositionen und Permutationen sind und auch wie man Matrizen multipliziert. Hier stellt sich mir erstmal die Frage was ich mache: Bilde ich die Transpositionen und bilde dann das Produkt (oder andersrum, ist ja egal) und ignoriere dass es sich um Permutationen handelt? Ich wüsste nicht wie ich die Permutation da unterbringen soll.
Ich löse die aufgabe ja selbst (und poste sie dann hier zur kontrolle), weiß aber nicht genau wie der anfang ist.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:20 Do 02.11.2006 | | Autor: | piet.t |
Hallo celeste,
ACHTUNG!!!!!!
bei dieser Schreibweise von Permutationen stehen zwar auch irgenwelche Zahlen in einem rechteckigen Schema, es sind aber keine(!!!!!) Matrizen, folglich multipliziert man hier auch anders.
Mal an einem kleinen Beispiel:
[mm]A=\pmat{ 1 & 2 & 3\\ 3 & 2 & 1}[/mm]
[mm]B=\pmat{ 1 & 2 & 3\\ 3 & 1 & 2}[/mm]
D.h. also A ist die Permutation, die 1 auf 3 abbildet, 2 auf 2 und 3 auf 1.
Entsprechend gilt für B: [mm] 1\to3, 2\to1, 3\to2.
[/mm]
Das "Produkt" der Permutationen ist jetzt die hintereinanderausführung dieser Abbildungen, d.h. in diesem Fall:
[mm]A\circ B = \pmat{ 1 & 2 & 3\\ 1 & 3 & 2}[/mm]
Denn wenn man erst B und dann A ausführt ergeben sich ja folgende Bilder:
[mm] 1\to [/mm] 3 [mm] \to [/mm] 1
2 [mm] \to [/mm] 1 [mm] \to [/mm] 3
3 [mm] \to [/mm] 2 [mm] \to [/mm] 2
Versuch das jetzt erstmal einigermaßen zu verdauen, vielleicht kommst Du dann ja schon selbst weiter. Ansonsten kannst Du ja nochmal nachfragen.
Gruß
piet
|
|
|
| |
|
ah danke.
dann ist die Multiplikation also:
[mm] A^{T}*B^{T} [/mm] = [mm] (AB)^{T}
[/mm]
A [mm] \circ [/mm] B = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 5 & 2 & 1 & 4 }
[/mm]
1->2->5
2->3->2
3->4->1
4->1->4
B hat eine Spalte mehr - egal?
und davon jetzt die Transposition:
[mm] (AB)^{T} [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 5 & 2 & 1 & 4 }^{T}
[/mm]
= [mm] \pmat{ 1 & 5 \\ 2 & 2 \\ 3 & 1 \\ 4 & 4}
[/mm]
hoffe das ist richtig so, das müsste es dann auch mit der aufgabe gewesen sein (oder fehlt noch was??).
Sagt mir bitte bescheid wenn es vollkommener schwachsinn war was ich gemacht habe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:35 Do 02.11.2006 | | Autor: | piet.t |
Hallo,
das war nochmal daneben, aber jetzt sehe ich noch etwas klarer, wo die Probleme liegen.
1.) Eine Permutation ist ja eine bijektive Abbildung einer Menge auf sich selbst, d.h. einfach eine Umsortierung der Elemente.
2.) "Transposition" steht erstmal für "Vertauschung". Das transponieren einer Matrix bedeutet, die Rollen von Zeilen und Spalten zu vertauschen. Im Zusammenhang mit Permutationen darf man das aber nicht so sehen, hier bedeutet "Transposition" eine spezielle Art von Permutation, nämlich eine, die zwei Elemente vertauscht und alle anderen fest läßt.
3.) Ein Satz über Permutationen sagt aus, dass sich jede Permutation als hintereinanderausführung von Vertauschungen darstellen läßt - und genau dazu soll die Aufgabe zwei Beispiele liefern.
Nochmal ausdrücklich: die Hintereinanderschaltung von Permutationen hat rein gar nichts mit einem Matrixprodukt zu tun - dass die Schreibweisen ähnlich aussehen ist ein unglücklicher Zufall.
Bei den beiden gegebenen Permutationen handelt es sich ja einmal um eine Permutation von 4 Elementen, einmal um eine von 5 Elementen - die darf man nicht so einfach miteinander multiplizieren - welche Menge sollte denn dann das Produkt permutieren? 1 bis 4 oder 1 bis 5?
In der Aufgabe sollst Du jetzt einfach für jede der gegebenen Permutationen überlegen welche Vertauschungen Du nacheinander durchführen musst um zum selben Ergebnis wie die angegebene Permutation zu kommen - Du kannst ja erst mal versuchen das erste Beispiel auszuknobeln, dann können wir nochmal über Deinen Lösungsversuch schauen.
Gruß
piet
|
|
|
| |
|
gut, dann ist bei mir alles verloren. jetzt ist mir erst mal garnix mehr klar.
d.h. ich muss erst transponieren und dann die verknüpfung machen.
das transponieren ist aber was ganz anderes als ich das kenne.
(hoffe ich verknüpfe wenigstens richtig  )
wie meinst du das mit vertauschen der elemente:
im sinne von
[mm] \pmat{ 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 } [/mm] oder [mm] \pmat{ 1 & 2 & 3 & 4 \\ 2 & 5 & 4 & 1 } [/mm] (aus B die 2 und 5)
aber wie ich meine denkweise kenne ist es was ganz anderes.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:17 Fr 03.11.2006 | | Autor: | statler |
Guten Morgen Celeste!
Beispiele für Transpositionen im hier gemeinten Sinne sind
[mm]\pmat{ 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 }[/mm]
oder auch
[mm]\pmat{ 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 }[/mm]
2 Elemente werden miteinander vertauscht, der Rest bleibt fest.
Du kannst ja zum Üben diese beiden mal miteinander multiplizieren, in beiden möglichen Reihenfolgen, und gucken, was sich ergibt.
Zur Schreibweise kommen wir dann vllt später noch.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
zu deinem Beispiel
[mm] T_1*T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 }
[/mm]
[mm] T_2*T_1 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 }
[/mm]
ok, dann meinen die wohl mit der Aufagebnstellung das ich 2 Transpositionen pro Permutation erstellen soll und dann die Transpositionen Multiplizieren soll (praktisch 2 aufgaben) - oder schon wieder falsch?
Ausgangspermutation:
[mm] \pmat{ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 }
[/mm]
Transposition 1:
[mm] \pmat{ 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2 }
[/mm]
Transposition 2:
[mm] \pmat{ 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 }
[/mm]
[mm] T_1*T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 }
[/mm]
1->1->3
2->3->4
3->4->1
4->2->2
und:
Ausgangspermutation:
[mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 1 & 3 }
[/mm]
Transposition 1:
[mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 2 & 1 & 3 }
[/mm]
Transposition 2:
[mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 5 & 1 & 3 }
[/mm]
[mm] T_1*T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 4 & 5 }
[/mm]
1->5->3
2->4->1
3->2->2
4->1->4
5->3->5
ist das jetzt das was die von mir wollen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:11 Fr 03.11.2006 | | Autor: | statler |
Mahlzeit!
> zu deinem Beispiel
> [mm]T_1*T_2[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 }[/mm]
> [mm]T_2*T_1[/mm]
> = [mm]\pmat{ 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 }[/mm]
Ich hab's gar nicht nachgerechnet, denn ...
> ok, dann meinen die wohl mit der Aufagebnstellung das ich 2
> Transpositionen pro Permutation erstellen soll und dann die
> Transpositionen Multiplizieren soll (praktisch 2 aufgaben)
> - oder schon wieder falsch?
>
> Ausgangspermutation:
> [mm]\pmat{ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 }[/mm]
>
> Transposition 1:
> [mm]\pmat{ 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2 }[/mm]
>
> Transposition 2:
> [mm]\pmat{ 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 }[/mm]
... das sind beides keine Transpositionen! Bei einer Transposition werden 2 Elemente miteinander vertauscht und alle anderen festgehalten (auf sich abgebildet). Bei deiner Tr. 1 bleibt die 1 fest und sonst nix. Bei Tr. 2 die 2 und kein weiteres Element.
> [mm]T_1*T_2[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 }[/mm]
> 1->1->3
> 2->3->4
> 3->4->1
> 4->2->2
>
> und:
>
> Ausgangspermutation:
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 1 & 3 }[/mm]
>
> Transposition 1:
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 2 & 1 & 3 }[/mm]
Bei der bleibt kein Elem. fest, also keine Tr.
> Transposition 2:
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 5 & 1 & 3 }[/mm]
Und bei der nur die 2, also auch keine Tr.
> [mm]T_1*T_2[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 4 & 5 }[/mm]
>
> 1->5->3
> 2->4->1
> 3->2->2
> 4->1->4
> 5->3->5
>
> ist das jetzt das was die von mir wollen?
Offenbar noch nicht!
Bis denne
Dieter
|
|
|
| |
|
ich habe unter fest was anderes verstanden, also nochmal schritt für schritt:
ich habe eine Permutation:
[mm] \pmat{ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 }
[/mm]
daraus bilde ich 2 Transpositionen:
[mm] T_1 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 }
[/mm]
[mm] T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 }
[/mm]
sind das jetzt 2 transpositionen von meiner Permutation ?
jetzt multipliziere ich die:
[mm] T_1*T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 }
[/mm]
1->1->3
2->2->2
3->4->4
4->3->1
jetzt richtig?
die andere Permutation mach ich leiber erst wenn ich das system verstanden haben
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:40 Fr 03.11.2006 | | Autor: | statler |
Hey!
> ich habe unter fest was anderes verstanden, also nochmal
> schritt für schritt:
> ich habe eine Permutation:
> [mm]\pmat{ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 }[/mm]
>
> daraus bilde ich 2 Transpositionen:
ohne 'daraus'; du bildest 2 T.
> [mm]T_1[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 \\ 1 & 2 & 4 & 3 }[/mm]
>
> [mm]T_2[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 }[/mm]
>
> sind das jetzt 2 transpositionen von meiner Permutation ?
Das sind jetzt 2 Transpositionen. Das sind immer 2 T., auch ohne daß irgendeine gegeben ist.
> jetzt multipliziere ich die:
> [mm]T_1*T_2[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 }[/mm]
>
> 1->1->3
> 2->2->2
> 3->4->4
> 4->3->1
>
> jetzt richtig?
Leider nicht, weil Transpositionen u. Permutationen überhaupt Abbildungen sind, die verknüpft man üblicherweise von rechts nach links. Da das i. a. nicht kommutativ ist, ergibt sich ein anderes Ergebnis. Oder gibt es bei euch eine andere Vereinbarung?
1 -> 4
2 -> 2
3 -> 1
4 -> 3
Prüf's nach
Du bist auf dem richtigen Weg, noch nicht heiß, aber schon warm ...
Bis zum nächsten Mal
Dieter
|
|
|
| |
|
ne, haben wir nicht. das war auch ne sache bei der ich mir nicht sicher war:
wir haben das glaub ich
[mm] T_1 \circ T_2 [/mm] genannt und es war mir unklar ob das jetzt die Multiplikation ist.
ich mach das ganze jetzt für das 2. Beispiel
[mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 1 & 3 }
[/mm]
[mm] T_1 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 4 & 5 & 3 }
[/mm]
[mm] T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 }
[/mm]
[mm] T_1*T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 4 & 3 & 1 }
[/mm]
1->4->5
2->2->2
3->3->4
4->5->3
5->1->1
noch n fehler?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:07 Fr 03.11.2006 | | Autor: | statler |
> ne, haben wir nicht. das war auch ne sache bei der ich mir
> nicht sicher war:
> wir haben das glaub ich
> [mm]T_1 \circ T_2[/mm] genannt und es war mir unklar ob das jetzt
> die Multiplikation ist.
>
> ich mach das ganze jetzt für das 2. Beispiel
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 1 & 3 }[/mm]
> [mm]T_1[/mm] =
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 4 & 5 & 3 }[/mm]
> [mm]T_2[/mm] =
> [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 }[/mm]
>
> [mm]T_1*T_2[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 4 & 3 & 1 }[/mm]
>
> 1->4->5
> 2->2->2
> 3->3->4
> 4->5->3
> 5->1->1
>
> noch n fehler?
Nee, nur, daß das keine Transpositionen sind.
|
|
|
| |
|
schei*e, sorry dass ich dich so nerve.
es müssen 3 feste stellen sein:
[mm] T_1 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 }
[/mm]
[mm] T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 3 & 4 & 1 }
[/mm]
[mm] T_1*T_2 [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 }
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:31 Fr 03.11.2006 | | Autor: | statler |
> schei*e, sorry dass ich dich so nerve.
Überhaupt nich Scheibe!
> es müssen 3 feste stellen sein:
JAA!
> [mm]T_1[/mm] = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 }[/mm]
> [mm]T_2[/mm]
> = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 3 & 4 & 1 }[/mm]
> [mm]T_1*T_2[/mm]
> = [mm]\pmat{ 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 3 & 5 & 1 }[/mm]
![[ok]](/images/smileys/ok.gif "[ok]") Das hast du ganzganz toll gemacht!
Jetzt noch eben zur Schreibweise (für später). Man schreibt einfacher [mm] T_{1} [/mm] = (45), das bedeutet 4 und 5 werden vertauscht, der ganze Rest bleibt fest.
Ein superduper Wochenende
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:33 Fr 03.11.2006 | | Autor: | celeste16 |
DAAANKE für die Hilfe.
ich wünsche auch dir ein schönes wochenende.
und danke nochmal für deine geduld.
tschüs
|
|
|
|
