Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.8.1 — the simplex method with Bland's rule never cycles

Proved
MatousekLP.Simplex.bland_never_cycles

by mikedeng1 · Oct 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1simplex-method

Let AAA be a real m×nm\times nm×n matrix of rank mmm with n≥mn\ge mn≥m, b∈Rmb\in\mathbb{R}^mb∈Rm and c∈Rnc\in\mathbb{R}^nc∈Rn, and consider the linear program "maximize cTxc^TxcTx subject to Ax=bAx=bAx=b, x≥0x\ge0x≥0". Bland's rule chooses as entering variable the variable with the smallest index among all nonbasic variables with a positive coefficient in the last row of the simplex tableau, and as leaving variable the one with the smallest index among all basic variables satisfying the ratio rule (5.3).

Then the simplex method with Bland's rule is always finite: there is no infinite sequence

B0→B1→B2→⋯B_0\to B_1\to B_2\to\cdotsB0​→B1​→B2​→⋯

in which every Bt+1B_{t+1}Bt+1​ is obtained from the feasible basis BtB_tBt​ by a pivot step following Bland's rule. Equivalently, since there are finitely many bases and each Bland step is determined by its starting basis, cycling is impossible.

Together with the optimality criterion and Lemma 5.6.1, the theorem shows that the simplex method, started from any feasible basis, ends after finitely many steps with an optimal basic feasible solution or a proof of unboundedness. The book notes that the duality theorem is an easy consequence.

Formalization Note Indices are 0-based, and "smallest index" compares variable indices. A Bland step is defined from the explicit tableau parameters of Lemma 5.5.1; it exists exactly when the tableau has some positive coefficient in the last row and some negative coefficient in the entering column, so the run stops precisely at an optimal or an unbounded tableau. The standing assumption of §4.2 (n≥mn\ge mn≥m, rank A=mA=mA=m) is a hypothesis.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Simplex_Tableau
open Matrix Filter
Formal statement
namespace MatousekLP.Simplex

/-- Theorem 5.8.1 (p. 73). The simplex method with Bland's pivot rule is always finite: there is
no infinite sequence `B₀, B₁, B₂, …` of bases in which every `B_{t+1}` is obtained from the feasible
basis `B_t` by a pivot step with Bland's rule. Equivalently (there are finitely many bases and
the Bland step is deterministic), cycling is impossible.
Standing assumption of §4.2 (p. 44): `n ≥ m` and `A` has rank `m`. -/
theorem bland_never_cycles {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
    (c : Fin n → ℝ) (hmn : m ≤ n) (hrank : A.rank = m) :
    ¬ ∃ Bs : ℕ → Finset (Fin n), ∀ t, BlandStep A b c (Bs t) (Bs (t + 1)) := by sorry

end MatousekLP.Simplex
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 73, Theorem 5.8.1 (Bland's rule stated on p. 72)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me