The extremal toolbox: A matrix problem

I’m starting a new series of posts this semester where I get “back to basics.” One of the few areas of mathematics in which I can claim anything even in the same connected component as “expertise” is extremal combinatorics. Unfortunately for me and my lazy, big-picture brain, though, extremal combinatorics is very much a “problem-solving” subject, with a relatively small number of tools that are used to solve all sorts of different problems. So without some practice solving these problems, or expositing the solutions, it’s easy to get rusty.

Hence, “The Extremal Toolbox.” In each post, I’ll take a (solved!) problem in extremal combinatorics — anything from Sperner’s theorem to Kakeya over finite fields, as long as there’s an extremal flavor — and try to break down a proof into its component parts.

Today I’m going to examine a problem which appeared on MathOverflow some time ago, which I didn’t quite solve (but came within epsilon of!) The relevant post is here; if you don’t care to click through, here’s the problem.

Let M be an n \times n matrix with non-negative integer entries. Suppose further that if m_{ij} is 0, then the sum of all the entries in the ith row or the jth column is at least n. Then the sum of all the entries in M is at least n^2/2.

How do we solve this?

The first thing to notice is that (as long as n is even) there are a number of matrices with total sum exactly n^2/2 — for instance, a “checkerboard pattern” of zeroes and ones, or having all entries along the diagonal be equal to n/2 and zeros everywhere else. There’s no apparent structure to these extremal entries… but one thing that you do notice is that all of them have row sums and column sums at least n/2. Note that if we can prove that the entries in any row and column have to sum to at least n/2, we’re immediately done, since there are n rows.

Trick: Write the quantity you want to optimize as a sum of “sub-quantities” which are easier to analyze.

New goal: Show that each row/column has sum at least n/2.

The obvious path here is to try for a proof by contradiction. Suppose that some row, say, has sum m < n/2. Then since our matrix has integer entries, that row has a lot of entries which are zeros; the columns containing those zeros each have to have entries summing to at least n-m. This looks like it could work!

Let’s make it more rigorous. Let’s say that the row has total sum m = cn, for some c < 1/2. Then the row must contain at least (1-c)n zeros; the columns containing these zeros have to each have sum at least (1-c)n, so the matrix must have sum at least (1-c)^2 n^2. But as c approaches 1/2, this lower bound only gives us n^2/4, which is obtainable by a number of methods.

But… we haven’t used all our information! In particular, we know that there’s a row whose entries sum to cn. And since the choice of row was arbitrary, we can even assume that it was the row with the smallest sum! Does this let us do better?

It sure does — following the above argument line-by-line, we have that the sum of all the entries is the maximum of cn^2, (1-c)^2 n^2 — doing some high-school algebra, we see that the coefficient of this maximum will always be at least \frac{3 - \sqrt{5}}{2}, which is about 0.38. This is a major improvement on 0.25, but it’s still not what we want.

Trick: If you have a free parameter in your argument, try making it extremal. The worst case scenario is that you gain no additional information; the best case is a considerably stronger result.

Darn. Is there any way to rescue this approach?

Well, look back over the argument. Is there anywhere where there’s some slack, where we can tighten it up? At first it doesn’t look like it — we’ve optimized and extremized everything we could. But note that so far we’ve looked at row sums and only row sums. Of course, it doesn’t really matter — the argument would proceed exactly the same if we used column sums — but “Without Loss of Generality” is a tricky phrase, especially in combinatorics, where it often means you’re giving up some tightness for ease of analysis.

So let’s try, instead of minimizing over all row sums, minimizing over all row sums and column sums. Suppose that there’s a row (WLOG, again, but this time we’re getting more information) with total sum m = cn, such that every row and column of our matrix has total sum at least m. Now, again, there must be at least (1-c)n zeros in the row, and the sum of the entries in all the columns containing those zeros is at least (1-c)^2 n^2. But this time we have some additional ammo; we know that the sum of the entries in the other columns is at least cn. So the sum of all the entries in the matrix must be at least (c^2 + (1-c)^2) n^2; it’s easy to check that the coefficient must always be at least 1/2.

Trick: If you have a free parameter, make it extremal — and keep in mind that it’s not always immediately clear how to do so! In general, be very careful when you’re trying to find the “slack” in your argument; it can be hidden.

What are the general lessons?

In actuality, this problem wasn’t very hard — the only real trick is considering the sums of the entries of the individual rows/columsn, which is an obvious enough thing to do. The key, though, was to make the argument as tight as possible, and not lose any information along the way. Sometimes this isn’t feasible; sometimes the best you can do is obtain an asymptotic bound. But when it is feasible — in particular, when it’s easy to get the right asymptotics without much thought at all — it’s often possible to work wonders with a fine-tuned version of the “obvious” approach.


Tags: , , ,

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

%d bloggers like this: