Widerspruchbeweis Permutationsmatrix?
Hey ich hab hier das obige Korollar, was ich schon länger zu beweisen versuche. Dafür habe ich ihn in drei Teilbeweise gegliedert, zuerst Beweis Homom., dann inj. und dann "Für n...". Die ersten beiden Teile habe ich geschafft, doch jetzt scheiter ich bei der surjektivität. Ich glaube mich iritiert, dass ich es für größer gleich 2 beweisen soll.
Ich weiß, dass hier normal auch ein Gegenbeispiel reichen sollte, aber nachdem mir auch dazu keines einfällt, würde ich gerne einen Widerspruchbeweis führen, komm damit aber auch nicht wirklich zurecht.
Alles was ich zu diesem Teil habe ist:
Das ist jetzt eigentlich ja nichts und ich deke auch das der Beweisbeginn bereits falsch ist. Es wär super wenn mit jemand den Beweis sagen kann, damit ich diesen nachvollziehen kann bzw. Tipps geben.
Das ist der Beweis.
Lösung 
2 Antworten
Deine Formulierung bei der "Annahme" wirkt ein wenig irreführend. Surjektivität bedeutet ja, dass es für jedes Element y aus dem Bildbereich [also in diesem Fall GL(n;K)] ein Element x aus dem Definitionsbereich [Sn] gibt, sodass F(x) = y gilt.
Bei dir klingt es aber so, als müsste jedes Element aus dem Defintionsbereich ein Bild haben, was aber sowieso bei jeder Funktion der Fall ist.
Um zu zeigen, dass die Abbildung nicht surjektiv ist, reicht in der Tat ein Gegenbeispiel. Z.B. kannst du zeigen, dass
1 1
0 1
durchaus in GL(2;K) liegt, jedoch keine Permutationsmatrix ist.
Für ein beliebiges n > 1 kannst du dieses Beispiel verallgemeinern.
Ok danke einmal, irgendwie ich weiß nicht, also wenn ich jetzt deine Matrix nimm, dann ist die ein Element aus der allgemeinen linearen Gruppe. Als Begründung dazu hätt ich, dass die det(Matrix)=1, damit ist sie invertierbar und in GL enthalten, weil GL alle invertierbaren nxn Matrizen enthält?
Richtig, GL(n;K) ist die Gruppe der invertierbaren nxn-Matrizen.
Und diese Matrix von dir ist nicht in Sn enthalten bzw. keine Permutationsmatrix, da aufgrund der Definition ja eine Permutationsmatrix in jeder Zeile und jeder Spalte genau eine 1 und sonst 0. Das wär hier dann ja nicht der Fall.
Naja, in S_n ist ohnehin keine Matrix enthalten, aber das ist auch nicht der Punkt. Dein zweites Argument ist hier ausschlaggebend: Die Matrix [nennen wir sie M] ist keine Permutationsmatrix, weil z.B. die erste Zeile von M mehr als nur eine 1 enthält.
Weil von deinem Homomorphismus aber nur Permutationsmatrizen getroffen werden, hat M kein Urbild, i.e. es gibt kein σ in der S_2 mit F(σ) = M. Also ist F nicht surjektiv.
Mhmmm ok das ist verständlich, danke:-) So hatte ich es eh gemeint, aber ich scheiter schon ziemlich am aufschreiben bzw. mathematischen argumentieren.
Ich hab das jetzt mal so aufgeschrieben und argumentiert nach deiner Argumentation. Ich habs auch veralgemeinert, aber weiß nicht ob das so richtig veralgemeinert ist?
Ich hab bei meiner Fragestellung ein Bild hinzugefügt...:-)
Mir ist nicht ganz klar, wie deine verallgemeinerte Matrix aussieht. Mal angenommen, ich würde den Fall n = 3 betrachten. Meinst du da die Matrix
1 1 0
0 1 0
0 0 1
oder
1 1 1
0 1 1
0 0 1
? Versteh mich nicht falsch, beide funktionieren als Gegenbeispiel, aber es ist wichtig für einen sauberen Beweis, dass jeder (hierfür qualifizierte) Leser zu jedem Zeitpunkt exakt weiß, wovon die Rede ist ;)
Allgemein, wenn du bei Matrizen mit der Pünktchenschreibweise arbeiten willst, würde ich dir raten, die Randelemente auf jeden Fall auch anzugeben, z.B.
1 1 ... 1 1
0 1 ... 1 1
... ... ...
0 0 ... 0 1
(ich hab in der Code-Umgebung die diagonalen und vertikale Punkte leider nicht hinbekommen, aber ich hoffe du weißt was ich meine :D )
Zudem scheinst du bei der Argumentation das Wort "Spalte" mit dem Wort "Zeile" verwechselt zu haben, aber das ist ein wenig pingelig ;)
Preisfragen fürs Verständnis (gehört nicht wirklich zur Aufgabe, aber könntest du dir bei Gelegenheit mal Gedanken drüber machen): Was passiert bei n = 1? Warum geht unsere Argumentation da schief? Ist die Abbildung da immer surjektiv oder gibt es Ausnahmen?
Ich hab die zweite gemeint, also die obere dreiecksmatrix. Ich habs oben noch einmal ausgebessert, dass mit der Spalte und Zeile hab ich jetzt auch gemerkt, dass das dann nicht geht bzw. richtig wär :-)
Wenn n=1 wär, dann hätte man ja eine 1x1 Matrix und die hätte dann ja nur einen Eintrag, entweder 1 oder 0. Aber wenn sie jetzt den Eintrag 1 hat wär die Determinante auch 1 bzw. beim Eintrag 0, wärs 0 und wenn sie null ist, dann ist sie ja auch nicht invertierbar und nicht in GL enthalten oder? Wie ist es bei einer Permutationsmatrix muss die 1er und 0er enthalten oder darf die auch 1x1 sein?
Eine Permutationsmatrix kann auch 1x1 sein. Aus der Definition folgt, dass (1) die einzige Permutationsmatrix der Größe 1x1 ist.
Ah ok, aber das heißt dann, dass das nur im Fall (1) gilt? Die Matrix (0) ist dann ja keine Abbildung, weil sie in der Definitionsmenge und Zielmenge nicht enthalten ist? Im Fall (1) wärs dann injektiv und surjektiv und somit bijektiv?
Das mit dem surjektiv ist so ne Sache... Wir haben ja oben gesehen, dass im Fall n>1 die Surjektivität daran scheitert, dass wir eine Matrix der GL(n;K) basteln können, die von der Abbildung nicht getroffen wird.
Im Fall n = 1 funktioniert unsere Konstruktion nicht, weil wir keine zweite Zeile zur Verfügung haben, in die wir unsere "überzählige Eins" packen könnten.
Aber das heißt ja noch nicht, dass wir keine andere Matrix der GL(1;K) finden können, die von der Abbildung nicht getroffen wird.
Wie sieht die GL(1;K) überhaupt aus? Was liegen da für Dinger drin?
Mhhh ich weiß jetzt nicht, ob ich die Frage richtig verstehe...:-/
Die Matrix (0) würd ich ja mal weglassen, weil die nicht in GL enthalten ist, aber die Matrix (1) schon. Diese könnte man erweitern um ihr Vielfaches, dann hätten wie die nächste Matrix (1.Zeile: 1 und 0, 2. Zeile: 0 und 1) usw. Dies wär dann die Einheitsmatrix 2x2,3x3,... . Und die Einheitsmatrix ist eine Permutationsmatrix oder?
GL(1;K) besteht nur aus der Matrix (1) ? Meinst du das?
GL(1;K) besteht nur aus der Matrix (1) ? Meinst du das?
Was ist denn z.B. mit der Matrix (2)? Liegt die etwa nicht in der GL(1; ℝ)?
Ouh ich habe jetzt nur an 0 und 1 gedacht sorry. Aber dann liegen ja alle matrizen also (3),(4),... außer 0 nicht in GL(1:K)
Ja, alle Matrizen (x) mit x ≠ 0 liegen in GL(1;K).
Aber von all diesen Matrizen ist nur die Matrix (1) eine Permutationsmatrix.
Das heißt, wenn der Körper ein Element x besitzt mit x ≠ 0 und x ≠ 1 [z.B. x = 2 im Fall der reellen Zahlen], dann gibt es ein Element der GL(1;K), das keine Permutationsmatrix ist und dementsprechend nicht von der Abbildung getroffen wird.
D.h. die Abbildung ist eigentlich so gut wie nie surjektiv, es sei denn der Körper hat nur ne 0 und ne 1 ;)
ok mh also is die abbildung nur bei 1 surjektiv oder bei 0 auch? Ich dacht wenn man jz null hätte, nein besser meine frage ist, ob die matrix (0) in GL enthaltn ist?
Nope, (0) ist nicht in der GL(1;K), denn ihre Determinante ist 0 und sie ist somit nicht invertierbar.
Im Fall der GL(1;K) kann mans auch einfacher ausdrücken: (0) ist nicht invertierbar, denn die Gleichung 0 * x = 1 hat keine Lösung ;)
Ouhhh cool haha, ich hab heute tatsächlich mehr gelernt als ich mir je erwartet hätt:)
Ich kann mich nur mehr für deine Hilfe bedanken:) auch bei dr roll
Prüfe mal die Mächtigkeit von Definitions- und Wertebereich. Wenn eine Abbildung injektiv aber nicht surjektiv ist muß die Mächtigkeit des Wertebereiches notwendig größer als die des Definitionsbereiches sein.
Nachtrag: Gilt natürlich nur für endliche Definitions- und Wertebereiche, sorry.
S_n ist ja ohnehin endlich. Wenn K unendlich ist, ist auch GL(n;K) unendlich und somit gibt es keine Surjektion. Ansonsten ist GL(n;K) endlich und man könnte durchaus die Mächtigkeiten vergleichen ;)
Mhhh ok, also ich weiß was die Mächtigkeit ist, und versteh was ihr mir damit sagen möchtet, aber wie prüft man das bzw beweist man das damit?
Der Ansatz von DerRoll ist: Wenn du die Elemente von S_n und GL(n;K) "zählst" und dabei herausfindest, dass |GL(n;K)| > |S_n| ist, dann kann es keine surjektive Abbildung von S_n nach GL(n;K) geben. Also wäre auch dein Homomorphismus keine surjektive Abbildung.
Um das anwenden zu können, müsstest du halt die Mächtigkeiten beider Mengen bestimmen oder wenigstens vergleichen können. Bei der S_n ist das Zählen einfach; die GL(n;K) durchzuzählen ist ein bisschen nervig, weil die Antwort von |K| abhängt, aber auch kein Hexenwerk.
Ich muss hier allerdings Werbung für den Ansatz meiner eigenen Antwort machen; der ist [meiner quasi unvoreingenommenen Meinung nach] deutlich einfacher ;)
Darf ich fragen in welchem Semester du bist? Solche Begriffe und insbesondere der Umgang mit ihnen sollten dir doch wenn du solche Dinge beweisen sollst eigentlich vertrauter sein.
Bei solchen Dingen darf man durchaus auch voreingenommen sein, ich habe jedenfalls damit kein Problem.
2. Semester, ja ich kenne diese Begriffe schon aber hab enorme Schwierigkeiten bei der Anwendung. Ich hab jetzt auch noch nie in dieser Art eine Mächtigkeit bestimmt, also ich lerne es eher theoretisch aber keine Anwendung
Welches Studienfach? Wenn es Mathematik ist bleibt dir nichts anderes übrig als eine Aufgabe nach der nächsten zu rechnen. Üben Üben Üben. Ich hab ein den ersten zwei Semestern etwa 80% aller Übungsblätter abgeschrieben. Aber ich habe wirklich Wert darauf gelegt JEDE Lösung die ich abgeschrieben habe auch zu verstehen. Und beim Vorbereiten auf die Klausuren habe ich alles erneut durch gerechnet.
Ich hatte bereits bei der Formulierung meiner Antwort vermutet (und @MagicalGrill hat das bestätigt) dass Definitions- und Wertebereich endlich sind. Damit sollte der Beweis einfach werden, auch wenn ich @MagicalGrill glaube (und glauben muß) dass seine Methode einfacher ist.
Mathematik auf Lehramt bzw. außer du meinst mit Fach Algebra und analytische Geometrie heißt es. Ja ich versuche Lösungen natürlich auch nachzuvollziehen, was dann trotzdem wieder etwas anderes ist als selbst zu beweisen. Finde ich :-)
Ok danke einmal, irgendwie ich weiß nicht, also wenn ich jetzt deine Matrix nimm, dann ist die ein Element aus der allgemeinen linearen Gruppe. Als Begründung dazu hätt ich, dass die det(Matrix)=1, damit ist sie invertierbar und in GL enthalten, weil GL alle invertierbaren nxn Matrizen enthält? Mir ist bis jetzt noch immer nicht klar, ob ich verstanden habe, was genau die allgemeine lineare Gruppe ist, da ich jetzt in meinem Buch keine Definition finde und ich das im Internet so verstanden habe. Und diese Matrix von dir ist nicht in Sn enthalten bzw. keine Permutationsmatrix, da aufgrund der Definition ja eine Permutationsmatrix in jeder Zeile und jeder Spalte genau eine 1 und sonst 0. Das wär hier dann ja nicht der Fall. Falls das kompletter unsinn ist, tuts ma leid:-/