= Solution
The preceding <perfect matching> gives a <permutation matrix> $P$ supported on the positive entries of $A$. Let
$$
\alpha=\min\{a_{ij}:p_{ij}=1\}>0.
$$
If $\alpha=1$, every row's selected entry is one and all other entries vanish, so $A=P$. Otherwise
$$
A'=\frac{A-\alpha P}{1-\alpha}
$$
is a <doubly stochastic matrix> with strictly fewer positive entries. Induct on the number of positive entries: the base case has exactly $n$ positive entries and is a <permutation matrix>. By induction, write $A'=\sum_i\beta_iP_i$ as a <convex combination>. Then
$$
A=\alpha P+(1-\alpha)\sum_i\beta_iP_i
$$
is another <convex combination>, with nonnegative coefficients summing to one. Thus
$$
\boxed{A=\sum_{i=1}^k\alpha_iP_i,\qquad \alpha_i\geq0,\quad\sum_i\alpha_i=1.}
$$
This constructive proof of the <Birkhoff-von Neumann theorem> is <Birkhoff decomposition by support matchings>.
Back to article page
