##
Gale duality and linear programing. *April 6, 2008*

*Posted by Ben Webster in Euclidean geometry, hyperplanes.*

trackback

trackback

So, I felt I should try to explain a bit about this hypertoric stuff. I think the first order of business should be explaining what Gale duality is. This is all “just” linear algebra, in principle very simple, though not exactly the usual perspective on these things. To slightly paraphrase some notes from Daniel Kleitman’s website:

The act of writing down explicit dual equations of a given hyperplane arrangement is not complicated but it is quite unnatural to human beings. You can expect to do it hesitantly and incorrectly the first three times you try to do it.

So, first of all, consider a **vector arrangement ** where is your favorite vector space over your favorite coefficient field . This is just an arbitrary set of non-zero vectors (with repetition allowed), though, for simplicity, I’ll assume it spans all of . You could also think of this as a hyperplane arrangement on , by looking at the zero set of thought of as a function on .

Now, let be the vector space of solutions to the equation , where . This is not just a vector space, but one equipped with a set distinguished functions . That is, is a new vector arrangement, which we call the **Gale dual** to .

To reiterate: given a hyperplane arrangement with fixed normal vectors to its hyperplanes, the Gale dual is the space of vanishing linear combinations of these normal vectors, with the hyperplane arrangement consisting of the subspaces where the th coefficient vanishes.

Well, that was simple. In fact, why am I making such a fuss about this stuff? (Because it’s awesome? Do we need more of a reason?)

Well, to try to convince you something interesting is going on here, let’s think a bit about how to translate statements back and forth between Gale dual arrangments. Note that we have a bijetion since both are indexed by the numbers 1 up to . Let be an arbitrary subset. Then we define to be the complement of .

**Theorem.** *For all , the vectors in are linearly independent if and only if spans .*

*In particular, ** is a basis if and only if is.
*

*Proof. * Linear independence implies that for any non-zero element of , there is a vector not lying in which has a non-zero coefficient, that is, there is an which doesn’t vanish there. This implies that spans . The opposite direction is an similar exercise. **QED!**

Note: to those of you who like matroids, this tells you how to define Gale duality of matroids. Since not all matroids are representable, this is actually a slightly richer definition.

Now, what I’ve told you about thus far is central hyperplane arrangments, ones where all the hyperplanes are linear (pass through the origin). But usually we prefer to think about more general hyperplane arrangements where the hyperplanes allowed to be affine subspaces.

To get these, rather than looking at the zero sets of , choose a vector and look at the level sets , then you’ll get an affine hyperplane arrangement.

However, a bunch of these are just translates of each other. If one picks a vector of the form , you’ll just have picked a different origin. Thus, we should mod out by this subspace, and think about our hyperplanes arrangements up to translation, determined by elements .

Now, if you think for a moment, you see that you can identify , so applying Gale duality to an arrangement of affine hyperplanes gives us a hyperplane arrangment with an extra function on it.

Now, let’s specialize to . Now, we have an order, so we can ask questions like:

**Pick a sign vector . Is the region defined by the inequalities non-empty?**

Naively, these inequalities constrain to lie on a particular side of each hyperplane.

We define the dual region to by .

A theorem that’s very important for our work says that this question can be understood in terms of Gale duality. This is a fact linear programmers learn with their mother’s milk, but which doesn’t seem to be particularly well-known amongst mathematicians in general, even though it just uses basic concepts of linear algebra.

**Theorem** (weak duality of linear programs): * is non-empty if and only if achieves a minimum on .*

Now, this is a pretty cool theorem (if you ask me), but in order to state the stronger duality theorems of linear programs, we need a slightly different class of objects: a **linear program** is

- a vector arrangement .
- two vectors

A **solution** to a linear program is an element of the **feasible region**

and we can define a function on ** **by** **

.

We define the **dual program** by dualizing the vector arrangement, and switching the places of and . Let be the feasible region of the dual.

Weak duality above tells us when these regions are non-empty, but in fact that is a much stronger duality theorem which is rather useful if you actually care about bounding the value of (which applied mathematicians do, very very much).

**Theorem** (strong duality): *If either a maximum of on or a minimum of on exists, than the other does, and they are equal.*

**Exercise:** Show that weak duality follows from strong duality.

Thus, exhibiting any point of the feasible region of the dual gives a bound on the original problem. Cool, no?

I don’t have time to discuss it, but one cool application of this is the theorem of Ford, Fulkerson, Elias, Feinstein, and Shannon that the maximal amount of flow through a network is the value of a minimal cut.

## Comments

Sorry comments are closed for this entry

Huh! I always knew this as the Ford-Fulkerson theorem. But according to Wikipedia, your three cited guys proved it independently the same year.

Where do you think I got the info? Anyway, I suppose Ford and Fulkerson deserve equal billing. I wasn’t really paying that much attention that far into the entry (frankly, I’m surprised you were, though I suppose you think about vertices, etc. more than I do).

[…] papers, the arXiv. trackback So, in past posts, I’ve attempted to explain a bit about Gale duality and about Koszul duality, so now I feel like I should try to explain what they have to do with […]

As was mentioned ghd Straightener at the beginning of this post, having a great deal of preparation needs to be able to be carried out before heading out over a camping outdoors vacation. Most electronics feature a manufacturer’s warranty when purchased brand new, so take note regarding any such offerings when browsing for 2 tip radios. Many little companies make the mistake by starting dissimilar using Family-FRS radios.