Lecture from 27.11.2024 | Video: Videos ETHZ

We often need to prove not only that solutions exist but also that they don’t exist. Proving non-existence requires a “certificate of inexistence”—an object whose existence implies the nonexistence of a solution to the original problem.

Certificates for Unsolvable Linear Systems

Let’s start with systems of linear equations: $A\mathbf{x}=\mathbf{b}$, where $A\in {\mathbb{R}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{R}}^m$. How can we prove that no solution $\mathbf{x}\in {\mathbb{R}}^n$ exists?

Theorem: Certificate of Inexistence for Linear Systems

The system $A\mathbf{x}=\mathbf{b}$ has no solution if and only if there exists a vector $\mathbf{y}\in {\mathbb{R}}^m$ such that ${\mathbf{y}}^{T}A=0$ and ${\mathbf{y}}^T\mathbf{b}\ne 0$.

Let’s break down the proof of this theorem.

Proof:

1. ($\Leftarrow$) Certificate implies no solution (Proof by contradiction):

• Assume a solution exists: Suppose a vector $\mathbf{y}$ exists such that ${\mathbf{y}}^{T}A=0$ and ${\mathbf{y}}^T\mathbf{b}\ne 0$. Let’s assume, for the sake of contradiction, that there’s also a solution $\mathbf{x}$ to $A\mathbf{x}=\mathbf{b}$.

• Reaching a contradiction: If $A\mathbf{x}=\mathbf{b}$, we can multiply both sides by ${\mathbf{y}}^T$ to get ${\mathbf{y}}^{T}A\mathbf{x}={\mathbf{y}}^T\mathbf{b}$. Since ${\mathbf{y}}^{T}A=0$, this simplifies to $0={\mathbf{y}}^T\mathbf{b}$. But this contradicts our initial assumption that ${\mathbf{y}}^T\mathbf{b}\ne 0$.

• Conclusion: Our assumption that a solution $\mathbf{x}$ exists must be false. The existence of $\mathbf{y}$ guarantees that $A\mathbf{x}=\mathbf{b}$ has no solution.

2. ($\Rightarrow$) No solution implies the existence of a certificate:

• Fundamental Subspaces: Remember that the four fundamental subspaces of a matrix $A$ (column space of $A$, nullspace of $A$, column space of $A^T$, nullspace of $A^T$) have specific orthogonality relationships: The column space of $A$ is orthogonal to the nullspace of $A^T$ ($C(A)\perp N(A^T)$), and the column space of $A^T$ is orthogonal to the nullspace of $A$ ($C(A^T)\perp N(A)$).

• No solution means b is not in the column space: If there’s no solution to $A\mathbf{x}=\mathbf{b}$, it means the vector $\mathbf{b}$ doesn’t lie in the column space of $A$ (denoted as $C(A)$).

• Projection onto the orthogonal complement: This tells us that the projection of $\mathbf{b}$ onto the orthogonal complement of $C(A)$, which is $N(A^T)$, is not the zero vector. Let’s call this non-zero projection $\mathbf{y}$.

• Satisfying the conditions: Because $\mathbf{y}$ is in the nullspace of $A^T$ ($N(A^T)$), we have $A^T\mathbf{y}=0$, which means ${\mathbf{y}}^{T}A=0^T=0$. Furthermore, since $\mathbf{y}$ is a non-zero projection of $\mathbf{b}$, we have ${\mathbf{y}}^T\mathbf{b}=\Vert \mathbf{y}{\Vert }^2>0$. This vector $\mathbf{y}$ is our certificate of inexistence.

The vector $\mathbf{y}$ acts as proof that the system is unsolvable.

Moving from Equality to Inequality Constraints

Let’s generalize to systems of linear inequalities: $A\mathbf{x}\le \mathbf{b}$, with $A\in {\mathbb{Q}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{Q}}^m$. We use rational numbers to avoid numerical issues. How do we determine if a solution $\mathbf{x}\in {\mathbb{R}}^n$ exists, and if not, how do we certify it?

Challenges with Inequalities

Can we directly extend the certificate idea from equalities to inequalities? If we have ${\mathbf{y}}^{T}A=0$ and multiply $A\mathbf{x}\le \mathbf{b}$ by ${\mathbf{y}}^T$, we get: ${\mathbf{y}}^{T}A\mathbf{x}\le {\mathbf{y}}^T\mathbf{b}$ The problem is that if $\mathbf{y}$ has both positive and negative entries, multiplying the inequality $A\mathbf{x}\le \mathbf{b}$ by ${\mathbf{y}}^T$ might flip some inequality signs. This prevents a clear contradiction.

