inversionen (fehlstände) einer permutation

04.02.2012, 00:13

martinio

Auf diesen Beitrag antworten »

inversionen (fehlstände) einer permutation

Hallo,

habe folgende Frage. In meinem Lin. Algebra Buch ist folgendes Beispiel gegeben:

$\begin{eqnarray*} \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3\end{pmatrix} \end{eqnarray*}$

Wieviele Fehlstände hat diese Permutation?
Meiner Meinung nach eine, nämlich die Paare ( 1 , 2 ). Allerdings sollen noch (1,4) und (3,4) angeben. (3,4) würde ich ja noch verstehen, da es sich um eine bijektive Abbildung handelt, aber warum dann ausgerechnet (1,4) ? ich sehe da keine Verbindung.

Grüße

04.02.2012, 00:27

Kimi_R

Auf diesen Beitrag antworten »

Man kann sich das mit den Fehlständen auch so merken: "Wenn (in der 2. Zeile) rechts davon was kleineres steht"

1<2
1<4
3<4

04.02.2012, 00:32

martinio

Auf diesen Beitrag antworten »

sorry aber das habe ich nicht ganz verstanden.

die zweite zeile ist 2 4 1 3 , da seh ich nur ( 4, 1) mit 1 < 4 , oder darf man auch die "die reihenfolge" vertauschen, bzw. elemente überspringen? Dann würde ich aucha uf ( 2 , 1) mit 1 < 2 und ( 4, 3 ) mit 3 < 4 kommen.

04.02.2012, 00:39

Kimi_R

Auf diesen Beitrag antworten »

Was du mit "Reihenfolge vertauschen" meinst versteh ich nicht so recht, "Elemente überspringen" muss man aber in der Tat

04.02.2012, 00:46

martinio

Auf diesen Beitrag antworten »

Zitat:

Original von Kimi_R
Was du mit "Reihenfolge vertauschen" meinst versteh ich nicht so recht, "Elemente überspringen" muss man aber in der Tat

ah okay gut, dann weiß ich jetzt wie es gemeint ist.

Was soll mir das hier nur sagen?

Die beiden Bemerkungen sind für mich echt nicht so durchsichtig, vorallem die untere, obiges verstehe ich noch mehr oder weniger.

EDIT Math1986: Bilder bitte immer im Forum hochladen!

[attach]22981[/attach]

04.02.2012, 00:55

Kimi_R

Auf diesen Beitrag antworten »

Was genau verstehst du daran nicht
In der Definition steht formal das, was wir eben angewendet haben

Die Bemerkung gibt eine Formel für die Berechnung des Signums der Permutation an, die ich bisher auch noch nicht kannte

Müsstest mir schon genauer sagen, was an der Stelle des Skripts unklar ist.

Anzeige

04.02.2012, 01:01

martinio

Auf diesen Beitrag antworten »

okay , zu aller erstmal wie das signum definiert ist.. die summe der produkte...

04.02.2012, 01:08

Kimi_R

Auf diesen Beitrag antworten »

Alles klar
Erstmal möcht ich sagen, dass du solche Definition nicht auf einen Anschlag aufnehmen musst. Du kannst sie ja auch Stück für Stück an deinem Beispiel durchgehen

In deinem Beispiel ist n = 4
Jetzt soll man die Paare anschauen, so dass
$\begin{eqnarray*} 1 \leq i < j \leq 4 \end{eqnarray*}$

Das wären (1,2), (1,3),...(3,4), d.h. in der ersten Komponente hab ich jetzt die i's stehen und in der zweiten die j

Dann überprüft man ob $\begin{eqnarray*} \sigma(i) > \sigma(j) \end{eqnarray*}$ . Falls ja, so hat man einen Fehlstand, falls nein, so hat man keinen. Muss halt alle oben gesammelten Paare (i,j) durchgehen

Mit s wird jetzt die Anzahl an Fehlständen bezeichnet (in deinem Beispiel also, wie wir gesehen haben, s=3)

Das Signum von deiner Permutation ist jetzt also, gemäß der Definition, (-1)^3
Allgemein ist das Signum 1 falls die Anzahl der Fehlstände gerade ist und sonst -1

04.02.2012, 02:36

martinio

Auf diesen Beitrag antworten »

hey super! das habe ich jetzt schon viel besser verstanden , vielen dank! :=)
Allerdings frage ich mich noch, wenn $\begin{eqnarray*} \sigma(i) > \sigma(j) \end{eqnarray*}$ gitl. sind beide komponenten immer die bilder, oder? d.h. sie beziehen sich auf die zweite zeile!

nun die zweite bemerkung, diese ist ja nichts anderes als eine andere definition so wie ich das sehen. dann gehe ich mal wieder auf dein beispiel ein:

$\begin{eqnarray*} 1 \leq i < j \leq 4 \end{eqnarray*}$

also $\begin{eqnarray*} sign_\sigma = \prod_{1 \leq i < j \leq 4} \frac{\sigma(j) - \sigma(i)}{j - i} \end{eqnarray*}$

