# Extreme points of transportation polytope

I'm interested in $n \times m$ joint probability tables with prescribed row and column marginals. Such tables form a convex set known as the transportation polytope. What are the extreme points of this set?

For example, for a $2 \times 2$ case of $$\begin{bmatrix} x_{11} & x_{12}\\\\ x_{21} & x_{22} \end{bmatrix}$$ with row constraint $x_{11} + x_{12} = 0.9$, column constraint $x_{11} + x_{21} = 0.8$, and $\sum_{i,j} x_{ij} = 1$, then there are two extreme points, $$\begin{bmatrix} 0.8 & 0.1\\\\ 0 & 0.1 \end{bmatrix}, \quad \begin{bmatrix} 0.7 & 0.2\\\\ 0.1 & 0 \end{bmatrix}.$$ And every joint table with the constraint lies in the convex hull of these two points.

Is there a general way of finding the extreme points? In other words, is there a generalization to Birkhoff–von Neumann theorem for this case?

-
The Birkhoff von-Neumann theorem shows that the output size may be factorial, so you should not expect to solve such problems efficiently (at least in the input size). Are you looking for something more tailored to this problem than general purpose algorithms/packages such as those available at ifor.math.ethz.ch/~fukuda/cdd_home and cgm.cs.mcgill.ca/~avis/C/lrs.html? –  Noah Stein Sep 20 '11 at 0:09
Also, I don't see why this is tagged community wiki. –  Noah Stein Sep 20 '11 at 0:09
My bad, I didn't realize that the community wiki box was checked. How do I undo it? –  Memming Sep 20 '11 at 15:41
I checked the FAQ, and there's no way to revert the community wiki. :'( –  Memming Sep 20 '11 at 15:51

A complete solution with references can be found in Section 8.1 of Brualdi, Combinatorial Matrix Classes, Cambridge University Press, 2006.

Here is how to make an extreme point, and all extreme points can be made in this way. Suppose $\{r_i\}$ and $\{c_j\}$ are the required row and column sums. Start with a zero matrix $A=(a_{ij})$. Choose $i,j$ so that $r_i,c_j>0$. Set $a_{ij}=\min(r_i,c_j)$ and subtract $\min(r_i,c_j)$ from both $r_i$ and $c_j$. Keep doing this until all the row sums or all the columns sums are zero (and it better be both of them zero or there is no such matrix).

And a characterization. For any matrix in the class you can define a bipartite graph with $m$ row-vertices and $n$ column-vertices where the edges indicate where the matrix entries are non-zero. Then the matrix is an extreme point iff the graph has no cycles.

-
I've been reading the book, and it has been extremely helpful. Thank you so much. –  Memming Oct 15 '11 at 19:19