Non-negative Certificates

The solution: require $\mathbf{y}\ge 0$. This ensures that multiplying $A\mathbf{x}\le \mathbf{b}$ by ${\mathbf{y}}^T$ preserves the inequality directions. If we find a $\mathbf{y}\ge 0$ such that ${\mathbf{y}}^{T}A=0$ and ${\mathbf{y}}^T\mathbf{b}<0$, we have a certificate.

Why ${\mathbf{y}}^T\mathbf{b}<0$?

If such a $\mathbf{y}$ exists and we assume a solution $\mathbf{x}$ to $A\mathbf{x}\le \mathbf{b}$ exists, we get: $0={\mathbf{y}}^{T}A\mathbf{x}\le {\mathbf{y}}^T\mathbf{b}<0$ This is a contradiction ($0<0$), proving that no solution $\mathbf{x}$ can exist.

Theorem: Farkas Lemma (Variant)

The system $A\mathbf{x}\le \mathbf{b}$ has no solution if and only if there exists a vector $\mathbf{y}\in {\mathbb{R}}^m$ such that $\mathbf{y}\ge 0$, ${\mathbf{y}}^{T}A=0$, and ${\mathbf{y}}^T\mathbf{b}<0$.

Proof (Partial):

1. ($\Leftarrow$) Certificate implies no solution (Proof by contradiction):

• Assume a certificate $\mathbf{y}$ exists, and assume there’s a solution $\mathbf{x}$ to $A\mathbf{x}\le \mathbf{b}$.

• Multiplying $A\mathbf{x}\le \mathbf{b}$ by the non-negative ${\mathbf{y}}^T$ gives ${\mathbf{y}}^{T}A\mathbf{x}\le {\mathbf{y}}^T\mathbf{b}$. Since ${\mathbf{y}}^{T}A=0$, we have $0\le {\mathbf{y}}^T\mathbf{b}$. But we also know ${\mathbf{y}}^T\mathbf{b}<0$, leading to the contradiction $0<0$.

• Therefore, no solution $\mathbf{x}$ can exist.

(The full proof of Farkas Lemma, including the other direction, will be covered later.)

1D Case Example

Consider these inequalities:

1. $3x\le 2$
2. $x\le 1$
3. $-2x\le -1$
4. $-5x\le -4$

Finding a Contradiction

Adding inequalities (1) and (4) gives $-2x\le -2$, implying $x\ge 1$. Combining this with $x\le \frac{2}{3}$ from inequality (1) leads to a contradiction.

Formalizing the Certificate

Multiply inequality (1) by 5 and inequality (4) by 3:

• $15x\le 10$
• $-15x\le -12$

Adding them yields $0\le -2$, a contradiction. The certificate is $\mathbf{y}=[5,0,0,3]$. Let’s verify:

• ${\mathbf{y}}^{T}A=[5,0,0,3]\left[\begin{array}{c}3\\ 1\\ -2\\ -5\end{array}\right]=15-15=0$
• ${\mathbf{y}}^T\mathbf{b}=[5,0,0,3]\left[\begin{array}{c}2\\ 1\\ -1\\ -4\end{array}\right]=10-12=-2<0$

This $\mathbf{y}$ satisfies all conditions ($\mathbf{y}\ge 0$, ${\mathbf{y}}^{T}A=0$, ${\mathbf{y}}^T\mathbf{b}<0$).

Important Note on the Certificate Vector

Other $\mathbf{y}$ vectors can work as certificates, as long as they satisfy the required conditions. For instance, $\mathbf{y}=[\frac{1}{3},0,0,\frac{1}{5}]$ would also be a valid certificate in this example.

This example shows how a linear combination of inequalities (represented by $\mathbf{y}$) reveals a contradiction, proving the system is unsolvable.

What Happens in Higher Dimensions?

In higher dimensions ($n\ge 2$), $A\mathbf{x}\le \mathbf{b}$ describes a polyhedron, a region bounded by hyperplanes.

The Challenge: How do we determine if this polyhedron is empty (no solution)?

The Approach: Project the polyhedron onto lower-dimensional spaces. If the original polyhedron is empty, its projection must also be empty.

Projection and its Implications:

If $P=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}\le \mathbf{b}\}$ and we project it onto a subspace, the projection $proj(P)$ is also a polyhedron. Crucially:

• $P$ is nonempty if and only if $proj(P)$ is nonempty. If the projection is empty, the original polyhedron is empty, and the system $A\mathbf{x}\le \mathbf{b}$ has no solution.

The Projection Process: Projection involves eliminating variables, eventually reducing the problem to one dimension. We’ll explore this process in detail later.

