6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Noah Stein
    Commented Sep 20, 2011 at 0:09

2 Answers 2

Reset to default
11
$\begingroup$

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 $\{r_i\}$ and $\{c_j\}$ are zero (and there is no such matrix if this never happens).

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I don't quite understand what you mean by "subtract $\min(r_i, c_j)$ from both $r_i$ and $c_j$". So the update becomes $r_i \leftarrow r_i - \min(r_i, c_j)$ but for what $j$? $\endgroup$
    – ViktorStein
    Commented Mar 7 at 14:42
  • 1
    $\begingroup$ $x\leftarrow \min(r_i,c_j)$, $r_i\leftarrow r_i-x$, $c_j\leftarrow c_j-x$, $a_{ij} \leftarrow x$. The idea is that the vectors $r$ and $c$ keep track of the required additional row and column sums. $\endgroup$
    – Brendan McKay
    Commented Mar 9 at 0:31
  • $\begingroup$ @ViktorStein For reference: Brendan is referring to: Corollary 8.1.4 of the linked book. Bonus: Theorem 8.1.6 counts the number of corners. $\endgroup$
    – ABIM
    Commented Oct 20 at 21:00
1
$\begingroup$

The answer above is partially wrong. The kind of extreme points which are obtained through the construction above, known as the northwest corner rule, can only generate a subset of extreme points (not all of them) of the polytope. To be more precise, the northwest rule can only generate those extreme points for which the graph (as described in the bottom of the answer above) is a caterpillar tree, as can be checked further here: http://www.newton.ac.uk/preprints/NI02033.pdf

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Thanks for citing that interesting paper. However, I don't believe your comment is correct. The NWC rule specifies (for a particular permutation of the rows and columns) exactly which entry must be fixed next, but in my description any entry can be picked that has non-zero row and column requirements. This allows a lot more choices. Try row sums 2,2,2 and column sums 3,1,1,1; it is quite easy to make the tree with three branches of length two (not a caterpillar). Any feasible graph which is acyclic (i.e. a forest) can be made: start with a leaf and use induction. $\endgroup$
    – Brendan McKay
    Commented Apr 12, 2012 at 14:36
  • 1
    $\begingroup$ Apologies... I misread your answer. You are right, what you describe is not the NWC but a more general approach. Many thanks for your comment, it was very useful. $\endgroup$
    – mcuturi
    Commented Apr 13, 2012 at 1:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .