Fourier–Motzkin elimination

Short description: Mathematical algorithm for eliminating variables from a system of linear inequalities

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 who proposed the method in 1826 and Theodore Motzkin who re-discovered it in 1936.

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 [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] inequalities with [math]\displaystyle{ r }[/math] variables [math]\displaystyle{ x_1 }[/math] to [math]\displaystyle{ x_r }[/math], with [math]\displaystyle{ x_r }[/math] 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 [math]\displaystyle{ x_r }[/math].

• those inequalities that are of the form [math]\displaystyle{ x_r \geq b_i-\sum_{k=1}^{r-1} a_{ik} x_k }[/math]; denote these by [math]\displaystyle{ x_r \geq A_i(x_1, \dots, x_{r-1}) }[/math], for [math]\displaystyle{ i }[/math] ranging from 1 to [math]\displaystyle{ n_A }[/math] where [math]\displaystyle{ n_A }[/math] is the number of such inequalities;
• those inequalities that are of the form [math]\displaystyle{ x_r \leq b_i-\sum_{k=1}^{r-1} a_{ik} x_k }[/math]; denote these by [math]\displaystyle{ x_r \leq B_i(x_1, \dots, x_{r-1}) }[/math], for [math]\displaystyle{ i }[/math] ranging from 1 to [math]\displaystyle{ n_B }[/math] where [math]\displaystyle{ n_B }[/math] is the number of such inequalities;
• those inequalities in which [math]\displaystyle{ x_r }[/math] plays no role, grouped into a single conjunction [math]\displaystyle{ \phi }[/math].

The original system is thus equivalent to

[math]\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 }[/math].

Elimination consists in producing a system equivalent to [math]\displaystyle{ \exists x_r~S }[/math]. Obviously, this formula is equivalent to

[math]\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 }[/math].

The inequality

[math]\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})) }[/math]

is equivalent to [math]\displaystyle{ n_A n_B }[/math] inequalities [math]\displaystyle{ A_i(x_1, \dots, x_{r-1}) \leq B_j(x_1, \dots, x_{r-1}) }[/math], for [math]\displaystyle{ 1 \leq i \leq n_A }[/math] and [math]\displaystyle{ 1 \leq j \leq n_B }[/math].

We have therefore transformed the original system into another system where [math]\displaystyle{ x_r }[/math] is eliminated. Note that the output system has [math]\displaystyle{ (n-n_A-n_B)+n_A n_B }[/math] inequalities. In particular, if [math]\displaystyle{ n_A = n_B = n/2 }[/math], then the number of output inequalities is [math]\displaystyle{ n^2/4 }[/math].

Example

Consider the following system of inequalities:

[math]\displaystyle{ \begin{cases} 2x - 5y + 4z \leqslant 10 \\ 3x - 6y + 3z \leqslant 9 \\ -x + 5y - 2z \leqslant -7 \\ -3x + 2y + 6z \leqslant 12 \\ \end{cases} }[/math]

To eliminate x, we can write the inequalities in terms of x:

[math]\displaystyle{ \begin{cases} x \leqslant \frac{10 + 5y - 4z}{2} \\ x \leqslant \frac{9 + 6y - 3z}{3} \\ x \geqslant 7 + 5y - 2z \\ x \geqslant \frac{-12 + 2y + 6z}{3} \\ \end{cases} }[/math]

We have two inequalities with "≤" and two with "≥"; the system has a solution if the right-hand side of each "≤" inequality is at least the right-hand side of each "≥" inequality. We have 2*2 such combinations:

[math]\displaystyle{ \begin{cases} 7 + 5y - 2z \leqslant \frac{10 + 5y - 4z}{2} \\ 7 + 5y - 2z \leqslant \frac{9 + 6y - 3z}{3} \\ \frac{-12 + 2y + 6z}{3} \leqslant \frac{10 + 5y - 4z}{2} \\ \frac{-12 + 2y + 6z}{3} \leqslant \frac{9 + 6y - 3z}{3} \\ \end{cases} }[/math]

We now have a new system of inequalities, with one fewer variable.

Complexity

Running an elimination step over [math]\displaystyle{ n }[/math] inequalities can result in at most [math]\displaystyle{ n^2/4 }[/math] inequalities in the output, thus naively running [math]\displaystyle{ d }[/math] successive steps can result in at most [math]\displaystyle{ 4(n/4)^{2^d} }[/math], a double exponential complexity. This is due to the algorithm producing many unnecessary constraints (constraints that are implied by other constraints). Unnecessary constraints can be detected using linear programming. It follows from McMullen's upper bound theorem that the number of necessary constraints grows as a single exponential. A single exponential implementation of Fourier-Motzkin elimination and complexity estimates are given in.

Imbert's acceleration theorems

Two "acceleration" theorems due to Imbert 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 [math]\displaystyle{ H_i }[/math] of an inequality [math]\displaystyle{ i }[/math] as the set of indexes of inequalities from the initial system [math]\displaystyle{ S }[/math] used to produce [math]\displaystyle{ i }[/math]. Thus, [math]\displaystyle{ H_i=\{i\} }[/math] for inequalities [math]\displaystyle{ i \in S }[/math] of the initial system. When adding a new inequality [math]\displaystyle{ k: A_i(x_1, \dots, x_{r-1}) \leq B_j(x_1, \dots, x_{r-1}) }[/math] (by eliminating [math]\displaystyle{ x_r }[/math]), the new history [math]\displaystyle{ H_k }[/math] is constructed as [math]\displaystyle{ H_k = H_i \cup H_j }[/math].

