Birkhoff-von Neumann theorem (doubly stochastic matrices)

Find the extreme points of the set $S$ of doubly stochastic matrices of order $n$. (A matrix $A$ is said to be doubly stochastic if its elements are nonnegative, and the sum of the elements in each row and each column is equal to $1$.)

A matrix $D=\left[d_{i j}\right]$ is doubly stochastic if each entry is nonnegative and if the sum of the entries in any row or column is equal to 1. Suppose $G=(X, Y, E)$ is a bipartite graph in which each vertex in $X$ corresponds to a row of $D$ and each vertex in $Y$ corresponds to a column of $D$. Furthermore, there is an edge between vertex $x_{i}$ in $X$ and vertex $y_{j}$ in $Y$ if and only if the entry $d_{i j}$ is positive. Show that there is a perfect matching in $G$.

A permutation matrix is a binary square matrix in which no two nonzero elements appear in the same row or same column. Prove the Birkhoff-von Neumann theorem: A square matrix $D$ is doubly stochastic if and only if there exist nonnegative numbers $r_{i}$ and permutation matrices $P_{i}(i=1,2, \ldots , k)$ such that $D=r_{1} P_{1}+r_{2} P_{2}+\cdots +r_{k} P_{k}$ and the sum $\sum r_{i}$ is 1. (In other words, $D$ is a convex combination of permutation matrices.)

Represent the following doubly stochastic matrix as a convex combination of permutation matrices:

Express the following double stochastic matrix $D$ as a convex combination of permutation matrices:

Express the following doubly stochastic matrix as a convex combination of permutation matrices: