Proposition 4.2.2 — a basic feasible solution is determined by its basis
ProvedMatousekLP.BFS.bfs_unique_of_basislinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1polyhedra
Let be a real matrix of rank (so ), let , and let be an -element set such that the columns of are linearly independent. If and are feasible solutions of , with
then . That is, there is at most one feasible solution vanishing outside .
The proposition shows that there are at most basic feasible solutions and justifies calling a set that determines one a feasible basis.
Formalization Note The standing assumption of §4.2 (p. 44), and , is kept as a hypothesis, as on the page.
Preamble
import Mathlib import Definitions.Def_MatousekLP_BFS_EquationalForm open Matrix
Formal statement
namespace MatousekLP.BFS
/-- Proposition 4.2.2 (p. 45). Standing assumption of §4.2 (p. 44): `A` has `m` rows, `n`
columns, `n ≥ m`, and rank `m`. -/
theorem bfs_unique_of_basis {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (hmn : m ≤ n) (hrank : A.rank = m) (B : Finset (Fin n))
(hB : IsBasis A B) (x y : Fin n → ℝ)
(hx : IsFeasible A b x) (hxB : ∀ j, j ∉ B → x j = 0)
(hy : IsFeasible A b y) (hyB : ∀ j, j ∉ B → y j = 0) :
x = y := by sorry
end MatousekLP.BFS
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 45, Proposition 4.2.2 (standing assumption of §4.2 on p. 44)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.