Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Signumfunktion (mit Transposition)

Signumfunktion (mit Transposition)

Universität / Fachhochschule

Matrizenrechnung

Tags: Matrizenrechnung

Helpneeder

23:02 Uhr, 11.01.2017

Hallo miteinander,

ich soll zeigen:

Ist

r \in S_{n}

eine Transposition, so ist sign(r)

= - 1

.

Hier stehe ich auf dem Schlauch, weil ich die Signumsfunktion nur für reelle Zahlen kenne.
Was passiert, wenn ich da eine Matrix einsetze?
Oder was wird da eingesetzt?

mihisu aktiv_icon

00:18 Uhr, 12.01.2017

Es wäre nicht schlecht, wenn du dir nochmal deine Vorlesungs-Aufzeichnungen bzw. das Skript (falls ihr eines habt) bzw. ein geeignetes Buch ansiehst, da du zum Thema anscheinend noch überhaupt nichts zu wissen scheinst.

\\\\
Hier ein kleiner Einstieg:

Fangen wir von vorne an.

S_{n}

ist die symmetrische Gruppe, welche alle Permutationen der Menge

{1, ..., n}

enthält.

Das heißt: Ein Element

σ \in S_{n}

ist eine bijektive Abbildung

σ : {1, ..., n} \to {1, ..., n}

.

Eine Transposition

r \in S_{n}

ist eine Permutation, welche zwei Elemente

i, j \in {1, ..., n}

mit

i \neq j

vertauscht und die restlichen Elemente festlässt:
Das heißt es gibt

i, j \in {1, ..., n}

mit

i \neq j

so dass gilt:

r (i) = j

r (j) = i

r (k) = k

für alle

k \in {1, ..., n} \ {i, j}

\\Definition 1:\\

Das Vorzeichen

s g n (σ)

einer Permutation

σ \in S_{n}

kann man auf unterschiedliche (aber äquivalente) Weise definieren. Hier wäre es sinnvoll zu wissen, welche ihr verwendet.

Die üblichste Definition geht wohl über die Anzahl der Fehlstände.

Ein Fehlstand einer Permutation

σ \in S_{n}

ist ein Paar

(i, j) \in {1, ..., n}^{2}

mit

i < j

und

σ (i) > σ (j)

.

Die Menge der Fehlstände einer Permutation

σ \in S_{n}

ist demnach definiert als:

i n v (σ) := {(i, j) \in {1, ..., n}^{2} | i < j u n d σ (i) > σ (j)}

Nun kann man das Vorzeichen einer Permutation

σ \in S_{n}

als

s g n (σ) := {(- 1)}^{| i n v (σ) |}

definieren, also als "-1 hoch die Anzahl der Fehlstände".

Beispiel:

Betrachte die Transposition

τ_{2, 4} \in S_{6},

welche 2 und 4 vertauscht. Wir betrachten also die Abbildung

τ_{2, 4} : {1, 2, 3, 4, 5, 6} \to {1, 2, 3, 4, 5, 6}

mit

τ (1) = 1, τ (2) = 4, τ (3) = 3, τ (4) = 2, τ (5) = 5, τ (6) = 6

.

Die Fehlstände sind

i n v (τ_{2, 4}) = {(2, 3), (2, 4), (3, 4)}

.
Die Anzahl der Fehlstände ist also

| i n v (τ_{2, 4}) | = 3

.
Daher ist

s g n (τ_{2, 4}) = {(- 1)}^{| i n v (τ_{2, 4}) |} = {(- 1)}^{3} = - 1

.

\\Definition 2:\\

Eine andere eher unübliche, äquivalente Definition ist über die Produktformel

s g n (σ) = \prod_{1 \leq i < j \leq n} \frac{σ (j) - σ (i)}{j - i}

möglich.

Betrachtet man wieder die Transposition

τ_{2, 4}

aus dem vorangegangenen Beispiel, so erhält man:

s g n (τ_{2, 4})

= \prod_{1 \leq i < j \leq n} \frac{τ_{2, 4} (j) - τ_{2, 4} (i)}{j - i}

= \frac{τ_{2, 4} (4) - τ_{2, 4} (2)}{4 - 2} \cdot \prod_{1 \leq i < j \leq n, (i, j) \neq (2, 4)} \frac{τ_{2, 4} (j) - τ_{2, 4} (i)}{j - i}

= \frac{2 - 4}{4 - 2} \cdot \prod_{1 \leq i < j \leq n, (i, j) \neq (2, 4)} \frac{j - i}{j - i}

= - 1 \cdot \prod_{1 \leq i < j \leq n, (i, j) \neq (2, 4)} 1

= - 1 \cdot 1

= - 1

\\Definition 3:\\

