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

and then discards \(x\). The resulting inequalities describe the projection of the original feasible polyhedron onto the \(y\)-coordinates. Equivalently, they remove the existential quantifier in “there exists an \(x\) satisfying this conjunction.” Standard treatments connect this algebraic rule to polyhedral projection and quantifier elimination for linear real arithmetic.^[1]^[2]^[3]

To see why the all-pairs step is exact, fix values of \(y\). An admissible \(x\) exists precisely when the greatest applicable lower bound is no larger than the least applicable upper bound. For finite bound families, that condition is equivalent to requiring every lower bound to be no larger than every upper bound. If there are only lower bounds, \(x\) can be chosen sufficiently large; with only upper bounds it can be chosen sufficiently small. Thus the method neither samples feasible points nor approximates a shape: it transforms one inequality description into an exact description of its coordinate projection over the declared ordered-field setting.

The method's celebrated simplicity is paired with a severe representational cost. If \(p\) inequalities provide lower bounds and \(q\) provide upper bounds, one elimination step can create \(pq\) cross-pair inequalities in addition to unaffected constraints. Repeated squaring of that pair-count recurrence gives a doubly exponential worst-case upper bound, but Monniaux notes that the cited literature had not exhibited examples achieving that bound; known examples exhibit single-exponential blowups.^[3] Fourier–Motzkin elimination therefore has two inseparable faces: an exact and transparent projection rule, and a constraint-explosion problem that makes elimination order and redundancy removal operationally decisive.

Structural Signature¶

Sig role-phrases:

Input system — a finite conjunction of linear equalities or inequalities over an ordered numeric domain
Elimination variable — the chosen variable whose existential role is to be removed
Sign partitions — the positive-, negative-, and zero-coefficient constraint groups for that variable
Bound families — the normalized lower-bound family and upper-bound family
Cross-pair test — the complete consistency test between those two families
Retained constraints — the untouched constraints that already omit the chosen variable
Projected feasible set — the feasible set over the remaining variables
Growth ledger — the redundancy and constraint-growth record governing repeated elimination

Write an input inequality as

\[ a_i x+b_i^{\mathsf T}y\leq c_i. \]

When \(a_i>0\), division gives the upper bound \(x\leq(c_i-b_i^{\mathsf T}y)/a_i\). When \(a_i<0\), division reverses the inequality and gives a lower bound. When \(a_i=0\), the constraint is retained unchanged. Every lower/upper pair is combined so the coefficient of \(x\) cancels. For non-strict inequalities this produces \(L_i(y)\leq U_j(y)\); if either contributing bound is strict, the corresponding cross-pair comparison must be strict. Equalities can be used for direct substitution before the inequality step, but that is an extension of the basic sign-partition rule rather than permission to treat inequalities as equations.^[3]

Four invariants define the method. First, projection equivalence: a remaining-variable assignment satisfies the output exactly when it extends to some input-feasible value of the eliminated variable. Second, linearity: normalization and nonnegative combination preserve linear inequalities. Third, complete bound compatibility: no lower/upper pair may be omitted unless another proof establishes its redundancy. Fourth, iteration closure: the output is again a finite linear-inequality system, so another variable can be eliminated by the same rule.

Remove linear order and “lower versus upper” loses meaning. Remove all cross-pair combinations and projection equivalence can fail. Keep \(x\) in the output and elimination has not occurred. Replace exact constraints with sampled witnesses and the result is approximation, not Fourier–Motzkin elimination. Those tests separate the method from generic simplification language.

What It Is Not¶

