Proposition 1.8 (Farkas Lemma (II))
Let \(A\) be an \(m\times n\) matrix, and let \(b\in\mathbb{R}^m\). Then exactly one of the following two possibilities occurs:
  1. There exists \(x\in\mathbb{R}^n\) with \(Ax=b\) and \(x\ge 0\) or
  2. There exists \(y\in\mathbb{R}^m\) with \(y^{T}A\ge 0^{T} \) and \( y^{T}b<0. \)

Explanation

First recall that

$$ \begin{align*} Ax= \begin{bmatrix} | & | & & | \\ a_1 & a_2 & \cdots & a_n\\ | & | & & | \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} = x_1a_1 + x_2a_2 + \cdots + x_na_n \end{align*} $$

Since \(x \geq 0\), then \(x_i \geq 0\) for all \(i\). Recall that the convex cone generated by \(a_1,\cdots,a_n \in \mathbb{R}^m\) is

$$ \begin{align*} \text{cone}(a_1, a_2,\cdots,a_n) = \{ x_1a_1 + x_2a_2 + \cdots + x_na_n \mid x_1,\cdots,x_n \geq 0 \} \end{align*} $$

Therefore because all the coefficents \(x_1,\cdots,x_n\) arenon-negative, then

$$ \begin{align*} Ax = x_1a_1 + x_2a_2 + \cdots + x_na_n \in \text{cone}(a_1, a_2,\cdots,a_n) \end{align*} $$

So \(Ax\) is an element of the cone generated by the columns of \(A\).

In fact the set of all vectors of the form \(Ax\) with \(x \geq 0\) is exactly the cone generated by the columns of \(A\). So

$$ \begin{align*} \{ Ax \mid x \geq 0\} = \text{cone}(a_1, a_2,\cdots,a_n) \end{align*} $$

Option 1 in Farkas’s lemma says that \(b\) lives in the cone generated by the columns of \(A\). In other words,

$$ \begin{align*} b \in \text{cone}(a_1, a_2,\cdots,a_n) \end{align*} $$

Option 2 must then mean that \(b\) is not in the cone. More specifically, that there is a separating hyperplane that separates \(b\) from the cone.

Why is that? We are given two conditions in option 2:

$$ \begin{align*} y^TA \geq 0 \quad \text{ and }\quad y^Tb < 0. \end{align*} $$

Notice now that any non-zero vector \(y\) defines a natural hyperplane as follows

$$ \begin{align*} H = \{ x \mid y^Tx = 0 \} \end{align*} $$

The coefficient vector here is normal to the hyperplane. But now notice that

$$ \begin{align*} y^TA= \begin{bmatrix} y_1 & y_2 & \cdots & y_m \end{bmatrix} \begin{bmatrix} | & | & & | \\ a_1 & a_2 & \cdots & a_n\\ | & | & & | \end{bmatrix} = \begin{bmatrix} y^Ta_1 & y^Ta_2 & \cdots & y^Ta_n \end{bmatrix} \end{align*} $$

By assumption we have \(y^T A \geq 0^T\). This implies that \(y^T a_i \geq 0\) for all \(i\). Now let

$$ \begin{align*} c = \lambda_1a_1 + \lambda_2a_2 + \cdots + \lambda_na_n \end{align*} $$

be any vector in the cone generated by \(a_1,\dots,a_n\), where \(\lambda_1,\dots,\lambda_n \geq 0\). Then

$$ \begin{align*} y^Tc &= y^T(\lambda_1a_1 + \lambda_2a_2 + \cdots + \lambda_na_n)\\ &= \lambda_1y^Ta_1 + \lambda_2y^Ta_2 + \cdots + \lambda_ny^Ta_n. \end{align*} $$

Since \(\lambda_i \geq 0\) and \(y^Ta_i \geq 0\) for all \(i\), each term on the right-hand side is non-negative. Therefore

$$ \begin{align*} y^Tc \geq 0. \end{align*} $$

Since \(c\) was an arbitrary element of the cone, every vector in the cone satisfies \(y^Tc \geq 0\). This tells us that the cone lies in the halfspace

$$ \begin{align*} y^Tx \geq 0 \end{align*} $$

However \(b\) lies in the opposite halfspace. Therefore, \(H\) separates \(b\) from the cone.

References