Loomis.loomis_theorem
theoremverifiedformalizationimported Lean
Loomis Theorem [MFoGT, Theorem 2.5.1]. For any pair of matrices A B : I → J → ℝ with B entrywise positive, there exist mixed strategies x : Δ(I), y : Δ(J) and a value v : ℝ such that for every column j ∈ J and every row i ∈ I, $$ v \cdot (xB)_j \le (xA)_j, \qquad (Ay)_i \le v \cdot (By)_i. $$ The common value v = lamB0 A B = muB0 A B.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Loomis in open Finset BigOperators in set_option linter.unusedSectionVars false in variable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in theorem Loomis.loomis_theorem (A B : I → J → ℝ) (hB : IsPositive B) : ∃ (x : stdSimplex ℝ I) (y : stdSimplex ℝ J) (v : ℝ), (∀ j, v * xB B x j ≤ xA A x j) ∧ (∀ i, Ay A y i ≤ v * By B y i)
- Formalizes
- EconCSLib, `Loomis.loomis_theorem`
- 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.Loomis.loomis_theorem← Loomis.loomis_theorem (EconCSLib/Math/Minimax/Loomis.lean:826): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- Loomis.loomis_value_eqLoomis scalar equality: every finite positive-
Bmatrix pair overℝhas equal maxmin and minmax Loomis ratios. - Loomis.IsPositiveA matrix
B : I → J → ℝis entrywise positive if every entry is> 0. This is the hypothesis driving the general Loomis theorem, and… - Loomis.xBRow-vector product
(xB)_j = ∑ᵢ xᵢ Bᵢⱼ. - Loomis.xARow-vector product
(xA)_j = ∑ᵢ xᵢ Aᵢⱼ. - Loomis.AyColumn-vector product
(Ay)_i = ∑ⱼ Aᵢⱼ yⱼ. - Loomis.ByColumn-vector product
(By)_i = ∑ⱼ Bᵢⱼ yⱼ. - Loomis.lamB0Maxmin Loomis scalar
λ₀ = sup_x λ_aux(x). - Loomis.exists_xx_lamB0Attainment of
lamB0: there exists a mixed strategyxxwith(xA xx)_j ≥ lamB0 · (xB xx)_jfor every column. - Loomis.muB0Minmax Loomis scalar
μ₀ = inf_y μ_aux(y). - Loomis.exists_yy_muB0Attainment of
muB0: there exists a mixed strategyyywith(Ay yy)_i ≤ muB0 · (By yy)_ifor every row. - wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
- Loomis.loomis_value_eqLoomis scalar equality: every finite positive-
- Used by 1
- EconCSLib.LinearAlgebra.perron_frobeniusPerron-Frobenius for positive matrices [MFoGT, Section 2.8, Exercise 1(2)]. A square matrix with strictly positive entries has a…
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 Loomis inopen Finset BigOperators inset_option linter.unusedSectionVars false invariable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in/-- **Loomis Theorem** [MFoGT, Theorem 2.5.1]. For any pair of matrices `A B : I → J → ℝ` with `B` entrywise positive, there exist mixed strategies `x : Δ(I)`, `y : Δ(J)` and a value `v : ℝ` such that for every column `j ∈ J` and every row `i ∈ I`, $$ v \cdot (xB)_j \le (xA)_j, \qquad (Ay)_i \le v \cdot (By)_i. $$ The common value `v = lamB0 A B = muB0 A B`. -/theorem Loomis.loomis_theorem (A B : I → J → ℝ) (hB : IsPositive B) : ∃ (x : stdSimplex ℝ I) (y : stdSimplex ℝ J) (v : ℝ), (∀ j, v * xB B x j ≤ xA A x j) ∧ (∀ i, Ay A y i ≤ v * By B y i) := by obtain ⟨x, Hx⟩ := exists_xx_lamB0 A B hB obtain ⟨y, Hy⟩ := exists_yy_muB0 A B hB refine ⟨x, y, lamB0 A B, Hx, fun i => ?_⟩ rw [loomis_value_eq A B hB] exact Hy i