Fourier–Motzkin elimination

Summary

Fourier–Motzkin elimination removes one variable from a system of linear inequalities, as Gaussian elimination does for equations. The new system has a solution exactly when the old one has, and its solutions are the projections of the old solutions. Repeating it decides whether a system of linear inequalities is solvable. It gives short proofs of Farkas' lemma and of the fact that projections of polyhedra are polyhedra. The number of inequalities can grow very fast, so it is mainly a theoretical tool.