1-farkas_lemma.Rmd

# Farkas' Lemma

A well-known result in linear algebra states that
a system of linear equations \(\mm{A}\vec{x} = \vec{b}\),
where \(\mm{A} \in \RR^{m\times n},\) \(\vec{b}\in \RR^m,\)
and 
\(\vec{x} = \begin{bmatrix} x_1\\ \vdots \\ x_n\end{bmatrix}\) is 
a tuple of variables, has no solution
if and only if there exists \(\vec{y} \in \RR^m\) such
that \(\vec{y}^\T\mm{A} = \vec{0}\)
and \(\vec{y}^\T \vec{b} \neq 0\).


It is easily seen that if such a \(\vec{y}\) exists, then the system
\(\mm{A}\vec{x} = \vec{b}\) cannot have a solution. (Simply
multiply both sides of \(\mm{A}\vec{x} = \vec{b}\) on the left by
\(\vec{y}^\T\).)  However, proving the converse requires 
a bit of work. A standard elementary proof involves using 
Gauss-Jordan elimination to reduce the original system to an equivalent
system \(\mm{Q}\vec{x} = \vec{d}\) such that \(\mm{Q}\)
has a row of zero, say in row \(i\), with \(\vec{d}_i \neq 0\).
The process can be captured by a square matrix \(\mm{M}\) satisfying
\(\mm{M}\mm{A} = \mm{Q}\).
We can then take \(\vec{y}^\T\) to be the \(i\)th row
of \(\mm{M}\).


An analogous result holds for systems of linear inequalities.
The following result is one of the many variants
of a result known as the **Farkas' Lemma**:

```{theorem, label="farkas"}
With \(\mm{A}\), \(\vec{x}\), and \(\vec{b}\) as above,
the system \(\mm{A}\vec{x} \geq \vec{b}\) has no solution
if and only if there exists \(\vec{y} \in \RR^m\) such that
\[\vec{y} \geq \vec{0},~\vec{y}^\T \mm{A} = \vec{0},~
\vec{y}^\T\vec{b} \gt 0.\]
```


In other words, the system \(\mm{A}\vec{x} \geq \vec{b}\)
has no solution if and only if one can infer the inequality \(0 \geq \gamma\) 
for some \(\gamma \gt 0\) by taking a nonnegative linear combination of the
inequalities.


This result essentially says that there is always 
a certificate (the \(m\)-tuple \(\vec{y}\) with the prescribed properties)
for the infeasibility of the system \(\mm{A}\vec{x} \geq \vec{b}\).
This allows third parties to verify
the claim of infeasibility without having to solve the system from scratch.

```{example, echo=TRUE}

For the system
\begin{align*}
2x - y + z & \geq 2 \\
-x + y - z & \geq 0 \\
   - y + z & \geq 0,
\end{align*}
adding two times the second inequality and
the third inequality to the first inequality gives
\(0 \geq 2\).  Hence, \(\vec{y} = \begin{bmatrix} 1\\ 2 \\ 1\end{bmatrix}\)
is a certificate of infeasibility for this example.
```


We now give a proof of Theorem \@ref(thm:farkas).
It is easy to see that if such a \(\vec{y}\) exists, then
the system \(\mm{A}\vec{x} \geq \vec{b}\) has no solution.


Conversely, suppose that the system \(\mm{A}\vec{x} \geq \vec{b}\) 
has no solution.
It suffices to show that we can infer
the inequality \(0 \geq \alpha\) for some postive \(\alpha\) by
taking nonnegative linear combination of the inequalities
in the system \(\mm{A}\vec{x} \geq \vec{b}\).
If the system already contains an inequality \(0 \geq \alpha\)
for some positive \(\alpha\), then
we are done.  Otherwise,
we show by induction on \(n\)
that we can infer such an inequality.


 **Base case**:  The system \(\mm{A}\vec{x} \geq \vec{b}\)
 has only one variable. 


 For the system to have no solution, there must exist
 two inequalites \(ax_1 \geq t\) and \(-a'x_1 \geq t'\)
 such that \(a, a' \gt 0\) and \(\frac{t}{a} \gt \frac{-t'}{a'}\).
 Adding \(\frac{1}{a}\) times the inequality
 \(ax_1 \geq t\) and \(\frac{1}{a'}\) times the inequality \(-a'x_1 \geq t'\)
 gives the inequality \(0 \geq \frac{t}{a} + \frac{t'}{a'}\) with a positive
 right-hand side.  This establishes the base case.


 **Induction hypothesis**: Let \(n \geq 2\) be an integer.
 Assume that given any system of linear inequalities 
\(\mm{A}'\vec{x} \geq \vec{b}'\)
 in \(n-1\) variables having no solution,
 one can infer the inequality \(0 \geq \alpha'\) for some positive
 \(\alpha'\) by taking a nonnegative linear combination of the inequalities
 in the system \(\mm{P}\vec{x} \geq \vec{q}\).


 Apply Fourier-Motzkin elimination to eliminate \(x_n\)
 from \(\mm{A}\vec{x} \geq \vec{b}\) to obtain
 the system 
 \(\mm{P}\vec{x} \geq \vec{q}\).
 As \(\mm{A}\vec{x}\geq \vec{b}\) has no solution, 
 \(\mm{P}\vec{x} \geq \vec{q}\)
 also has no solution.


 By the induction hypothesis,
 one can infer the inequality \(0 \geq \alpha\) for some positive
 \(\alpha\) by taking a nonnegative linear combination of the inequalities
 in \(\mm{P}\vec{x} \geq \vec{q}\).
 However, each inequality 
 in \(\mm{P}\vec{x} \geq \vec{q}\)
 can be obtained from a nonnegative linear combination
 of the inequalites in \(\mm{A}\vec{x} \geq \vec{b}\).
 Hence, one can infer the inequality \(0 \geq \alpha\) 
 by taking a nonnegative linear combination of nonnegative linear
 cominbations of the inequalities in \(\mm{A}\vec{x}\geq \vec{b}\).
 Since a nonnegative linear combination of nonnegative linear
 cominbations of the inequalities in \(\mm{A}\vec{x}\geq \vec{b}\)
 is simply a nonnegative linear combination of the 
  inequalities in \(\mm{A}\vec{x}\geq \vec{b}\), the result follows.

\(\qed\)



**Remark.** Notice that in the proof above,
if \(\mm{A}\) and \(\vec{b}\)
have only rational entries, then we can take \(\vec{y}\) to have
only rational entries as well.

```{corollary, label="farkas-std-eq"}
    Let \(\mm{A} \in \RR^{m\times n}\) and
    let \(\vec{b} \in \RR^m\).
    The system
    \begin{align*}
    \mm{A}\vec{x} & = \vec{b} \\
    \vec{x} & \geq \vec{0}
    \end{align*}
    has no solution if and only if there
    exists \(\vec{y} \in \RR^m\) such
    that
    \(\vec{y}^\T \mm{A} \leq \vec{0}\)
    and \(\vec{y}^\T\vec{b} \gt 0\).
    Furthermore, if \(\mm{A}\) and \(\vec{b}\) are rational,
    \(\vec{y}\) can be taken to be rational.

```

*Proof.*
One can easily check that if such a \(\vec{y}\) exists, there
is no soluton.


We now prove the converse.
The system
\begin{align*}
\mm{A}\vec{x} & = \vec{b} \\
\vec{x} & \geq \vec{0}
\end{align*}
can be rewritten as
\begin{align*}
\begin{bmatrix}
\mm{A} \\
-\mm{A} \\
\mm{I}
\end{bmatrix}\vec{x} \geq 
\begin{bmatrix}
\vec{b} \\
-\vec{b} \\
\vec{0}
\end{bmatrix}
\end{align*}
where \(\mm{I}\) is the \(n\times n\) identity matrix.
Then by Theorem \@ref(thm:farkas),
if this system has no solution, then there exist
\(\vec{u}, \vec{v} \in \mathbb{R}^m\),
\(\vec{w} \in \mathbb{R}^n\) satisfying

\[\vec{u},\vec{v},\vec{w} \geq \vec{0},~
\mathbf{u}^\T\mm{A} -
\mathbf{v}^\T\mm{A} +
\mathbf{w} = \mathbf{0},~
\mathbf{u}^\T\mathbf{b} -
\mathbf{v}^\T\mathbf{b} \gt 0.
\]
The result now follows from
setting \(\vec{y} = \vec{u} - \vec{v}\).

Rationality follows from the remark after the proof of
Theorem \@ref(thm:farkas).

\(\qed\)