0 Daumen
593 Aufrufe

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 .

Avatar von

Hallo,

schreibe zunächst auf, wie die Einträge \(P_{\sigma}\) formal genau definiert sind, dann berechne den Eintrag

$$(P_{\sigma}P_{\sigma^{-1}})_{i,k}$$

nach der Definition der Matrizenmultiplikation.

Gruß Mathhilf

danke für die Antwort teil a hab ich gemacht aber für teil b habe ich keine idee

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community