Doppelt-Stochastische Matrix

In der Mathematik bezeichnet eine doppelt-stochastische Matrix (manchmal auch doppelt-stochastische Übergangsmatrix) eine quadratische Matrix, deren Zeilen- und Spaltensummen eins betragen und deren Elemente zwischen null und eins liegen.

Charakterisierungen

Die folgenden Charakterisierungen von doppelt-stochastisch Matrizen sind äquivalent:

• Eine Matrix ist doppelt-stochastisch genau dann, wenn Zeilen- und Spaltensummen eins betragen und alle Elemente der Matrix zwischen null und eins liegen. .

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

• Eine Matrix ist doppelt-stochastisch genau dann, wenn Zeilen- und Spaltensummen eins betragen und alle Elemente der Matrix nicht negativ sind.

Satz von Birkhoff und von Neumann

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

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.

Weblinks

Birkhoff-von Neumann theorem bei PlanetMath