Projections of Sets and the Farkas Lemma: A Guided Exploration

Our goal is to develop a method for determining if a system of linear inequalities has a solution. We’ll use the concept of projection to simplify this problem.

Projection of a Set of Inequalities

Definition: Rational Polyhedra

A rational polyhedron $P$ is defined by a finite set of linear inequalities with rational coefficients:

$P=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}\le \mathbf{b}\}$

where $A\in {\mathbb{Q}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{Q}}^m$. Rational coefficients ensure computational procedures terminate. A polyhedron represents the feasible region of the inequalities. Why use rationals? This avoids complexities with irrational numbers and ensures that algorithms based on these concepts will always finish.

Projection onto a Subspace

To project $P$ onto a lower-dimensional subspace defined by a subset of variables $S=\{1,\dots ,s\}\subseteq \{1,\dots ,n\}$, we use the following definition:

$pro{j}_S(P):=\{{\mathbf{x}}_S\in {\mathbb{R}}^s|\exists \mathbf{y}\in {\mathbb{R}}^{n-s}\text{ such that }\left[\begin{array}{c}{\mathbf{x}}_S\\ \mathbf{y}\end{array}\right]\in P\}$

${\mathbf{x}}_S$ contains components of $\mathbf{x}$ with indices in $S$, and $\mathbf{y}$ represents the remaining variables. This projection extracts all possible values of variables in $S$ consistent with the original inequalities. What does this mean? Imagine shining a light onto the polyhedron from a specific direction and observing the shadow cast onto a lower-dimensional surface. The shadow represents the projection. We are checking which coordinates in the lower dimensional space are consistent with at least one solution in the higher dimensional space.

The Critical Equivalence

The key property of projection is:

$P\ne \varnothing ⟺pro{j}_S(P)\ne \varnothing$

A non-empty $P$ (a solution exists) is equivalent to a non-empty projection $pro{j}_S(P)$. This is fundamental to our strategy. If the “shadow” is empty, the object casting the shadow must also be empty.

Why is this important?

• Dimensionality Reduction: If $pro{j}_S(P)$ is empty for any $S$, then $P$ is empty, meaning no solution exists. This lets us analyze simpler, lower-dimensional problems. If we can show that the shadow is empty, we know the original object must be empty too.
• Algorithmic Implications: This suggests an algorithm: project onto progressively lower dimensions until we reach a one-dimensional problem, which is easy to solve. Keep projecting until the problem becomes simple enough to solve directly.

Open Question: How do we describe $pro{j}_S(P)$ with a finite set of linear inequalities? This will allow us to repeat the projection process. We’ll answer this next.

The One-Dimensional Case: A Foundation

Consider a one-dimensional polyhedron $P$:

$P=\{x\in \mathbb{R}|\mathbf{a}x\le \mathbf{b}\}$

where $\mathbf{a}\in {\mathbb{Q}}^m$ ($a_i\ne 0$ for all $i$) and $\mathbf{b}\in {\mathbb{Q}}^m$. Each inequality constrains $x$.

Explicit Representation

Rewrite each inequality $a_{i}x\le b_i$ as:

• $x\le \frac{b_i}{a_i}$ if $a_i>0$
• $x\ge \frac{b_i}{a_i}$ if $a_i<0$

Thus:

$P=\left\{x\in \mathbb{R}|x\le \frac{b_i}{a_i}\text{ if }{a}_i>0,x\ge \frac{b_i}{a_i}\text{ if }{a}_i<0\right\}$

This represents an interval. In other words, $x$ must lie within certain bounds.

Finding the Bounds

Define:

• $u=\min \left\{\frac{b_i}{a_i}|a_i>0\right\}$ (minimum upper bound) What is the smallest upper bound placed on $x$?
• $l=\max \left\{\frac{b_i}{a_i}|a_i<0\right\}$ (maximum lower bound) What is the largest lower bound placed on $x$?

Then:

$P=\{x\in \mathbb{R}|l\le x\le u\}$

Condition for Non-emptiness

$P$ is non-empty (has a solution) if and only if:

$P\ne \varnothing ⟺l\le u$ The lower bound must be less than or equal to the upper bound for a solution to exist. If the lower bound is greater than the upper bound, there is no value of $x$ that can satisfy all the constraints.

Equivalence with a Linear Combination

The condition $l\le u$ is equivalent to:

${\mathbf{y}}^T\mathbf{b}\ge 0\forall \mathbf{y}\ge 0\text{ such that }{\mathbf{y}}^T\mathbf{a}=0$

Let’s illustrate with examples.

Example 1: Feasible System

