# Fourier–Motzkin elimination

Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions.

The algorithm is named after Joseph Fourier and Theodore Motzkin.

## Elimination

The elimination of a set of variables, say V, from a system of relations (here linear inequalities) refers to the creation of another system of the same sort, but without the variables in V, such that both systems have the same solutions over the remaining variables.

If all variables are eliminated from a system of linear inequalities, then one obtains a system of constant inequalities. It is then trivial to decide whether the resulting system is true or false. It is true if and only if the original system has solutions. As a consequence, elimination of all variables can be used to detect whether a system of inequalities has solutions or not.

Consider a system ${\displaystyle S}$ of ${\displaystyle n}$ inequalities with ${\displaystyle r}$ variables ${\displaystyle x_{1}}$ to ${\displaystyle x_{r}}$, with ${\displaystyle x_{r}}$ the variable to be eliminated. The linear inequalities in the system can be grouped into three classes depending on the sign (positive, negative or null) of the coefficient for ${\displaystyle x_{r}}$.

• those inequalities that are of the form ${\displaystyle x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$; denote these by ${\displaystyle x_{r}\geq A_{j}(x_{1},\dots ,x_{r-1})}$, for ${\displaystyle j}$ ranging from 1 to ${\displaystyle n_{A}}$ where ${\displaystyle n_{A}}$ is the number of such inequalities;
• those inequalities that are of the form ${\displaystyle x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$; denote these by ${\displaystyle x_{r}\leq B_{j}(x_{1},\dots ,x_{r-1})}$, for ${\displaystyle j}$ ranging from 1 to ${\displaystyle n_{B}}$ where ${\displaystyle n_{B}}$ is the number of such inequalities;
• those inequalities in which ${\displaystyle x_{r}}$ plays no role, grouped into a single conjunction ${\displaystyle \phi }$.

The original system is thus equivalent to

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq x_{r}\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\wedge \phi }$.

Elimination consists in producing a system equivalent to ${\displaystyle \exists x_{r}~S}$. Obviously, this formula is equivalent to

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))\wedge \phi }$.

The inequality

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))}$

is equivalent to ${\displaystyle n_{A}n_{B}}$ inequalities ${\displaystyle A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$, for ${\displaystyle 1\leq i\leq n_{A}}$ and ${\displaystyle 1\leq j\leq n_{B}}$.

We have therefore transformed the original system into another system where ${\displaystyle x_{r}}$ is eliminated. Note that the output system has ${\displaystyle (n-n_{A}-n_{B})+n_{A}n_{B}}$ inequalities. In particular, if ${\displaystyle n_{A}=n_{B}=n/2}$, then the number of output inequalities is ${\displaystyle n^{2}/4}$.

## Complexity

Running an elimination step over ${\displaystyle n}$ inequalities can result in at most ${\displaystyle n^{2}/4}$ inequalities in the output, thus running ${\displaystyle d}$ successive steps can result in at most ${\displaystyle 4(n/4)^{2^{d}}}$, a double exponential complexity. This is due to the algorithm producing many unnecessary constraints (constraints that are implied by other constraints). The number of necessary constraints grows as a single exponential.[1] Unnecessary constraints may be detected using linear programming.

## Imbert's acceleration theorems

Two "acceleration" theorems due to Imbert[2] permit the elimination of redundant inequalities based solely on syntactic properties of the formula derivation tree, thus curtailing the need to solve linear programs or compute matrix ranks.

Define the history ${\displaystyle H_{i}}$ of an inequality ${\displaystyle i}$ as the set of indexes of inequalities from the initial system ${\displaystyle S}$ used to produce ${\displaystyle i}$. Thus, ${\displaystyle H_{i}=\{i\}}$ for inequalities ${\displaystyle i\in S}$ of the initial system. When adding a new inequality ${\displaystyle k:A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$ (by eliminating ${\displaystyle x_{r}}$), the new history ${\displaystyle H_{k}}$ is constructed as ${\displaystyle H_{k}=H_{i}\cup H_{j}}$.

Suppose that the variables ${\displaystyle O_{k}=\{x_{r},\ldots ,x_{r-k+1}\}}$ have been eliminated. Each inequality ${\displaystyle i}$ partitions the set ${\displaystyle O_{k}}$ into:

• ${\displaystyle E_{i}}$, the set of effectively eliminated variables. A variable ${\displaystyle x_{j}}$ is in the set as soon as at least of inequality in the history ${\displaystyle H_{i}}$ of ${\displaystyle i}$ results from the elimination of x_j.
• ${\displaystyle I_{i}}$, the set of implicitely eliminated variables. A variable is implicitely eliminated when it appears in at least one inequality of ${\displaystyle H_{i}}$, but appears neither in ${\displaystyle i}$ nor ${\displaystyle E_{i}}$
• all remaining variables.

A non-redundant inequality has the property that its history is minimal.[3]

Theorem (Imbert's first acceleration theorem). If the history ${\displaystyle H_{i}}$ of an inequality ${\displaystyle i}$ is minimal, then ${\displaystyle 1+|E_{i}|\ \leq \ |H_{i}|\ \leq 1+\left|E_{i}\cup (I_{i}\cap O_{k})\right|}$.

An inequality that does not satisfy these bounds is necessarily redundant, and can be removed from the system without changing its solution set.

The second acceleration theorem detects minimal history sets:

Theorem (Imbert's second acceleration theorem). If the inequality ${\displaystyle i}$ is such that ${\displaystyle 1+|E_{i}|=|H_{i}|}$, then ${\displaystyle H_{i}}$ is minimal.

This theorem provides a quick detection criterion and is used in practice to avoid more costly checks, such as those based on matrix ranks. See the reference for implementation details.[3]