Total unimodulare Matrix

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

Sei $A\in \mathbb {R} ^{n\times m}$ eine Matrix. Dann heißt $A$ total unimodular (manchmal auch absolut unimodular oder vollständig unimodular) genau dann, wenn jede Unterdeterminante von $A$ einen der Werte $-1$ oder $0$ oder $1$ hat. Insbesondere sind dann alle Elemente (also alle $1\times 1$ -Untermatrizen) von $A\in \mathbb {R} ^{n\times m}$ in $\{-1,0,1\}$ .

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 $A$ total unimodular, so ist auch die transponierte Matrix $A^{T}$ total unimodular, denn Determinanten bleiben unter Transposition erhalten.
Ihre Bedeutung bekommen total unimodulare Matrizen aufgrund der folgenden Aussage: Ist $A$ total unimodular und $b\in \mathbb {Z} ^{n}$ , so besitzt das Polyeder $P=\{x\,|\,Ax\leq b\}$ nur ganzzahlige Ecken. Ist ein lineares Optimierungsproblem $\min c^{T}x$ unter der Nebenbedingung $x\in P$ gegeben, so ist die Optimallösung $x^{*}$ ganzzahlig. Ist außerdem $c\in \mathbb {Z} ^{n}$ , so ist auch der Zielfunktionswert $c^{T}x^{*}$ 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

$A:={\begin{pmatrix}1&1&0&0\\0&0&1&1\\1&0&1&0\end{pmatrix}}$

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

Daher ist die Matrix total unimodular.

Literatur

Martin Aigner: Diskrete Mathematik (= Vieweg Studium: Aufbaukurs Mathematik). 6., korrigierte Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8.
Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. 3. Auflage. Springer Spektrum, Berlin 2018, ISBN 978-3-662-57690-8, S. 122 ff.
Alexander Schrijver: Combinatorial optimization. Polyhedra and efficiency. Springer, Berlin 2003, ISBN 978-3-540-44389-6 (3 Bände, 1881 Seiten).

Basierend auf einem Artikel in:

Wikipedia.de