Es gibt auch noch weitere äquivalente Eigenschaften, über welche man das Vorzeichen einer Permutation definieren kann.
Die (meinem Gefühl nach) wohl zweithäufigste Definition des Vorzeichens lautet:

s g n (σ) := 1,

wenn sich

σ

als ein Produkt einer ungeraden Anzahl an Transpositionen darstellen lässt.

s g n (σ) := - 1,

wenn sich

σ

als ein Produkt einer geraden Anzahl an Transpositionen darstellen lässt.

\\\\

Je nachdem, wie viel du zu Permutationen bzw. zum Vorzeichen von Permutationen schon weißt bzw. verwenden darft, ist der Beweis für die gestellte Aufgabe schwerer/aufwändiger oder leicher/kurz. Daher nochmal: Es wäre gut zu wissen, wie ihr das Vorzeichen eine Permutation definiert habt (wahrscheinlich über Fehlstände, aber schau lieber mal nach). Wenn ihr beispielsweise die Produktformel bereits gezeigt habt, wäre der Beweis recht kurz. Noch, nämlich eigentlich gar nicht erforderlich, wäre der Beweis, wenn du die dritte Definition hättest.

Helpneeder

23:12 Uhr, 12.01.2017

Erstmal vielen Dank für deine ausführliche Erklärung. Im Skript meines Profs kann ich die Definition nicht finden, aber ich habe in dem Buch geschaut, das er benutzt, und dort wird - wie du bereits vermutet hast - über die Anzahl der Fehlstände definiert.

Dank deiner Ausführungen habe ich jetzt zumindest die Aussage verstanden, die ich beweisen soll. Auf den Beweis selbst bin ich aber immer noch nicht gekommen.

Ich hatte die Idee, ihn induktiv anzugehen - auch wenn ich mir vorher schon dachte, dass - falls es überhaupt funktioniert - wahrscheinlich eher ein unüblicher Weg ist.
Also meine Vorstellung war die Folgende:

Sei

τ_{1 i + 1} \in S_{n}

eine Transposition, wobei 1 und

i + 1

vertauscht sind.
Durch Induktion wird gezeigt, dass sign(

τ_{1 i + 1}) = - 1

unabhängig vom Abstand zwischen den vertauschten Elementen.

IA: Für

τ_{12} (i = 1)

inv(

τ_{12}) = {(1,2)}

| inv(

τ_{12}) | = 1

sign(

τ_{12}) = {(- 1)}^{1} = - 1

IS: Für

τ_{1 i + 2}

...

.
Schon an dieser Stelle geht es dann nicht wirklich weiter.

Die Intuition lässt jedenfalls vermuten, dass mit wenn ich

i

(also den Abstand der vertauschten Elemente) um 1 vergrößere, die Anzahl der Fehlstände immer um 2 wächst, wodurch die Anzahl immer ungerade ist...

Aber wie kann ich das nun zeigen?

Eine andere Idee wäre, zu behaupten, dass inv(

τ) = 1 + (2 \cdot (i - 1))

.
Das lässt sich für einzelne

i

auch leicht überprüfen.
Aber trotzdem komme ich allgemein mit dem Beweis nicht weiter.

mihisu aktiv_icon

20:50 Uhr, 13.01.2017

Überlegung, ohne Beweis:

Es ist:

i n v (τ_{1, i + 1}) = {(1, k) \in ℕ^{2} | 2 \leq k \leq i} \dot{\cup} {(k, i + 1) \in ℕ^{2} | 2 \leq k \leq i} \dot{\cup} {(1, i + 1)}

i n v (τ_{1, i + 2}) = {(1, k) \in ℕ^{2} | 2 \leq k \leq i + 1} \dot{\cup} {(k, i + 2) \in ℕ^{2} | 2 \leq k \leq i + 1} \dot{\cup} {(1, i + 2)}

Also:

i n v (τ_{1, i + 1}) = {(1, k) \in ℕ^{2} | 2 \leq k \leq i + 1} \dot{\cup} {(k, i + 1) \in ℕ^{2} | 2 \leq k \leq i}

i n v (τ_{1, i + 2}) = {(1, k) \in ℕ^{2} | 2 \leq k \leq i + 1} \dot{\cup} {(k, i + 2) \in ℕ^{2} | 2 \leq k \leq i + 2}

Man sieht also, dass beim Schritt von

τ_{1, i + 1}

τ_{1, i + 2},

die

i - 1

Fehlstände

{(k, i + 1) \in ℕ^{2} | 2 \leq k \leq i}

wegfallen und stattdessen die

i + 1

Fehlstände

{(k, i + 2) \in ℕ^{2} | 2 \leq k \leq i + 2}

hinzukommen.

Meiner Meinung nach, ist es relativ schwer, eine Induktion von

