Trennende Invariante der GL(2,Z) auf Z^(2x1)

Neue Frage »

Telperion Auf diesen Beitrag antworten »
Trennende Invariante der GL(2,Z) auf Z^(2x1)
Moin zusammen,
es geht um folgende Aufgabe:
Zitat:
Zeige, dass eine Gruppe ist, die auf operiert, so dass
eine trennende Invariante ist.

Anscheinend ist der Begriff trennende Invariante nicht so bekannt, deshalb hier mal unsere Definition:

Zitat:
Def.:
Sei eine Gruppe, die auf der Menge operiert. Eine Abbildung in eine Menge heißt Invariante der Operation, falls . Die Invariante heißt trennend, falls bereits impliziert.

Hierbei bezeichne die Bahn von m unter G. Bei ist nicht "" gemeint, sodern die Operation von auf angewand.

Ich muss also erstmal die Operation finden. Da scheitert es aber schon, da uns heute beim Besten willen keine einfallen wollte. Es hat sicherlich was mit dem Euklidischen Algorithmus zu tun und seiner Formulierung mithilfe von Matrizen, aber so wirklich weiter gekommen sind wir nicht.

Liebe Grüße,
Dominik
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Als Operation würde sich die normale Matrix-Vektor-Multiplikation anbieten.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Hey IfindU,
an die Matrix-Vektor-Multiplikation habe ich durchaus auch gedacht, aber ich frage mich dann, wieso bei der Multiplikation mit einer Matrix aus die Abbildung eine Invariante ist. Sprich: Wieso bleibt der ggT nach der Multiplikation mit so einer Matrix erhalten ( auf der Bahn). Das ist mir nicht klar.

Liebe Grüße,
Dominik
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Hi,

eine vollständige Antwort habe ich bis jetzt noch nicht: Aber überlege dir erst einmal welche Determinante die Matrizen aus der Gruppe haben müssen. Dann wie die Determinante aussieht, und was du dann über den ggT einzelner Matrixeinträge sagen kannst.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Hi,

wir haben die Determinante einer Matrix noch nicht eingeführt, weshalb ich auch nichts über den ggT in Zusammenhang mit der Determinante sagen kann.

Vielen Dank, dass du dich mit der Aufgabe beschäftigst Freude

Liebe Grüße,
Dominik
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Technisch gesehen könntest du auch eine allgemeine 2x2 Matrix mit ganzen Werten nehmen, und schauen, wann diese invertierbar ist. Ist aber eine etwas nervige Rechnung.
 
 
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Hm, das kann ich wohl machen, aber die Matrizen aus sind doch eh alle in invertierbar, oder sehe ich da jetzt irgendwas komplett falsch?
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Jop, die sind per Definition invertierbar. Bloss nicht jede allgemeine 2 x 2 Matrix, selbst wenn sie aus linear unabhängigen Zeilen besteht, ist nicht in invertierbar.
Beim invertieren bekommt man einen Bruch, der selten eine ganze Zahl ist. Ich bin ziemlich sicher, dass man die Aufgabe nicht lösen kann, ohne das zu benutzen.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Okay, also meinst du, dass ich einfach mal so eine allgemeine Matrix mit Einträgen aus invertieren soll und schauen soll, was dabei rauskommt?
Dann werde ich das mal machen. Warscheinlich geht das dann über die Determinante einfacher..
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Ok, ich denke ich habs.

Man zeigt im Prinzip 2 Richtungen: Sei . Dann ist jeder Teiler von auch Teiler von (das ist ziemlich leicht). Und dann zeigt man noch die umgekehrte Richtung, wofür ich die Sache mit der Determinate gebraucht habe.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Also ich hab mal auf Wiki nach dem Inversen geschaut, ich kann das ja wenn dann immernoch eben nachrechnen. Sei also unsere Matrix . Dann muss aus sein, damit wir wieder ganze Zahlen erhalten.

Wenn ich jetzt mal sage, dass meine Operation (was ich noch nachrechnen muss aber sicher hinkommt) die Linksmultiplikation mit einer invertierbaren Matrix ist.
Also ist eine Gruppenoperation.

Jetzt mal mein anschaulicher Gedankengang. Wenn der ganz falsch ist verwerfe ich ihn gleich, wenn er richtig ist kann ich mich an die formale Ebene wagen:
Wenn ich mit einer Invertierbaren Matrix multipliziere, deren Einträge in liegen bekomme ich wieder eine Matrix mit Einträgen in und ich kann immer wieder zu meiner ursprünglichen Matrix "zurück".
Wen ich den Euklid durchziehe mache ich ja eigentlich nichts anderes, d,h. ich ziehe ihn bis zum Ende durch, forme jede Zeile nach ihrem Rest um und setzte dann rückwärts ein, sodass ich Bézout-Identitäten erhalte. Das kann ich ja hier dann genauso machen.
Dann wird mein ggT nicht verändert, weil ich die Matrixmultiplikation mit invertierbaren Matrizen durchführe.

