= Solution
An <extreme point> of a <convex set> cannot be written as a nontrivial convex combination of two distinct members. If a <permutation matrix> $P=\theta B+(1-\theta)C$ with $0<\theta<1$ and $B,C$ doubly stochastic, each zero entry of $P$ forces the corresponding entries of $B,C$ to be zero by nonnegativity. The unique possible nonzero entry in each row must then be one by the row sum. Thus $B=C=P$, proving that every <permutation matrix> is extreme.
Conversely, let $A$ be a <doubly stochastic matrix> that is not a <permutation matrix>. At least one entry lies strictly between zero and one. Form a <bipartite graph> whose two vertex classes are rows and columns, with edges precisely at these fractional entries. Every incident row has at least two fractional entries: a single fractional entry, with all other entries zero or one, could not give row sum one. The same holds for columns.
A finite nonempty graph whose incident vertices all have degree at least two contains a cycle. In a <bipartite graph> that cycle has even length. Assign alternating signs $+1,-1$ to its entries, giving a nonzero matrix $D$ with every row and column sum zero. Choose $\varepsilon>0$ smaller than the distance of each cycle entry from both zero and one. Then $A+\varepsilon D$ and $A-\varepsilon D$ remain <doubly stochastic matrices>, are distinct, and satisfy
$$
A=\tfrac12(A+\varepsilon D)+\tfrac12(A-\varepsilon D).
$$
So $A$ is not extreme. Therefore
$$
\boxed{\operatorname{Ext}(\mathcal C)=\{\text{permutation matrices}\}.}
$$
This <alternating-cycle perturbation of a doubly stochastic matrix> proves the extreme-point part of the <Birkhoff-von Neumann theorem> directly.
Back to article page
