Lemma 6.5.5 — a finitely generated cone is a finite union of primitive cones
ProvedMatousekLP.Duality.cone_eq_union_primitiveconesconvex-geometryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be the convex cone generated by finitely many vectors , i.e. the set of their nonnegative linear combinations. Then there are finitely many primitive cones in (each generated by at most linearly independent vectors) with
Combined with Lemma 6.5.4 and the closedness of finite unions of closed sets, this yields Lemma 6.5.3: every finitely generated convex cone is closed.
Formalization Note The primitive cones are indexed by Fin N for some natural number N; since , necessarily . The generators of the primitive cones are arbitrary vectors of , as in the book's statement.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Duality_Cones
Formal statement
namespace MatousekLP.Duality
/-- Matoušek & Gärtner, Lemma 6.5.5 (p. 97): the convex cone `C` in `ℝ^m` generated by finitely
many vectors `a₁, …, aₙ` is the union of finitely many primitive cones `P₁, …, P_N`. -/
theorem cone_eq_union_primitive {m n : ℕ} (a : Fin n → EuclideanSpace ℝ (Fin m)) :
∃ (N : ℕ) (P : Fin N → Set (EuclideanSpace ℝ (Fin m))),
(∀ j, IsPrimitiveCone (P j)) ∧ coneGen a = ⋃ j, P j := by sorry
end MatousekLP.Duality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 97, Lemma 6.5.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.