Permutation allgemein (Zyklen, Transpositionen)

02.11.2009, 14:19

Nani

Auf diesen Beitrag antworten »

Permutation allgemein (Zyklen, Transpositionen)

Guten Tag, liebes Matheboard!

Ich habe folgende Permutation gegeben:

$\begin{eqnarray*} \rho = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 10 & 7 & 4 & 8 & 9 & 5 & 1 & 6 & 2 \end{pmatrix} \end{eqnarray*}$

Die erste Teilaufgabe wäre, die Permutation in ein Produkt disjunkter Zyklen zu zerlegen
Folgendes habe ich heraus bekommen: (1 3 7 5 8) (2 10) (4) (6 9)
[sollte eigentlich stimmen: eine Frage jedoch: zwischen die Klammern kommt kein ° (Kringel), oder? ]

Bei der zweiten Teilaufgabe soll man die Permutation in eine Transposition zerlegen.

Heisst das, man soll einfach bei der gegebenen Permutation zwei Einträge vertauschen (zB die 6 mit der 9) oder wie funktioniert das genau?

02.11.2009, 15:20

Mystic

Auf diesen Beitrag antworten »

Ja, die Zyklendarstellung stimmt und man könnte auch $\begin{eqnarray*} \circ \end{eqnarray*}$ zwischen den Zyklen schreiben, üblich ist es aber nicht, so wie man z.B. auch einfach $\begin{eqnarray*} 2ab \end{eqnarray*}$ schreibt und nicht $\begin{eqnarray*} 2 \cdot a \cdot b \end{eqnarray*}$ .

Deine Permutation läßt sich nicht in eine Transposition zerlegen, dazu müsste sie schon selbst eine Transposition sein... Bist du dir sicher, dass du die Aufgabe hier richtig wiedergegeben hast? verwirrt

verwirrt

02.11.2009, 15:28

kiste

Auf diesen Beitrag antworten »

Die Aufgabenstellung ist so gemeint dass er die Permutation in ein Produkt von Transpositionen zerlegen soll.
z.B. (1 2 3) = (1 3)(1 2)

02.11.2009, 15:35

Mystic

Auf diesen Beitrag antworten »

Aha, dann solltest das aber auch so schreiben... Dachte mir schon, dass das so nicht stimmen kann... Augenzwinkern

Augenzwinkern

Fang mal damit an einen Zyklus als Produkt von Transpositionen zu schreiben und beginn dazu am besten mit Zyklen der Länge 3... Versuche das zu steigern, bis du das allgemeine Gesetz siehst... Danach brauchst du dann nur noch diese Darstellungen in die Darstellung der Permutation als Produkt disjunkter Zyklen einsetzen...

03.11.2009, 00:23

Nani

Auf diesen Beitrag antworten »

Ouw - ich entschuldige mich für meinen Fehler!

Das ist wohl ein wenig unter gegangen... unglücklich

unglücklich

Also, ich habe nun folgendes Produkt von Transpositionen erhalten:

$\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 7 & 2 & 5 & 4 & 1 \end{pmatrix} \circ \begin{pmatrix} 6 \\ 6 \end{pmatrix} \circ \begin{pmatrix} 7 & 8 & 9 \\ 8 & 3 & 9 \end{pmatrix} \circ \begin{pmatrix} 10 \\ 10 \end{pmatrix} \end{eqnarray*}$

(wobei man (6,6) und (10,10) auch weglassen könnte..)

Ist das richtig so?

03.11.2009, 00:34

Reksilat

Auf diesen Beitrag antworten »

Nein, das sind keine Transpositionen und die Darstellung ist auch vollkommen konfus und sagt mir gar nichts. verwirrt

verwirrt

Du hast oben ein Produkt von disjunkten Zykeln gegeben. Wenn Du kistes Bemerkung verstanden hast, wie man (1 2 3) in Transpositionen zerlegt, solltest Du auch wissen, was hier zu tun ist.

Gruß,
Reksilat.

Edit: Sorry, Mystic, hatte Dich nicht gesehen. Kannst gerne weitermachen.

Anzeige

03.11.2009, 00:35

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Nani
Ist das richtig so?

Nein.

03.11.2009, 00:48

Nani

Auf diesen Beitrag antworten »

Nein eben, ich seh das korrekte Vorgehen noch nicht so ganz...

