Fourier–Motzkin elimination
The algorithm is named after Joseph Fourier[1] who proposed the method in 1826 and Theodore Motzkin who re-discovered it in 1936.
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.
It is then trivial to decide whether the resulting system is true or false.
As a consequence, elimination of all variables can be used to detect whether a system of inequalities has solutions or not.
The linear inequalities in the system can be grouped into three classes depending on the sign (positive, negative or null) of the coefficient for
Consider the following system of inequalities:[2]: 100–102 Since all the inequalities are in the same form (all less-than or all greater-than), we can examine the coefficient signs for each variable.
which gives the 3 inequalities: Simplifying: This system uses only 2 variables instead of 3.
Examining the coefficient signs for each variable yields all-positive for y, so we can immediately say that the system is unbounded in y: since all y coefficients are positive and all inequalities are less-than-or-equal, setting y to negative infinity (or any sufficiently large negative number) would satisfy the reduced system, therefore there exist corresponding x and z for the larger systems as well, and there are infinitely many such solutions.
E.g. setting y = -1000000, x = 0, z = -2222222 satisfies the original system as well as the reduced ones.
McMullen's upper bound theorem that the number of non-redundant constraints grows as a single exponential.
[3] A single exponential implementation of Fourier-Motzkin elimination and complexity estimates are given in.
[4] Linear programming is well-known to give solutions to inequality systems in polynomial time, favoring it over Fourier-Motzkin elimination.
Two "acceleration" theorems due to Imbert[5] 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.
as the set of indexes of inequalities from the initial system
: A non-redundant inequality has the property that its history is minimal.
An inequality that does not satisfy these bounds is necessarily redundant, and can be removed from the system without changing its solution set.
This theorem provides a quick detection criterion and is used in practice to avoid more costly checks, such as those based on matrix ranks.
[6] 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.
However, the elimination process results in a new system that possibly contains more inequalities than the original.
A recently developed open-source software for MATLAB[7] 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.
Similarly, STIs refers to inequalities that are implied by the non-negativity of information theoretic measures and basic identities they satisfy.
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.
