matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLineare Algebra SonstigesVorzeichen Permutation Formel
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Lineare Algebra Sonstiges" - Vorzeichen Permutation Formel
Vorzeichen Permutation Formel < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Vorzeichen Permutation Formel: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 01:31 Fr 16.07.2021
Autor: Annkathrin20

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.



        
Bezug
Vorzeichen Permutation Formel: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Vorzeichen Permutation Formel: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:57 Fr 16.07.2021
Autor: Annkathrin20


> 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

Bezug
                        
Bezug
Vorzeichen Permutation Formel: Antwort
Status: (Antwort) fertig Status 
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


>  


Bezug
        
Bezug
Vorzeichen Permutation Formel: Antwort
Status: (Antwort) fertig Status 
Datum: 10:32 So 25.07.2021
Autor: HJKweseleit

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.




Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]