EconCSLib.LinearAlgebra.fm_feasible_of_feasible
theoremverifiedformalizationimported Lean
EconCSLib.LinearAlgebra.fm_feasible_of_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.fm_feasible_of_feasible (A : I โ Fin (n+1) โ ๐) (b : I โ ๐) (hfeas : IsFeasible A b) : IsFeasible (fmA A) (fmB A b)
- Formalizes
- EconCSLib, `EconCSLib.LinearAlgebra.fm_feasible_of_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.fm_feasible_of_feasible← EconCSLib.LinearAlgebra.fm_feasible_of_feasible (EconCSLib/Math/LinearAlgebra/FourierMotzkin.lean:194): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- 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.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.
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.fm_feasible_of_feasible (A : I โ Fin (n+1) โ ๐) (b : I โ ๐) (hfeas : IsFeasible A b) : IsFeasible (fmA A) (fmB A b) := by obtain โจx, hxโฉ := hfeas refine โจfun j => x j.castSucc, ?_โฉ intro idx -- Split each original row sum into first n + last entry. have hsplit : โ i : I, rowEval A i x = (โ j : Fin n, A i j.castSucc * x j.castSucc) + A i (Fin.last n) * x (Fin.last n) := by intro i rw [rowEval, Fin.sum_univ_castSucc] rcases idx with k | โจp, qโฉ ยท -- Zero-row pass-through. have hk := hx k.val rw [hsplit, k.property, zero_mul, add_zero] at hk simp only [fmB_inl, rowEval_def, fmA_inl] exact hk ยท -- Combined-row inequality. have hp := hx p.val have hq := hx q.val rw [hsplit] at hp hq have hฮฑq_pos : 0 < -A q.val (Fin.last n) := by linarith [q.property] have hฮฒp_pos : 0 < A p.val (Fin.last n) := p.property -- ฮฑq ยท (hp stripped) + ฮฒp ยท (hq stripped) gives the combined inequality. have hcomb : (-A q.val (Fin.last n)) * b p.val + A p.val (Fin.last n) * b q.val โค (-A q.val (Fin.last n)) * (โ j : Fin n, A p.val j.castSucc * x j.castSucc) + A p.val (Fin.last n) * (โ j : Fin n, A q.val j.castSucc * x j.castSucc) := by have hp_strip : b p.val - A p.val (Fin.last n) * x (Fin.last n) โค โ j : Fin n, A p.val j.castSucc * x j.castSucc := by linarith have hq_strip : b q.val - A q.val (Fin.last n) * x (Fin.last n) โค โ j : Fin n, A q.val j.castSucc * x j.castSucc := by linarith nlinarith [mul_le_mul_of_nonneg_left hp_strip hฮฑq_pos.le, mul_le_mul_of_nonneg_left hq_strip hฮฒp_pos.le] simp only [fmB_inr, rowEval_def, fmA_inr] -- Distribute the sum in the goal RHS. have hRHS : (โ j : Fin n, ((-A q.val (Fin.last n)) * A p.val j.castSucc + A p.val (Fin.last n) * A q.val j.castSucc) * x j.castSucc) = (-A q.val (Fin.last n)) * (โ j : Fin n, A p.val j.castSucc * x j.castSucc) + A p.val (Fin.last n) * (โ j : Fin n, A q.val j.castSucc * x j.castSucc) := by rw [Finset.mul_sum, Finset.mul_sum, โ Finset.sum_add_distrib] refine Finset.sum_congr rfl ?_ intro j _ ring rw [hRHS] exact hcomb