• $x\le 3$
• $-x\le -1$ (or $x\ge 1$)

Here, $\mathbf{a}=\left[\begin{array}{c}1\\ -1\end{array}\right]$, $\mathbf{b}=\left[\begin{array}{c}3\\ -1\end{array}\right]$, $u=3$, $l=1$. Since $l\le u$, the system is feasible ($x=2$ is a solution). We can find a value of $x$ that satisfies both inequalities.

Let $\mathbf{y}=\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]$. ${\mathbf{y}}^T\mathbf{a}=0$ means $y_1-y_2=0$, so $y_1=y_2\ge 0$. Then ${\mathbf{y}}^T\mathbf{b}=3y_1-y_2=2y_1\ge 0$. The condition holds.

Example 2: Infeasible System

• $x\le 1$
• $-2x\le -3$ (or $x\ge 1.5$)

Here, $\mathbf{a}=\left[\begin{array}{c}1\\ -2\end{array}\right]$, $\mathbf{b}=\left[\begin{array}{c}1\\ -3\end{array}\right]$, $u=1$, $l=1.5$. Since $l>u$, there’s no solution. The lower bound is greater than the upper bound. There is no value of $x$ that can satisfy both inequalities.

If $y_1=2y_2\ge 0$ (from ${\mathbf{y}}^T\mathbf{a}=0$), then ${\mathbf{y}}^T\mathbf{b}=y_1-3y_2=-y_2$. For $\mathbf{y}=\left[\begin{array}{c}2\\ 1\end{array}\right]$, we have ${\mathbf{y}}^T\mathbf{a}=0$, but ${\mathbf{y}}^T\mathbf{b}=-1<0$. The condition is violated. We found a non-negative $\mathbf{y}$ such that ${\mathbf{y}}^T\mathbf{a}=0$ and ${\mathbf{y}}^T\mathbf{b}<0$.

Important

A $\mathbf{y}\ge 0$ with ${\mathbf{y}}^T\mathbf{a}=0$ and ${\mathbf{y}}^T\mathbf{b}<0$ certifies infeasibility. If no such $\mathbf{y}$ exists, the system is feasible. This is core to Farkas’ Lemma. The existence of this special vector $\mathbf{y}$ provides a concrete way to prove that the system has no solution. This is a powerful tool for reasoning about the solvability of systems of inequalities.

Elimination of One Variable: Projecting to a Lower Dimension

We now have a method for analyzing 1D systems. But how do we reduce higher-dimensional problems to 1D? We’ll use an algorithm to eliminate one variable at a time through projection.

Let $P=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}\le \mathbf{b}\}$. We’ll eliminate $x_n$.

A less confusing explanation

Algorithm

1. Partitioning: Group inequalities based on the sign of $x_n$‘s coefficient ($a_{i,n}$):

   • $M_0=\{i|a_{i,n}=0\}$ (no $x_n$) The inequalities in this set do not involve the variable we are trying to eliminate.
   • $M_{+}=\{i|a_{i,n}>0\}$ (positive coefficient) The inequalities in this set have a positive coefficient for the variable we are trying to eliminate.
   • $M_{-}=\{i|a_{i,n}<0\}$ (negative coefficient) The inequalities in this set have a negative coefficient for the variable we are trying to eliminate.

2. Rewriting and Combining:

   • $M_{+}$: For each $i\in M_{+}$, rewrite as: $x_n\le \frac{b_i}{a_{i,n}}-{\sum }_{j=1}^{n-1}\frac{a_{ij}}{a_{i,n}}{x}_j$. Isolate $x_n$ by dividing by its coefficient. Let $d_i=\frac{b_i}{a_{in}}$ and $f_{ij}=-\frac{a_{ij}}{a_{in}}$
   • $M_0$: For each $k\in M_0$, rewrite as : $0\le b_k-{\sum }_{j=1}^{n-1}{a}_{kj}{x}_j$ Let $d_k=b_k$ and $f_{kj}=-a_{kj}$. This makes the notation consistent with the other inequalities.
   • $M_{-}$: For each $i\in M_{-}$, rewrite as: $x_n\ge \frac{b_i}{a_{i,n}}-{\sum }_{j=1}^{n-1}\frac{a_{ij}}{a_{i,n}}{x}_j$. Isolate $x_n$, remembering to flip the inequality. Let $d_i=\frac{b_i}{a_{in}}$ and $f_{ij}=-\frac{a_{ij}}{a_{in}}$

3. Constructing the Lower-Dimensional Polyhedron:

To eliminate $x_n$, we need to ensure that for any values of the other variables, there exists a value of $x_n$ that satisfies all constraints. This is the core idea behind projection.

