= Birkhoff decomposition by support matchings
{c}
{title2=$A=\sum_i\alpha_iP_i$}
For a <doubly stochastic matrix>, the <Hall marriage theorem> supplies a <perfect matching> in its positive-entry support. Subtract the smallest matched entry times the corresponding <permutation matrix>. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a <convex combination> of <permutation matrices>. With $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.
Back to article page
