Doubly stochastic matrix
In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix), is a square matrix formula_1 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 formula_3 doubly stochastic matrices is a convex polytope known as the Birkhoff polytope formula_4. Using the matrix entries as Cartesian coordinates, it lies in an formula_5-dimensional affine subspace of formula_6-dimensional Euclidean space defined by formula_7 independent linear constraints specifying that the row and column sums all equal one. (There are formula_7 constraints rather than formula_9 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) states that the polytope formula_4 is the convex hull of the set of formula_3 permutation matrices, and furthermore that the vertices of formula_4 are precisely the permutation matrices. In other words, if formula_13 is a doubly stochastic matrix, then there exist formula_14 and permutation matrices formula_15 such that (Such a decomposition of "X" is known as a 'convex combination'.) A proof of the theorem based on Hall's marriage theorem 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. 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 "x" ≠ 0 whenever "p" ≠ 0. Thus if we let λ be the smallest "x" corresponding to a non-zero "p", 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". For instance if formula_21 then formula_22, formula_23, and formula_24. Proof: Construct a bipartite graph 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 "x" ≠ 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 "x". For every "i" in "A", the sum over "j" in A' of "x" is 1, since all columns "j" for which "x" ≠ 0 are included in A', and "X" is doubly stochastic; hence |"A"| is the sum over all "i" ∈ "A", "j" ∈ A' of "x". Meanwhile |A'| is the sum over all "i" (whether or not in "A") and all "j" in A ' of "x" ; 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 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" row sum is equal to "r  (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" row of the original matrix by "r" separate rows, each equal to the original row divided by "r" ; to apply Birkhoff's theorem to the resulting square matrix; and at the end to additively recombine the "r" rows into a  single "i" 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.