0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.