Double stochastic matrix

In mathematics , a double-stochastic matrix (sometimes also double-stochastic transition matrix ) denotes a square matrix whose row and column sums are and whose elements are between and . ${\ displaystyle 1}$ ${\ displaystyle 0}$ ${\ displaystyle 1}$

Characterizations

The following characterizations of double-stochastic matrices are equivalent:

A matrix is double-stochastic if and only if the row and column sums are one and all elements of the matrix are between and . ${\ displaystyle 0}$ ${\ displaystyle 1}$

A matrix is double-stochastic if and only if both and the transposed matrix are transition matrices . ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle M ^ {T}}$

A matrix is double-stochastic if and only if the rows and columns are sums and all elements of the matrix are not negative. ${\ displaystyle 1}$

Eigenvalues and Eigenvectors

Like all transition matrices, double-stochastic matrices also have the eigenvalue as the greatest eigenvalue . Since every doubly stochastic matrix is both row and column stochastic, the one vector (which has only ones as entries) is both left and right eigenvector of every doubly stochastic matrix. If the matrix is double-stochastic and additionally either irreducible or genuinely positive (see Perron-Frobenius theorem ), then the only stationary distribution of the Markov chain that is characterized by is the uniform distribution , i.e. the probability vector . ${\ displaystyle 1}$ ${\ displaystyle \ mathbf {1}}$ ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle {\ tfrac {1} {n}} \ mathbf {1}}$

Theorem by Birkhoff and von Neumann

For a matrix it is true that it is double-stochastic if and only if it is a convex combination of permutation matrices . ${\ displaystyle n \ times n}$

Addition: The permutation matrices are the extremal points of the set of double-stochastic matrices.

literature

Joseph PS Kung, Gian-Carlo Rota , Catherine H. Yan: Combinatorics: The Rota Way . Cambridge University Press , Cambridge (et al.) 2009, ISBN 978-0-521-73794-4 .
Peter Knabner , Wolf Barth : Lineare Algebra. Basics and applications (= Springer textbook ). Springer Spectrum, Berlin et al. 2013, ISBN 978-3-642-32185-6 .

Web links

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