Mehmet Emre Tiryaki
Back to Notes

Farkas and Gordan Theorems

Farkas' Theorem

Given A∈Rm×nA \in \mathbb{R}^{m \times n} and b∈Rmb \in \mathbb{R}^m, exactly one of the following holds:

  1. there is x∈Rnx \in \mathbb{R}^n with Ax=bAx = b, x≥0⃗x \ge \vec{0},
  2. there is y∈Rmy \in \mathbb{R}^m with bTy>0b^T y > 0, ATy≤0⃗A^T y \le \vec{0}.

Proof Consider the LP and its dual,

(LP)min⁡  0⃗Txs.t.Ax=b,  x≥0⃗(DP)max⁡  bTys.t.ATy≤0⃗(LP) \quad \min \; \vec{0}^T x \quad \text{s.t.} \quad Ax = b, \; x \ge \vec{0} \qquad \qquad (DP) \quad \max \; b^T y \quad \text{s.t.} \quad A^T y \le \vec{0}
  • 1 true implies 2 false LP is feasible with objective value 0, so by weak duality every dual feasible yy has bTy≤0b^T y \le 0.
  • 2 false implies 1 true y=0⃗y = \vec{0} is dual feasible with value 0, and since 2 is false no feasible yy does better, so DP has optimal value 0. By strong duality LP has an optimal solution, in particular it is feasible.

Gordan's Theorem

Given A∈Rm×nA \in \mathbb{R}^{m \times n}, exactly one of the following holds:

  1. there is x∈Rnx \in \mathbb{R}^n with Ax=0⃗Ax = \vec{0}, x≥0⃗x \ge \vec{0}, x≠0⃗x \neq \vec{0},
  2. there is y∈Rmy \in \mathbb{R}^m with ATy<0⃗A^T y < \vec{0}.

Proof 2 holds iff there are y∈Rmy \in \mathbb{R}^m, ε>0\varepsilon > 0 with ATy+ε1⃗≤0⃗A^T y + \varepsilon \vec{1} \le \vec{0}, i.e. iff there is (y,ε)∈Rm+1(y, \varepsilon) \in \mathbb{R}^{m+1} with

[0⃗1]T[yε]>0,[AT1⃗][yε]≤0⃗\begin{bmatrix} \vec{0} \\ 1 \end{bmatrix}^T \begin{bmatrix} y \\ \varepsilon \end{bmatrix} > 0, \qquad \begin{bmatrix} A^T & \vec{1} \end{bmatrix} \begin{bmatrix} y \\ \varepsilon \end{bmatrix} \le \vec{0}

This is the second alternative of Farkas for the matrix [A1⃗T]\begin{bmatrix} A \\ \vec{1}^T \end{bmatrix} and right-hand side (0⃗,1)(\vec{0}, 1), so it holds iff there is no xx with

[A1⃗T]x=[0⃗1],x≥0⃗\begin{bmatrix} A \\ \vec{1}^T \end{bmatrix} x = \begin{bmatrix} \vec{0} \\ 1 \end{bmatrix}, \qquad x \ge \vec{0}

i.e. no x≥0⃗x \ge \vec{0} with Ax=0⃗Ax = \vec{0} whose coordinates sum to 1. The system is homogeneous, so any x≥0⃗x \ge \vec{0}, x≠0⃗x \neq \vec{0} with Ax=0⃗Ax = \vec{0} can be scaled by 1/∑ixi>01 / \sum_i x_i > 0 to sum to 1. So this is the same as no x≥0⃗x \ge \vec{0}, x≠0⃗x \neq \vec{0} with Ax=0⃗Ax = \vec{0}, i.e. 1 is false.