Theorem 2.7 — the dimension of a projection
ProvedDisjunctive.Polarity.projection_dimension_formuladisjunctive-programmingpolyhedraprojection
This is Theorem 2.7 of Balas's Disjunctive Programming: an exact formula for how projection affects dimension.
where is the number of variables projected out and is the rank of the -columns of 's equality subsystem. In particular, the projection is dimension-preserving, , exactly when , i.e. when has full column rank.
Formalization Note. EqRankA A B b is ; the theorem is stated for Poly2 A B b
nonempty, matching the book's standing assumption .
Preamble
import Mathlib import Definitions.Def_Disjunctive_Polarity_Projection import Definitions.Def_Disjunctive_Polarity_EqualitySubsystem
Formal statement
namespace Disjunctive.Polarity
/-- Theorem 2.7 (Balas §2.2.2, p. 29): the dimension of the projection of `Q` equals the
dimension of `Q`, minus the number of variables projected out, plus the rank of the `u`-columns
of `Q`'s equality subsystem. -/
theorem projection_dimension_formula {m p q : ℕ} (A : Matrix (Fin m) (Fin p) ℝ)
(B : Matrix (Fin m) (Fin q) ℝ) (b : Fin m → ℝ) (hQ : (Poly2 A B b).Nonempty) :
PolyDim (ProjOntoX (Poly2 A B b)) = PolyDim (Poly2 A B b) - (p : ℤ) + (EqRankA A B b : ℤ) := by sorry
end Disjunctive.Polarity
Source
Balas, Disjunctive Programming, Springer 2018, DOI 10.1007/978-3-030-00148-3, p. 29, Theorem 2.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.