3 - Algebraische und geometrische Ideen in der Theorie der diskreten Optimierung [ID:5360]
50 von 315 angezeigt

Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Es ist wieder Zeit für die nächste Vorlesung. Wir machen aber quasi mit einer kleinen Übungsaufgabe

hier weiter, sprich mit dem Beweis. Hat jemand ein bisschen so Gedanken gehabt über die Pause,

wie ihr da rangehen könnt? Wir haben also so einen rationalen polyethischen Kegel gegeben

und der soll erzeugt werden durch rationale Vektoren. Und wenn ich also weiß,

diese Vektoren sind rational, dann kann ich auch annehmen, sie sind ganzzahlig.

So, demzufolge weiß ich, dass für jeden Gitterpunkt in diesem Kegel existieren jetzt Lambda 1 bis Lambda k

nicht negativ unreell erstmal, sodass sich dieser Punkt z schreiben lässt als so eine

nicht negative oder chronische Linealkombination.

So, also wir haben hier dieses typische Parallelogramm, der Vektor z lässt sich

schreiben als Lambda 1 r1 plus Lambda 2 r2. So, dummerweise sind die nicht ganzzahlig.

Die Ri haben wir nach Konstruktion schon ganzzahlig gemacht, schon mal super,

aber dummerweise sind die Koeffizienten nicht ganzzahlig, die wollen wir ja ganzzahlig haben.

Und jetzt müssen wir uns einen kleinen Trick einfallen lassen, um die ganzzahlig zu machen.

Und der Trick geht wie folgt. Wir runden die einfach mal ab.

Da haben wir jetzt möglicherweise was vergessen und was wir vergessen haben ist genau diesen

fraktionellen Anteil. So, was wissen wir hier darüber?

Naja, wir wissen, das hier ist eine nicht negative ganze Zahl. Bei Lambda i war vorher

eine nicht negative reelle Zahl. Ab und zu bleibt nicht negativ, sind jetzt ganzzahlig.

Das hier ist ein Punkt aus C gestitten z hoch n, ist also ein Gitterpunkt in dem Kegel.

Super, das da oben sieht schon mal gut aus. Das da unten, wissen wir irgendwas über das da unten.

Also ich weiß, das was immer hier steht ist nicht negativ. Das heißt also das,

was hier steht insgesamt ist eine nicht negative Linearkombination der Kegel erzeugen.

Das heißt also das hier liegt im Kegel. Weiß ich noch irgendwas mehr über diese Summe?

Ja, die Summe ist auch ganzzahlig. Warum?

Ja, diese Dinger sind hier alles schreckliche drin, aber hier oben ganzzahliger Vektor,

ganzzahliger Vektor. Das heißt, was da übrig bleibt muss jetzt auch ganzzahliger Vektor sein.

Super, das heißt das hier ist ein Gitterpunkt im Kegel. So, hilft uns das jetzt irgendwie weiter?

Direkt eine endliche Menge von Gitterpunkten des Kegels hinzuschreiben,

die so eine Erzeugungseigenschaft oder Darstellungseigenschaft haben,

wo diese Lambda i nicht negativ und ganzzahlig sind.

Es steht quasi schon alles da. Man muss es jetzt nur richtig interpretieren.

Also wir bilden jetzt eine Menge F und das soll die Menge aller Punkte sein, die sich schreiben lassen

als Linearkombination. Der Ri, wobei die Alpha i nicht negativ sind und echt kleine 1.

Was hat es die Menge mit unserem Problem zu tun?

Naja, dieser Punkt da oben hier, der hier entsteht, das hier ist ja nicht nur nicht negativ,

sondern auch echt kleiner 1. Also das hier ist ein Element von F.

Also egal was da als Rest hier übrig bleibt, es ist immer in dieser Menge F drin.

So, und nicht nur in F drin, sondern sogar in den Gitterpunkten von F.

Wie viele Gitterpunkte hat F? Endlich viele.

Das kann man ganz einfach sehen, dass man also die Norm von x, man suche sich eine beliebige aus,

ist ja gerade die Norm, diese Summe. Und die ist nach der Dreiecksumgleichung kleiner gleich die Summe der Alpha i Norm Ri.

Und das ist echt kleiner als die Summe der Norm der Ri. Und das ist eine endliche Zahl, weil die Ri sind ja gegeben.

Gut, das heißt wir haben dargestellt unser z als eine Summe von Lambda i abgerundet mal Ri plus einmal klein f mit klein f.

Und der Gitterpunkt in groß F. Super, also das z ist jetzt eine nicht negative ganz zahlige Linearkombination von Elementen,

also von Kegelerzeugern und einem Element aus dieser Menge F geschnitten z durch n.

Und das z ist ein beliebiger Punkt im Kegel gewesen. Also haben wir jetzt eine Hilbertbasis hier, also die Menge R1 bis Rk

zusammen mit F geschnitten z hoch n bildet eine endliche Hilbertbasis, also Hilbertbasis ist ja endlich, aber machen wir zur Betonung,

eine endliche Hilbertbasis von C. Ist der Beweis klar oder gibt es irgendwo noch Erklärungsbewerb?

Also ich kann jetzt nicht genau sagen, wie der Punkt genau aussieht, aber ich weiß er liegt in einer beschränkten Menge,

Zugänglich über

Offener Zugang

Dauer

01:14:38 Min

Aufnahmedatum

2015-07-27

Hochgeladen am

2015-08-07 11:28:12

Sprache

de-DE

Einbetten
Wordpress FAU Plugin
iFrame
Teilen