gerade Permutationen

18.11.2007, 15:21

speedyschmidt

gerade Permutationen

Hallo, Ihr da draussen! Wink

Hab folgende Aufgabenstellung, mit der ich nicht klarkomme:

Eine Paarvertauschung ist eine Permutation, bei der genau 2 Elemente vertauscht werden, während die restlichen Elemente auf unverändert bleiben. Eine Permutation heißt gerade, wenn sie durch eine gerade Anzahl an Paarvertauschungen beschrieben werden kann.

(a) Zeigen Sie, dass die Menge aller geraden Permutationen eine Untergruppe ist.

(b) Zeigen Sie, dass die Verknüpfung einer geraden und einer ungeraden Permutation eine ungerade Permutation ist.

zu (a) ja es ist schon einleuchtend, dass die Verknüpfung wieder eine gerade Permutation ergibt und dass die Inversen Elemente auch gerade Permutationen sind, aber wie zeige ich das? Kann ich eine beliebige gerade Permutation irgendwie darstellen?

zu (b) auch das scheint recht offensichtlich zu sein, doch auch hier würde ich gerne wissen, wie genau man das schreiben kann.

Dankeschön schonmal im Voraus,

Euer Speedy! Mit Zunge

18.11.2007, 16:53

Frooke

Auf diesen Beitrag antworten »

Zeige, dass jede Permutation als Produkt von Transpositionen geschrieben werden kann (man nennt Deine «Paarvertauschungen» bei uns auch Transpositionen, aber ich weiss nicht wie offiziell das ist)...

Verkette dann mal zwei «gerade» Permutationen, dann siehst Du, dass wieder eine ungerade Anzahl von Transpotitionen dasteht. So im Stil (ich weiss nicht, wie man Mehrfachverkettungen sonst aufschreibt...)

$\begin{eqnarray*} \pi = \overset{2m}{\underset{k=1}{\bigcirc}}\tau_k \end{eqnarray*}$

$\begin{eqnarray*} \rho = \overset{2n}{\underset{k=1}{\bigcirc}}\sigma_k \end{eqnarray*}$

$\begin{eqnarray*} \pi\circ\rho =\overset{2m}{\underset{k=1}{\bigcirc}}\tau_k\circ \overset{2n}{\underset{k=1}{\bigcirc}}\sigma_k = \overset{2p}{\underset{k=1}{\bigcirc}}\mu_k \end{eqnarray*}$

beim letzten = musst Du noch was dazu sagen:
Die Tau's sind alle selbstinvers, d.h. die Tatsache, dass eine ungerade Anzahl bleibt, bleibt bestehen, aber es ist nicht notwendigerweise 2(m+n)=2p...

Für die Inversen sollte die «Produktdarstellung» auch helfen.

(b) analog.

EDIT: Etwas expliziter...

18.11.2007, 18:53

speedyschmidt

Auf diesen Beitrag antworten »

hmmm, dein erster Satz macht mir Sorgen...

Das ist doch genau das, was ich nicht hinkriege^^

Und das die Tau's alle selbstinvers sind, versteh ich irgendwie auch noch nicht:

wenn ich folgendes habe:

a-->a
b-->c
c-->d
d-->b,

dann sind das doch 2 paarvertauschungen, aber es ist nicht zu sich selbstinvers...

Vielleicht steh ich auf dem Schlauch, wär nett, wenn du dich nochmal meldest (oder ein anderer ;-) )

18.11.2007, 22:40

Frooke

Auf diesen Beitrag antworten »

Ich meinte so: Wenn Du EINE Transposition hast, also eine Permutation, die zwei Elemente vertauscht, dann macht nochmaliges Anwenden dieser Transposition den «Tausch» rückgängig.

Zum Beweis der Behauptung: Mache einen Induktionsbeweis über die Anzahl Stellen, die bei der Permutation vertauscht werden.

EDIT: Induktionsanfang ist ja klar. Hast Du eine Idee für den Schritt?

19.11.2007, 21:20

speedyschmidt

Auf diesen Beitrag antworten »

Hmmm?

Ich weiß nichtmal, was ich per Induktion zeigen soll....

Schon das:Zeigen Sie, dass die Menge aller geraden Permutationen eine Untergruppe ist.?

oder das?:Zeige, dass jede Permutation als Produkt von Transpositionen geschrieben werden kann

20.11.2007, 19:15

Frooke

Auf diesen Beitrag antworten »

Zitat:

Original von speedyschmidt
Schon das:Zeigen Sie, dass die Menge aller geraden Permutationen eine Untergruppe ist.?

Zeige:

- Die Menge aller geraden Permutationen ist eine nichtleere Teilmenge der Menge der Permutationen.
- Verkettung zweier gerader Permutationen ergeben wieder eine gerade Permutation.
- Inverse einer geraden Permutation ist auch wieder eine gerade Permutation.

Das ist schon alles.

Zitat:

Original von speedyschmidt
oder das?:Zeige, dass jede Permutation als Produkt von Transpositionen geschrieben werden kann.

Mache Induktion über die Anzahl Stellen, die eine Permutation $\begin{eqnarray*} \pi \end{eqnarray*}$ vertauscht, also:

$\begin{eqnarray*} n=0\Longrightarrow \pi=\mathrm {Id} \end{eqnarray*}$ (die Identität). Z.B. ist $\begin{eqnarray*} \tau\circ\tau^{-1}=\mathrm{Id} \end{eqnarray*}$ für jede Transposition $\begin{eqnarray*} \tau \end{eqnarray*}$ . Damit ist die Verankerung ok.

Versuche nun zu zeigen, dass eine Permutation, die n Stellen verändert, als Produkt von einer Permutation, die n-1 Stellen vertauscht und einer Transpotition dargestellt werden kann. Auf die «n-1 Permutation» kannst Du dann die Induktionsvoraussetzung anwenden.

Neue Frage »

Antworten »

gerade Permutationen

Verwandte Themen