Birkhoff-von Neumann Theorem

The Birkhoff-von Neumann Theorem, in combinatorics and linear algebra, states that every doubly stochastic matrix, a square matrix of nonnegative real numbers whose rows and columns each sum to one, can be written as a weighted average of permutation matrices, with nonnegative weights summing to one. Equivalently, the theorem shows that the polytope of doubly stochastic matrices of a given size is exactly the convex hull of the permutation matrices of that size, so its vertices are precisely the permutation matrices themselves. Named for Garrett Birkhoff and John von Neumann, the theorem underlies applications from fair random assignment to the analysis of bipartite graph matchings.