Ist der Gedankengang richtig? Wenn, dann würde ich mich an das Formale machen.


Liebe Grüße,
Dominik

\edit: Ich habe deinen neuen Beitrag erst gesehen, nachdem ich den hier abgeschickt habe.
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Also ich kann mir nicht wirklich vorstellen, wie du das formalisieren willst, auch wenns mich interessieren würde. Und ich schätze du wirst mit der Begründung recht haben, also warum diese Identität überhaupt gilt, aber das sauber zu formalisieren wird glaub ich nicht so einfach, da ich mir nicht wirklich vorstellen kann (was aber bei Linearen Algebra sehr wohl nur an mir liegen kann) wie man da rangehen sollte.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Okay.
""Sei , also . Sei .
Es ist . Dann ist klar, dass da alle Zahlen aus und t schon m_1 und m_2 teilt. Analog geht das für

"" Sei t teiler von . Dann folgt . Ehrlich gesagt bin ich der Meinung, dass ich hier fertig bin, oder nicht? Ich habe das Gefühl, dass da erstmal was nicht stimmen kann.

Vielen Dank für deine Mühe! =)

Liebe Grüße,
Dominik
PS: Vielleicht versuche ich morgen meine erste Argumentation nochmal zu formalisieren, ich stelle mir das aktuell aber ziemlich schwer vor. smile
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Bei der Rückrichtung machst du es dir etwas zu einfach, denn wenn t die Summe teilt, muss es nicht jeden einzelnen Summanden teilen (2 teilt 1+1, aber nicht 1). Du brauchst dass t sowohl , als auch teilt, und dann musst du versuchen es irgendwie hinzubiegen, dass t dann x_1 und x_2 teilt.

Ich erinnere hier noch einmal an die Definition:
teilt
jester. Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Zitat:
Original von IfindU
Beim invertieren bekommt man einen Bruch, der selten eine ganze Zahl ist. Ich bin ziemlich sicher, dass man die Aufgabe nicht lösen kann, ohne das zu benutzen.


Ab hier verrennt ihr euch ein bisschen in die Determinante Big Laugh Dominik wird darauf nicht sinnvoll zurückgreifen können und es ist auch nicht nötig.

Wir zeigen erstmal, dass Invariante ist. Sei dazu und .
Dann sieht man leicht ein, dass , genau wie Dominik in seinem letzten Beitrag in "" gezeigt hat (wofür stehen die Pfeile hier eigentlich genau? verwirrt )

Die Idee ist ja, dass der ggT von a und b auch jede Linearkombination teilt. Jetzt haben wir aber zu ein Inverses (egal wie es aussieht), welches uns a und b wieder aus dieser Linearkombination zurückgibt (und zwar wieder als Linearkombination der Einträge von ), sodass wir mit gleichem Argument bekommen, dass

Leider kommt das einer Komplettlösung nun schon sehr nahe, aber ich weiß nicht, wie ich die Idee anders formulieren soll... Ich hoffe das, was ich geschrieben habe, war verständlich.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Hey jester.,
vielen Dank für deinen Beitrag. Freude
Zitat:
(wofür stehen die Pfeile hier eigentlich genau? verwirrt )

Die stehen für die zwei Richtungen, die IfindU mir vorgeschlagen hat.
Ich habe durchaus verstanden, was du mit deinem Beitrag sagen wollltest und hab den Beweis auch hinbekommen. Du hast Recht, es war fast eine Komplettlösung, aber sie hat mir geholfen und ich habe mir ja vorher auch viele Gedanken darüber gemacht. Augenzwinkern

Aktuell sitze ich noch daran zu zeigen, dass trennende Invariante ist.

Liebe Grüße,
Dominik
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
So, hier mal mein Ansatz für die trennende Invariate:
Sei . Sei weiter . Dann ist mit dem Lemma von Bézout

Also unterscheide sich und nur um . Die Bahnen von partitionieren dann , sodass zwei Elemente aus genau dann in einer Klasse liegen, wenn sie den selben ggT haben. (Ich hoffe ich habe hier die Richtige Vorstellung der Bahnen?)
Jetzt haben aber den gleichen ggT, weshalb sie schon in einer Klasse liegen.

Ist das so richtig?

Liebe Grüße,
Dominik
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Mir ist nicht ganz klar, was du damit zeigen willst.

Meins ist vermutlich wieder unnötig technisch, aber was möglich sein sollte ist, 2 Vektoren mit dem gleichen ggT zu nehmen, und eine Matrix aus GL zu konstruieren, die die eine in die andere überführt. Das wird dann wohl mit Bezout gehen, aber ich hätte dann lieber die Matrix noch einmal aufgeschrieben.

