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
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

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
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 Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
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.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]