Total unimodulare Matrix - LinkFang.de





Total unimodulare Matrix


Eine total unimodulare Matrix ist eine Matrix mit ganzzahligen Einträgen, bei der noch weitere Ansprüche an die Determinanten aller quadratischen Untermatrizen gestellt sind. Total unimodulare Matrizen spielen in der diskreten Optimierung eine Rolle, da sie unter bestimmten Bedingungen die Ganzzahligkeit der Lösung eines linearen Optimierungsproblems garantieren.

Definition

Sei [math] A \in \mathbb{R}^{n \times m} [/math] eine Matrix. Dann heißt [math] A [/math] total unimodular (manchmal auch absolut unimodular) genau dann, wenn alle Minoren (Determinanten von quadratischen Untermatrizen) von [math] A [/math] den Wert [math] -1,0 [/math] oder [math] 1 [/math] haben. Insbesondere sind dann alle Einträge ([math] 1 \times 1 [/math]-Untermatrizen) aus [math] \{-1,0,1 \} [/math].

Alternativ formuliert ist eine total unimodulare Matrix eine (nicht notwendigerweise quadratische) Matrix, bei der alle quadratischen, nichtsingulären Untermatrizen ganzzahlig unimodular sind.

Eigenschaften

  • Die Inzidenzmatrix eines ungerichteten bipartiten Graphen ist total unimodular.
  • Die Inzidenzmatrix eines gerichteten Graphen ist total unimodular.
  • Ist [math] A [/math] total unimodular, so ist auch die transponierte Matrix [math] A^T [/math] total unimodular, denn Determinanten bleiben unter Transposition erhalten.
  • Ihre Bedeutung bekommen total unimodulare Matrizen aufgrund der folgenden Aussage: Ist [math] A [/math] total unimodular und [math] b \in \mathbb{Z}^n [/math], so besitzt das Polyeder [math]P= \{x \, | \, Ax \leq b \} [/math] nur ganzzahlige Ecken. Ist ein lineares Optimierungsproblem [math] \min c^Tx [/math] unter der Nebenbedingung [math]x \in P [/math] gegeben, so ist die Optimallösung [math] x^* [/math] ganzzahlig. Ist außerdem [math] c \in \mathbb{Z}^n [/math], so ist auch der Zielfunktionswert [math] c^Tx^* [/math] ganzzahlig.
  • Die Anzahl an Untermatrizen einer Matrix ist exponentiell in der Anzahl der Zeilen/Spalten der Matrix. Obwohl alle diese Untermatrizen zur Charakterisierung der totalen Unimodularität herangezogen werden, gibt es einen polynomiellen Algorithmus zur Entscheidung, ob eine Matrix total unimodular ist oder nicht.

Beispiel

Betrachte die Matrix

[math] A:= \begin{pmatrix} 1&1&0&0\\ 0&0&1&1\\ 1&0&1&0 \end{pmatrix} [/math]
  1. Alle Einträge sind entweder [math] 0 [/math] oder [math] 1 [/math] und damit auch alle [math] 1 \times 1 [/math]-Untermatrizen
  2. Enthält eine [math] 2 \times 2 [/math] Matrix nur Einträge aus [math] \{-1,0,1 \} [/math] und dabei mindestens eine Null, so ist ihre Determinante auch aus [math] \{-1,0,1 \} [/math]. Insbesondere sind die Determinanten aller [math] 2 \times 2 [/math]-Untermatrizen der obigen Matrix aus [math] \{-1,0,1 \} [/math].
  3. Mittels der Regel von Sarrus kann man überprüfen, dass auch die Determinanten der vier [math] 3 \times 3 [/math]-Untermatrizen aus [math] \{-1,0,1 \} [/math] sind.

Daher ist die Matrix total unimodular.

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Total unimodulare Matrix (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.