Not Gaussian elimination. Gaussian elimination performs equality-preserving row operations on linear equations, often producing a unique solution or parametric solution space. Fourier–Motzkin elimination combines inequalities with sign-aware nonnegative multipliers, preserves existential projection, and can multiply the constraint count.
Not the simplex method. Simplex optimizes an objective by moving among basic feasible solutions. Fourier–Motzkin needs no objective and can be used for projection, feasibility, or quantifier elimination. A linear program may be reduced or analyzed with it, but the two procedures have different state and stopping conditions.
Not every polyhedral projection algorithm. Projection is the geometric result. Vertex conversion, block elimination, dual descriptions, and specialized polyhedral software can compute the same result by different mechanisms. Fourier–Motzkin is the sign-partition and all-cross-pairs route on an inequality description.
Not unrestricted quantifier elimination. It handles conjunctions and, in suitable logical procedures, formulas of linear arithmetic over ordered fields or the reals. Polynomial inequalities, integer divisibility, nonlinear functions, and arbitrary Boolean structure require additional case handling or different algorithms.^[2]^[3]
Not lossless integer elimination by default. Projecting the real relaxation may admit remaining-variable values that have no integer extension. Integer procedures must preserve integrality through rounding, congruences, or other machinery.
Not merely “add inequalities until a variable cancels.” The coefficient-sign partition, preservation of zero-coefficient constraints, complete lower/upper pairing, and existential-projection invariant are constitutive. Accidental cancellation without those obligations does not establish correctness.

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.^[1]
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. This supports extended formulations, marginal feasible regions, and removal of auxiliary modeling variables.
Linear-real-arithmetic quantifier elimination. The algorithm removes existential variables from conjunctions of linear inequalities, providing a building block for decision procedures and symbolic reasoning.^[2]^[3]
Linear optimization preprocessing and explanation. Projection can expose implied constraints among retained variables, identify infeasibility, or remove local variables before a downstream solver. Whether this is computationally wise depends on growth and redundancy.
Information-theoretic rate regions. Coding proofs often introduce auxiliary rates, binning rates, or split-message variables. Eliminating those auxiliaries converts an internal achievability system into inequalities over the advertised communication rates. Software work in this field explicitly couples Fourier–Motzkin elimination with redundancy removal using information inequalities.^[4]
Control, scheduling, and resource models. Whenever internal continuous variables occur only linearly, the same rule can expose the exact feasible envelope on externally controlled quantities.

The boundary is exact linear inequality reasoning over an appropriate ordered domain. Using “eliminate the hidden factor by comparing lower and upper pressures” in social analysis may borrow a suggestive image, but it does not retain coefficient normalization, cross-pair completeness, or projection equivalence. The transferable residue outside mathematics is already carried by elimination, constraint, and projection-like reasoning; the named algorithm remains domain-specific.

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?

The lower/upper table turns that question into an audit. Each negative-coefficient inequality contributes a lower bound, each positive-coefficient inequality an upper bound, and each zero-coefficient inequality an obligation already stated in the retained variables. Every lower bound must fit below every upper bound. If a projected inequality looks suspicious, its two parent constraints can be traced. If growth is extreme, the counts \(p\), \(q\), and \(pq\) show exactly which elimination created it.

This view also exposes three distinct operations often blurred together: projection changes the variable vocabulary while preserving extendability; feasibility testing asks whether any complete assignment exists; optimization chooses the best feasible assignment under an objective. Fourier–Motzkin directly performs the first, can be iterated for the second, and only indirectly supports the third.

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.

The algorithm is local and compositional. One does not need to enumerate vertices of the full polyhedron. Each elimination reads only coefficient signs, normalizes bounds, forms pairs, and produces another system of the same type. The provenance of every derived inequality is explicit, and a feasible retained point can be extended by choosing any eliminated value between its greatest lower and least upper bounds.

Yet semantic compression can cause syntactic expansion. Replacing \(p+q\) constraints with \(pq\) pairs is profitable only when the removed dimension is worth the new description. Redundancy detection, subsumption tests, normalization of proportional inequalities, and a careful elimination order manage that burden. Sparse variable incidence may suggest eliminating a variable with small \(pq\); domain-specific implication oracles may remove more constraints than generic linear programming detects. The method manages complexity best when projection is the real output and intermediate descriptions stay controlled—not when it is used blindly as a universal LP solver.

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.

These inferences arise from the bound interval. The algorithm is useful not just because it produces equations, but because every failure and optimization point can be located in the relationship among the lower family, upper family, and projected description.

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. The published region is their projection onto user-visible rates, and redundant information inequalities can be removed after or during elimination.^[4] The symbols change from coordinates to rates, but the mathematical roles do not.

