www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
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 Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de