Fourier-Motzkin elimination

Fourier-Motzkin elimination, also called the FME method, is a mathematical algorithm for removing variables from a system of linear inequalities. Eliminating a variable produces a new system of the same kind that no longer mentions it but has exactly the same solutions in the remaining variables, so eliminating every variable leaves a set of constant inequalities that is plainly true or false, and that outcome tells whether the original system has any solution at all. The method is named for Joseph Fourier, who proposed it in 1826, and Theodore Motzkin, who rediscovered it in 1936. Each elimination step can square the number of inequalities, so naive repetition grows at a double exponential rate because many of the new constraints are redundant; McMullen's upper bound theorem shows the non-redundant constraints grow only exponentially, and Imbert's acceleration theorems remove redundant inequalities by inspecting how each was derived. It also appears in information theory, where it removes auxiliary rates from achievability conditions.