Doubly stochastic matrix
From Wikipedia, the free encyclopedia
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. Thus, a doubly stochastic matrix is both left stochastic and right stochastic.
Such a matrix is necessarily a square matrix, by double counting. The class of n × n doubly stochastic matrices is a convex polytope in RN (where N = n2), known as the Birkhoff polytope, Bn. Its dimension is (n − 1)2, since the line 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 Bn of doubly stochastic matrices of order n is the convex closure of the set of permutation matrices of the same order, and furthermore that the vertices (extreme points) of Bn are precisely the permutation matrices.
