total unimodulare Matrix

22.05.2013, 20:14

DerJFK

total unimodulare Matrix

Aufgabe

Ich möchte beweisen, dass falls eine Matrix folgenden Bedingungen genügt total unimodular ist.

1. $\begin{eqnarray*} A \in \{0,1\}^{m \times n} \end{eqnarray*}$
2. Jede Spalte bzw. Zeile enthält mindestens zwei 1en
3. In jeder Spalte treten die 1en konsekutiv auf, also es können in einer Spalte keine zwei 0en zwischen zwei 1en stehen.
4. Alle Zeilen sind linear unabhängig

Die gesamt Aufgabe war nur mit den Voraussetzungen 1 und 3, jedoch kann ich 4 hinzunehmen, denn falls Zeilen linear abhängig sind, ist die Determinante sowieso 0. Ist also nur interessant falls sie das nicht sind. 2. Habe ich noch dazu genommen, weil ich, falls es eine Zeile oder Spalte mit nur einer 1 und sonst 0 gibt, die Determinante sich nur am Vorzeichen verändert und es mich ja nur interessiert ob sie -1,0 oder 1 wird.

Anmerkung

Wir haben totale unimodular so definiert, dass jede quadratische Untermatrix die Determinante -1,0 oder 1 ist.

Ideen

Wie gesagt, ich habe oben den Fall weiter eingeschränkt. Jedoch führen meine bisherigen Ansätze zu nichts.

Ich weiß schonmal, wegen (4.) dass die Determinante nicht null ist. Wenn es jetzt zwei 1en in einer Spalte oder Zeile gibt und ich nach diesen entwickel bekomme ich die Summe der beiden Determanten der resultierenden Untermatrizen. Nur da kann ich bisher nicht folgern, dass eine von beiden 0 werden muss :/

Hoffe mir kann jemand einen Anstoß geben, starre dieses Problem schon eine Weile an.

23.05.2013, 08:53

RavenOnJ

Auf diesen Beitrag antworten »

RE: total unimodulare Matrix

Zitat:

Original von DerJFK
3. In jeder Spalte treten die 1en konsekutiv auf, also es können in einer Spalte keine zwei 0en zwischen zwei 1en stehen.

Aber eine 0 darf zwischen zwei 1 auftauchen? Dann folgen die 1 aber auch nicht mehr aufeinander. Irgendwas stimmt da nicht.

Schreib mal das Original der Aufgabe auf, ohne das, was du dazu genommen/gefunden hast. Vielleicht unterlagst du ja einer falschen Schlussfolgerung.

23.05.2013, 10:24

DerJFK

Auf diesen Beitrag antworten »

Zitat:

3. In jeder Spalte treten die 1en konsekutiv auf, also es können in einer Spalte keine zwei 0en zwischen zwei 1en stehen.

Sorry, hatte mich verschrieben.

Die 1en in einer Spalte treten konsekutiv auf.

$\begin{eqnarray*} \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ \vdots \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \end{eqnarray*}$ oder $\begin{eqnarray*} \begin{pmatrix} 1 \\ \vdots \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \end{eqnarray*}$ oder $\begin{eqnarray*} \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ \vdots \\ 1 \end{pmatrix} \end{eqnarray*}$

Jedenfalls ist mir inzwischen auch ein Ansatz zur Lösung eingefallen.

Ich vernachlässige nun wieder meine zusätzlichen Bedingungen und nehme nur die Voraussetzung, dass jede Spalte wie eine der obigen aussieht. (1en in Spalten treten konsekutiv auf)

Berechne ich nun die Determinante kann ich die Spalten wie folgt umsortieren, wobei sich maximal das Vorzeichen der Determinante ändert. (hierbei sei $\begin{eqnarray*} n \end{eqnarray*}$ die die Dimension der quadratischen Teilmatrix)

Ich sortiere so, dass die erste Zeile folgende Gestalt hat: $\begin{eqnarray*} a_{1j}= \begin{cases} 1 & 1 \le j \le k \\ 0 & k+1 \le j \le n \end{cases} \end{eqnarray*}$

weiter sei die erste Spalte, die Spalte in der die kleinste Kette von von konsekutiven 1en steht (von den Spalten die in der ersten Zeile ein 1 haben).

(sei angemerkt, das falls es in der ersten Zeile keine 1en geben sollte, wäre die Determinante direkt 0 )

Nun kann ich drei Fälle unterscheiden:

1. $\begin{eqnarray*} k=1 \end{eqnarray*}$ => Wir können die Determinante nach der ersten Zeile entwickeln und wenden auf die resultierende Matrix wieder die Sortierung an.

2. $\begin{eqnarray*} k \ge 2 \end{eqnarray*}$ => wir ziehen von den Spalten 2,...,k die erste Spalte ab, hierbei ändert sich die Determinante nicht und wir erhalten wieder den 1. Fall.

Damit kann die Determinante nur -1,0,1 sein. Und da in jeder Teilmatrix ebenfalls die 1en konsekutiv auftreten, sind auch die Determinanten aller quadratischen Teilmatrizen -1,0,1 => Matrix ist total unimodular

23.05.2013, 12:59

RavenOnJ

Auf diesen Beitrag antworten »

Das Verfahren ist gut Freude

. Es wäre aber noch anzumerken, dass der Fall k=1 in der Gesamtmatrix nicht vorkommen kann, da es ja mindestens zwei 1en in jeder Zeile geben muss. Der Fall kann allerdings in den Unterdeterminanten auftauchen.

18.06.2015, 10:45

DIDODO

Auf diesen Beitrag antworten »

Moin Moin

warum ändert sich die Determinante im Fall 2 nicht, wenn man von den Spalten 2,..., k den ersten Eintrag von einer 1 auf eine 0 ändert??? verwirrt

18.06.2015, 11:33

DerJFK

Auf diesen Beitrag antworten »

Zum einen verändern Spalten- und Zeilenvertauschung einer Matrix die Determinante nicht. Zum anderen steht nach der Umsortierung in der Ersten Spalte die kleinste Kette konsekutiver 1en, d.h. wenn ich diese von den anderen Abziehe erhalte ich in der ersten Zeile dann in den Einträgen 2,...,k überall 0en und sonst treten auch maximal nur weitere 0en auf (welche aber nach Konstruktion die konsekutiven Ketten nicht zerstören).

Weil ich jetzt in der ersten Zeile nur noch eine 1 und sonst 0en stehen habe, kann nach dieser Zeile entwickeln.

EDIT: Sorry, Vertauschung kann die Determinante ändern, aber nur im Vorzeichen. Was damit nix kaputt macht.

Neue Frage »

Antworten »

total unimodulare Matrix

Verwandte Themen