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.

Solution 1:

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

Solution 2:

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.