Permutationen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:14 Di 26.12.2006 | | Autor: | Phoney |
| Aufgabe | | Zeigen Sie: Jede Permutation lässt sich als Produkt von Transpoisitionen schreiben. Dabei ändert sich die Parität nicht: Für jede Permutation ist es eindeutig bestimmt, ob die Anzahl der benötigten Transpositionen gerade oder ungerade ist. |
Hallo.
An der obengenannten Aufgabe scheitere ich leider total
Ich weiss schon, dass für Zyklen der Länge 1 gilt: $id = (a b) [mm] \circ [/mm] (b a)$
Für Zyklen größer der Länge 1 gilt:
[mm] $g=(a_1,....a_r)$ [/mm] mit $r [mm] \ge [/mm] 2$
g kann ich jetzt in r-1 Transpositionen zerlegen (wäre sicherlich eine nette Teilaufgabe, das zu beweisen - hat dazu jemand einen Link oder vielleicht eine Beweisidee?)
$g = [mm] (a_1 a_2) \circ (a_2 a_3) \circ [/mm] ... [mm] \circ (a_{r-1} a_{r})$
[/mm]
Wenn ich das jetzt mal versuche auf die Aufgaben zu übertragen, habe ich ja
[mm] \sigma [/mm] = [mm] (a_1 [/mm] ... [mm] a_r)
[/mm]
Wenn ich nun Sigma erst in disjunkte Zyklen und dann jeden Zyklus in Traspositionen zerlegen.
Dann ist ja die Anzahl der Transpositionen r-1. Sei [mm] $N(\sigma) [/mm] = r-1$
Und nu? Damit habe ich ja eigentlich nichts gezeigt. Nichts bewiesen ;(
|
|
| |
|
Tipp: Induktion über Länge der Permutation.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:20 Mo 01.01.2007 | | Autor: | Phoney |
Hallo,
> Tipp: Induktion über Länge der Permutation.
Davon habe ich ja noch nie etwas gehört.
Inwiefern unterscheidet sich das denn von der vollständigen Induktion? Ich kenne nur das Induktionsverfahren, wo man halt für n letztendlich n+1 einsetzen muss.
Kann man mir da genaueres sagen?
Grüße
Johann
|
|
|
| |
|
Hallo Phoney!
> > Tipp: Induktion über Länge der Permutation.
>
>
> Davon habe ich ja noch nie etwas gehört.
>
> Inwiefern unterscheidet sich das denn von der vollständigen
> Induktion? Ich kenne nur das Induktionsverfahren, wo man
> halt für n letztendlich n+1 einsetzen muss.
Wenn in der Mathematik von Induktion die Rede ist, ist eigentlich immer vollständige Induktion gemeint. Ansonsten sagt man dazu, was man meint. "Induktion über" soll dir angeben, was das n ist, das dann zu n+1 wird. Hier soll also die Länge der Permutation n sein, und du sollst im Induktionsschritt zeigen, dass es, wenn es für die Länge n gilt, dann auch für die Länge n+1 gilt.
> Kann man mir da genaueres sagen?
Alles klar jetzt?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:24 Mo 01.01.2007 | | Autor: | Phoney |
Hallo.
> Wenn in der Mathematik von Induktion die Rede ist, ist
> eigentlich immer vollständige Induktion gemeint. Ansonsten
> sagt man dazu, was man meint. "Induktion über" soll dir
> angeben, was das n ist, das dann zu n+1 wird. Hier soll
> also die Länge der Permutation n sein, und du sollst im
> Induktionsschritt zeigen, dass es, wenn es für die Länge n
> gilt, dann auch für die Länge n+1 gilt.
>
> > Kann man mir da genaueres sagen?
>
> Alles klar jetzt?
Ne, worauf genau soll ich denn jetzt die Induktion anwenden, ich habe
[mm] $g=(a_1,....a_r)$ [/mm] mit $r [mm] \ge [/mm] 2$
$g = [mm] (a_1 a_2) \circ (a_2 a_3) \circ [/mm] ... [mm] \circ (a_{r-1} a_{r})$ [/mm]
[mm] \sigma [/mm] = [mm] (a_1 [/mm] ... [mm] a_r)
[/mm]
und was soll ich zeigen, dass es für [mm] a_{r+1} [/mm] auch gilt?
|
|
|
| |
|
Hallo Phoney!
> > Wenn in der Mathematik von Induktion die Rede ist, ist
> > eigentlich immer vollständige Induktion gemeint. Ansonsten
> > sagt man dazu, was man meint. "Induktion über" soll dir
> > angeben, was das n ist, das dann zu n+1 wird. Hier soll
> > also die Länge der Permutation n sein, und du sollst im
> > Induktionsschritt zeigen, dass es, wenn es für die Länge n
> > gilt, dann auch für die Länge n+1 gilt.
> >
> > > Kann man mir da genaueres sagen?
> >
> > Alles klar jetzt?
>
> Ne, worauf genau soll ich denn jetzt die Induktion
> anwenden, ich habe
>
> [mm]g=(a_1,....a_r)[/mm] mit [mm]r \ge 2[/mm]
>
> [mm]g = (a_1 a_2) \circ (a_2 a_3) \circ ... \circ (a_{r-1} a_{r})[/mm]
>
> [mm]\sigma[/mm] = [mm](a_1[/mm] ... [mm]a_r)[/mm]
>
> und was soll ich zeigen, dass es für [mm]a_{r+1}[/mm] auch gilt?
Ja, genau. Die Aufgabe war doch "Jede Permutation lässt sich als Produkt von Transpoisitionen schreiben.". Und wenn du nun zuerst zeigst, dass es für einen Induktionsanfang, vllt r=2 gilt, dann musst du im Induktionsschritt zeigen, dass es auch für r+1 gilt. Aber frag mich nicht, wie man das macht, ich hab von Permutationen keine Ahnung, und deine Schreibweise kenne ich auch nicht.
Viele Grüße
Bastiane
|
|
|
|
