Aufgabe:
(a) Sei \( \sigma \in S_{n} \) eine Permutation mit zugehöriger Permutationsmatrix \( P_{\sigma} \). Zeigen Sie:
\( P_{\sigma^{-1}}=P_{\sigma}^{-1}=P_{\sigma}^{\mathrm{t}} \)
(b) Notation: Für \( i, j \in\{1, \ldots, n\}, i \neq j \) bezeichne \( \tau_{i, j} \) die Transposition, die \( i \) und \( j \) vertauscht. Das heißt, \( \tau_{i, j}(k)=k \) für alle \( k \neq i, j, \tau_{i, j}(i)=j \) und \( \tau_{i, j}(j)=i .^{1} \)
Eine Transposition \( \sigma \in S_{n} \) heißt Basistransposition, wenn \( \sigma \) zwei aufeinanderfolgende Zahlen vertauscht, d.h. \( \sigma=\tau_{i, i+1} \) für ein \( i \in\{1, \ldots, n-1\} . \) Zeigen Sie, dass jede Permutation ein Produkt von Basistranspositionen ist. Beispiel: Sei \( \sigma=\left(\begin{array}{llll}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2\end{array}\right) \). Dann lässt sich \( \sigma \) schreiben als \( \sigma=\tau_{3,4} \circ \tau_{2,3} \circ \tau_{1,2} \circ \tau_{3,4} \circ \tau_{2,3} \).
Hinweis: Nach Beispiel \( 9.27 \) genügt es, die Aussage für Transpositionen zu zeigen, da jede Permutation sich als Produkt von Transpositionen schreiben lässt.
Bemerkung: Dies ist die Grundlage von Bubblesort.
Problem/Ansatz:
Können Sie bitte beim lösen helfen .
