Hilfe für den Beweis Transposition?

Ich brauche Hilfe für den Beweis: Zeigen Sie: Ist n Element N und t Element Sn eine Transposition, so gilt sgn(T) = -1.

Answer 1

[Willibergi]

Sei

$\tau = (i, j) \in S_n$

eine Transposition. Das Signum ist definiert als

$\operatorname{sgn}(\tau) = (-1)^{|\operatorname{inv}(\tau)|}$

wobei inv(τ) die Menge der Fehlstände ist. Jedes Paar zweier Zahlen, das nach der Permutation "falsch" herum steht, ist dabei ein Fehlstand. Steht z.B. die 5 nach der Permutation links von der 2, ist (2, 5) ein Fehlstand.

Bei einer Transposition haben wir genau einen offensichtlichen Fehlstand, nämlich (i, j). In der natürlichen Ordnung stand i vor j, die Transposition hat i und j aber getauscht. Ist die Transposition zum Beispiel (25), ist nun 5 das zweite Element und 2 das fünfte. Es ist aber 2 < 5, d.h. 2 müsste links von der 5 stehen - das ist der Fehlstand. Damit enthält inv(τ) genau ein Element, also:

$\operatorname{sgn}(\tau) = (-1)^1 = -1$

Grundsätzlich musst du bei der händischen Berechnung des Signums tatsächlich alle (geordneten) Zahlenpaare durchgehen - alle. In der symmetrischen Gruppe der Ordnung 5 wären das diese:

$(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)$

Dann überprüfst du für jedes Zahlenpaar, ob es nach der Permutation immer noch in dieser Reihenfolge vorliegt oder es gespiegelt wurde. Wurde es gespiegelt, ist es ein Fehlstand. Am Ende zählst du alle Fehlstände zusammen - sind es gerade viele, ist das Signum 1, sind es ungerade viele, ist das Signum -1.

Eine Alternative ist die Produktformel für das Signum, diese reduziert den händischen Aufwand, ist aber meist mit deutlich mehr Rechenaufwand verbunden.

Woher ich das weiß: Studium / Ausbildung – Studium Mathematik