Ich habe ja die Zyklen

(1 3 7 5 8 ) (2 10) (4) (6 9)

Dann könnte eine Transposition doch:

(...) (10 2) (4) (9 6) sein, oder?

(bei "..." ist es offensichtlich etwas komplizierter...)

..oder müssen die Klammern nicht mehr so beibehalten werden?
(..Zyklen der Länge 3 gäbe es dann ja nur für den ersten Zykel..)

03.11.2009, 00:59

Mystic

Auf diesen Beitrag antworten »

Transpositionen sind Zyklen der Länge 2, d.h. mit genau 2 Elementen... In obiger Darstellung wären also (2 10) und (6 9) bereits Transpositionen... Den Zyklus ( 1 3 7 5 9) müßte man allerdings erst als Produkt von Transpositionen schreiben, was tatsächlich möglich ist... Ich habe schon weiter oben schon geschrieben, du solltest das mit Zyklen der Länge 3 mal ausprobieren und dann die Länge steigern, bis ein Gesetz sichtbar wird...

03.11.2009, 14:51

Nani

Auf diesen Beitrag antworten »

Also, ich denke, ich habe es verstanden - zumindest für Dreierzyklen:

Angenommen, es gibt ein Zyklus (1 2 3).

Das bedeutet: Die 1 geht nach 3, die 3 nach 2 und die 2 wieder nach 1.
Das Produkt einer solchen Zyklenschreibweise ist als Hintereinanderausführung der Transpositionen zu lesen, also:

(1 3 ) (2 3)

Das bedeutet: Zuerst wird die Transposition (2 3) ausgeführt, und dann (1 3) (von rechts nach links, allgemein gesagt)

Nun fügt man das Wissen der beiden "Teile" zusammen und erhält:

(1 2) (2 3) = (1 2 3)

Ich hoffe, meine "Theorie" stimmt..
..bei eine Zykel der Länge 4 (also bspw. (1 2 3 4) blicke ich nämlich schon nicht mehr ganz durch =(

03.11.2009, 15:19

Reksilat

Auf diesen Beitrag antworten »

Stimmt schon. Einfach um Dir auf die Sprünge zu helfen:
(1 2 3 4)= (1 4)(1 3)(1 2)

Gruß,
Reksilat.

03.11.2009, 23:48

Nani

Auf diesen Beitrag antworten »

Ahhh...

smile

Dann hatte ich doch die richtige Vermutung =)
..nach den letzten Posts war ich so verunsichert, dass ich mir zu unsicher war, meine Vermutung hier preis zu geben..

Das heisst, mein ursprüngliches Produkt von Transpositionen heisst:

(1 8) (1 5) (1 7) (1 3) (2 10) (6 9)

[wenn ich das vom Fischer richtig gelesen habe, kann man die 4 weglassen, oder?]

04.11.2009, 01:01

Reksilat

Auf diesen Beitrag antworten »

Sieht gut aus. Freude

Freude

Die Elemente die festgelassen werden (die sog. Fixpunkte) muss man in dieser Darstellung nicht mehr mit hinschreiben.

Gruß,
Reksilat.

04.11.2009, 01:49

Nani

Auf diesen Beitrag antworten »

Jupii

smile

Zur ursprünglichen (Anfangs-) Permutation hätte ich aber noch eine Frage, bzw. zwei:

Zum einen: Wie um Himmels Willen berechnet man $\begin{eqnarray*} \rho^{1989} \end{eqnarray*}$ ? (bzw. wie sieht das Vorgehen aus?)

..und zum andern: Wie kann man vorgehen, wenn man die kleinste Zahl n (natürlich nicht = 0) finden will, so dass gilt: $\begin{eqnarray*} \rho^n = id \end{eqnarray*}$ ?

Vielen herzlichen Dank für die Hilfe und eine gute Nacht!

04.11.2009, 10:11

Reksilat

Auf diesen Beitrag antworten »

Wenn Du die zweite Frage beantwortet hast, sollte Dir auch die erste nicht mehr schwerfallen.
Schau Dir dazu die verschiedenen elementfremden Zykeln an. Wie oft muss ich z.B. den Zyklus (1 3 7 5 8) hintereinander ausführen, um die Identität zu erhalten. Man sieht, dass diese Anzahl ein Teiler von n sein muss.

Gruß,
Reksilat.

04.11.2009, 17:57

Nani

Auf diesen Beitrag antworten »

Also - ich denke, es wäre gut, wenn du mir zwei Hintereinanderausführungen (also rho^2) zeigen könntest, weil ich mir nicht ganz sicher bin, ob ich das richtig gemacht habe...
Auf alle Fälle würde ich auf 24 (4!) kommen.

04.11.2009, 18:41

Reksilat

Auf diesen Beitrag antworten »

Schau Dir doch mal den Zyklus $\begin{eqnarray*} \pi=(1 3 7 5 8) \end{eqnarray*}$ an, was macht der mit den Elementen?

$\begin{eqnarray*} \begin{array}{c|c|c|c|c|c} &1&3&7&5&8\\\hline\pi&3&7&5&8&1\\\pi^2&7&5&8&1&3\\\pi^3&5&8&1&3&7\\\pi^4&8&1&3&7&5\\\pi^5&1&3&7&5&8\end{array} \end{eqnarray*}$

Wie Du siehst, lässt $\begin{eqnarray*} \pi^5 \end{eqnarray*}$ alle Elemente fest. Es ist also $\begin{eqnarray*} \pi^5={\rm id.} \end{eqnarray*}$

04.11.2009, 19:37

Nani

Auf diesen Beitrag antworten »

Ahhh

smile

geeeeenial! =)