Suppose that the variables [math]\displaystyle{ O_k = \{x_{r}, \ldots, x_{r - k + 1}\} }[/math] have been officially eliminated. Each inequality [math]\displaystyle{ i }[/math] partitions the set [math]\displaystyle{ O_k }[/math] into [math]\displaystyle{ E_i \cup I_i \cup R_i }[/math]:

• [math]\displaystyle{ E_i }[/math], the set of effectively eliminated variables, i.e. on purpose. A variable [math]\displaystyle{ x_j }[/math] is in the set as soon as at least one inequality in the history [math]\displaystyle{ H_i }[/math] of [math]\displaystyle{ i }[/math] results from the elimination of [math]\displaystyle{ x_j }[/math].
• [math]\displaystyle{ I_i }[/math], the set of implicitly eliminated variables, i.e. by accident. A variable is implicitly eliminated when it appears in at least one inequality of [math]\displaystyle{ H_i }[/math], but appears neither in inequality [math]\displaystyle{ i }[/math] nor in [math]\displaystyle{ E_i }[/math]
• [math]\displaystyle{ R_i }[/math], all remaining variables.

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

Theorem (Imbert's first acceleration theorem). If the history [math]\displaystyle{ H_i }[/math] of an inequality [math]\displaystyle{ i }[/math] is minimal, then [math]\displaystyle{ 1 + |E_i| \ \leq \ |H_i| \ \leq 1 + \left| E_i \cup (I_i \cap O_k)\right| }[/math].

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 [math]\displaystyle{ i }[/math] is such that [math]\displaystyle{ 1 + |E_i| = |H_i| }[/math], then [math]\displaystyle{ H_i }[/math] 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.

Applications in information theory

Information-theoretic achievability proofs result in conditions under which the existence of a well-performing coding scheme is guaranteed. These conditions are often described by linear system of inequalities. The variables of the system include both the transmission rates (that are part of the problem's formulation) and additional auxiliary rates used for the design of the scheme. Commonly, one aims to describe the fundamental limits of communication in terms of the problem's parameters only. This gives rise to the need of eliminating the aforementioned auxiliary rates, which is executed via Fourier–Motzkin elimination. However, the elimination process results in a new system that possibly contains more inequalities than the original. Yet, often some of the inequalities in the reduced system are redundant. Redundancy may be implied by other inequalities or by inequalities in information theory (a.k.a. Shannon type inequalities). A recently developed open-source software for MATLAB performs the elimination, while identifying and removing redundant inequalities. Consequently, the software's outputs a simplified system (without redundancies) that involves the communication rates only.

Redundant constraint can be identified by solving a linear program as follows. Given a linear constraints system, if the [math]\displaystyle{ i }[/math]-th inequality is satisfied for any solution of all other inequalities, then it is redundant. Similarly, STIs refers to inequalities that are implied by the non-negativity of information theoretic measures and basic identities they satisfy. For instance, the STI [math]\displaystyle{ I(X_1;X_2) \leq H(X_1) }[/math] is a consequence of the identity [math]\displaystyle{ I(X_1;X_2) = H(X_1) - H(X_1 | X_2) }[/math] and the non-negativity of conditional entropy, i.e., [math]\displaystyle{ H(X_1|X_2) \geq 0 }[/math]. Shannon-type inequalities define a cone in [math]\displaystyle{ \mathbb R^{2^n-1} }[/math], where [math]\displaystyle{ n }[/math] is the number of random variables appearing in the involved information measures. Consequently, any STI can be proven via linear programming by checking if it is implied by the basic identities and non-negativity constraints. The described algorithm first performs Fourier–Motzkin elimination to remove the auxiliary rates. Then, it imposes the information theoretic non-negativity constraints on the reduced output system and removes redundant inequalities.

See also

• Farkas' lemma – can be proved using FM elimination.
• Real closed field – the cylindrical algebraic decomposition algorithm performs quantifier elimination over polynomial inequalities, not just linear.

Further reading

• Schrijver, Alexander (1998). Theory of Linear and Integer Programming. John Wiley & sons. pp. 155–156. ISBN 978-0-471-98232-6. 
• Keßler, Christoph W. (1996). "Parallel Fourier–Motzkin Elimination". Universität Trier: 66–71. 
• Williams, H. P. (1986). "Fourier's Method of Linear Programming and its Dual". American Mathematical Monthly 93 (9): 681–695. doi:10.2307/2322281. http://www.maa.org/pubs/monthly.html. 

External links

• Chapter 1 of Undergraduate Convexity, textbook by Niels Lauritzen at Aarhus University.
• FME software for Information theory, open-source code in MATLAB by Ido B. Gattegno, Ziv Goldfeld and Haim H. Permuter.
• Symbolic Fourier-Motzkin elimination, open-source code in Python implementing the two Imbert acceleration theorems.