Lemma 7.1, p. 16 — on P_M, Mp̄ ≥ −λ ≥ −(B − 1)γ for a Z₊-matrix M
ProvedLinExchangeSP.ZPlus.lemma_7_1linear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedraz-matrix
Let be a square -matrix with , and let with . Put and . If satisfies , then
componentwise.
The lemma gives a lower bound on every constraint of ; the constraints of the approximating M2VPI system are nonnegative combinations of these lower bounds.
Formalization Note is the standing assumption of §7 (p. 16, ", "); it is needed for the second inequality. is needed for . The positive-diagonal assumption of §7 is not needed and is not imposed.
Preamble
import Mathlib import Definitions.Def_LinExchangeSP_ZPlus_Setting
Formal statement
namespace LinExchangeSP.ZPlus
/-- Lemma 7.1 (p. 16): for `M ∈ Z₊(t, t)`, `γ > 0` and `p̄ ≥ 0` with `Mp̄ ≤ γ`, every row satisfies
`M_i p̄ ≥ -λ_i ≥ -(B - 1)γ_i`, with `λ_i = ∑_{j ≠ i} γ_j` and `B = ∑ⱼ γⱼ / minᵢ γᵢ`. -/
theorem lemma_7_1 {t : ℕ} (ht : 0 < t) (M : Matrix (Fin t) (Fin t) ℚ) (hM : IsZPlus M)
(γ : Fin t → ℚ) (hγ : ∀ i, 0 < γ i) (p : Fin t → ℝ) (hp : ∀ j, 0 ≤ p j)
(hMp : ∀ i, rowVal M p i ≤ (γ i : ℝ)) :
∀ i, -((lam γ i : ℚ) : ℝ) ≤ rowVal M p i ∧
-((Bconst γ ht - 1) * (γ i : ℝ)) ≤ -((lam γ i : ℚ) : ℝ) := by sorry
end LinExchangeSP.ZPlus
Source
Garg & Végh, A strongly polynomial algorithm for linear exchange markets, arXiv:1809.06266v3, p. 16, Lemma 7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.