paper a day : the Gale-Ryser theorem

By request, today’s paper is kind of about the mathematics of paint-by-numbers puzzles. Merry Christmas, Erin.

A Simple Proof of the Gale-Ryser Theorem
Manfred Krause
The American Mathematical Monthly, Vol. 103, No. 4. (Apr., 1996), pp. 335-337.

The Gale-Ryser Theorem is one of those beautiful little gems in combinatorics. The problem is rather simple to state. Suppose you have a k by n matrix A of zeros and ones. Let r be the vector of sums along each row and c be the vector of sums along each column. The question is this : given an r and a c, when does there exist a matrix A with those row and column sums?

First off, note that r and c satisfy

\| r \|_1 = \|c\|_1

since the total number of ones has to be constant. We need a few more concepts to understand the result. A partition of N is a set of positive integers r1 ≥ r2 ≥ … ≥ rk whose sum is N. It turns out that it’s sufficient to only consider r and c that are partitions (hint : start swapping rows and columns).

Given two partitions r and c of N, we say r is dominated by c if

\sum_{i=1}^{m} r_i \le \sum_{i=1}^{m} c_i \qquad \forall m

where the summands become 0 if we exhaust the partition. As it turns out, dominance provides a partial order on the set of partitions that is particularly useful in combinatorics. The whole theory of majorization is based around the dominance order.

The last concept we need is a Ferrers board and the conjugate partition. Given a partition r of N, imagine a matrix of 0’s and 1’s that has rj 1’s in row j. This is the Ferrers matrix of the partition. The conjugate partition of r, denoted by r*, is the partition whose Ferrers matrix is the transpose of the Ferrers matrix for r.

The Gale-Ryser theorem says that a matrix A exists with row and column sums r and c if and only if r is dominated by c*.

To prove that we need the dominance relation, suppose that r is not dominated by c*. Then look for gaps in A — that is, rows in which you get a 0 and then a 1. Induction on the number of gaps proves it. If there are no gaps we have a Ferrers matrix, so we’re done. If there is a gap, you can swap two entries in a column to reduce the number of gaps.

The novelty in the paper is a new proof of the “only if” half of the statement. It’s basically an algorithm that provably constructs a matrix satisfying the row and column sums given. Clearly this matrix is not unique in general. You start with the Ferrers matrix A0 for c and do a series of swaps until the row sums equal r. Let Aj be the matrix after j swaps. The algorithm guarantees the following:

\| r(A_j) - q \|_2 < \| r(A_{j-1}) - q \|_2

So it will eventually converge to a valid matrix.

The application to paint-by-numbers should be pretty clear. A PBN is just a 0-1 matrix of pixels. If the image in the PBN is convex, then the puzzle is kind of trivial, but you can use the theorem to decide if it's solvable. An interesting extension to work out would be a theorem or fast algorithm for deciding if a general PBN is solvable or not. If I had the time to think about this, I would. Maybe it's something to do on a rainy afternoon after my deadlines have passed.


3 thoughts on “paper a day : the Gale-Ryser theorem

  1. Aww… a Christmas present from the scrooge who celebrates secularmas. :-p

    PS — My parents have not one, but TWO Christmas trees this year. And no holes in the ground.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s