EconCSLib.LinearAlgebra.reduced_pair_ineq
theoremverifiedformalizationimported Lean
EconCSLib.LinearAlgebra.reduced_pair_ineq
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.reduced_pair_ineq {A : I โ Fin (n+1) โ ๐} {b : I โ ๐} {x' : Fin n โ ๐} (hx' : โ idx, fmB A b idx โค rowEval (fmA A) idx x') (p : PosRows A) (q : NegRows A) : (b p.val - โ j : Fin n, A p.val j.castSucc * x' j) / A p.val (Fin.last n) โค (b q.val - โ j : Fin n, A q.val j.castSucc * x' j) / A q.val (Fin.last n)
- Formalizes
- EconCSLib, `EconCSLib.LinearAlgebra.reduced_pair_ineq`
- 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.reduced_pair_ineq← EconCSLib.LinearAlgebra.reduced_pair_ineq (EconCSLib/Math/LinearAlgebra/FourierMotzkin.lean:259): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- 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.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.
- Used by 1
- EconCSLib.LinearAlgebra.feasible_of_fm_feasibleEconCSLib.LinearAlgebra.feasible_of_fm_feasible
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.reduced_pair_ineq {A : I โ Fin (n+1) โ ๐} {b : I โ ๐} {x' : Fin n โ ๐} (hx' : โ idx, fmB A b idx โค rowEval (fmA A) idx x') (p : PosRows A) (q : NegRows A) : (b p.val - โ j : Fin n, A p.val j.castSucc * x' j) / A p.val (Fin.last n) โค (b q.val - โ j : Fin n, A q.val j.castSucc * x' j) / A q.val (Fin.last n) := by have h_pq := hx' (Sum.inr (p, q)) simp only [fmB_inr, rowEval_def, fmA_inr] at h_pq -- Distribute the sum in h_pq's RHS. have hdist : (โ 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) = (-A q.val (Fin.last n)) * (โ j : Fin n, A p.val j.castSucc * x' j) + A p.val (Fin.last n) * (โ j : Fin n, A q.val j.castSucc * x' j) := by rw [Finset.mul_sum, Finset.mul_sum, โ Finset.sum_add_distrib] refine Finset.sum_congr rfl ?_ intro j _ ring rw [hdist] at h_pq -- h_pq : (-A q last) ยท b p + A p last ยท b q โค (-A q last) ยท ฮฃp + A p last ยท ฮฃq have hฮฒp : 0 < A p.val (Fin.last n) := p.property have hฮฑq : 0 < -A q.val (Fin.last n) := by linarith [q.property] have hAql_neg : A q.val (Fin.last n) < 0 := q.property have hAql_ne : A q.val (Fin.last n) โ 0 := ne_of_lt hAql_neg -- Convert U_q's denominator (negative) to a positive form. set sumP := โ j : Fin n, A p.val j.castSucc * x' j with hsumP_def set sumQ := โ j : Fin n, A q.val j.castSucc * x' j with hsumQ_def have hUq_flip : (b q.val - sumQ) / A q.val (Fin.last n) = -(b q.val - sumQ) / (-A q.val (Fin.last n)) := by rw [neg_div_neg_eq] rw [hUq_flip] rw [div_le_div_iffโ hฮฒp hฮฑq] -- Goal: (b p val - sumP) * (-A q val last) โค -(b q val - sumQ) * (A p val last) linarith