EconCSLib.LinearAlgebra.feasible_of_fm_feasible
theoremverifiedformalizationimported Lean
EconCSLib.LinearAlgebra.feasible_of_fm_feasible
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators in set_option linter.unusedSectionVars false in variable {π : Type*} [Field π] [LinearOrder π] [IsStrictOrderedRing π] in variable {I : Type*} [Fintype I] [DecidableEq I] {n : β} in theorem EconCSLib.LinearAlgebra.feasible_of_fm_feasible (A : I β Fin (n+1) β π) (b : I β π) (hred : IsFeasible (fmA A) (fmB A b)) : IsFeasible A b
- Formalizes
- EconCSLib, `EconCSLib.LinearAlgebra.feasible_of_fm_feasible`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.EconCSLib.LinearAlgebra.feasible_of_fm_feasible← EconCSLib.LinearAlgebra.feasible_of_fm_feasible (EconCSLib/Math/LinearAlgebra/FourierMotzkin.lean:304): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 14
- EconCSLib.LinearAlgebra.NegRowsRows where the last-column coefficient is strictly negative.
- EconCSLib.LinearAlgebra.PosRowsRows where the last-column coefficient is strictly positive.
- EconCSLib.LinearAlgebra.fmB_inlEconCSLib.LinearAlgebra.fmB_inl
- EconCSLib.LinearAlgebra.fmA_inrEconCSLib.LinearAlgebra.fmA_inr
- EconCSLib.LinearAlgebra.IsFeasiblePrimal feasibility of the system
A x β₯ b. - EconCSLib.LinearAlgebra.fmA_inlEconCSLib.LinearAlgebra.fmA_inl
- EconCSLib.LinearAlgebra.reduced_pair_ineqEconCSLib.LinearAlgebra.reduced_pair_ineq
- EconCSLib.LinearAlgebra.fmAReduced matrix coefficient.
- EconCSLib.LinearAlgebra.rowEval_defEconCSLib.LinearAlgebra.rowEval_def
- EconCSLib.LinearAlgebra.ZeroRowsRows where the last-column coefficient is zero.
- EconCSLib.LinearAlgebra.rowEvalEvaluate the LHS of row
iof the matrixA : I β Fin n β πat the pointx : Fin n β π. - EconCSLib.LinearAlgebra.fmBReduced right-hand side.
- EconCSLib.LinearAlgebra.fmB_inrEconCSLib.LinearAlgebra.fmB_inr
- EconCSLib.LinearAlgebra.FMRowIndexReduced row index after Fourier-Motzkin elimination of the last column.
- Used by 1
- EconCSLib.LinearAlgebra.theorem_of_alternative_auxEconCSLib.LinearAlgebra.theorem_of_alternative_aux
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BigOperators inset_option linter.unusedSectionVars false invariable {π : Type*} [Field π] [LinearOrder π] [IsStrictOrderedRing π] invariable {I : Type*} [Fintype I] [DecidableEq I] {n : β} intheorem EconCSLib.LinearAlgebra.feasible_of_fm_feasible (A : I β Fin (n+1) β π) (b : I β π) (hred : IsFeasible (fmA A) (fmB A b)) : IsFeasible A b := by obtain β¨x', hx'β© := hred classical -- Per-row lower/upper bounds (defined on subtypes). let L : PosRows A β π := fun p => (b p.val - β j : Fin n, A p.val j.castSucc * x' j) / A p.val (Fin.last n) let U : NegRows A β π := fun q => (b q.val - β j : Fin n, A q.val j.castSucc * x' j) / A q.val (Fin.last n) -- Choose x_last by case-split on emptiness of PosRows / NegRows. let x_last : π := if hPos : (Finset.univ : Finset (PosRows A)).Nonempty then Finset.univ.sup' hPos L else if hNeg : (Finset.univ : Finset (NegRows A)).Nonempty then Finset.univ.inf' hNeg U else (0 : π) refine β¨Fin.snoc x' x_last, ?_β© intro i -- Decompose original row evaluation: first n + last entry. have hsplit : rowEval A i (Fin.snoc x' x_last) = (β j : Fin n, A i j.castSucc * x' j) + A i (Fin.last n) * x_last := by rw [rowEval_def, Fin.sum_univ_castSucc] simp [Fin.snoc_castSucc, Fin.snoc_last] rcases lt_trichotomy (A i (Fin.last n)) 0 with hlt | heq | hgt Β· -- Negative last-column coefficient: i β NegRows. let hiN : NegRows A := β¨i, hltβ© have hUbound : x_last β€ U hiN := by by_cases hPos : (Finset.univ : Finset (PosRows A)).Nonempty Β· -- x_last = sup' L; need sup' L β€ U(hiN), i.e., β p, L p β€ U hiN. change (if h : _ then Finset.univ.sup' h L else if h' : _ then Finset.univ.inf' h' U else 0) β€ U hiN rw [dif_pos hPos] apply Finset.sup'_le intro p _ exact reduced_pair_ineq hx' p hiN Β· -- x_last = inf' U (NegRows nonempty since hiN exists). have hNeg : (Finset.univ : Finset (NegRows A)).Nonempty := β¨hiN, Finset.mem_univ _β© change (if h : _ then Finset.univ.sup' h L else if h' : _ then Finset.univ.inf' h' U else 0) β€ U hiN rw [dif_neg hPos, dif_pos hNeg] exact Finset.inf'_le _ (Finset.mem_univ hiN) have hUval : A i (Fin.last n) * U hiN = b i - β j : Fin n, A i j.castSucc * x' j := by show A i (Fin.last n) * ((b i - β j : Fin n, A i j.castSucc * x' j) / A i (Fin.last n)) = _ have : A i (Fin.last n) β 0 := ne_of_lt hlt field_simp have hmul : A i (Fin.last n) * U hiN β€ A i (Fin.last n) * x_last := mul_le_mul_of_nonpos_left hUbound hlt.le rw [hsplit] linarith Β· -- Zero last-column coefficient: i β ZeroRows. let hiZ : ZeroRows A := β¨i, heqβ© have h := hx' (Sum.inl hiZ) simp only [fmB_inl, rowEval_def, fmA_inl] at h rw [hsplit, heq, zero_mul, add_zero] exact h Β· -- Positive last-column coefficient: i β PosRows. let hiP : PosRows A := β¨i, hgtβ© have hPos : (Finset.univ : Finset (PosRows A)).Nonempty := β¨hiP, Finset.mem_univ _β© have hLbound : L hiP β€ x_last := by change L hiP β€ (if h : _ then Finset.univ.sup' h L else if h' : _ then Finset.univ.inf' h' U else 0) rw [dif_pos hPos] exact Finset.le_sup' _ (Finset.mem_univ hiP) have hLval : A i (Fin.last n) * L hiP = b i - β j : Fin n, A i j.castSucc * x' j := by show A i (Fin.last n) * ((b i - β j : Fin n, A i j.castSucc * x' j) / A i (Fin.last n)) = _ have : A i (Fin.last n) β 0 := ne_of_gt hgt field_simp have hmul : A i (Fin.last n) * L hiP β€ A i (Fin.last n) * x_last := mul_le_mul_of_nonneg_left hLbound hgt.le rw [hsplit] linarith