For each pair of inequalities $i\in M_{+}$ and $l\in M_{-}$, combine them:

$d_l+{\sum }_{j=1}^{n-1}{f}_{lj}{x}_j\le d_i+{\sum }_{j=1}^{n-1}{f}_{ij}{x}_j$

This ensures that every lower bound on $x_n$ is less than or equal to every upper bound on $x_n$. Importantly, this new inequality does not include $x_n$.

The projected polyhedron $Q$ in ${\mathbb{R}}^{n-1}$ is then:

$Q=\left\{\mathbf{x}\in {\mathbb{R}}^{n-1}|\begin{array}{l}0\le d_k+{\sum }_{j=1}^{n-1}{f}_{kj}{x}_j\forall k\in M_0\\ d_l+{\sum }_{j=1}^{n-1}{f}_{lj}{x}_j\le d_i+{\sum }_{j=1}^{n-1}{f}_{ij}{x}_j\forall i\in M_{+},l\in M_{-}\end{array}\right\}$

We’ve projected onto a lower dimension! Repeat this process to eliminate more variables. We now have a polyhedron described by inequalities in one fewer variable. We can repeat this process until we reach a one-dimensional problem, which we can analyze directly using the methods we discussed earlier.

Example: Projecting from 2D to 1D

Consider the system:

1. Partitioning: $M_0=\varnothing$, $M_{+}=\{1,2\}$, $M_{-}=\{3,4\}$.

2. Rewriting:

   • $M_{+}$: $x_2\le 2-\frac{1}{2}{x}_1$; $x_2\le 1+x_1$
   • $M_{-}$: $x_2\ge 1$; $x_2\ge x_1$

3. Constructing Q: Combine inequalities:

   • $1\le 2-\frac{1}{2}{x}_1⟹x_1\le 2$
   • $x_1\le 2-\frac{1}{2}{x}_1⟹x_1\le \frac{4}{3}$
   • $1\le 1+x_1⟹x_1\ge 0$
   • $x_1\le 1+x_1⟹0\le 1$ (always true)

Therefore, $Q=\{x_1\in \mathbb{R}|0\le x_1\le \frac{4}{3}\}$. $Q$ is non-empty, so the original 2D system is also non-empty.

Example: Empty Set

Let’s modify the system slightly:

Using the same procedure, we get the following inequalities:

$2\le 2-\frac{1}{2}{x}_1⟹x_1\le 0$ $x_1\le 2-\frac{1}{2}{x}_1⟹x_1\le \frac{4}{3}$ $2\le 1+x_1⟹x_1\ge 1$ $0\le 1$

This results in $1\le x_1\le 0$ which has no solution. The projection $Q$ is empty, indicating the original system has no solution.

Theorem 3: The Projection Theorem: Formalizing Projection

This theorem proves that our variable elimination algorithm correctly produces a polyhedron that represents the projection of the original polyhedron. In simpler terms, it confirms that our method of eliminating a variable creates a new, valid system of inequalities that describes the “shadow” of the original feasible region in a lower-dimensional space.

Theorem 3: The Projection Theorem

Let $P=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}\le \mathbf{b}\}$ be a rational polyhedron ($A\in {\mathbb{Q}}^{m\times n}$, $\mathbf{b}\in {\mathbb{Q}}^m$). Let $S=\{1,\dots ,n-1\}$. Let $Q$ be the set obtained by eliminating $x_n$ using our algorithm. Then:

1. $Q$ is a polyhedron.
2. $Q=pro{j}_S(P)$.

This theorem has two important parts:

1. $Q$ is a polyhedron: The result of the elimination process is still a well-defined polyhedron (a region defined by linear inequalities). This ensures we can continue applying the elimination process.
2. $Q=pro{j}_S(P)$: This polyhedron is exactly the projection we want. It represents all possible values of the remaining variables that are consistent with the original system of inequalities. This means that if we find a solution in the projected space ($Q$), we can guarantee there’s a corresponding solution in the original higher-dimensional space ($P$). Conversely, if there’s no solution in $Q$, there can’t be a solution in $P$ either.

Proof

Part 1: $Q$ is a Polyhedron

Our algorithm constructs $Q$ using a finite number of linear inequalities in $n-1$ variables:

• Inequalities from $M_0$ (those not involving $x_n$) are directly included in $Q$: $0\le d_k+{\sum }_{j=1}^{n-1}{f}_{kj}{x}_j\forall k\in M_0$. These inequalities already constrain the remaining variables without needing to consider $x_n$.

