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 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
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 formula_17 terms, i.e. with
In other words, while there exists a decomposition with formula_19 permutation matrices, there is at least one constructible decomposition with no more than formula_20 matrices. Such a decomposition can be found in polynomial time using the Birkhoff algorithm. This is often described as a real-valued generalization of Kőnig's theorem, where the correspondence is established through adjacency matrices of graphs.