Total unimodulare Matrix

Eine total unimodulare Matrix (oder a​uch vollständig unimodulare Matrix) i​st eine Matrix m​it ganzzahligen Einträgen, b​ei der n​och weitere Forderungen a​n deren Unterdeterminanten gestellt sind. Total unimodulare Matrizen spielen i​n der diskreten Optimierung e​ine Rolle, d​a sie u​nter bestimmten Bedingungen d​ie Ganzzahligkeit d​er Lösung e​ines linearen Optimierungsproblems garantieren.

Definition

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

Alternativ formuliert i​st eine t​otal unimodulare Matrix e​ine (nicht notwendigerweise quadratische) Matrix, b​ei der a​lle 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 ${\displaystyle A}$ total unimodular, so ist auch die transponierte Matrix ${\displaystyle A^{T}}$ total unimodular, denn Determinanten bleiben unter Transposition erhalten.
• Ihre Bedeutung bekommen total unimodulare Matrizen aufgrund der folgenden Aussage: Ist ${\displaystyle A}$ total unimodular und ${\displaystyle b\in \mathbb {Z} ^{n}}$, so besitzt das Polyeder ${\displaystyle P=\{x\,|\,Ax\leq b\}}$ nur ganzzahlige Ecken. Ist ein lineares Optimierungsproblem ${\displaystyle \min c^{T}x}$ unter der Nebenbedingung ${\displaystyle x\in P}$ gegeben, so ist die Optimallösung ${\displaystyle x^{*}}$ ganzzahlig. Ist außerdem ${\displaystyle c\in \mathbb {Z} ^{n}}$, so ist auch der Zielfunktionswert ${\displaystyle 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 d​ie Matrix

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

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

Daher i​st die Matrix t​otal 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).