• Combining inequalities from $M_{+}$ and $M_{-}$ creates new inequalities in $n-1$ variables: $d_l+{\sum }_{j=1}^{n-1}{f}_{lj}{x}_j\le d_i+{\sum }_{j=1}^{n-1}{f}_{ij}{x}_j\forall i\in M_{+},l\in M_{-}$. This step cleverly encodes the constraints on $x_n$ into constraints on the remaining variables. Essentially, these new inequalities say: “For these values of the other variables, there exists some value of $x_n$ that works.”

Why does combining inequalities eliminate a variable?

Think of it this way: The inequalities in $M_{+}$ give upper bounds on $x_n$, while those in $M_{-}$ give lower bounds. For a solution to exist, there must be some value of $x_n$ that satisfies both a lower and an upper bound simultaneously. By saying that every lower bound must be less than or equal to every upper bound, we guarantee that such a value of $x_n$ exists without explicitly needing to refer to it anymore.

Because $Q$ is defined by a finite set of linear inequalities in $n-1$ variables, it’s a polyhedron in ${\mathbb{R}}^{n-1}$. The algorithm produces a new system of inequalities, and this system defines a polyhedron in a lower-dimensional space.

Part 2: $Q=pro{j}_S(P)$

We’ll prove this by showing two set inclusions: $pro{j}_S(P)\subseteq Q$ and $Q\subseteq pro{j}_S(P)$. This is a standard way to show that two sets are equal: prove that each set contains the other.

(a) $pro{j}_S(P)\subseteq Q$:

Intuition: If a point is in the projection, it must satisfy the new constraints

If a point (values for $x_1,\dots ,x_{n-1}$) is in the projection of $P$, that means there was some value of $x_n$ that made it a valid solution in the original higher-dimensional space. Therefore, that point must also satisfy the new constraints in $Q$, which were specifically designed to capture the essence of the eliminated variable.

If $\mathbf{x}=(x_1,\dots ,x_{n-1})\in pro{j}_S(P)$, then there exists an $x_n$ such that $(\mathbf{x},x_n)\in P$. This means $(\mathbf{x},x_n)$ satisfies all original inequalities. Consequently, for any $i\in M_{+}$ and $l\in M_{-}$, we must have:

$d_l+{\sum }_{j=1}^{n-1}{f}_{lj}{x}_j\le x_n\le d_i+{\sum }_{j=1}^{n-1}{f}_{ij}{x}_j$

This is just restating that $x_n$ must lie between its lower and upper bounds. But this precisely implies that $\mathbf{x}$ satisfies the inequalities defining $Q$ (which were formed by combining these lower and upper bounds). Therefore, $pro{j}_S(P)\subseteq Q$. If a point is in the projection, it must satisfy the inequalities in the new system $Q$.

(b) $Q\subseteq pro{j}_S(P)$:

Intuition: If a point satisfies the new constraints, it must be in the projection

If a point satisfies the new constraints in $Q$, it means that for those values of the remaining variables, there was a feasible range for the eliminated variable $x_n$. We can then pick any value within that feasible range to construct a solution that exists in the original higher-dimensional space, thus confirming that the point is indeed in the projection.

If $\mathbf{x}=(x_1,\dots ,x_{n-1})\in Q$, then $\mathbf{x}$ satisfies all inequalities in $Q$. Define:

• $L=\max \{d_l+{\sum }_{j=1}^{n-1}{f}_{lj}{x}_j|l\in M_{-}\}$ (maximum lower bound on $x_n$)
• $U=\min \{d_i+{\sum }_{j=1}^{n-1}{f}_{ij}{x}_j|i\in M_{+}\}$ (minimum upper bound on $x_n$)

Since $\mathbf{x}\in Q$, the combined inequalities guarantee that $L\le U$. This is crucial: it means there’s a non-empty range $[L,U]$ for $x_n$. Choose any $x_n\in [L,U]$. This is guaranteed to be possible due to the $L\le U$ condition. This step effectively “reconstructs” a value for the eliminated variable.

Now, let’s verify that $(\mathbf{x},x_n)$ satisfies the original inequalities in $P$:

• For $i\in M_{+}$, $x_n\le U\le d_i+{\sum }_{j=1}^{n-1}{f}_{ij}{x}_j$. Satisfied because we chose $x_n$ to be less than or equal to the minimum upper bound.
• For $l\in M_{-}$, $x_n\ge L\ge d_l+{\sum }_{j=1}^{n-1}{f}_{lj}{x}_j$. Satisfied because we chose $x_n$ to be greater than or equal to the maximum lower bound.
• For $k\in M_0$, the inequalities are satisfied since $\mathbf{x}\in Q$ by assumption. These inequalities didn’t involve $x_n$ anyway.