Und (2 10) und (6 9) kann ich "weglassen", weil das dann "nur" Pi^1 geben würde, also einfach n=1.

$\begin{eqnarray*} \rho^{1983} \end{eqnarray*}$ wäre dann (5 8 1 3 7) , nicht wahr?

05.11.2009, 01:02

Reksilat

Auf diesen Beitrag antworten »

Nein, das ist nicht richtig.

Schauen wir uns doch mal die Permutation $\begin{eqnarray*} \pi=(1 3 7 5 8)(24) \end{eqnarray*}$ an, was macht diese mit den Elementen?

$\begin{eqnarray*} \begin{array}{c|c|c|c|c|c|c|c} &1&3&7&5&8&2&4\\\hline\pi&3&7&5&8&1&4&2\\\pi^2&7&5&8&1&3&2&4\\\pi^3&5&8&1&3&7&4&4\\\pi^4&8&1&3&7&5&2&4\\\pi^5&1&3&7&5&8&4&2\end{array} \end{eqnarray*}$

Hier lässt $\begin{eqnarray*} \pi^5 \end{eqnarray*}$ nicht mehr alle Elemente fest. Allerdings ist dann $\begin{eqnarray*} \pi^{10}={\rm id.} \end{eqnarray*}$
Wenn Du verstanden hast, warum das so ist, bist Du einen großen Schritt weiter. Augenzwinkern

Augenzwinkern

Gruß,
Reksilat.

05.11.2009, 09:29

Nani

Auf diesen Beitrag antworten »

Oke, ich habe mein Produkt nun auch so vollständig aufgeschrieben.

Der erste Zyklus hatten wir ja schon - und die anderen zwei sind ja Zweierzyklen, das heisst, das Vorgehen ist gleich - ergo komme ich auch auf n = 10.

05.11.2009, 14:39

Reksilat

Auf diesen Beitrag antworten »

Wieso habe ich denn gestern eigentlich die Lösung schon fast verraten? Ich Schussel! Ein guter Lehrer hätte da ganz andere Beispiele genommen. Hammer

Hammer

Egal, es bleibt noch die Frage, wieso 10 die kleinste natürliche Zahl mit dieser Eigenschaft ist.

Und wenn Du Lust hast, kannst Du Dir ja auch noch entsprechendes für (1 3 10)(2 5 7 6 9 8 4) und (1 6 2 4)(2 10 5 8 3 7 9) überlegen. Augenzwinkern

Augenzwinkern

Gruß,
Reksilat.

05.11.2009, 15:50

Nani

Auf diesen Beitrag antworten »

Hehe :-)
Vielen Dank - ich glaube, ich habe es wirklich verstanden =)
Stichwort: kgV sollte alle Zweifel klären ;-)

Besten Dank!

05.11.2009, 15:53

Reksilat

Auf diesen Beitrag antworten »

Ausgezeichnet! Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »