Certifying infeasibility

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

It is easily seen that if such a \(\mathbf{y}\) exists, then the system \(\mathbf{A}\mathbf{x} = \mathbf{b}\) cannot have a solution. (Simply multiply both sides of \(\mathbf{A}\mathbf{x} = \mathbf{b}\) on the left by \(\mathbf{y}^\mathsf{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 \(\mathbf{R}\mathbf{x} = \mathbf{d}\) such that \(\mathbf{R}\) has a row of zero, say in row \(i\), with \(d_i \neq 0\). The process can be captured by a square matrix \(\mathbf{M}\) satisfying \(\mathbf{M}\mathbf{A} = \mathbf{R}\). We can then take \(\mathbf{y}^\mathsf{T}\) to be the \(i\)th row of \(\mathbf{M}\).

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

Theorem 2.1. With \(\mathbf{A}\), \(\mathbf{x}\), and \(\mathbf{b}\) as above, the system \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) has no solution if and only if there exists \(\mathbf{y} \in \mathbb{R}^m\) such that \[\mathbf{y} \geq \mathbf{0},~\mathbf{y}^\mathsf{T} \mathbf{A} = \mathbf{0},~ \mathbf{y}^\mathsf{T}\mathbf{b} \gt 0.\]

In other words, the system \(\mathbf{A}\mathbf{x} \geq \mathbf{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 \(\mathbf{y}\) with the prescribed properties) for the infeasibility of the system \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\). This allows third parties to verify the claim of infeasibility without having to solve the system from scratch.

We now give a proof of the lemma above.

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

Corollary 2.2. Let \(\mathbf{A} \in \mathbb{R}^{m\times n}\) and let \(\mathbf{b} \in \mathbb{R}^m\). Prove that \begin{eqnarray*} \mathbf{A}\mathbf{x} = \mathbf{b} \\ \mathbf{x} \geq \mathbf{0} \end{eqnarray*} has no solution if and only if there exists \(\mathbf{y} \in \mathbb{R}^m\) such that \(\mathbf{y}^\mathsf{T} \mathbf{A} \geq \mathbf{0}\) and \(\mathbf{y}^\mathsf{T}\mathbf{b} \lt 0\). Furthermore, if \(\mathbf{A}\) and \(\mathbf{b}\) are rational, \(\mathbf{y}\) can be taken to be rational.

Worked examples

1. You are given that the following system has no solution. \begin{eqnarray*} x_1 + x_2 + 2x_3& \geq & 1 \\ -x_1 + x_2 + x_3 & \geq & 2 \\ x_1-x_2 + x_3 & \geq & 1 \\ -x_2 - 3x_3 & \geq & 0. \end{eqnarray*} Obtain a certificate of infeasibility for the system.

   The system can be written as \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) with \(\mathbf{A} = \begin{bmatrix} 1 & 1 & 2 \\ -1 & 1 & 1 \\ 1 & -1 & 1 \\ 0 & -1 & -3 \end{bmatrix}\) and \(\mathbf{b} = \begin{bmatrix} 1 \\ 2 \\ 1 \\ 0\end{bmatrix}\). So we need to find \(\mathbf{y} \geq 0\) such that \(\mathbf{y}^\mathsf{T} \mathbf{A} = \mathbf{0}\) and \(\mathbf{y}^\mathsf{T} \mathbf{b} \gt 0\). As the system of equations \(\mathbf{y}^\mathsf{T} \mathbf{A} = \mathbf{0}\) is homogeneous, we could without loss of generality fix \(\mathbf{y}^\mathsf{T} \mathbf{b} = 1\), thus leading to the system \begin{eqnarray*} \mathbf{y}^\mathsf{T}\mathbf{A} = \mathbf{0} \\ \mathbf{y}^\mathsf{T}\mathbf{b} = 1 \\ \mathbf{y} \geq \mathbf{0} \end{eqnarray*} that we could attempt to solve directly. However, it is possible to obtain a \(\mathbf{y}\) using the Fourier-Motzkin Elimination Method.

   Let us first label the inequalities: \begin{align*} x_1 + x_2 + 2x_3& \geq 1~~~~~(1) \\ -x_1 + x_2 + x_3 & \geq 2~~~~~(2) \\ x_1-x_2 + x_3 & \geq 1~~~~~(3) \\ -x_2 - 3x_3 & \geq 0.~~~~(4) \end{align*} Eliminating \(x_1\) gives: \begin{align*} -x_2 - 3x_3 & \geq 0~~~~~(4) \\ 2x_2 + 3x_3& \geq 3~~~~~(5) \\ 2x_3 & \geq 3.~~~~(6) \\ \end{align*} Note that \((5)\) is obtained from \((1) + (2)\) and \((6)\) is obtained from \( (2) + (3)\).

   Multiplying \((5)\) by \(\frac{1}{2}\) gives \begin{align*} -x_2 - 3x_3 & \geq 0~~~~~~(4) \\ x_2 + \frac{3}{2}x_3& \geq \frac{3}{2}~~~~(7) \\ 2x_3 & \geq 3.~~~~~(6) \\ \end{align*} Eliminating \(x_2\) gives: \begin{align*} 2x_3 & \geq 3~~~~~~~(6) \\ - \frac{3}{2} x_3 & \geq \frac{3}{2}~~~~~(8) \end{align*} where \((8)\) is obtained from \((4) + (7)\).

   Now \(\frac{3}{4}\times (6) + (8)\) gives \(0 \geq \frac{15}{4}\), a contradiction.

   To obtain a certificate of infeasibility, we trace back the computations. Note that \(\frac{3}{4} (6) + (8)\) is given by \(\frac{3}{4} ((2)+(3)) + (4)+ (7)\), which in turn is given by \(\frac{3}{4} ((2)+(3)) + (4)+ \frac{1}{2}(5)\), which in turn is given by \(\frac{3}{4} ((2)+(3)) + (4)+ \frac{1}{2}((1) + (2))\).

   Thus, we can obtain \(0 \geq \frac{15}{4}\) from the nonnegative linear combination of the original inequalities as follows: \(\frac{1}{2} (1) + \frac{5}{4} (2) + \frac{3}{4} (3) + (4)\).

   Therefore, \(\mathbf{y} = \begin{bmatrix} \frac{1}{2} \\ \frac{5}{4} \\ \frac{3}{4} \\ 1\end{bmatrix}\) is a certificate of infeasibility.

   (Check that \(\mathbf{y}^\mathsf{T}\mathbf{A} = \mathbf{0}\) and \(\mathbf{y}^\mathsf{T} \mathbf{b} \gt 0\).)

2. Prove Corollary 2.2.

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

   We now prove the converse. The system \begin{eqnarray*} \mathbf{A}\mathbf{x} = \mathbf{b} \\ \mathbf{x} \geq \mathbf{0} \end{eqnarray*} can be rewritten as \begin{eqnarray*} \begin{bmatrix} \mathbf{A} \\ -\mathbf{A} \\ \mathbf{I} \end{bmatrix}\mathbf{x} \geq \begin{bmatrix} \mathbf{b} \\ -\mathbf{b} \\ \mathbf{0} \end{bmatrix} \end{eqnarray*} where \(\mathbf{I}\) is the \(n\times n\) identity matrix. Then by Farkas' Lemma, if this system has no solution, then there exist \(\mathbf{u}, \mathbf{v} \in \mathbb{R}^m\), \( \mathbf{w} \in \mathbb{R}^n\) satisfying \[\mathbf{u},\mathbf{v},\mathbf{w} \geq \mathbf{0},~ \mathbf{u}^\mathsf{T}\mathbf{A} - \mathbf{v}^\mathsf{T}\mathbf{A} + \mathbf{w} = \mathbf{0},~ \mathbf{u}^\mathsf{T}\mathbf{b} - \mathbf{v}^\mathsf{T}\mathbf{b} \gt 0. \] The result now follows from setting \(\mathbf{y} = \mathbf{v} - \mathbf{u}\).

   Rationality follows from the remark after the proof of the lemma.

3. Let \(\mathbf{A} \in \mathbb{R}^{m\times n}\) and let \(\mathbf{b} \in \mathbb{R}^m\). Prove that \begin{align*} \mathbf{A}\mathbf{x} & \geq \mathbf{b} \\ \mathbf{x} & \geq \mathbf{0} \end{align*} has no solution if and only if there exists \(\mathbf{y} \in \mathbb{R}^m\) such that \(\mathbf{y} \geq \mathbf{0},~\mathbf{y}^\mathsf{T} \mathbf{A} \leq \mathbf{0}\) and \(\mathbf{y}^\mathsf{T}\mathbf{b} \gt 0\).

   The system is equivalent to \begin{align*} \begin{bmatrix} \mathbf{A} \\ \mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{x} \end{bmatrix} & \geq \begin{bmatrix} \mathbf{b} \\ \mathbf{0} \end{bmatrix}. \end{align*} By Theorem 2.1, this system has no solution if and only if there exists \(\begin{bmatrix} \mathbf{u} \\ \mathbf{v} \end{bmatrix}\geq \mathbf{0}\) such that \(\begin{bmatrix} \mathbf{u}^\mathsf{T} & \mathbf{v}^\mathsf{T}\end{bmatrix} \begin{bmatrix} \mathbf{A} \\ \mathbf{I} \end{bmatrix} = \mathbf{0}\) and \(\mathbf{u}^\mathsf{T}\mathbf{b} \gt 0\). We can rewrite \(\begin{bmatrix} \mathbf{A} \\ \mathbf{I} \end{bmatrix} = \mathbf{0}\) as \(\mathbf{u}^\mathsf{T}\mathbf{A} + \mathbf{v}^\mathsf{T} = \mathbf{0}\). Since \(\mathbf{v} \geq \mathbf{0}\), the result now follows from setting \(\mathbf{y} = \mathbf{u}\).