Vorzeichen Permutation Formel < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Guten Morgen!
Ich möchte gerne eine Formel beweisen, die im Skript nicht bewiesen wird.
Ich tippe den Abschnitt aus dem Skript ab:
Definition: Fehlstand einer Permutation
Sei [mm] $\sigma \in \mathbb{S}_{n}$.
[/mm]
a. Ein Zahlenpaar $(i,j)$ mit $1 [mm] \le [/mm] i, j [mm] \le [/mm] n$ heißt ein Fehlstand oder Inversion von [mm] $\sigma$, [/mm] falls $i < j$, aber [mm] $\sigma(i) [/mm] > [mm] \sigma(j)$.
[/mm]
Mit [mm] $N(\sigma) [/mm] := [mm] inv(\sigma) [/mm] := [mm] \{ (i,j) \in \{1, \ldots, n \} \times \{1, \ldots, n \} \; \vert \; i < j, \sigma(i) > \sigma(j) \}$ [/mm] bezeichnen wir die Menge aller Inversionen von [mm] $\sigma$.
[/mm]
b. Die Abbildung $sgn: [mm] \mathbb{S}_{n} \rightarrow \{- 1, 0 , + 1 \}, \sigma \mapsto [/mm] (- [mm] 1)^{\vert inv(\sigma) \vert}$ [/mm] nennen wir das Signum oder Vorzeichen von [mm] $\sigma$. [/mm]
Danach steht in einer Bemerkung:
"Für ein bel. [mm] $\sigma \in \mathbb{S}_{n}$ [/mm] gilt die Formel [mm] $sgn(\sigma) [/mm] = [mm] \prod\limits_{1 \le i < j \le n} \frac{\sigma(j) - \sigma(i)}{j - i}$".
[/mm]
Zu dieser Formel finde ich im Netz keinen Beweis, vielleicht ist der Beweis auch trivial. Ich möchte aber die Formel gerne beweisen. Habe allerdings keinen Ansatz...
$(j - i)$ ist immer positiv, da $i < j$. daher ist der Zähler des Bruchs für das Vorzeichen zuständig. Aber dann komme ich schon nicht mehr weiter.
Wir schreibe ich das Produkt geschickt um? Der Bruch [mm] $\frac{\sigma(j) - \sigma(i)}{j - i}$ [/mm] muss ja nicht mal unbedingt eine ganze Zahl sein, oder?
Wäre für jeden Tipp dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:00 Fr 16.07.2021 | | Autor: | statler |
Guten Morgen Anni,
wenn du dir die Permutation [mm] $\sigma$ [/mm] so
[mm] $\pmat{ 1 & ... & n \\ \sigma(1) & ... & \sigma(n) }$
[/mm]
hinschreibst, dann kannst du dir überlegen, wie oft du im Nenner den Faktor k erhältst, nämlich (n-k)-mal. Das sind in der oberen Zeile die Paare (k+1, 1), (k+2, 2), ... , (n, n-k).
In der unteren Zeile bildest du die Differenzen der Bildpaare, und da das dieselben Zahlen sind, erhältst du insgesamt (n-k)-mal als Ergebnis [mm] $\pm$k. [/mm] Dabei ergibt sich das Minuszeichen genau dann, wenn es sich um einen Fehlstand handelt. Soweit erstmal :)
Wir sind hier übrigens üblicherweise beim Du.
Gruß Dieter
|
|
|
| |
|
> Guten Morgen Anni,
>
> wenn du dir die Permutation [mm]\sigma[/mm] so
> [mm]\pmat{ 1 & ... & n \\ \sigma(1) & ... & \sigma(n) }[/mm]
>
> hinschreibst, dann kannst du dir überlegen, wie oft du im
> Nenner den Faktor k erhältst, nämlich (n-k)-mal. Das sind
> in der oberen Zeile die Paare (k+1, 1), (k+2, 2), ... , (n,
> n-k).
> In der unteren Zeile bildest du die Differenzen der
> Bildpaare, und da das dieselben Zahlen sind, erhältst du
> insgesamt (n-k)-mal als Ergebnis [mm]\pm[/mm]k. Dabei ergibt sich
> das Minuszeichen genau dann, wenn es sich um einen
> Fehlstand handelt. Soweit erstmal :)
>
> Wir sind hier übrigens üblicherweise beim Du.
> Gruß Dieter
Hallo, danke dir für den Tipp 
Ich bin mir nicht sicher, ob ich alles verstanden habe, aber ich versuch es mal:
Seien $k, n [mm] \in \mathbb{N}$ [/mm] beliebig.
Definiere die Mengen
(1) [mm] $I_{k} [/mm] := [mm] \{1, \ldots, k \}$
[/mm]
(2) $M := [mm] \{ (i,j) \in I_{n}^{2}\; \vert \; 1 \le i < j \le n \}$
[/mm]
(3) [mm] $M_{k} [/mm] := [mm] \{(i, j) \in M\; \vert \; j - i = k \}$, [/mm] wobei [mm] $\vert M_{k} \vert [/mm] = n - k$
Es gilt dann $ [mm] \prod\limits_{(i,j) \in M} \frac{\sigma(j) - \sigma(i)}{j - i} [/mm] = [mm] \prod\limits_{(i,j) \in M}( \sigma(j) [/mm] - [mm] \sigma(i)) \cdot \frac{1}{j - i} [/mm] = [mm] \underbrace{\prod\limits_{(i,j) \in M}( \sigma(j) - \sigma(i))}_{(1)} \cdot \underbrace{\prod\limits_{(i,j) \in M} \frac{1}{j - i}}_{(2)}$
[/mm]
Jetzt versuchen wir die Produkte (1) und (2) umzuschreiben:
Zu (2)
______
Es gilt doch $ [mm] \prod\limits_{(i,j) \in M} \frac{1}{j - i} [/mm] = [mm] \prod\limits_{k \in I_{n}} \prod\limits_{(i,j) \in M_{k}} \frac{1}{j - i} [/mm] = [mm] \prod\limits_{k \in I_{n}} \frac{1}{k^{n - k}} [/mm] $ (Hier habe ich deinen Tipp umgesetzt, sofern ich ihn richtig verstanden habe). Kann man das Ergebnis noch weiter vereinfachen?
Zu (1)
______
[mm] $\prod\limits_{(i,j) \in M} (\sigma(j) [/mm] - [mm] \sigma(i)) [/mm] = [mm] \prod\limits_{(i,j) \in inv(\sigma)} (\sigma(j) [/mm] - [mm] \sigma(i)) \cdot \prod\limits_{(i,j) \in M \setminus inv(\sigma)} (\sigma(j) [/mm] - [mm] \sigma(i))$ [/mm] (Hier habe leider noch keine Idee dazu)
Habe aber das Gefühl, dass ich die Rechnung unnötig kompliziert mache, weil ich nicht denke, dass die Rechnung am Ende aufgeht. Zumindest kann ich mir noch nicht vorstellen, wie das Produkt [mm] $\prod\limits_{k \in I_{n}} \frac{1}{k^{n - k}}$ [/mm] sich aufheben soll.
Gruß, Anni
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:29 Sa 17.07.2021 | | Autor: | statler |
Guten Morgen Anni!
> Seien [mm]k, n \in \mathbb{N}[/mm] beliebig.
>
> Definiere die Mengen
>
> (1) [mm]I_{k} := \{1, \ldots, k \}[/mm]
> (2) [mm]M := \{ (i,j) \in I_{n}^{2}\; \vert \; 1 \le i < j \le n \}[/mm]
>
> (3) [mm]M_{k} := \{(i, j) \in M\; \vert \; j - i = k \}[/mm], wobei
> [mm]\vert M_{k} \vert = n - k[/mm]
>
>
> Es gilt dann [mm]\prod\limits_{(i,j) \in M} \frac{\sigma(j) - \sigma(i)}{j - i} = \prod\limits_{(i,j) \in M}( \sigma(j) - \sigma(i)) \cdot \frac{1}{j - i} = \underbrace{\prod\limits_{(i,j) \in M}( \sigma(j) - \sigma(i))}_{(1)} \cdot \underbrace{\prod\limits_{(i,j) \in M} \frac{1}{j - i}}_{(2)}[/mm]
>
> Jetzt versuchen wir die Produkte (1) und (2)
> umzuschreiben:
>
>
> Zu (2)
> ______
>
> Es gilt doch [mm]\prod\limits_{(i,j) \in M} \frac{1}{j - i} = \prod\limits_{k \in I_{n}} \prod\limits_{(i,j) \in M_{k}} \frac{1}{j - i} = \prod\limits_{k \in I_{n}} \frac{1}{k^{n - k}}[/mm]
> (Hier habe ich deinen Tipp umgesetzt, sofern ich ihn
> richtig verstanden habe). Kann man das Ergebnis noch weiter
> vereinfachen?
Das ist so völlig ok, aber s. u.
>
> Zu (1)
> ______
>
>
> [mm]\prod\limits_{(i,j) \in M} (\sigma(j) - \sigma(i)) = \prod\limits_{(i,j) \in inv(\sigma)} (\sigma(j) - \sigma(i)) \cdot \prod\limits_{(i,j) \in M \setminus inv(\sigma)} (\sigma(j) - \sigma(i))[/mm]
> (Hier habe leider noch keine Idee dazu)
>
>
> Habe aber das Gefühl, dass ich die Rechnung unnötig
> kompliziert mache, weil ich nicht denke, dass die Rechnung
> am Ende aufgeht. Zumindest kann ich mir noch nicht
> vorstellen, wie das Produkt [mm]\prod\limits_{k \in I_{n}} \frac{1}{k^{n - k}}[/mm]
> sich aufheben soll.
Vielleicht befaßt du dich besser erstmal mit der Menge
[mm] $M_{\sigma} [/mm] := [mm] \{(\sigma(i), \sigma(j)) | (i, j) \in M\}$.
[/mm]
M enthält von den beiden Paaren (i, j) und (j, i) dasjenige, in dem die 2. Koordinate die größere ist.
[mm] M_{\sigma} [/mm] enthält von den beiden Paaren (r, s) und (s, r) genau eines. Welches hängt davon ab, ob [mm] \sigma [/mm] hier einen Fehlstand hat oder nicht. (Insbesondere taucht die Differenz k genauso oft auf wie in M, bei Fehlstand allerdings als -k. So hatte ich mir das zuerst überlegt, aber du brauchst [mm] M_{k} [/mm] gar nicht.)
Deswegen ist nämlich
[mm] $\produkt_{(i, j) \in M}^{} (\sigma(j) [/mm] - [mm] \sigma(i)) [/mm] = [mm] \produkt_{(r, s) \in M_{\sigma}}^{} [/mm] (s - r) = [mm] (-1)^{sgn(\sigma)} \centerdot \produkt_{(i, j) \in M}^{} [/mm] (j - i) $
Gruß aus HH
Dieter
>
|
|
|
| |
|
Ein Bild Beispiel sagt mehr als tausend Worte.
Lassen wir mal den Formalkram weg und nehmen als Beispiel für n=11 die folgende Anordnung:
n 1 2 3 4 5 6 7 8 9 10 11
[mm] \sigma(n) [/mm] 8 4 11 7 3 10 6 2 9 5 1
11 Männer sind von 1 bis 11 durchnummeriert. Auf ihrer Stirn steht ihre persönliche Nummer. Sie stellen sich gemäß ihrer Nummer der Reihe nach auf.
Auf ihrer Brust steht das jeweilige [mm] \sigma(i). [/mm]
Der erste geht nun der Reihe nach an allen anderen vorbei und gibt ihnen die Hand. Ein Beobachter schreibt der Reihe nach die Nummern der Begegnungen auf und bildet daraus die Differenzen des Nenners: 2-1, 3-1, 4-1,... 11-1. Dann geht der zweite an allen der Reihe nach vorbei und gibt jedem die Hand, der Beobachter bildet 3-2, 4-2, 5-2,..,11-2 usw. bis 11-10.
Fazit: Jeder hat jedem genau einmal die Hand gegeben, jede Differenzenkombination ist positiv und kommt genau einmal vor.
Ein zweiter Beobachter schreibt aber jeweils die Differenzen aus den [mm] \sigma-Werten [/mm] der Brust auf und bildet daraus die Differenzen des Zählers: 4-8, 11-8, 7-8,...,1-8, dann 11-4, 7-4, 3-4,..., 1-4 usw. bis 1-5. Auch hier hat jeder jedem genau einmal die Hand gegeben (es ist ja der selbe Vorgang), und da alle [mm] \sigma-Werte [/mm] verschieden sind, kommt auch hier jede Differenzenkombination genau einmal vor, bei Inversion mit negativem Vorzeichen.
Das bedeutet aber, dass sich jeder Zähler - ggf. bis auf das Vorzeichen - irgendwo im Nenner wiederfindet und sich daher beide gegeneinander wegkürzen, so dass am Ende nur [mm] -1^{Anzahl der Inversionen} [/mm] übrig bleibt.
|
|
|
|
