Doubly stochastic matrix


In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
, is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
Thus, a doubly stochastic matrix is both left stochastic and right stochastic.
Indeed, any matrix that is both left and right stochastic must be square: 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.

Birkhoff polytope

The class of doubly stochastic matrices is a convex polytope known as the Birkhoff polytope. Using the matrix entries as Cartesian coordinates, it lies in an -dimensional affine subspace of -dimensional Euclidean space defined by independent linear constraints specifying that the row and column sums all equal one. Moreover, the entries are all constrained to be non-negative and less than or equal to one.

Birkhoff–von Neumann theorem

The Birkhoff–von Neumann theorem states that the polytope is the convex hull of the set of permutation matrices, and furthermore that the vertices of are precisely the permutation matrices. In other words, if is doubly stochastic matrix, then there exist and permutation matrices such that
This representation is known as the Birkhoff–von Neumann decomposition, and it may not be unique in general. By Carathéodory's theorem, however, there exists a decomposition with no more than terms, i.e. with
In other words, while there exists a decomposition with permutation matrices, there is at least one constructible decomposition with no more than matrices. Such a decomposition can be found in polynomial time using the Birkhoff algorithm.

Other properties