The Birkhoff-von Neumann theorem states that every 
doubly stochastic
matrix is a convex combination of 
permutation matrices. Thus, if 
is a doubly stochastic
matrix, then
 |
where the 
are permutation matrices, 
, and 
. The decomposition may be chosen with
.
Equivalently, the vertices of the Birkhoff polytope are precisely the permutation matrices. This formulation distinguishes the theorem from the several other results called Birkhoff's theorem.