Thus, $(\mathbf{x},x_n)$ satisfies all original inequalities, so $(\mathbf{x},x_n)\in P$, and therefore, $\mathbf{x}\in pro{j}_S(P)$. So, $Q\subseteq pro{j}_S(P)$.If a point satisfies the inequalities in $Q$, it must be in the projection of $P$.

Since $pro{j}_S(P)\subseteq Q$ and $Q\subseteq pro{j}_S(P)$, we conclude that $Q=pro{j}_S(P)$. The algorithm produces a new system of inequalities that exactly captures the projection of the original polyhedron. This completes the proof. This confirms that the elimination algorithm correctly computes the projection. We can now use this algorithm to reduce the dimensionality of our problem systematically.

Use These Projections Repeatedly

The real power of the projection theorem lies in its ability to be applied repeatedly. This allows us to systematically reduce the dimensionality of a problem until we reach a one-dimensional polyhedron, which we know how to solve by simply comparing its upper and lower bounds.

Lemma: Repeated Projections

Let $A\in {\mathbb{Q}}^{m\times n}$, $\mathbf{b}\in {\mathbb{Q}}^m$, and $P=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}\le \mathbf{b}\}$. For indices $1\le k<j<n$, consider the index sets $S_1=\{1,\dots ,n-k\}$ (eliminating the last $k$ variables) and $S_2=\{1,\dots ,n-j\}$ (eliminating the last $j$ variables, where $j>k$). Then: $pro{j}_{S_2}(P)=pro{j}_{S_2}(pro{j}_{S_1}(P))$

Intuition: The Shadow of a Shadow

Think of projecting a 3D object onto a 2D plane, and then projecting that 2D shadow onto a 1D line. This is the same as directly projecting the 3D object onto the 1D line. The order of projections doesn’t matter when we are ultimately projecting onto a subset of the final variables. We’re essentially eliminating variables in stages.

Proof: The proof is straightforward. Projecting onto $S_1$ eliminates the last $k$ variables. Projecting the result onto $S_2$ eliminates a further $j-k$ variables. In total, we’ve eliminated the last $j$ variables, which is exactly what $pro{j}_{S_2}(P)$ does directly.

The Elimination Process Algebraically

Let’s describe projection algebraically. This provides a more abstract but powerful way to understand the process.

Definition:

Given $A\in {\mathbb{Q}}^{m\times n}$, $\mathbf{b}\in {\mathbb{Q}}^m$, and $P=\{\mathbf{x}\in {\mathbb{R}}^n|A\mathbf{x}\le \mathbf{b}\}$, let $A^{(i)}$ be the submatrix of $A$ containing the first $i$ columns. Define:

• $P^{(0)}=P$ (the original polyhedron)
• $C^{(0)}={\mathbb{R}}^m$ (all possible linear combinations initially)

For $i\in \{1,\dots ,n\}$, define:

• $C^{(i)}=\{\mathbf{y}\in {\mathbb{R}}^m|\mathbf{y}\ge 0,{\mathbf{y}}^T{A}_{\cdot ,k}=0\text{ for }k=n-i+1,\dots ,n\}$. This defines a set of non-negative vectors $\mathbf{y}$ that are orthogonal to the last i columns of $A$. These vectors will be used to form specific linear combinations of the inequalities.

Understanding $C^{(i)}$

$C^{(i)}$ represents the set of valid “certificate” vectors after eliminating the last $i$ variables. The condition ${\mathbf{y}}^T{A}_{\cdot ,k}=0$ ensures that these certificate vectors effectively “cancel out” the eliminated variables when applied to the system of inequalities, allowing us to focus on the remaining variables.

• $P^{(i)}=\{\mathbf{x}\in {\mathbb{R}}^{n-i}|{\mathbf{y}}^T{A}^{(n-i)}\mathbf{x}\le {\mathbf{y}}^T\mathbf{b}\forall \mathbf{y}\in C^{(i)}\}$. This describes the projected polyhedron $P^{(i)}$ using linear combinations of the original inequalities, weighted by the vectors in $C^{(i)}$.

Theorem: Algebraic Projection

$pro{j}_{S_{n-i}}(P)=P^{(i)}$, where $S_{n-i}=\{1,2,\dots ,n-i\}$. This theorem states that the algebraic description $P^{(i)}$ is equivalent to the geometric projection $pro{j}_{S_{n-i}}(P)$.

Proof:

