Verständnis von Beweis zu natürlichzahligen linearen Gleichungen

Neue Frage »

blubbel Auf diesen Beitrag antworten »
Verständnis von Beweis zu natürlichzahligen linearen Gleichungen
Hallo,

Ich habe wieder eine nicht so übliche Problemstellung. Das wird durch die Definitionen etwas länger; Kurzversion: Es gibt ein (relativ einfaches?) Problem, zu dem ich einen Beweis habe, der jedoch an einer Stelle unverständlich ist. Wäre super, wenn mir jemand helfen kann.
Vielleicht reicht es schon, alles ab Knackpunkt zu lesen.

Langversion:
Gegeben ist eine ganzzahlige Matrix C sowie Vektoren v, für die vC=0 gilt. Die Komponenten der Vektoren sind dabei aus den natürlichen Zahlen. Ein solcher Vektor wird p-Invariante genannt.
Ein support einer Invariante ist die Indexmenge der Koordinaten, an denen die Invariante positiv ist. Eine Invariante x wird minimal genannt, falls es keine weitere Invariante y gibt, dessen support eine Teilmenge des supports von x ist. (intuitiv: überall wo x Nullen hat, hat auch y Nullen, aber y hat zusätzlich an weiteren Koordinaten Nullen, wo x positiv ist)

Nun ist die Aussage des Satzes im Bild unten die folgende: Wenn man eine minimale Invariante y mit yC=0 hat, so gilt:
support(y) = Rang (M) + 1

Dabei ist M die Matrix, die man erhält, wenn man die Zeilen von C mit dem support von y indexiert - d.h. man wählt alle Zeilen von C, dessen Index im support von y enthalten ist. Mit Rang ist der übliche Rang gemeint.

Kommen wir zum Beweis (siehe Bild). Die Gleichung (1) ist nichts weiter als die Definition einer Invariante (Erinnerung: Invarianten sind Vektoren über den natürlichen Zahlen). Die Gleichung (2) macht auch Sinn, man findet die µ-Werte, da die ursprüngliche Matrix aus den ganzen Zahlen ist.

Nun der Knackpunkt: Was meint der Autor mit "at least one of the terms in L_i can be eliminated between (1) and (2)"..? Dass man (1)-(2) oder (2)-(1) rechnen soll? Egal welches davon, wie kommt er plötzlich zu einer Gleichung, in der die Koeffizienten µ alle positiv sind? Da hakt es bei mir aktuell. Wie er danach auf genau s'=r+1 Termen kommt ist mir auch noch ein Rätsel.


Ich wäre super Dankbar, wenn sich jemand die Zeit nimmt und sich das kurz anschaut smile
Leider verzweifel ich schon seit einigen Tagen an der einen Stelle im Beweis und weiß nicht, was gemeint ist.


Bei Fragen: Bitte Posten! Ich bin auch für Vermutungen o.Ä. dankbar smile
RavenOnJ Auf diesen Beitrag antworten »

Es muss ja gelten: , da sonst der Rang von maximal wäre, die linear unabhängig und die einzige Lösung für die in



wäre der Nullvektor. Da die , müssen die linear abhängig sein, man kann einen geeigneten der weglassen (o.B.d.A. soll dies sein) und der Rang der Matrix



ist wiederum . Man kann deswegen eine erneute Gleichung



aufstellen und dasselbe Verfahren wie oben durchführen bis man zu einer Matrix kommt. Auch dort gibt es für



eine Lösung ungleich dem Nullvektor,alle , und diese ist sogar eindeutig wenn gefordert wird. Würde man das Verfahren fortsetzen und einen weiteren Vektor weglassen, so wären die restlichen auf alle Fälle linear unabhängig, die zu (1) analoge Gleichung hätte also nur den Nullvektor als Lösung.
 
 
blubbel Auf diesen Beitrag antworten »

Hallo,

erstmal Danke für die Antwort smile

Das macht für mich alles Sinn, bis auf den einen Punkt:

Zitat:
Original von RavenOnJ
man kann einen geeigneten der weglassen (o.B.d.A. soll dies sein) und der Rang der Matrix



ist wiederum .


Wären die Koeffizienten aus den ganzen Zahlen, so macht das für mich Sinn. Da sie aber auf die natürlichen Zahlen beschränkt sind, ist es für micht nicht direkt ersichtlich, dass man so oft Zeilen wegnehmen kann, bis nur noch r+1 Zeilen übrig sind. Kann es nicht einen Fall geben, wo man negative Koeffizienten benötigen würde, um mit r+1 Zeilen auf die 0 zu kommen?
RavenOnJ Auf diesen Beitrag antworten »

das ist mir allerdings auch schon aufgefallen (hatte leider schon gepostet) und da hänge ich gerade.
blubbel Auf diesen Beitrag antworten »

Achso alles klar Augenzwinkern

Das ist nämlich bei mir gerade der Punkt, irgendwie fehlt mir im Beweis die Begründung. Es muss aber irgend etwas damit zu tun haben, dass man ja gerade nur die Zeilen der Matrix auswählt, in denen der Vektor positiv ist. Warum ist mir aber noch nicht schlüssig verwirrt
blubbel Auf diesen Beitrag antworten »

Hallo,

ich bin es noch einmal. Leider bin ich da in der Zwischenzeit immer noch nicht weiter gekommen, benötige den Beweis jedoch. verwirrt
Ein letzter Push, in der Hoffnung, dass doch jemand weiter helfen kann. Gott Selbst wenn es nur eine Idee ist, her damit! Augenzwinkern


Grüße!
Neue Frage »
Antworten »



Verwandte Themen

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