Lemma 6.6.2 — solvability of Ax = b
ProvedMatousekLP.Duality.linear_system_solvable_ifflinear-algebralinear-systemsp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a real matrix and . The system has a solution if and only if every with also satisfies
This is the linear-algebra counterpart of the Farkas lemma (the entry " has a solution " of the book's table of variants); it is used in §6.6 to derive the Farkas lemma from minimally infeasible systems.
Formalization Note is written Aᵀ *ᵥ y = 0 and is y ⬝ᵥ b.
Preamble
import Mathlib
Formal statement
namespace MatousekLP.Duality
open Matrix
/-- Matoušek & Gärtner, Lemma 6.6.2 (p. 99): the system `Ax = b` has a solution if and only if
every `y ∈ ℝ^m` with `yᵀA = 0ᵀ` (written `Aᵀ *ᵥ y = 0`) also satisfies `yᵀb = 0`. -/
theorem linear_system_solvable_iff {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) :
(∃ x : Fin n → ℝ, A *ᵥ x = b) ↔ ∀ y : Fin m → ℝ, Aᵀ *ᵥ y = 0 → y ⬝ᵥ b = 0 := by sorry
end MatousekLP.Duality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 99, Lemma 6.6.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.