Implementation techniques also transfer within this family. A sparsity-based variable order reduces pair counts regardless of whether the system came from a compiler, a network code, or an operations-research model. Linear-programming redundancy tests can remove implied inequalities. Provenance tracking can turn an infeasible scalar residue into an explanation in the original constraints.

Outside linear ordered constraints, the name should not transfer literally. Eliminating a nuisance concept from an argument, a confounder from an empirical study, or an intermediary from an organization may instantiate broader simplification or projection patterns, but it lacks exact lower/upper pair completeness. The algorithm's portable structure is already represented by algorithm and projection; its specialized identity stays with linear inequality systems.

Examples¶

Canonical: projecting a two-variable inequality system¶

Consider a small system of the same worked bound-pairing form used in instructional treatments of the method:^[5]

\[ x+y\leq6,\qquad -x+2y\leq4,\qquad -x\leq0. \]

Eliminate \(x\). The first inequality gives the upper bound \(x\leq6-y\). The second gives \(x\geq2y-4\), and the third gives \(x\geq0\). There are no constraints independent of \(x\). Pairing each lower bound with the sole upper bound yields

\[ 2y-4\leq6-y\quad\Rightarrow\quad 3y\leq10, \]

and

\[ 0\leq6-y\quad\Rightarrow\quad y\leq6. \]

The second output inequality is redundant because \(y\leq10/3\) already implies \(y\leq6\). Thus the projection onto the \(y\)-axis is exactly \(y\leq10/3\). For any such \(y\), choose \(x\) between \(\max(2y-4,0)\) and \(6-y\); for any \(y>10/3\), the first lower bound exceeds the upper bound and no witness exists.

Mapped back: The input conjunction is the three inequalities; the chosen variable is \(x\); the sign partitions yield two lower bounds and one upper bound; the normalized bound families are \(\{2y-4,0\}\) and \(\{6-y\}\); the cross-pair test creates two inequalities; the retained-constraint set is empty; the projected feasible set is \(y\leq10/3\); and the growth/redundancy ledger records two generated constraints of which one is implied.

Applied/practice: removing an auxiliary communication rate¶

Information-theoretic achievability proofs often introduce an auxiliary rate \(U\) used internally by a coding construction and then report only user rates \((R_1,R_2)\). Consider the stylized linear system

\[ R_1+U\leq A,\qquad R_2-U\leq B,\qquad 0\leq U\leq D, \]

with \(D\geq0\). Normalize the bounds on \(U\):

\[ U\leq A-R_1,\quad U\leq D,\quad U\geq R_2-B,\quad U\geq0. \]

All lower/upper pairings give

\[ R_1+R_2\leq A+B,\qquad R_2\leq B+D, \]

\[ R_1\leq A,\qquad 0\leq D. \]

The last is already an assumed parameter condition. The remaining three inequalities describe the advertised \((R_1,R_2)\) region without mentioning the code-internal split rate. Real derivations contain more auxiliaries and many Shannon-type inequalities; computational tooling combines Fourier–Motzkin with redundancy removal for precisely this reason.^[4]

Mapped back: The input conjunction is the internal achievability system; the chosen variable is auxiliary rate \(U\); the sign partitions separate resource-consuming and resource-contributing occurrences; the lower and upper families are the four normalized bounds; the cross-pair test produces the visible rate constraints; parameter-only constraints are retained; the projected set is the user-rate region; and the growth ledger motivates domain-aware redundancy removal as further auxiliary rates are eliminated.

Structural Tensions¶

T1: Exact semantic reduction vs. syntactic explosion. Eliminating a coordinate gives an exact lower-dimensional meaning, but the all-pairs rule can replace a short description with a much longer one. Diagnostic: Does removing this variable reduce the consumer's problem more than \(pq\) new inequalities enlarge the representation?

T2: Complete pairing vs. aggressive redundancy pruning. Every lower/upper pair is required for a direct correctness proof, yet many resulting inequalities are implied by others. Prune too timidly and the system explodes; prune unsafely and the projection enlarges. Diagnostic: Is each discarded inequality backed by a valid implication or redundancy certificate in the declared domain?

