In
mathematics, especially in
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
and
combinatorics, a doubly stochastic matrix
(also called bistochastic matrix) is a
square matrix of nonnegative
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s, 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
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
: 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
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...
defined by
independent linear constraints specifying that the row and column sums all equal one. (There are
constraints rather than
because one of these constraints is dependent, as the sum of the row sums must equal the sum of the column sums.) 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 (often known simply as Birkhoff's theorem
[W. B. Jurkat and H. J. Ryser, "Term Ranks and Permanents of Nonnegative Matrices" (1967).]) states that the polytope is the convex hull of the set of permutation matrices
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
, and furthermore that the vertices of are precisely the permutation matrices. In other words, if is a doubly stochastic matrix, then there exist and permutation matrices such that
:
(Such a decomposition of ''X'' is known as a 'convex combination'.) A proof of the theorem based on Hall's marriage theorem
In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations:
* The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a di ...
is given below.
This representation is known as the Birkhoff–von Neumann decomposition, and may not be unique. It is often described as a real-valued generalization of Kőnig's theorem, where the correspondence is established through adjacency matrices of graphs.
Other properties
* The product of two doubly stochastic matrices is doubly stochastic. However, the inverse of a nonsingular doubly stochastic matrix need not be doubly stochastic (indeed, the inverse is doubly stochastic iff it has nonnegative entries).
* The stationary distribution of an irreducible aperiodic finite Markov chain is uniform if and only if its transition matrix is doubly stochastic.
* Sinkhorn's theorem
Sinkhorn's theorem states that every square matrix with positive entries can be written in a certain standard form.
Theorem
If ''A'' is an ''n'' × ''n'' matrix with strictly positive elements, then there exist diagonal matrices ''D''1 and ' ...
states that any matrix with strictly positive entries can be made doubly stochastic by pre- and post-multiplication by diagonal matrices
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero; the term usually refers to square matrices. Elements of the main diagonal can either be zero or nonzero. An example of a 2×2 diagonal m ...
.
* For , all bistochastic matrices are unistochastic In mathematics, a unistochastic matrix (also called ''unitary-stochastic'') is a doubly stochastic matrix whose entries are the squares of the absolute values of the entries of some unitary matrix.
A square matrix ''B'' of size ''n'' is doubly sto ...
and orthostochastic, but for larger this is not the case.
* Van der Waerden's conjecture
In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Both are special cases of a more general function ...
that the minimum permanent
Permanent may refer to:
Art and entertainment
* ''Permanent'' (film), a 2017 American film
* ''Permanent'' (Joy Division album)
* "Permanent" (song), by David Cook
Other uses
* Permanent (mathematics), a concept in linear algebra
* Permanent (cy ...
among all doubly stochastic matrices is , achieved by the matrix for which all entries are equal to . Proofs of this conjecture were published in 1980 by B. Gyires and in 1981 by G. P. Egorychev and D. I. Falikman; for this work, Egorychev and Falikman won the Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...
in 1982.Fulkerson Prize
Mathematical Optimization Society, retrieved 2012-08-19.
Proof of the Birkhoff–von Neumann theorem
Let ''X'' be a doubly stochastic matrix. Then we will show that there exists a permutation matrix ''P'' such that ''xij'' ≠ 0 whenever ''pij'' ≠ 0. Thus if we let λ be the smallest ''xij'' corresponding to a non-zero ''pij'', the difference ''X'' – λ''P'' will be a scalar multiple of a doubly stochastic matrix and will have at least one more zero cell than ''X''. Accordingly we may successively reduce the number of non-zero cells in ''X'' by removing scalar multiples of permutation matrices until we arrive at the zero matrix, at which point we will have constructed a convex combination of permutation matrices equal to the original ''X''.[Birkhoff's theorem]
notes by Gábor Hetyei.
For instance if then
, , and
.
''Proof:'' Construct a bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
in which the rows of ''X'' are listed in one part and the columns in the other, and in which row ''i'' is connected to column ''j'' iff ''xij'' ≠ 0. Let ''A'' be any set of rows, and define A' as the set of columns joined to rows in ''A'' in the graph. We want to express the sizes , ''A'', and , A', of the two sets in terms of the ''xij''.
For every ''i'' in ''A'', the sum over ''j'' in A' of ''xij'' is 1, since all columns ''j'' for which ''xij'' ≠ 0 are included in A', and ''X'' is doubly stochastic; hence , ''A'', is the sum over all ''i'' ∈ ''A'', ''j'' ∈ A' of ''xij''.
Meanwhile , A', is the sum over all ''i'' (whether or not in ''A'') and all ''j'' in A' of ''xij'' ; and this is ≥ the corresponding sum in which the ''i'' are limited to rows in ''A''. Hence , A', ≥ , ''A'', .
It follows that the conditions of Hall's marriage theorem
In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations:
* The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a di ...
are satisfied, and that we can therefore find a set of edges in the graph which join each row in ''X'' to exactly one (distinct) column. These edges define a permutation matrix whose non-zero cells correspond to non-zero cells in ''X''. ∎
Generalisations
There is a simple generalisation to matrices with more columns and rows such that the ''i th'' row sum is equal to ''ri'' (a positive integer), the column sums are equal to 1, and all cells are non-negative (the sum of the row sums being equal to the number of columns). Any matrix in this form can be expressed as a convex combination of matrices in the same form made up of 0s and 1s. The proof is to replace the ''i th'' row of the original matrix by ''ri'' separate rows, each equal to the original row divided by ''ri'' ; to apply Birkhoff's theorem to the resulting square matrix; and at the end to additively recombine the ''ri'' rows into a single ''i th'' row.
In the same way it is possible to replicate columns as well as rows, but the result of recombination is not necessarily limited to 0s and 1s. A different generalisation (with a significantly harder proof) has been put forward by R. M. Caron et al.[R. M. Caron et al., 'Nonsquare "Doubly Stochastic" Matrices', 1996.]
See also
*Stochastic matrix
In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It is also called a probability matrix, transition matrix, ...
*Unistochastic matrix In mathematics, a unistochastic matrix (also called ''unitary-stochastic'') is a doubly stochastic matrix whose entries are the squares of the absolute values of the entries of some unitary matrix.
A square matrix ''B'' of size ''n'' is doubly sto ...
*Birkhoff algorithm Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One su ...
References
*
External links
PlanetMath page on Birkhoff–von Neumann theorem
PlanetMath page on proof of Birkhoff–von Neumann theorem
{{Matrix classes
Matrices