Gale duality and linear programing.

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 S=\{v_1,\ldots,v_n\}\subset V where V is your favorite vector space over your favorite coefficient field \mathbb{K}. This is just an arbitrary set of non-zero vectors (with repetition allowed), though, for simplicity, I’ll assume it spans all of V. You could also think of this as a hyperplane arrangement on V^*, by looking at the zero set of v_i thought of as a function on V^*.

Now, let W be the vector space of solutions to the equation \sum_{i=1}^nw_iv_i=0, where w_i\in \mathbb{K}. This is not just a vector space, but one equipped with a set distinguished functions w_i:W\to \mathbb{K}. That is, S^\vee = \{w_1,\ldots, w_n\}\subset W^* is a new vector arrangement, which we call the Gale dual to S.

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 ith 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 p: S\to S^{\vee} since both are indexed by the numbers 1 up to n. Let R\subset S be an arbitrary subset. Then we define R^\vee \subset S^\vee to be the complement of p(R).

Theorem. For all R\subset S, the vectors in R are linearly independent if and only if R^\vee spans W^*.

In particular, R is a basis if and only if R^\vee is.

Proof. Linear independence implies that for any non-zero element of W, there is a vector not lying in R which has a non-zero coefficient, that is, there is an w_i\in R^\vee which doesn’t vanish there. This implies that R^\vee spans W^*. 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 v_i, choose a vector \mathbf{a}=(a_1,\ldots, a_n)\in \mathbb{K}^n and look at the level sets H_i=\{\xi\in V^*|\xi(v_i)=a_i\}, 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 (\xi(v_1),\ldots, \xi(v_n)\}, 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 \mathbf{a}\in \mathbb{K}^n/V^*.

Now, if you think for a moment, you see that you can identify \mathbb{K}^n/V^*=W^*, 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 \mathbb{K}=\mathbb{R}. Now, we have an order, so we can ask questions like:

Pick a sign vector \sigma:S\to\{\pm 1\}. Is the region defined by the inequalities A_\sigma=\{\xi\in V^*| \sigma_i(\xi(v_i)-a_i)\leq 0\} non-empty?

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

We define the dual region to A_\sigma by A^\vee_\sigma =\{\mathbf{b}\in W| \sigma_ib_i\geq 0\}.

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): A_\sigma is non-empty if and only if \mathbf{a} achieves a minimum on A_\sigma^\vee.

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 S\subset V-\{0\}.
  • two vectors \mathbf{a},\mathbf{b}\in \mathbf{R}^n

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

F=\{\xi\in V^*| \xi(v_i)\leq a_i\}

and we can define a function \phi_{\mathbf{b}} on F by

\phi_{\mathbf{b}}(\xi)=\sum_{i=1}^nb_i\xi(v_i).

We define the dual program by dualizing the vector arrangement, and switching the places of \mathbf{a} and \mathbf{b}. Let F^\vee 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 \phi_{\mathbf{b}} (which applied mathematicians do, very very much).

Theorem (strong duality): If either a maximum of \phi_{\mathbf{b}} on F or a minimum of \phi^\vee_{\mathbf{a}} on F^\vee 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.

4 thoughts on “Gale duality and linear programing.”

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

  2. 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).

  3. Pingback: Gale and Koszul duality, together at last « Secret Blogging Seminar ~

  4. 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.

Comments are closed.