Polyeder mit ganzzahligen Ecke < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine Matrix A heißt total unimodular, wenn die Determinante jeder quadratischen Untermatrix von A einen Wert
aus [mm] \{1; 0; 1\} [/mm] hat. Sei b ein ganzzahliger Vektor und A eine total unimodulare Matrix.
Beweisen Sie: Der Polyeder
[mm] \{x| Ax = b; x \ge 0 \} [/mm] hat nur ganzzahlige Ecken, d.h. alle Komponenten der Ecken sind ganzzahlig |
also die Ecken haben wir so definiert:
Das Polyeder X = {x : Ax [mm] \le [/mm] b} sei durch A [mm] \in [/mm] R^(m×n), b [mm] \in R^m, [/mm] gegeben und
es sei z [mm] \in [/mm] X. Dann ist z genau dann Ecke, wenn es eine reguläre n × n-Untermatrix A^(J),
J [mm] \subseteq [/mm] {1, . . . ,m}, |J| = n, gibt mit A^(J)z = bJ .
Aber wie ich das mit ganzzahligen Ecken beweisen soll, habe ich nicht verstanden, kann mir jemand dabei helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:18 Mi 09.11.2011 | | Autor: | Stoecki |
Sei [mm] A^{-1}_{J} [/mm] die Inverse zu deiner nxn [mm] A^{J} [/mm] Untermatrix. Dann sind deine Ecken ist genau dann ganzzahlig, wenn für alle J aus der Indexmenge gilt, dass x = [mm] A^{-1}_{J}b_{J} [/mm] ganzzahlig ist. Es fällt also für die Untermatrix der Fall raus, dass die determinente von [mm] A^{J} [/mm] gleich 0 ist. Zum Beweis ein Tipp: Cramersche Regel
Wenn du nicht weiter kommst, meld dich noch mal.
Gruß Bernhard
|
|
|
| |
|
ok, dass ist ganz lieb von dir. aber ich habe hiere keine richtigen Gleichungen, wie soll ich denn dann die cramersche regel anwenden, also worauf genau?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Fr 11.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
