Permutationen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe versuche mir mit selbstgebastelten beispielen Definitionen und Sätze verständlicher (und "merkbarer") zu machen; daher habe ich Fragen zu Permutationen und Transpostitionen:
1.)
ich habe zwei mengen jeweils {1,2,3}, die zuordnung sieht so aus:
1 3
2 2
3 1
hierbei gibt es ja eine Transposition (vertauschung), weshalb es sich um eine ungerade Permutation handelt, oder?
wenn ich jetzt das signum der permutation berechnen möchte, dan nehme ich da diese formel:
sgn [mm] \pi=\produkt_{1
[mm] =\bruch{1-3}{3-1}=-1 [/mm] (ja?)
Die Fehlstände berechne ich mit sgn [mm] \pi=-1^{s} [/mm] und s=anzahl der fehlstände..
soweit kein problem, wenn das stimmt..
aber wenn ich jetzt ein beispiel :
1 3
2 1
3 2
nehme, so mehrere transpositionen (2--> deshalb gerade permut.) vorkommen, wie setzte ich das dann in die formeln ein???
[Dateianhang nicht öffentlich]
Kann mir jemand helfen?
Vielen dank schonmal
LG
pythagora
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:50 Do 08.04.2010 | | Autor: | pythagora |
hat jemand vielleicht eine Idee?? Ich komme da immer noch nicht weiter :(
Liebe Grüße
pythagora
|
|
|
| |
|
Hallo pythagora,
wir betrachten die Menge $M = [mm] \{1,2,3\}$. [/mm] Eine Permutation von $M$ ist eine bijektiv Abbildung von $M$ auf sich selbst. Deine Permutation [mm] $\pi$ [/mm] ist definiert durch [mm] $\pi(1) [/mm] = 3$, [mm] $\pi(2) [/mm] = 2$ und [mm] $\pi(3) [/mm] = 1$. (Verwendet man die Zyklendarstellung, so ist [mm] $\pi [/mm] = (13)(2) = (13)$, wobei man die $(2)$ getrost weglassen kann.) [mm] $\pi$ \textbf{ist} [/mm] eine Transposition (= $2$-Zyklus) und somit eine ungerade Permutation. Deshalb wissen wir, dass [mm] $sgn(\pi)=\prod_{1\leq i < j \leq n}^{}\frac{\pi(j)-\pi(i)}{j-i} [/mm] = [mm] -1\,(n [/mm] = 3)$ (In deiner Formel fehlen die Gleichheitszeichen!) ist. (Bemerkung: Das ist die Methode aus Fehlständen (Inversionen) das Signum einer Permutation zu bestimmen. Es geht aber oft viel leichter über die sogenannten Bahnen der Permutation!). Also, wir berechnen [mm] $sgn(\pi)=\prod_{1\leq i < j \leq 3}^{}\frac{\pi(j)-\pi(i)}{j-i} [/mm] = [mm] \frac{\pi(2) - \pi(1)}{2-1}\cdot \frac{\pi(3) - \pi(1)}{3-1}\cdot \frac{\pi(3) - \pi(2)}{3-2} [/mm] = [mm] \frac{2 - 3}{2-1}\cdot \frac{1 - 3}{3-1}\cdot \frac{1 - 2}{3-2} [/mm] = -1$. Es ist [mm] $sgn(\pi) [/mm] = [mm] (-1)^s$ [/mm] und nicht [mm] $sgn(\pi) [/mm] = [mm] -1^s$.
[/mm]
Deine nächste Beispielpermutation (lass es uns [mm] $\sigma$ [/mm] nennen) [mm] $\sigma [/mm] = (132)$ (Zyklendarstellung)
ist das Produkt zweier Transpositionen: [mm] $\sigma [/mm] = (13)(12)$. Die Anzahl der Fehlstände ist die Mächtigkeit der Tupel-Menge [mm] $\{(i,j) : 1\leq i,j \leq n \text{ mit } i < j \text { und } \sigma(i)>\sigma(j))\}$ [/mm] (hier ist $n= 3$). Die Menge der Fehlstände von [mm] $\sigma$ [/mm] ist also die Tupel-Menge [mm] $\{(1,3) , (1,2)\}$.
[/mm]
Ich hoffe, das Du jetzt sehen kannst , dass $sgn [mm] (\sigma) [/mm] = 1$ ist.
Gruß mathfunnel
|
|
|
| |
|
Hallo mathfunnel,
vielen lieben dank erstmal für deine Hilfe.
Ich habe allerdings noch Fragen:
> Deshalb wissen wir, dass [mm]sgn(\pi)=\prod_{1\leq i < j \leq n}^{}\frac{\pi(j)-\pi(i)}{j-i} = -1\,(n = 3)[/mm]
> (In deiner Formel fehlen die Gleichheitszeichen!) ist.
> (Bemerkung: Das ist die Methode aus Fehlständen
> (Inversionen) das Signum einer Permutation zu bestimmen.
ich dachte [mm] sgn(\pi) [/mm] = [mm] (-1)^s [/mm] wäre die formel mit den Felhständen?? So steht es zumindest im skript bei mir?!
> Es
> geht aber oft viel leichter über die sogenannten Bahnen
> der Permutation!). Also, wir berechnen
> [mm]sgn(\pi)=\prod_{1\leq i < j \leq 3}^{}\frac{\pi(j)-\pi(i)}{j-i} = \frac{\pi(2) - \pi(1)}{2-1}\cdot \frac{\pi(3) - \pi(1)}{3-1}\cdot \frac{\pi(3) - \pi(2)}{3-2} = \frac{2 - 3}{2-1}\cdot \frac{1 - 3}{3-1}\cdot \frac{1 - 2}{3-2} = -1[/mm].
ok, bei diesem beispiel klar, danke dir^^
Aber wie ist das mit dem zweiten beispiel, kann ich das da auch mit den bahnen machen?? ich hab das so gemacht:
[mm] sgn(\pi)=\prod_{1\leq i < j \leq 3}^{}\frac{\pi(j)-\pi(i)}{j-i} [/mm] = [mm] \frac{\pi(2) - \pi(1)}{2-1}\cdot \frac{\pi(3) - \pi(1)}{3-1}\cdot \frac{\pi(3) - \pi(2)}{3-2} =\bruch{-2}{1}*\bruch{-1}{2}*\bruch{1}{1}=1
[/mm]
und da es 2 Fehlstände sind, sind es hierbei [mm] (-1)^{2}=1
[/mm]
also ist signum=1 für das zweite beispiel, ja?
und beim ersten beispiel sind es da 3 fehlstände und daher [mm] (-1)^{3}=-1???
[/mm]
> Es ist [mm]sgn(\pi) = (-1)^s[/mm] und nicht [mm]sgn(\pi) = -1^s[/mm].
> Deine
> nächste Beispielpermutation (lass es uns [mm]\sigma[/mm] nennen)
> [mm]\sigma = (132)[/mm] (Zyklendarstellung)
> ist das Produkt zweier Transpositionen: [mm]\sigma = (13)(12)[/mm].
> Die Anzahl der Fehlstände ist die Mächtigkeit der
> Tupel-Menge [mm]\{(i,j) : 1\leq i,j \leq n \text{ mit } i < j \text { und } \sigma(i)>\sigma(j))\}[/mm]
> (hier ist [mm]n= 3[/mm]). Die Menge der Fehlstände von [mm]\sigma[/mm] ist
> also die Tupel-Menge [mm]\{(1,3) , (1,2)\}[/mm].
also muss ich für die berechnung über die fehlstände einen ring (1,3,2) machen und den dann in (x,y) zerlegen. Aber wie genau geht das?? der rückweg von (1,3)(1,2) zu (1,3,2) ist klar, da ich einfach von rechts nach links verknüpfe, aber wie komme ich auf die zweier paare?? gibt es da eine regel??
Hilfe wäre super..
Vielen Dank
pythagora
|
|
|
| |
|
Hallo pythagora,
erstmal zu den Bahnen: Die Bahnen und die Zyklendarstellung habe ich nur erwähnt, aber ich habe sie hier nicht benutzt!
Es ist korrekt, dass [mm] $sgn(\pi) [/mm] = [mm] (-1)^s$ [/mm] die "'Formel mit den Fehlständen"' ist, da ja $s$ die Anzahl der Fehlstände ist. Aber diese Formel unterscheidet sich kaum von [mm] $sgn(\pi)=\prod_{1\leq i < j \leq n}^{}\frac{\pi(j)-\pi(i)}{j-i}$. [/mm] Das kann man leicht erkennen, wenn man die Zähler den Nennern so zuordnet, dass das Produkt aussieht wie [mm] $\prod_{1\leq i < j \leq n}^{}\frac{\pm(j-i)}{j-i}$, [/mm] wobei das Vorzeichen entsprechend gewählt werden muss. Der Unterschied der beiden Formeln ist lediglich, dass
die erste die Anzahl der Fehlstände als bekannt voraussetzt, während die zweite implizit die Fehlstände "'zählt"'.
Deine Berechnungen bzgl. des zweiten Beispiels sind völlig korrekt. Ebenfalls hast Du richtig erkannt, dass die Anzahl der Fehlstände im ersten Beispiel gleich $3$ ist.
Die Anzahl der Fehlstände ist gleich der Anzahl der Indextupel $(i,j)$ mit den erwähnten Eigenschaften. Der Ausdruck $(i,j)$ ist keine Permutation! Beispielsweise ist im zweiten Beispiel das Tupel $(1,2)$ ein Fehlstand, weil [mm] $\sigma(1) [/mm] > [mm] \sigma(2)$ [/mm] aber $1 < 2$ ist.
LG mathfunnel
|
|
|
| |
|
Hallo mathfunnel,
vielen Dank, dass du mir hilfst.
> Aber diese Formel unterscheidet sich kaum von
> [mm]sgn(\pi)=\prod_{1\leq i < j \leq n}^{}\frac{\pi(j)-\pi(i)}{j-i}[/mm].
> Das kann man leicht erkennen, wenn man die Zähler den
> Nennern so zuordnet, dass das Produkt aussieht wie
> [mm]\prod_{1\leq i < j \leq n}^{}\frac{\pm(j-i)}{j-i}[/mm], wobei
> das Vorzeichen entsprechend gewählt werden muss. Der
> Unterschied der beiden Formeln ist lediglich, dass
> die erste die Anzahl der Fehlstände als bekannt
> voraussetzt, während die zweite implizit die Fehlstände
> "'zählt"'.
Aber wie kommst du von der ersten formel auf die zweite?? denn irdendwie ist ja das [mm] \pi [/mm] weg..
> Deine Berechnungen bzgl. des zweiten Beispiels sind völlig
> korrekt. Ebenfalls hast Du richtig erkannt, dass die Anzahl
super, danke.
> Die Anzahl der Fehlstände ist gleich der Anzahl der
> Indextupel [mm](i,j)[/mm] mit den erwähnten Eigenschaften. Der
> Ausdruck [mm](i,j)[/mm] ist keine Permutation! Beispielsweise ist im
> zweiten Beispiel das Tupel [mm](1,2)[/mm] ein Fehlstand, weil
> [mm]\sigma(1) > \sigma(2)[/mm] aber [mm]1 < 2[/mm] ist.
ok. Und wenn ich jetzt einen ring (a,b,c) habe und diesen in tupel zerlege, bekomme ich (a,b),(a,c) oder?? aber wie komme ich so allegemein darauf (bei sowas kurzem geht das noch, aber wie zerlege ich längere ringe in tupel? immer das erste element mit dem zweiten in ein tupel & dann das erste mit dem dritten und so weiter??
LG pythagora
|
|
|
| |
|
Hallo pythagora,
> Aber wie kommst du von der ersten formel auf die zweite?? denn irdendwie ist ja das $ [mm] \pi [/mm] $ weg.. "'
Das ist der Witz! Das [mm] $\pi$ [/mm] ist eine Permutation und vertauscht deshalb nur die Indizes. Nimm eins der Beispiele und suche zu jedem Zähler $(j-i)$ im Produkt, den Nenner der gleich $(j-i)$ oder $(i-j)= -(j-i)$ ist! Daran sieht man auch, dass $ [mm] \prod_{1\leq i < j \leq n}^{}\frac{\pi(j)-\pi(i)}{j-i} \in \{1,-1\}$ [/mm]
> ok. Und wenn ich jetzt einen ring (a,b,c) habe und diesen in tupel zerlege, bekomme ich (a,b),(a,c)
> oder?? aber wie komme ich so allegemein darauf (bei sowas kurzem geht das noch, aber wie zerlege ich
> längere ringe in tupel? immer das erste element mit dem zweiten in ein tupel [mm] \& [/mm] dann das erste mit
> dem >dritten und so weiter??
Was meinst Du mit einem Ring? Wenn [mm] $\zeta$ [/mm] ein Zyklus ist, für den in der Zyklendarstellung [mm] $\zeta [/mm] = (abc)$ gilt, dann ist $(abc) = (ab)(ac)$ (wenn man zuerst die Transposition $(ab)$ und danach $(ac)$ als Abbildung ausführt$. Das hängt von der Konvention ab, die man benutzt). Der Zusammenhang mit der Anzahl $s$ der Fehlstände ist [mm] $(-1)^s [/mm] = [mm] (-1)^r$, [/mm] wobei $r$ die Anzahl der in der "'Transpositionszerlegung"' vorkommenden Transpositionen ist. Dazu solltest Du aber erstnmal in der Literatur nachlesen, was eine Zyklendarstellung ist, falls Du das noch nicht weißt.
LG mathfunnel
|
|
|
|
