Doppelt-stochastische Matrix

In der Mathematik bezeichnet eine doppelt-stochastische Matrix (manchmal auch doppelt-stochastische Übergangsmatrix) eine quadratische Matrix, deren Zeilen- und Spaltensummen ${\displaystyle 1}$ betragen und deren Elemente zwischen ${\displaystyle 0}$ und ${\displaystyle 1}$ liegen.

Charakterisierungen

Die folgenden Charakterisierungen doppelt-stochastischer Matrizen sind äquivalent:

• Eine Matrix ist doppelt-stochastisch genau dann, wenn Zeilen- und Spaltensummen eins betragen und alle Elemente der Matrix zwischen ${\displaystyle 0}$ und ${\displaystyle 1}$ liegen.

• Eine Matrix ${\displaystyle M}$ ist doppelt-stochastisch genau dann, wenn sowohl ${\displaystyle M}$ als auch die transponierte Matrix ${\displaystyle M^{T}}$ Übergangsmatrizen sind.

• Eine Matrix ist doppelt-stochastisch genau dann, wenn Zeilen- und Spaltensummen ${\displaystyle 1}$ betragen und alle Elemente der Matrix nicht negativ sind.

Eigenwerte und Eigenvektoren

Wie alle Übergangsmatrizen besitzen auch doppelt-stochastische Matrizen als betragsgrößten Eigenwert den Eigenwert ${\displaystyle 1}$. Da jede doppelt-stochastische Matrix sowohl zeilen- als auch spaltenstochastisch ist, ist der Einsvektor ${\displaystyle \mathbf {1} }$ (welcher nur Einsen als Einträge hat) sowohl Links- als auch Rechtseigenvektor jeder doppelt-stochastischen Matrix. Ist nun die Matrix ${\displaystyle M}$ doppelt-stochastisch und noch zusätzlich entweder irreduzibel oder echt positiv (vgl. Satz von Perron-Frobenius), so ist die einzige stationäre Verteilung der Markow-Kette, die durch ${\displaystyle M}$ charakterisiert wird, die Gleichverteilung, also der Wahrscheinlichkeitsvektor ${\displaystyle {\tfrac {1}{n}}\mathbf {1} }$ (das ${\displaystyle n}$ bezieht sich auf die Dimension der ${\displaystyle n\times n}$-Matrix ${\displaystyle M}$).

Satz von Birkhoff und von Neumann

Für eine ${\displaystyle n\times n}$-Matrix gilt, dass sie genau dann doppelt-stochastisch ist, wenn sie eine Konvexkombination von Permutationsmatrizen ist.

Zusatz: Die Permutationsmatrizen sind die Extremalpunkte der Menge der doppelt-stochastischen Matrizen.

Literatur

• Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way. Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4. 
• Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer Spektrum, Berlin u. a. 2013, ISBN 978-3-642-32185-6. 

Weblinks

• Andrea Ambrosio, Stephen Forrest: Birkhoff-von Neumann theorem. In: PlanetMath. (englisch)
• Eric W. Weisstein: Doubly Stochastic Matrix. In: MathWorld (englisch).