Analog of Birkhoff's theorem for doubly stochastic matrices

Question

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?

Answer 1

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.