Farkas’ lemma: purely algebraic intuition

Here is a statement of Farkas Lemma from the Wikipedia. Let $A$ be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the following two statements is true:

1. There exists an $x \in \mathbb{R}^n$ such that $Ax = b$ and $x \geq 0$.
2. There exists a $y \in \mathbb{R}^m$ such that $A^T y \geq 0$ and $b^T y < 0$.

This result has a simple geometric interpretation: either $b$ lies in the cone formed by the columns of $A$ or it is possible to find a vector $y$ such that $y$ forms an acute angle with all columns of $A$ and an obtuse angle with $b$.

I was wondering if there is a way to make the result intuitive purely at the algebraic level of solving linear equations and inequalities?

The lemma is important in finance and the geometric intuition is not much help there since the vectors are payoffs and prices of financial assets which have no natural geometric meaning. Gale's Theory of Linear Economic Models has a purely algebraic proof, but that is an opaque induction argument.

EDIT: A little more about my application. We have $m$ assets and $n$ possible future states of nature. $A_{ij}$ is the payoff by asset $i$ in state $j$. $b_i$ is the price of asset $i$. $x_j$ is the value of one dollar in state $j$. $y_i$ is the amount of asset $i$ in a portfolio.

So Farkas' lemma tells us that either (1) there is a way of assigning a non-negative price to a dollar in each state in a way such that the price of each asset is just the sum total of the value of its payoffs, or (2) there is a portfolio whose price is negative, so you get paid for holding it, but whose payoffs are non-negative, which means that you do not have to pay anything back. I want to understand, in terms which make economic sense, why (1) and (2) should be mutually exclusive. Acute and obtuse angles are no help here.

-
Why do you say that "geometric intuition is not much help there"? Isn't this this rather an example showing that geometric intuition can indeed be helpful even for problems that on the surface don't seem to have anything to do with geometry? – Hans Lundmark Oct 29 '10 at 8:05
@Hans. That's certainly one way of looking at it. My problem is that while geometry lets me discover and prove the result there is no way I can then explain the result in purely finance terms without saying "let me draw a picture" at some point. I was hoping that if I had an intuition in terms of solving inequalities then that might have a more natural interpretation for my particular application. – Jyotirmoy Bhattacharya Oct 29 '10 at 9:10
I honestly don't know what algebraic intuition should mean. Isn't intuition what you have when you 'see' what the answer should be? I think Hans's suggestion is worth more consideration. You want to interpret this lemma in terms of a model to which it applies. The only bridge you have so far is a geometric picture, but there is a disconnect between that picture and your understanding of the model. You are asking for a new bridge. If instead you improve the infrastructure around that model (i.e., make peace with a geometric representation of your algebraic intuition), you may gain more. – yasmar Oct 29 '10 at 15:43
@Mike. Thanks for your offer, but for my purpose bringing in linear programming would make things more complicated. – Jyotirmoy Bhattacharya Oct 29 '10 at 17:57
For those who may want to know more of the finance story, (1) and (2) not having simultaneous solutions would be called "no arbitrage leads to the existence of state prices". The continuous-time multiperiod version is one of the pillars of modern asset pricing theory and has been studied at a high level of generality by probabilists. See for example math.uni.opole.pl/~aspakow/md/… – Jyotirmoy Bhattacharya Oct 30 '10 at 3:09

If you want an intuition that explains why Farka's Lemma should be true, you will have to use the geometric interpretation; there's no way around that.

If you want an intuition that shows what Farka's Lemma achieves (but not why it should be true), there is indeed an algebraic explanation.

Namely, Farka's Lemma answers the following question: what is a sufficient and necessary condition for the system of equations

$$\begin{array}{rcl}a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &=& b_2 \\ &\vdots& \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &=& b_m \end{array}$$

to have a positive solution $x_i\ge 0$?

Oviously, if one of the equations has the form

$$c_1x_1 + c_2x_2 + \dots + c_nx_n = b$$

where all the $c_i$ are positive $c_i > 0$, but the right-hand side $b$ is negative $b<0$, then it's clearly impossible to choose all the $x_i$ positive and have them satisfy the equation, because the left-hand side would always be positive.

This was only for a single equation, but it is equally obvious that if any linear combination of the equations of your system

$$\left(\sum y_i a_{i1}\right)x_1 + \left(\sum y_i a_{i2}\right)x_2 + \dots + \left(\sum y_i a_{in}\right) x_n = \sum y_i b_i$$

has this form with positive coefficients on the left- and a negative number on the right-hand side, then you can't solve it for $x_i \ge 0$.

Now, what Farka's Lemma says is that this is in fact the only bad thing that can happen. If the system

$$Ax = b$$

doesn't have a solution $x\ge0$, then this must be because there exists a nasty linear combination of some equations

$$(y^TA)x = y^Tb$$

that obstructs solvability because it satisfies $y^TA \ge 0$ but $y^Tb \le 0$.

In a sense, Farka's Lemma shows that the non-solvability of the system can be "certified"; the vector $y$ is a "certificate" for the fact that the system cannot be solved. Such certificates, commonly called obstructions, are common in other branches of mathematics, like algebraic geometry (Hilbert's Nullstellensatz) or algebraic topology (homology, cohomology).

-

First suppose both conditions are true. From the first of them we know $x\geq 0$, from the second --- $y^TA\geq 0$. Therefore $y^Tb=y^TAx\geq 0$. Contradiction.

Now suppose that both conditions are false. Let $\{e_k\}_{k=1}^n$ be the standard basis in $\mathbb{R}^n$. Note that the set $\{Ax\mid x\geq 0\} = \{\sum_kx_k Ae_k\mid x_k\geq 0\}$ is closed and take the nearest point to $b$ in it. From minimality of $\|b-Ax\|^2$ for any $k$ we have either $x_k>0$ and $\partial_{x_k}\|b-Ax\|^2=0$ either $x_k=0$ and $\partial_{x_k}\|b-Ax\|^2\geq 0$. Thus \left[\begin{aligned}x_k&>0,&(b-Ax,Ae_k)&=0,\\x_k&=0,& (b-Ax,Ae_k)&<0\end{aligned}\right.\tag{1}

Take $y=Ax-b$. From (1) we have $(y,Ae_k)\geq 0$ and hence $A^Ty\geq 0$. Finally $$b^Ty=(y,b)=(Ax-b,b)=(Ax-b,b-Ax)+(Ax-b,Ax)=$$ $$-\|b-Ax\|^2-\sum_kx_k (b-Ax,Ae_k)=-\|b-Ax\|^2<0.$$ So the second condition should be true. Contradiction.

-