Skip to content

Fourier–Motzkin Elimination

Project a finite system of linear inequalities onto fewer variables by separating one variable's lower and upper bounds and emitting every cross-bound consistency inequality.

Version
v3 · 2026-09-19 · History
Domain-specific #
1873
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Linear Inequalities and Polyhedral Projection → Mathematics

Core Idea

Fourier–Motzkin elimination is a symbolic algorithm for removing variables from a finite system of linear inequalities while preserving exactly the feasible values of the variables that remain. For one chosen variable \(x\), it rewrites every inequality involving \(x\) as either a lower bound \(L_i(y)\leq x\) or an upper bound \(x\leq U_j(y)\), where \(y\) denotes all other variables. It retains inequalities that do not mention \(x\), replaces the two bound families by every cross-pair condition

\[ L_i(y)\leq U_j(y), \]

How would you explain it like I'm…

Pair Up the Clues

Imagine you have clues about two secret numbers, like 'x is bigger than y' and 'x is smaller than 10.' You want new clues that talk only about y, so you can forget x. You pair up every 'x is at least this' clue with every 'x is at most that' clue, and each pair becomes a clue about y. The new clues allow exactly the y's that the old clues allowed.

Pair Up the Limits

Fourier–Motzkin elimination works on a list of rules like 'x is at least y + 1' and 'x is at most 10'. To get rid of x, you sort the rules into 'x must be at least this' rules and 'x must be at most this' rules. Then you pair every 'at least' with every 'at most' and write a new rule saying the low limit can't be bigger than the high limit. Rules without x stay as they are. The new list is exactly right: the other values work in it whenever some x existed that made all the old rules true. The catch is that the list can grow very long, very fast.

Exact Inequality Projection

Fourier–Motzkin elimination removes a variable x from a finite system of linear inequalities while preserving exactly which values of the remaining variables y are feasible. Rewrite each inequality that mentions x as a lower bound L(y) ≤ x or an upper bound x ≤ U(y), and keep the inequalities without x. Then replace the bounds with every pair condition L_i(y) ≤ U_j(y). This is exact, because an x exists exactly when the largest lower bound is at most the smallest upper bound. If there are only lower bounds or only upper bounds, x can always be chosen, so no pair conditions are needed. Geometrically, you get the 'shadow' of the feasible region on the y-coordinates. The cost: p lower and q upper bounds produce p × q new inequalities, so repeated elimination can blow up badly.

 

Fourier–Motzkin elimination removes variables from a finite system of linear inequalities while preserving exactly the feasible set of the remaining variables. For a chosen x, each constraint involving x is normalized into a lower bound L_i(y) ≤ x or an upper bound x ≤ U_j(y). Constraints not mentioning x are kept, and the bound families are replaced by all cross-pairs L_i(y) ≤ U_j(y). Exactness follows because, for fixed y, an admissible x exists iff the largest lower bound does not exceed the smallest upper bound. With finitely many bounds, that is equivalent to every L_i ≤ every U_j. If only lower or only upper bounds exist, x can be taken large or small enough. The result describes the projection of the polyhedron onto the y-coordinates. Equivalently, it eliminates the existential quantifier ∃x over a conjunction, which is quantifier elimination for linear real arithmetic. The cost: one step can create pq inequalities, so repeated elimination has a doubly exponential worst-case upper bound, though known examples show single-exponential blowup. Elimination order and redundancy removal therefore matter in practice.

Scope of Application

Within its literal scope, Fourier–Motzkin elimination transfers without metaphor across several practices that share linear ordered constraints.

  • Systems of linear inequalities. Repeated elimination can decide feasibility: after all variables are removed, a contradiction such as \(0<0\) or \(0\leq-1\) certifies infeasibility, while a consistent scalar residue permits back-substitution of bounds.
  • Polyhedral projection. An H-represented polyhedron \(P=\{(x,y):A(x,y)\leq b\}\) can be projected onto \(y\)-space by eliminating the \(x\)-coordinates.

Clarity

Fourier–Motzkin elimination clarifies what “remove this variable” must mean. Deleting every inequality that mentions \(x\) enlarges the feasible set incorrectly. Substituting an arbitrary value for \(x\) takes a slice, not a projection. Optimizing \(x\) for one objective preserves only an extremal answer. Correct elimination asks a quantified question: for each proposed \(y\), does at least one \(x\) satisfy all original bounds simultaneously?

Manages Complexity

The input may describe an object in a high-dimensional space even though a user cares about only a few coordinates. Fourier–Motzkin compresses away the internal coordinates and returns constraints expressed in the visible vocabulary. An engineering design can eliminate internal flows to reveal an operating envelope; a logical procedure can eliminate quantified variables; a rate proof can eliminate coding auxiliaries. The consumer no longer needs to carry witnesses for the hidden variables when asking whether a visible point is extendable.

Abstract Reasoning

The mechanism licenses concrete diagnoses and interventions:

  • If a variable occurs with only one coefficient sign, eliminating it creates no cross-pair inequalities from that group. Preserve the variable-free constraints and use unboundedness in the opposite direction. If the application intended a bounded variable, the missing opposite bound is a modeling signal.
  • If both sign groups are large, the next step can grow roughly as their product. Change the elimination order, remove redundant constraints first, or use a different projection representation.
  • If two derived inequalities are proportional and one is weaker, the weaker one can be discarded. This reduces syntax without changing the projected set.
  • If a retained assignment violates one cross-pair inequality, no eliminated-variable witness exists. The contributing lower and upper parents supply a compact explanation of the conflict.
  • If real projection accepts a point but integer extension fails, the domain assumption—not the pair algebra—is wrong. Switch to an integer-preserving elimination procedure or carry congruence information.
  • If a strict bound participates, equality at the paired boundary may be forbidden. Propagate strictness instead of silently weakening the projection.
  • If the downstream task needs a witness, store derivation or back-substitution information. The projected inequalities decide extendability, but the output alone does not necessarily report a particular eliminated value.

Knowledge Transfer

The method transfers literally from polyhedral theory to automated reasoning because both manipulate the same object: finite conjunctions of linear inequalities with existentially hidden variables. “Project a polyhedron” and “eliminate an existential variable” are two readings of the same transformation. The sign partition, normalized bounds, all-pairs step, strictness rule, and redundancy problem remain unchanged.

It transfers just as literally to information-theoretic rate derivations. Auxiliary rates appear as real variables constrained by linear inequalities.

Relationships to Other Abstractions

Local relationship map for Fourier–Motzkin EliminationParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Fourier–MotzkinEliminationDOMAINPrime abstraction: Projection — presupposesProjectionPRIMEPrime abstraction: Algorithm — is a kind ofAlgorithmPRIME

Current abstraction Fourier–Motzkin Elimination Domain-specific

Parents (2) — outgoing typed relations

  • Fourier–Motzkin Elimination is a kind of Algorithm Prime

    prime:algorithm (proposed primary parent, strict subsumption). Fourier–Motzkin is a definite input-to-output procedure with correctness and resource semantics.

  • Fourier–Motzkin Elimination presupposes Projection Prime

    prime:algorithm (proposed primary parent, strict subsumption). Fourier–Motzkin is a definite input-to-output procedure with correctness and resource semantics.

Hierarchy paths (2) — routes to 2 parentless roots

Neighborhood in Abstraction Space

Fourier–Motzkin Elimination sits in a sparse region of the domain-specific corpus (68th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Computational Complexity & Hardness (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25