D.h. also nichts anderes, dass sich die Fehlstände einer Permutation auch über die Summe der Produkte von $\begin{eqnarray*} \frac{\sigma(j) - \sigma(i)}{j - i} \end{eqnarray*}$ berechnen lassen.

Dabei steht das Bild der größeren Komponente minus das Bild der kleineren Komponente im Zähler und die beiden Komponenten in gleicher Reihenfolge an sich im Nenner. Wie wäre das nun an einem Beispiel? Ich müsste doch alle Paare nun nach der Reihenfogle einsetzen oder nicht?

05.02.2012, 12:58

martinio

Auf diesen Beitrag antworten »

gut kann mir jemand bei der bemerkung helfen?

05.02.2012, 13:05

Trak92

Auf diesen Beitrag antworten »

nimm doch einfach mal
$\begin{eqnarray*} \sigma (x) =<br /> \begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} \end{eqnarray*}$

Und setze für alle Zahlen ein

05.02.2012, 13:14

martinio

Auf diesen Beitrag antworten »

die fehlstände wären hier 2

1 < 3
2 < 3

dann wäre mein erstes paar j ( 1 / 3 ) und i ( 2 / 1 ) mit $\begin{eqnarray*} \sigma(i) < \sigma(j) \end{eqnarray*}$
müsste ich ja hier einsetzen:
$\begin{eqnarray*} sign_\sigma = \prod_{1 \leq i < j \leq 3} \frac{\sigma(j) - \sigma(i)}{j - i} \end{eqnarray*}$

würde ich ja dann als bruch :

$\begin{eqnarray*} \frac{ 3 - 1}{1 - 2} \end{eqnarray*}$ = -2, was ich halt nicht verstehe wie das mit der summe der produkte gemeint ist...

05.02.2012, 13:23

Trak92

Auf diesen Beitrag antworten »

Das große pi ist kein sigma! Es bedeutet, dass du über alle indices multiplizieren musst. Ich machs mal für gegebenes sigma vor:

$\begin{eqnarray*} \sigma (x) =<br /> \begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} <br /> sign(\sigma)=\prod_{i<j}\frac{\sigma (j)-\sigma(i)}{j-i}<br /> =\frac{\sigma (3)-\sigma (1)}{3-1} \cdot \frac{\sigma (2)-\sigma (1)}{2-1}\cdot \frac{\sigma (3)-\sigma (2)}{3-2} \end{eqnarray*}$

$\begin{eqnarray*} =\frac{2-3}{3-1}\cdot \frac{1-3}{2-1}\cdot \frac{2-1}{3-2} \end{eqnarray*}$

05.02.2012, 13:53

martinio

Auf diesen Beitrag antworten »

ahhhhh okay :=) schon wieder verstanden! super jetzt kann ich endlich im skript weiter machen! besten dank! eig. garnicht so schwer, ich sollte mir das öfter an beispielen klarmachen! zum thema der abbildungsmatrix komme ich dann später wieder Augenzwinkern

Augenzwinkern

05.02.2012, 14:17

martinio

Auf diesen Beitrag antworten »

noch eine frage, du hast die rheinfolge der "brüche" von rechts nach links gewählt, im prinzip ist es aber egal wie rum ich dies tue da hier die kommutativität gilt könnte ich auch von links nach rechts gehen und so alle aufmultiplizieren , oder?

wenn ich dies nun ausmultipliziere erhalte ich die zahl 1, dies würde mir ja nun sagen, da die anzahl der fehlstände = 2 ist, ist sign -1 ^2 = 1 , stimmt dies, d.h. die permutation ist gerade.

Wenn ich das nun richtig beurteilen kann, dient diese Bemerkung dazu bei Permutationen mit einer vielzahl von Elementen, schneller zu bewerten ( gerade oder ungerade) als wenn man die inversionen zählen würde.

So in Ordnung? Kann man das so sagen?

05.02.2012, 15:12

Trak92

Auf diesen Beitrag antworten »

ja die brüche kannst du nach belieben umtauschen...

Die bemerkung ist halt dazu da, die Signatur zu definieren, ohne begriffe wie fehlstände zu benutzen, das hört sich ja auch blöd an zu sagen, das eine Funktion fehlstände hat...find ich...

05.02.2012, 15:28

martinio

Auf diesen Beitrag antworten »

alright, könntest du mir dann vll. noch bei der nächsten bemerkung helfen?

[attach]23000[/attach

05.02.2012, 15:50

Trak92

Auf diesen Beitrag antworten »

was gibts da froß zu zu sagen, man beweist halt das sign(rho ring sigma)=sign(rho)*sign(sigma)

du setzt halt die verknüpfung ein und erhälst das produkt...

05.02.2012, 15:51

martinio

Auf diesen Beitrag antworten »

also auch eher trivial für die klausur`?

05.02.2012, 15:53

Trak92

Auf diesen Beitrag antworten »

es ist halt einsetzen in die definition und dann aus einem bruch zwei machen...ob sowas bei euch in der klausur vorkommt keine Ahnung, merken sollte man sich aber nur die definition der signatur mit groß pi also die vorige bemerkung, das herleiten ist dann schnell erledigt...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »