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
v2 · 2026-09-06 · History
Domain-specific #
1873
Origin domain
mathematics
Subdomain
linear inequalities and polyhedral projection

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), \]

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) — more general patterns this builds on

  • 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 (3) — routes to 3 parentless roots

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08