• Part 1: $pro{j}_{S_{n-i}}(P)\subseteq P^{(i)}$ We need to show that if a point is in the geometric projection, it’s also in the algebraically defined set.

  Let $\mathbf{x}\in pro{j}_{S_{n-i}}(P)$. This means there exists a $\mathbf{z}\in {\mathbb{R}}^i$ such that the combined vector $(\mathbf{x},\mathbf{z})$ is in the original polyhedron $P$, so it satisfies $A(\mathbf{x},\mathbf{z})\le \mathbf{b}$.

  Now, consider any $\mathbf{y}\in C^{(i)}$. By definition, $\mathbf{y}$ is non-negative and orthogonal to the last $i$ columns of $A$. Multiplying the inequality $A(\mathbf{x},\mathbf{z})\le \mathbf{b}$ by ${\mathbf{y}}^T$ (and remembering that $\mathbf{y}$ cancels out the last $i$ columns), we get: ${\mathbf{y}}^T{A}^{(n-i)}\mathbf{x}\le {\mathbf{y}}^T\mathbf{b}$.

  Since this holds for all $\mathbf{y}\in C^{(i)}$, we have $\mathbf{x}\in P^{(i)}$.

• Part 2: $P^{(i)}\subseteq pro{j}_{S_{n-i}}(P)$ This is the more challenging direction, often proven by induction on $i$. We need to show that if a point is in the algebraically defined set, it must also be in the geometric projection. The detailed proof of this part relies on techniques beyond the scope of this guided explanation, but the core idea is as follows:

  • Base Case (i=1): This corresponds to the Projection Theorem (Theorem 3) we already proved, which establishes the equivalence for eliminating a single variable.

  • Inductive Step: Assuming the theorem holds for eliminating $i-1$ variables ($P^{(i-1)}=pro{j}_{S_{n-i+1}}(P)$), we need to show it holds for eliminating $i$ variables. This typically involves applying the Fourier-Motzkin elimination procedure and using the inductive hypothesis to argue that a solution in $P^{(i)}$ implies the existence of a corresponding solution in the projection $pro{j}_{S_{n-i}}(P)$.

Since both inclusions hold, we have $pro{j}_{S_{n-i}}(P)=P^{(i)}$. The algebraic description captures the geometric projection process precisely.

Farkas Lemma: A Certificate of Infeasibility

Farkas’ Lemma is a cornerstone result that provides a definitive way to determine if a system of linear inequalities has a solution. It gives us a concrete “certificate” to prove that no solution exists.

Theorem: Farkas' Lemma

Let $A\in {\mathbb{Q}}^{m\times n}$ and $\mathbf{b}\in {\mathbb{Q}}^m$. Then exactly one of the following two possibilities is true:

1. Feasible System: There exists $\mathbf{x}\in {\mathbb{R}}^n$ such that $A\mathbf{x}\le \mathbf{b}$. (The system has a solution)
2. Infeasible System (with Certificate): There exists $\mathbf{y}\in {\mathbb{R}}^m$ such that $\mathbf{y}\ge 0$, ${\mathbf{y}}^{T}A=0$, and ${\mathbf{y}}^T\mathbf{b}<0$. (The system has no solution, and $\mathbf{y}$ proves it) This $\mathbf{y}$ is our certificate of infeasibility.

The Power of Farkas' Lemma

Farkas’ Lemma provides a powerful duality: either there’s a solution to the original system, or there’s a “certificate” (the vector $\mathbf{y}$) that proves there isn’t. This either/or property is incredibly useful in optimization and constraint satisfaction problems. Finding such a certificate definitively proves that there is no solution to the system of inequalities.

Proof (Using Projections):

1. Applying the algebraic projection repeatedly until all variables are eliminated, we get $P^{(n)}=pro{j}_{\varnothing }(P)$. This represents projecting the original polyhedron down to a zero-dimensional space - essentially asking if there’s any feasible point left. $pro{j}_{\varnothing }(P)$ is either empty or a single point.

2. Now, the first statement of Farkas’ Lemma ($A\mathbf{x}\le \mathbf{b}$ has a solution) is equivalent to saying that the original polyhedron $P$ is non-empty.

3. The second statement of Farkas’ Lemma (the existence of the certificate $\mathbf{y}$) is equivalent to saying that the final projection $pro{j}_{\varnothing }(P)$ is empty—meaning there’s no solution. We proved earlier that a polyhedron is non-empty if and only if its projection is non-empty.

Therefore, if there’s no solution ($P$ is empty), repeated projections will eventually lead to an empty set ($pro{j}_{\varnothing }(P)$ is empty), which guarantees the existence of a certificate $\mathbf{y}$ satisfying the conditions in the second statement of the lemma.

Continue here: 22 Determinants, Permutations, Properties, Cofactors, Cramers Rule