Q: Analog of Birkhoff's theorem for doubly stochastic matrices Birkhoff's theorem states that extreme point of the set of doubly stochastic matrices are permutation matrices. An $n \times n$ matrix $A$ is doubly stochastic if each row and column sums to 1. What can be said if we instead know that there is a vector $a = (a_1,\dots,a_n)$ such that $\sum_{i} A_{ij} = a_j$ and $\sum_{j} A_{ij} = a_i$? That is, for a fixed $a$ what are the extreme points of the set of such matrices?

A: To restate, you're interested in the extreme points of the following set:
$$
S_a = \{ A \in \mathbb{R}^{n\times n} \ : A_{ij} \ge0 , \ A1=a, \ A^T1=a \}
$$
I'm assuming that the matrices must be nonnegative, since you're generalizing doubly stochastic matrices, and otherwise the set is unbounded. This also means the vector $a$ is nonnegative.
I thought I figured it out, but my approach doesn't quite work, but I'll outline it anyway since it could still be useful.
Assume without loss of generality the elements of $a$ are sorted in nonincreasing order, and the indices $k_1, k_2, \ldots k_m$ correspond to the locations of the changes in magnitude:
$$
a_1 = a_2 \ldots = a_{k_1} > a_{k_1+1} = a_{k_1+2} \ldots = a_{k_2} > a_{k_2+1} \ldots 
$$
Let $d_j = a_{k_j}-a_{k_{j+1}}$, and let $1_{k}$ be a vector with 1's in the first $k$ elements, so that $a$ is decomposed:
$$
a = \sum_{j=1}^m d_{j} 1_{k_j}
$$
Then I think one should be able to show that the elements of $S_a$ can likewise be decomposed:
$$
S_a \stackrel{?}{=} \sum_{j=1}^m d_{j} S_{1_{k_j}}
$$
But $S_{1_k}$ is the set of matrices which is doubly stochastic in the leading $k\times k$ subblock and zero elsewhere.
So $S_a$ has at most $k_1! k_2! \ldots k_m!$ extreme points. Each is of the form $\sum_{j=1}^m d_{j} P_j$, where $P_j$ is a permutation matrix in the leading $k_j \times k_j$ subblock and zero elsewhere.
As a simple example, if $a=[7, 3, 1]$, then $k_1=1$, $k_2=2$, $k_3=3$, $d_1=4$, $d_2=2$, $d_3=1$ then the extreme points of $S_a$ are a subset of the following $1!2!3!=12$ matrices:
$$
\begin{bmatrix}
7 & 0 &0\\
0 & 3 &0\\
0 & 0 &1
\end{bmatrix},
\begin{bmatrix}
7 & 0 &0\\
0 & 2 &1\\
0 & 1 &0
\end{bmatrix},
\begin{bmatrix}
6 & 0 &1\\
1 & 2 &0\\
0 & 1 &0
\end{bmatrix},
\begin{bmatrix}
6 & 0 &1\\
0 & 3 &0\\
1 & 0 &0
\end{bmatrix},
\begin{bmatrix}
6 & 1 &0\\
0 & 2 &1\\
1 & 0 &0
\end{bmatrix},
\begin{bmatrix}
6 & 1 &0\\
1 & 2 &0\\
0 & 0 &1
\end{bmatrix},
$$
$$
\begin{bmatrix}
5 & 2 &0\\
2 & 1 &0\\
0 & 0 &1
\end{bmatrix},
\begin{bmatrix}
5 & 2 &0\\
2 & 0 &1\\
0 & 1 &0
\end{bmatrix},
\begin{bmatrix}
4 & 2 &1\\
3 & 0 &0\\
0 & 1 &0
\end{bmatrix},
\begin{bmatrix}
4 & 2 &1\\
2 & 1 &0\\
1 & 0 &0
\end{bmatrix},
\begin{bmatrix}
4 & 3 &0\\
2 & 0 &1\\
1 & 0 &0
\end{bmatrix},
\begin{bmatrix}
4 & 3 &0\\
3 & 0 &0\\
0 & 0 &1
\end{bmatrix}.
$$
However, four of these matrices are not extreme points because they contain a $2\times 2$ submatrix with nonzero entries.
