Doppelt stochastische Matrix

In der Mathematik , insbesondere in der Wahrscheinlichkeitstheorie und Kombinatorik , ist eine doppelt stochastische Matrix (auch bistochastische Matrix genannt ) eine quadratische Matrix nichtnegativer reeller Zahlen , deren Zeilen und Spalten jeweils die Summe 1 ergeben, d.h. ${\displaystyle X=(x_{ij})}$

${\displaystyle \sum _{i}x_{ij}=\sum _{j}x_{ij}=1,}$

Eine doppelt stochastische Matrix ist somit sowohl links- als auch rechtsstochastisch . ^{[ 1 ]}

Tatsächlich muss jede Matrix, die sowohl links- als auch rechtsstochastisch ist, quadratisch sein : Wenn sich alle Zeilen zu 1 summieren, dann muss die Summe aller Einträge in der Matrix gleich der Anzahl der Zeilen sein, und da dasselbe für die Spalten gilt, müssen die Anzahl der Zeilen und Spalten gleich sein.

Die Klasse der doppelt stochastischen Matrizen ist ein konvexes Polytop, das als Birkhoff-Polytop bekannt ist . Verwendet man die Matrixeinträge als kartesische Koordinaten , so liegt es in einem n-dimensionalen affinen Unterraum des n-dimensionalen euklidischen Raums, der durch unabhängige lineare Nebenbedingungen definiert ist, die festlegen, dass die Zeilen- und Spaltensummen jeweils gleich 1 sind. (Es gibt Nebenbedingungen n = 1 und nicht n = 1, da eine dieser Nebenbedingungen abhängig ist, da die Summe der Zeilensummen gleich der Summe der Spaltensummen sein muss.) Darüber hinaus sind alle Einträge nichtnegativ und kleiner oder gleich 1. ${\displaystyle n\times n}$${\displaystyle B_{n}}$${\displaystyle (n-1)^{2}}$${\displaystyle n^{2}}$${\displaystyle 2n-1}$${\displaystyle 2n-1}$${\displaystyle 2n}$

Der Satz von Birkhoff-von Neumann (oft einfach als Satz von Birkhoff ^{[ 2 ] [ 3 ] [ 4 ]} bezeichnet ) besagt, dass das Polytop die konvexe Hülle der Menge der Permutationsmatrizen ist und dass die Eckpunkte von genau den Permutationsmatrizen entsprechen. Anders ausgedrückt: Ist eine doppelt stochastische Matrix, so existieren und Permutationsmatrizen, sodass ${\displaystyle B_{n}}$${\displaystyle n\times n}$${\displaystyle B_{n}}$${\displaystyle X}$${\displaystyle \theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1}$${\displaystyle P_{1},\ldots ,P_{k}}$

${\displaystyle X=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.}$

(Eine solche Zerlegung von X wird als „konvexe Kombination“ bezeichnet.) Ein Beweis des Satzes, der auf dem Hallschen Heiratssatz basiert, wird im Folgenden gegeben .

Diese Darstellung ist als Birkhoff-von-Neumann-Zerlegung bekannt und möglicherweise nicht eindeutig. Sie wird oft als reellwertige Verallgemeinerung des Satzes von König beschrieben , wobei die Korrespondenz über Adjazenzmatrizen von Graphen hergestellt wird. Der Satz von Birkhoff-von-Neumann findet auch Anwendungen in der ganzzahligen linearen Programmierung . ^{[ 5 ]}

• Das Produkt zweier doppelt stochastischer Matrizen ist wieder doppelt stochastisch. Die Inverse einer nichtsingulären doppelt stochastischen Matrix muss jedoch nicht doppelt stochastisch sein (tatsächlich ist die Inverse doppelt stochastisch, wenn sie nichtnegative Einträge besitzt).
• Die stationäre Verteilung einer irreduziblen aperiodischen endlichen Markov-Kette ist genau dann gleichmäßig, wenn ihre Übergangsmatrix doppelt stochastisch ist.
• Der Satz von Sinkhorn besagt, dass jede Matrix mit strikt positiven Einträgen durch Vor- und Nachmultiplikation mit Diagonalmatrizen doppelt stochastisch gemacht werden kann .
• Für sind alle bisochastischen Matrizen unistochastisch und orthostochastisch , aber für größere ist dies nicht der Fall.${\displaystyle n=2}$${\displaystyle n}$
• Van der Waerdens Vermutung besagt , dass die kleinste Permanente unter allen n × n doppelt stochastischen Matrizen gleich der Matrix ist, deren Einträge alle gleich sind . ^{[ 6 ]} Beweise für diese Vermutung wurden 1980 von B. Gyires ^{[ 7 ]} und 1981 von G. P. Egorychev ^{[ 8 ]} und D. I. Falikman ^{[ 9 ]} veröffentlicht; für diese Arbeit erhielten Egorychev und Falikman 1982 den Fulkerson-Preis. ^{[ 10 ]}${\displaystyle n!/n^{n}}$${\displaystyle 1/n}$

Sei X eine doppelt stochastische Matrix. Wir zeigen dann, dass eine Permutationsmatrix P existiert, sodass x _{_ij}  ≠ 0 gilt, wann immer p_{_ij}  ≠ 0. Sei λ das kleinste x_{_ij}, das einem von Null verschiedenen p _{_ij} entspricht . Die Differenz X  – λP ist somit ein skalares Vielfaches einer doppelt stochastischen Matrix und enthält mindestens eine Nullzelle mehr als X. Daher können wir die Anzahl der von Null verschiedenen Zellen in X sukzessive reduzieren , indem wir skalare Vielfache von Permutationsmatrizen entfernen, bis wir die Nullmatrix erhalten. Damit haben wir eine Konvexkombination von Permutationsmatrizen konstruiert, die gleich dem ursprünglichen X ist . ^{[ 2 ]}

Zum Beispiel, wenn dann , , und . ${\displaystyle X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}}$${\displaystyle P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}}$${\displaystyle \lambda ={\frac {2}{12}}}$${\displaystyle X-\lambda P={\frac {1}{12}}{\begin{pmatrix}7&0&3\\0&6&4\\3&4&3\end{pmatrix}}}$

Beweis: Konstruiere einen bipartiten Graphen , in dem die Zeilen von X in einem Teil und die Spalten im anderen Teil aufgelistet sind und in dem Zeile i genau dann mit Spalte j verbunden ist , wenn x _{_ij}  ≠ 0. SeiA eine beliebige Menge von Zeilen und seiA die Menge der Spalten, die im Graphen mit Zeilen aus A verbunden sind. Wir wollen die Größen von A undA der beiden Mengen durch die x_{_ij} ausdrücken. ${\displaystyle A}$${\displaystyle A'}$${\displaystyle |A|}$${\displaystyle |A'|}$

Für jedes i in A ist die Summe über j in A' von x _ij gleich 1, da alle Spalten j, für die x _ij ≠ 0 gilt, in A '  enthalten sind und X doppelt stochastisch ist; daher ist die Summe über alle i  ∈  A , j  ∈  A ' von x _ij . ${\displaystyle |A|}$

Inzwischen ist die Summe über alle i (unabhängig davon, ob sie in A enthalten sind ) und alle j in A ' von x _ij  ; und diese ist ≥ die entsprechende Summe, in der die i auf Zeilen in A beschränkt sind . Daher . ${\displaystyle |A'|}$${\displaystyle |A'|\geq |A|}$

Daraus folgt, dass die Voraussetzungen des Hallschen Heiratstheorems erfüllt sind und wir daher eine Menge von Kanten im Graphen finden können, die jede Zeile in X mit genau einer (verschiedenen) Spalte verbinden. Diese Kanten definieren eine Permutationsmatrix, deren von Null verschiedene Zellen den von Null verschiedenen Zellen in X entsprechen .

Es gibt eine einfache Verallgemeinerung für Matrizen mit mehr Spalten und Zeilen, sodass die Summe der i  ^-ten Zeile gleich r_i (einer positiven ganzen Zahl) ist, die Spaltensummen gleich 1 sind und alle Zellen nichtnegativ sind (die Summe der Zeilensummen entspricht der Anzahl der Spalten). Jede Matrix dieser Form lässt sich als Konvexkombination von Matrizen derselben Form aus Nullen und Einsen darstellen. Der Beweis besteht darin, die i  ^-te Zeile der ursprünglichen Matrix durch r_{_i} separate Zeilen zu ersetzen, die jeweils gleich der ursprünglichen Zeile geteilt durch r_{_i} sind  ; den Satz von Birkhoff auf die resultierende quadratische Matrix anzuwenden; und schließlich die r _{_i} Zeilen additiv zu einer einzigen i-  ^ten Zeile zusammenzufügen.

Genauso können sowohl Spalten als auch Zeilen dupliziert werden, aber das Ergebnis der Rekombination ist nicht notwendigerweise auf 0 und 1 beschränkt. Eine andere Verallgemeinerung (mit einem deutlich schwierigeren Beweis) wurde von R. M. Caron et al. ^{[ 3 ] vorgeschlagen.}

• Stochastische Matrix
• Unistochastische Matrix
• Birkhoff-Algorithmus

• Brualdi, Richard A. (2006). Kombinatorische Matrixklassen . Enzyklopädie der Mathematik und ihrer Anwendungen. Band 108. Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl  1106.05001 .

• PlanetMath-Seite zum Birkhoff-von-Neumann-Theorem
• PlanetMath-Seite zum Beweis des Satzes von Birkhoff-von Neumann