Alternativ warte bis Jester. eine schöne Lösung liefert Augenzwinkern
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Also, ich muss für die trennende Invariante zeigen, dass wenn ist bereits folgt.
Die Bahnen bilden eine Partition, also kann ich auch zeigen, dass für bereits folgt, dass in derselben Klasse liegen, oder nicht?

Das habe ich gerade versucht zu zeigen, allerdings wohl nicht besonders erfolgreich..

Liebe Grüße,
Dominik
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Wenn ich mich nicht irre, haben wir folgendes gezeigt:
Wenn wir den gleichen ggT haben, bleiben wir durch die Gruppenoperation beim gleichen ggT. Aber es könnte ja sein, dass wir 2 Bahnen mit dem gleichen ggT haben, die sich nie treffen.

Was wir zeigen müssen ist, dass es nur eine Bahn mit dem gleichen ggT geben kann. Und ich sehe aktuell nicht wie den ggT als Linearkombination darstellen das zeigt.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Hm, ich bin irgendwie verwirrt, glaube ich.
Sind wir uns denn einig, dass zwei Elemente genau dann in einer Bahn liegen, wenn die den gleichen ggT haben?
Denn dann glaube ich, dass ich gezeigt habe, dass aus der Gleichheit des ggTs schon folgt, dass die Elemente in der gleichen von den Bahnen erzeugten Klassen liegen und damit auch in der selben Bahn.
Ich kann aber auch völlig falsch liegen.

Liebe Grüße
IfindU Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Nehmen wir mal die Gruppe , die auf operiert (durch normale Addition).

Nun haben wir die Situation, dass ungerade Zahlen immer auf ungerade abgebildet werden, und gerade auf gerade. Aber:
Es gibt 2 Bahnen auf den ungeraden, und 2 auf den Geraden. Explizit heißt das wir haben und .

D.h. nur weil eine Eigenschaft erhalten bleibt, hier ungerade zu sein, heißt es nicht, dass sie auf der gleichen Bahn liegen.

Deine Aufgabe bei der ggT Sache ist es zu zeigen, dass gerade das hier nicht passiert. Die Situation die wir beim ggT haben, aber noch nachweisen müssen, ist dass eher die Gruppe in diesem Beispiel operiert, und wir ungerade <=> gleiche Bahn haben.
Telperion Auf diesen Beitrag antworten »
RE: Trennende Invariante der GL(2,Z) auf Z^(2x1)
Ja du hast Recht, ich habe meine Invariante auf ein Element angewendet und rausgefunden, dass ich eine Invariante habe, was aber natürlich klar ist. Ich muss da ehrlich gesagt nochmal drüber nachdenken, wie ich die trennende Invariante genau zeige..
Ich hab ja noch bis Mittwoch, die Aufgabe ist aber ziemlich heftig.

Schonmal vielen Dank für deine Hilfe, das Beispiel hat mir geholfen.

Liebe Grüße,
Dominik
Telperion Auf diesen Beitrag antworten »

Hey,
ich habe mir nochmal Gedanken gemacht:
Seien . Weiter gelte . Dann weiß ich aus einer Bemerkung im Skript, die den Euklidischen Algorithmus mithilfe von Matrizen darstellt, dass eine Matrix existiert, mit mit . Diese Matrix ist aus und damit invertierbar, sodass ich dann also schreiben kann.
Dann habe ich also ein Elemente gefunden, welches mir mein in überführt, oder nicht?

Vielleicht passt es ja diesmal.

Liebe Grüße,
Dominik
IfindU Auf diesen Beitrag antworten »

Schaut schon sehr gut aus, aber ich würde noch eine Matrix finden, so dass ist, dann kannst du wirklich leicht eine Matrix angeben, die sie überführt. Aktuell ists noch ein wenig unschlüssig, wieso es reicht den Vektor (t, 0) zu betrachten.
Telperion Auf diesen Beitrag antworten »

Danke, dass du nochmal drüber schaust IfindU. Freude

Also es gilt . Ich weiß, dass auch eine Matrix existiert mit . Dann kann ich also einsetzen:
. Diesen Schritt kann ich machen, weil B nach Vorraussetzung invertierbar ist.

Meintest du das so?
IfindU Auf diesen Beitrag antworten »

Jop, genau. Und damit liegen die bereits auf der gleichen Bahn, und das ist was du zeigen wolltest. Freude
Telperion Auf diesen Beitrag antworten »

Wow, vielen Dank für deine geduldige, ausführliche und fachlich sehr kompetente Hilfe. smile Das hat wirklich sehr viel Spaß gemacht und mir wirklich geholfen. Freude

Liebe Grüße,
Dominik Wink
IfindU Auf diesen Beitrag antworten »

Schön, dass ich helfen konnte.

Grüße
IfindU Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »