= Birkhoff-von Neumann theorem
{c}
Every <doubly stochastic matrix> is a <convex combination> of <permutation matrices>. Equivalently, the <extreme points> of the doubly stochastic <convex polytope> are exactly the permutation matrices. The extreme-point assertion follows from an <alternating-cycle perturbation of a doubly stochastic matrix>; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.
Back to article page