T3: Elimination-order freedom vs. path-dependent cost. Any variable order can reach the same final projection semantically, but intermediate constraint counts can differ drastically. Diagnostic: Which candidate variable minimizes sign-pair product and downstream coefficient density, and is that local heuristic hiding a worse later step?

T4: Real-domain elegance vs. discrete-domain unsoundness. Ordered-field bounds make witness existence an interval question. Integer witnesses can fail even when the interval is nonempty over the reals. Diagnostic: Are eliminated variables genuinely continuous, or must the output preserve divisibility, parity, or lattice restrictions?

T5: Compact output vs. witness recovery. Projection answers whether an extension exists but hides which eliminated values realize it. Applications may later need a concrete schedule, flow, or code parameter. Diagnostic: Is membership in the projected region sufficient, or must derivation and back-substitution data be retained?

T6: Canonical transparency vs. specialized performance. Fourier–Motzkin's rule is easy to explain, trace, and verify. More sophisticated polyhedral or solver methods may compute large projections faster but with less direct provenance. Diagnostic: Is auditability of each derived inequality more valuable here than raw projection throughput?

T7: Autonomy vs. reduction (named method vs. parent composition). The method can be described as an algorithm that implements projection under linear constraint. Those parents expose its cross-domain skeleton, but they do not entail coefficient-sign partitioning, complete lower/upper pairing, strictness propagation, or characteristic constraint growth. Diagnostic: Are those linear-inequality roles and their interventions needed, making the named node explanatory, or is the case adequately described as generic projection or elimination?

Structural–Framed Character¶

Fourier–Motzkin elimination is structural-leaning under the five locked criteria:

Vocabulary travel: its role vocabulary travels literally across mathematical applications but not beyond linear ordered constraints.
Evaluative weight: correctness is formal and observer-independent, with no normative ranking.
Institutional origin: no institutional declaration constitutes the algorithm or its projected set.
Human-practice boundedness: the rule is executable independently of a particular professional practice.
Import versus recognition: polyhedral, logical, optimization, and rate-region uses recognize the same mechanism; uses outside linear ordered constraints merely import a metaphor.

The method remains domain-specific because its correctness depends on linear combinations, an ordered numeric carrier, inequality reversal under division by a negative coefficient, and finite conjunction. Its character: a strongly structural-leaning algorithm whose exact identity is bounded to linear inequality reasoning rather than a universal prime.

Structural Core vs. Domain Accent¶

What is skeletal. A broader pattern removes a hidden dimension by deriving every condition that visible variables must satisfy for some hidden witness to exist. It partitions constraints by how they restrict the hidden role, combines complementary restrictions, preserves constraints already expressed in the visible vocabulary, and returns a reduced interface. That skeleton belongs to projection, constraint, elimination, and algorithm.

What is domain-bound. Fourier–Motzkin's explanatory power comes from the cargo that cannot be removed: a finite linear inequality system; coefficient signs; division in an ordered field; lower and upper affine functions; reversal of order for negative coefficients; pairwise nonnegative combination; strict-bound propagation; H-represented polyhedra; existential linear arithmetic; \(pq\) growth; and linear-implication redundancy. These features tell the practitioner exactly how to derive the output and why it is correct.

Why it does not clear the prime bar. The full mechanism transfers across several technical subfields, but all use the same mathematical substrate. Replacing affine inequalities with arbitrary organizational rules or causal hypotheses destroys the algebraic derivation and its guarantees. The generalizable residue is already owned by broader primes; the named algorithm earns a domain-specific node because its mature closure supplies diagnostics—sign imbalance, pair-product growth, strictness, integer mismatch, and redundancy—that the parent composition does not predict on its own.

prime:algorithm (proposed primary parent, strict subsumption). Fourier–Motzkin is a definite input-to-output procedure with correctness and resource semantics. It specializes Algorithm to sign-partitioned elimination of linear-inequality variables and exact projection. Removing those additions leaves an algorithm; removing procedure leaves no Fourier–Motzkin method.
prime:projection (proposed constitutive parent, composition / implements). The output is precisely the image of the feasible set under coordinate deletion, or equivalently the set of retained assignments with some hidden-variable extension. Projection supplies that retained-versus-discarded dimension structure; the child supplies an H-representation algorithm.
prime:linear_programming_lp (related, not proposed as a parent). A linear program's feasible constraints can be projected or its feasibility tested by elimination, but the method requires no objective and is not a species of optimization problem.
prime:constraint (related/inherited structure). Linear inequalities are constraints, but adding a direct edge would be too broad to distinguish the node once Algorithm and Projection are present.
domain_specific:feasible_region (related object). The method projects a linear feasible region; the region is the represented object, not the transformation procedure.

