Doubly stochastic matrix
Encyclopedia
In mathematics
, especially in probability
and combinatorics
, a doubly stochastic matrix
(also called bistochastic),
is a square matrix of nonnegative real number
s, each of whose rows and columns sums to 1. Thus, a doubly stochastic matrix is both left stochastic
and right stochastic.
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 RN (where N = n2), known as the Birkhoff polytope, Bn. Its dimension is (n − 1)2, 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 Bn 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 Bn 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, especially in probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, a doubly stochastic matrix
(also called bistochastic),
is a square matrix of nonnegative real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s, each of whose rows and columns sums to 1. Thus, a doubly stochastic matrix is both left stochastic
Stochastic matrix
In mathematics, a stochastic matrix is a matrix used to describe the transitions of a Markov chain. It has found use in probability theory, statistics and linear algebra, as well as computer science...
and right stochastic.
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
Convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn...
in RN (where N = n2), known as the Birkhoff polytope, Bn. Its dimension is (n − 1)2, 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 Bn of doubly stochastic matrices of order n is the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of the set of permutation matrices
Permutation matrix
In mathematics, in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere...
(of order n), and furthermore that the vertices (extreme points) of Bn are precisely the permutation matrices.
Sinkhorn's theorem
Sinkhorn's theorem
-Theorem:If A is an n × n matrix with strictly positive elements, then there exist diagonal matrices D1 and D2 with strictly positive diagonal elements such that D1AD2 is doubly stochastic....
states that any matrix with strictly positive entries can be made doubly stochastic by pre- and post-multiplication by diagonal matrices
Diagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...
.
For n = 2, all bistochastic matrices are unistochastic
Unistochastic matrix
In mathematics, a unistochastic matrix is a doubly stochastic matrix whose entries are the square of the absolute value of some unitary matrix.The detailed definition is as follows...
and orthostochastic
Orthostochastic matrix
In mathematics, an orthostochastic matrix is a doubly stochastic matrix whose entries are the square ofthe absolute value of some orthogonal matrix.The detailed definition is as follows...
, but for larger n it is not the case.