sign(pi) eindeutig

30.08.2006, 15:52

sunbird

sign(pi) eindeutig

Ich möchte gerne beweisen, daß $\begin{eqnarray*} sign(\pi) \end{eqnarray*}$ , für $\begin{eqnarray*} \pi \end{eqnarray*}$ eine beliebige Permutation, eindeutig ist.

Es läßt sich ja jede Permutation als Produkt von Transpositionen schreiben. Soviel ist klar. Nun ist die Anzahl der Transpositionen aber nicht eindeutig - wohl aber, ob die Anzahl gerade oder ungerade ist. Und darauf läuft der Beweis ja hinaus. Leider habe ich keinen richtigen Ansatz da wir das Thema nur gestreift haben.

Wäre nett wenn mir jemand einen Tipp geben könnte smile

30.08.2006, 17:11

therisen

Auf diesen Beitrag antworten »

Hallo,
bei mir ist es auch schon lange her, dass ich mal etwas zur symmetrischen Gruppe gelesen habe, aber ich kann es ja mal probieren.

Für $\begin{eqnarray*} \sigma, \tau \in S_n \end{eqnarray*}$ gilt $\begin{eqnarray*} i(\sigma \tau) \equiv i(\sigma) + i(\tau) \pmod 2 \end{eqnarray*}$ . Der Beweis dazu ist nicht ganz einfach, also hoffe ich, du kennst diesen Satz.

Es seien also $\begin{eqnarray*} \sigma \end{eqnarray*}$ und $\begin{eqnarray*} \tau \end{eqnarray*}$ zwei verschiedene Darstellungen derselben Permutation, d.h. es gilt $\begin{eqnarray*} \sigma = \tau \end{eqnarray*}$ . Nun ist nach obigem Satz $\begin{eqnarray*} i(\sigma \sigma) \equiv 0 \pmod 2 \end{eqnarray*}$ und daher $\begin{eqnarray*} 0 \equiv i(\sigma \tau) \equiv i(\sigma) + i(\tau) \pmod 2 \end{eqnarray*}$ . Daraus folgt nun, dass $\begin{eqnarray*} i(\sigma) \equiv i(\tau) \pmod 2 \end{eqnarray*}$ ist und somit also $\begin{eqnarray*} \operatorname{sgn}(\sigma) = \operatorname{sgn}(\tau) \end{eqnarray*}$ .

Man reiße mir bitte nicht den Kopf ab, wenn das falsch ist Augenzwinkern

Gruß, therisen

30.08.2006, 18:31

irre.flexiv

Auf diesen Beitrag antworten »

Zitat:

Allerdings ist $\begin{eqnarray*} g:= f^{-1} \end{eqnarray*}$ in $\begin{eqnarray*} x_0 = 0 \end{eqnarray*}$ unstetig.

Was ist i?

Edit: Wie genaus habt ihr sign definiert sunbird?

30.08.2006, 18:46

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von irre.flexiv

Zitat:

Allerdings ist $\begin{eqnarray*} g:= f^{-1} \end{eqnarray*}$ in $\begin{eqnarray*} x_0 = 0 \end{eqnarray*}$ unstetig.

Was ist i?

Edit: Wie genaus habt ihr sign definiert sunbird?

Hm, irgendwie sehe ich keinen Zusammenhang zwischen dem Zitat und deinem Beitrag Big Laugh

$\begin{eqnarray*} i(\pi) \end{eqnarray*}$ gibt die Zahl der Inversionen von $\begin{eqnarray*} \pi \end{eqnarray*}$ an.

$\begin{eqnarray*} \operatorname{sgn}(\pi) = (-1)^{i(\pi)} \end{eqnarray*}$

30.08.2006, 18:52

irre.flexiv

Auf diesen Beitrag antworten »

*Rofl* das ist mir ja auch noch nicht untergekommen Big Laugh

31.08.2006, 18:34

sunbird

Auf diesen Beitrag antworten »

Hallo,
also erstmal danke für die Antworten.
Wir haben es wie folgt definiert: $\begin{eqnarray*} sign(\pi) = (-1)^{f(\pi)} \text{ mit } f(\pi) = \sum_{i=1}^k (m_i - 1) \end{eqnarray*}$ wobei die $\begin{eqnarray*} m_i \end{eqnarray*}$ die Zykellängen von Pi sind. Aber später haben wir nur noch $\begin{eqnarray*} sign(\pi) = (-1)^{(\text{Anzahl der Transpositionen von }\pi)} \end{eqnarray*}$ benutzt.