No structured dag_edges are installed in this working draft. The proposed working overlay must be independently checked against the live mixed graph before queue admission.

Relationships to Other Abstractions¶

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

Fourier–Motzkin Elimination → Algorithm → Function (Mapping)

Show alternative paths (2)

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Knowledge Space — 0.84
Big O Notation — 0.84
Generalized Semi-Infinite Programming — 0.83
Feature scaling — 0.83
Normal Order of an Arithmetic Function — 0.83

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

Not to Be Confused With¶

Gaussian elimination: equations, row operations, and equality solution spaces rather than inequality bounds and projected feasibility. Tell: are the inputs equations or ordered inequalities?
Simplex / network simplex: optimization by basis pivots rather than symbolic coordinate projection by complete bound pairing. Tell: is an objective optimized or a variable eliminated?
Variable substitution: uses a defining equality; Fourier–Motzkin handles two-sided inequality information even when no equality defines the variable. Tell: is there an equality that uniquely defines the removed variable?
Farkas' lemma: characterizes implication or infeasibility through nonnegative multipliers and can certify results, but it is not the same constructive one-variable all-pairs procedure. Tell: is the task a certificate or an explicit projected inequality system?
Cylindrical algebraic decomposition: much broader quantifier elimination for polynomial real algebra; correspondingly more complex machinery. Tell: are nonlinear polynomials and Boolean cells present?
Cooper elimination / Presburger arithmetic: integer linear arithmetic requires divisibility and modular information absent from ordinary real Fourier–Motzkin elimination. Tell: must integer congruences be preserved?
Vertex projection: projecting enumerated points or vertices may produce the same geometric image in a different representation. Fourier–Motzkin works directly on inequalities. Tell: is the input an H-representation or a vertex list?
Redundancy removal: an important companion operation that decides whether a generated constraint is implied. It controls the method's output but does not itself eliminate a variable. Tell: is a variable removed or only an implied inequality discarded?
Fourier transform: shares Fourier's name only. It decomposes functions into frequency components and has no lower/upper-bound pairing identity. Tell: are frequencies analyzed or inequality bounds paired?

References¶

[1] Schrijver, Alexander. Theory of Linear and Integer Programming. Wiley, 1986; paperback edition 1998. Provides standard polyhedral and linear-inequality treatment of projection, elimination, and feasibility. registry ↩a ↩b

[2] Eaves, B. Curtis, and Uriel G. Rothblum. “Dines–Fourier–Motzkin Quantifier Elimination and an Application of Corresponding Transfer Principles over Ordered Fields”. Mathematical Programming 53 (1992): 307–321. Establishes the ordered-field and quantifier-elimination setting. registry ↩a ↩b ↩c

[3] Monniaux, David. “A Quantifier Elimination Algorithm for Linear Real Arithmetic”. In Logic for Programming, Artificial Intelligence, and Reasoning, LNCS 5330 (2008): 243–257. States the positive/negative partition and pairwise cancellation rule and analyzes formula-size growth in linear-real quantifier elimination. registry ↩a ↩b ↩c ↩d ↩e

[4] Gattegno, Ido B., Ziv Goldfeld, and Haim H. Permuter. “Fourier–Motzkin Elimination Software for Information Theoretic Inequalities”. arXiv:1610.03990, 2016. Develops software for eliminating variables from information-theoretic inequality systems while exploiting Shannon-type inequalities to remove redundancies. registry ↩a ↩b ↩c

[5] Cheung, Kevin. “Fourier–Motzkin Elimination Method”. Carleton University MATH 5801 notes. Gives a worked construction of bound pairing and solution recovery for systems of linear inequalities. registry ↩