s g n (τ_{1, i + 1})

bzgl.

i

auf diese Art durchzuführen.

Meiner Meinung nach wäre es noch einfacher direkt (also ohne Induktion) zu zeigen, dass

i n v (τ_{1, i + 1}) = {(1, k) \in ℕ^{2} | 2 \leq k \leq i} \dot{\cup} {(k, i + 1) \in ℕ^{2} | 2 \leq k \leq i} \dot{\cup} {(1, i + 1)}

bzw.

i n v (τ_{i, j}) = {(i, k) \in ℕ^{2} | i + 1 \leq k \leq j - 1} \dot{\cup} {(k, j) \in ℕ^{2} | i + 1 \leq k \leq j - 1} \dot{\cup} {(i, j)}

ist.

\\\\

Eine anderer Frage ist: Wenn du

s g n (τ_{1, i + 1}) = - 1

für alle

i

gezeigt hast, wie kommst du dann auf

s g n (τ_{i, j}) = - 1

für alle

i, j

? Hast du die Regel

s g n (σ \circ π) = s g n (σ) \cdot s g n (π)

zur Verfügung, dann ginge das recht schnell. Ansonsten sehe ich nicht, wie du von

s g n (τ_{1, i + 1}) = - 1

auf

s g n (τ_{i, j}) = - 1

schließen willst.

\\\\

Wenn du noch gar nichts weiter zu

s g n

weißt, sondern nur die Definition von

s g n

über Fehlstände zur Verfügung hast

...

(Je mehr Eigenschaften von

s g n

schon gezeigt wurden bzw. verwendet werden dürfen, desto einfachere Beweise kann man gegebenenfalls finden. Es kann also einfachere Beweise geben, wenn du mehr als nur die Definition verwenden kannst/darfst.)

...

würde ich wohl so ansetzen:

Behauptung 1: Verknüpfen mit einer Nachbartransposition

τ_{k, k + 1}

ändert einen Fehlstand.
Wenn

(k, k + 1)

ein Fehlstand von

σ

ist, ist

(k, k + 1)

kein Fehlstand von

σ \circ τ_{k, k + 1}

.
Wenn

(k, k + 1)

kein Fehlstand von

σ

ist, ist

(k, k + 1)

ein Fehlstand von

σ \circ τ_{k, k + 1}

.
Sonst ändert sich an den Fehlständen nichts.

Folgerung 1:

s g n (σ \circ τ_{k, k + 1}) = (- 1) \cdot s g n (σ)

Behauptung 2: Eine Transposition

τ_{i, j}

lässt sich als Produkt einer ungeraden Anzahl von Nachbartranspositionen schreiben:

τ_{i, j} = τ_{j - 1, j} \circ τ_{j - 2, j - 1} \circ ... \circ τ_{i + 1, i + 2} \circ τ_{i, i + 1} \circ τ_{i + 1, i + 2} \circ ... \circ τ_{j - 2, j - 1} \circ τ_{j - 1, j}

Folgerung 2:

s g n (τ_{i, j}) = {(- 1)}^{n} = - 1

wobei

n

die ungerade Anzahl der Nachbartranspositionen aus Behauptung 2 ist.

\\\\

Alternativ könnte man auch versuchen zu zeigen, dass

i n v (τ_{i, j}) = {(i, k) \in ℕ^{2} | i + 1 \leq k \leq j - 1} \dot{\cup} {(k, j) \in ℕ^{2} | i + 1 \leq k \leq j - 1} \dot{\cup} {(i, j)}

ist, indem man durch Fallunterscheidungen untersucht, wann

(p, q)

ein Fehlstand von

τ_{i, j}

ist.

Dann kann man folgern, dass

| i n v (τ_{i, j}) | = | {(i, k) \in ℕ^{2} | i + 1 \leq k \leq j - 1} \dot{\cup} {(k, j) \in ℕ^{2} | i + 1 \leq k \leq j - 1} \dot{\cup} {(i, j)} |

= (j - 1 - (i + 1) + 1) + (j - 1 - (i + 1) + 1) + 1 = 2 \cdot (j - i - 1) + 1 = 2 \cdot (j - i) - 1

ist. Also dass gilt:

s g n (τ_{i, j}) = {(- 1)}^{| i n v (τ_{i, j}) |} = {(- 1)}^{2 \cdot (j - i) - 1} = - 1

Helpneeder

18:58 Uhr, 18.01.2017

Vielen Dank nochmal.
Inzwischen habe ich es begriffen, denke ich.
Du hast mir sehr weitergeholfen - auch wenn sich herausgestellt hat, dass offenbar eine kleine "Skizzierung" als Beweis offenbar genügt hat.

1350704

1348714

	Status: nicht eingeloggt	Noch nicht registriert?