Linear images of polyhedra are polyhedra
ProvedLinearOptimization.polyhedron_linear_imagegeometrylinear-programmingpolyhedraprojection
(Corollary 2.5) Let be a polyhedron and let be an matrix. Then, the set
is also a polyhedron.
Preamble
import Definitions.Def_Polyhedron
open Matrix
/-- **Bertsimas & Tsitsiklis, Corollary 2.5 (p. 74).** The image `{Mx | x ∈ P}` of a polyhedron
under a linear map (given by a matrix `M`) is a polyhedron. -/
Formal statement
theorem LinearOptimization.polyhedron_linear_image {m n p : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(M : Matrix (Fin p) (Fin n) ℝ) :
∃ (m' : ℕ) (A' : Matrix (Fin m') (Fin p) ℝ) (b' : Fin m' → ℝ),
M.mulVec '' polyhedron A b = polyhedron A' b' := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 2.5, p. 74
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For all natural numbers , every real matrix , every , and every real matrix , the theorem asserts the existence of a natural number , a real matrix , and such that the image equals the polyhedron . In words: the image of a ""-form polyhedron under a linear map is again a ""-form polyhedron; the number of describing inequalities is existentially quantified with no bound. The statement covers the degenerate cases , , and an empty source polyhedron (whose image, the empty set, must be representable by some infeasible system ).
Human review
Confirmed by the mission captain (proposal self-audit).