Wir haben das aber echt nur ganz kurz auf zwei Seiten gestreift. Aber da unser Prof. ein Freund der Gruppentheorie ist dachte ich mir, fürs Vordiplom schadet es nicht, sich mal mit der Symmetrischen Gruppe zu beschäftigen Augenzwinkern

Den Satz kannte ich noch nicht - aber da ich jetzt weiß wonach ich suchen muß sollte das schon hinhauen.

LG,
sunbird smile

01.10.2006, 19:55

therisen

Auf diesen Beitrag antworten »

Auch wenn das Thema schon etwas älter ist, möchte ich der Vollständigkeit halber noch diesen wunderschön raffinierten Beweis posten, den ich gerade gelesen habe. Inhaltlich wiedergegeben lautet er:

Sei $\begin{eqnarray*} \pi \in S_n \end{eqnarray*}$ ( $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ ) und es gelte $\begin{eqnarray*} \pi = \prod_{i=1}^k t_{k+1-i} \end{eqnarray*}$ sowie $\begin{eqnarray*} \pi = \prod_{i=1}^l t'_{l+1-i} \end{eqnarray*}$ mit geeigneten Transpositionen $\begin{eqnarray*} t_{i}, t'_{j} \end{eqnarray*}$ ( $\begin{eqnarray*} 1 \leq i \leq k, \; 1 \leq j \leq l \end{eqnarray*}$ ). Wir zeigen nun $\begin{eqnarray*} (-1)^k = (-1)^l \end{eqnarray*}$ . Dazu definieren wir $\begin{eqnarray*} P(1, \dots, n) := \prod_{i=1}^{n-1} \prod_{k=i+1}^n (i-k) \end{eqnarray*}$ . Man ersetzt nun für $\begin{eqnarray*} 1 \leq i \leq n \end{eqnarray*}$ die Zahl $\begin{eqnarray*} i \end{eqnarray*}$ durch $\begin{eqnarray*} \pi(i) \end{eqnarray*}$ , d.h. $\begin{eqnarray*} P(\pi(1), \dots, \pi(n)) := \prod_{i=1}^{n-1} \prod_{k=i+1}^n (\pi(i)-\pi(k)) \end{eqnarray*}$ . Dann gilt $\begin{eqnarray*} P(\pi(1), \dots, \pi(n)) = c_\pi P(1, \dots, n) \end{eqnarray*}$ mit einem durch $\begin{eqnarray*} \pi \end{eqnarray*}$ eindeutig bestimmten Vorzeichenfaktor $\begin{eqnarray*} c_\pi = \pm 1 \end{eqnarray*}$ . Man überlegt sich nun, dass bei einer beliebigen Transposition $\begin{eqnarray*} t \end{eqnarray*}$ gilt: $\begin{eqnarray*} c_t =-1 \end{eqnarray*}$ . Nach Voraussetzung ist $\begin{eqnarray*} \pi = \prod_{i=1}^k t_{k+1-i} = \prod_{i=1}^l t'_{l+1-i} \end{eqnarray*}$ und damit $\begin{eqnarray*} c_\pi = (-1)^k = (-1)^l \end{eqnarray*}$ .

Gruß, therisen

11.11.2006, 21:31

RedSunset

Auf diesen Beitrag antworten »

was bezeichnet denn hier das $\begin{eqnarray*} P(..) \end{eqnarray*}$ ?
und wie darf ich mir eine Produktsumme von einer Produktsumme ( $\begin{eqnarray*} \prod_{i=1}^{n-1} \prod_{k=i+1}^n (i-k) \end{eqnarray*}$ ) vorstellen?

11.11.2006, 22:35

therisen

Auf diesen Beitrag antworten »

$\begin{eqnarray*} P(1, \dots, n) \end{eqnarray*}$ ist einfach ein künstlich eingeführtes Produkt.

Produktsumme? Was soll denn das bitte sein? Big Laugh

Ich fange mal an, das Produkt auszuschreiben: $\begin{eqnarray*} P(1, \dots, n) =(1-2)(1-3)\cdots(1-n)(2-3)\cdots(2-n) \cdots\cdots (n-1-n) \end{eqnarray*}$ .

Den Beweis wirklich zu verstehen ist nicht ganz einfach und ich rate dir, wenn ich mir deinen Wissensstand so anschaue, dass du dir darüber erstmal nicht weiter den Kopf zerbrichst. Augenzwinkern

Gruß, therisen

Neue Frage »

Antworten »

sign(pi) eindeutig

Verwandte Themen