Total unimodulare Matrix

Matrix, deren Minoren den Wert -1,0 oder 1 haben

Eine total unimodulare Matrix (oder auch vollständig unimodulare Matrix) ist eine Matrix mit ganzzahligen Einträgen, bei der noch weitere Forderungen an deren Unterdeterminanten 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

Bearbeiten

Sei   eine Matrix. Dann heißt   total unimodular (manchmal auch absolut unimodular oder vollständig unimodular) genau dann, wenn jede Unterdeterminante von   einen der Werte   oder   oder   hat. Insbesondere sind dann alle Elemente (also alle  -Untermatrizen) von   in  .

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

Eigenschaften

Bearbeiten
  • Die Inzidenzmatrix eines ungerichteten bipartiten Graphen ist total unimodular.
  • Die Inzidenzmatrix eines gerichteten Graphen ist total unimodular.
  • Ist   total unimodular, so ist auch die transponierte Matrix   total unimodular, denn Determinanten bleiben unter Transposition erhalten.
  • Ihre Bedeutung bekommen total unimodulare Matrizen aufgrund der folgenden Aussage: Ist   total unimodular und  , so besitzt das Polyeder   nur ganzzahlige Ecken. Ist ein lineares Optimierungsproblem   unter der Nebenbedingung   gegeben, so ist die Optimallösung   ganzzahlig. Ist außerdem  , so ist auch der Zielfunktionswert   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

Bearbeiten

Betrachte die Matrix

 
  1. Alle Einträge sind entweder   oder   und damit auch alle  -Untermatrizen
  2. Enthält eine   Matrix nur Einträge aus   und dabei mindestens eine Null, so ist ihre Determinante auch aus  . Insbesondere sind die Determinanten aller  -Untermatrizen der obigen Matrix aus  .
  3. Mittels der Regel von Sarrus kann man überprüfen, dass auch die Determinanten der  -Untermatrizen aus   sind.

Daher ist die Matrix total unimodular.

Literatur

Bearbeiten