Doubly stochastic matrix

In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic), is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Thus, a doubly stochastic matrix is both left stochastic and right stochastic.^[1]

Such a transition matrix is necessarily a square matrix: if every row sums to one then the sum of all entries in the matrix must be equal to the number of rows, and since the same holds for columns, the number of rows and columns must be equal. The class of n × n doubly stochastic matrices is a convex polytope in R^N (where N = n²), known as the Birkhoff polytope, B_n. Its dimension is (n − 1)², since the row and column sums being equal to 1 imposes 2n − 1 linear constraints (not 2n, because if the total of all n columns is n, the same must be true of the total of all n rows).

The principal fact about doubly stochastic matrices is the Birkhoff–von Neumann theorem. This states that the set B_n of doubly stochastic matrices of order n is the convex hull of the set of permutation matrices (of order n), and furthermore that the vertices (extreme points) of B_n are precisely the permutation matrices.

Sinkhorn's theorem states that any matrix with strictly positive entries can be made doubly stochastic by pre- and post-multiplication by diagonal matrices.

For n = 2, all bistochastic matrices are unistochastic and orthostochastic, but for larger n it is not the case.

See also

• Stochastic matrix

External links

• PlanetMath page on Birkhoff–von Neumann theorem
• PlanetMath page on proof of Birkhoff–von Neumann theorem

References

1. ^ Marshal, Olkin (1979). Inequalities: Theory of Majorization and Its Applications. pp. 8. ISBN 0-12-473750-1.