Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.6.1 — a pivot step leads to a feasible basis, or detects unboundedness

Proved
MatousekLP.Simplex.pivot_step

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, c∈Rnc\in\mathbb{R}^nc∈Rn, and let B={k1<⋯<km}B=\{k_1<\dots<k_m\}B={k1​<⋯<km​} be a feasible basis with complement N={ℓ1<⋯<ℓn−m}N=\{\ell_1<\dots<\ell_{n-m}\}N={ℓ1​<⋯<ℓn−m​} and simplex tableau xB=p+QxNx_B=p+Qx_NxB​=p+QxN​, z=z0+rTxNz=z_0+r^Tx_Nz=z0​+rTxN​. Let xvx_vxv​, v=ℓβv=\ell_\betav=ℓβ​, be a nonbasic variable with rβ>0r_\beta>0rβ​>0 (an admissible entering variable).

  1. If xux_uxu​, u=kαu=k_\alphau=kα​, satisfies the leaving criterion
qαβ<0and−pαqαβ=min⁡{−piqiβ:qiβ<0},q_{\alpha\beta}<0\quad\text{and}\quad -\frac{p_\alpha}{q_{\alpha\beta}}=\min\Bigl\{-\frac{p_i}{q_{i\beta}}: q_{i\beta}<0\Bigr\},qαβ​<0and−qαβ​pα​​=min{−qiβ​pi​​:qiβ​<0},

then B′=(B∖{u})∪{v}B'=(B\setminus\{u\})\cup\{v\}B′=(B∖{u})∪{v} is again a feasible basis. 2. If no xux_uxu​ satisfies it, i.e. qiβ≥0q_{i\beta}\ge 0qiβ​≥0 for all iii, then the linear program is unbounded. More precisely, there is a family x(t)x(t)x(t), t∈Rt\in\mathbb{R}t∈R, of solutions of Ax=bAx=bAx=b with xv(t)=tx_v(t)=txv​(t)=t and all other nonbasic variables 000; x(t)x(t)x(t) is feasible for every t≥0t\ge0t≥0, and cTx(t)→∞c^Tx(t)\to\inftycTx(t)→∞ as t→∞t\to\inftyt→∞.

The lemma shows that the simplex method moves from feasible basis to feasible basis, and that it stops only at an optimal tableau or with a certificate of unboundedness.

Formalization Note Indices are 0-based; ppp, QQQ, rrr are the explicit parameters of Lemma 5.5.1. "No xux_uxu​ satisfies the criterion" is expressed as qiβ≥0q_{i\beta}\ge0qiβ​≥0 for all iii, which is equivalent because a minimum over a nonempty finite set is attained. The standing assumption of §4.2 is a hypothesis.

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

/-- Lemma 5.6.1 (p. 68). Let `B` be a feasible basis and let the entering variable `x_v`,
`v = ℓ_β`, have a positive coefficient `r_β` in the last row of `T(B)`.
(1) If the leaving variable `x_u`, `u = k_α`, satisfies (5.3), then `B′ = (B \ {u}) ∪ {v}` is
again a feasible basis.
(2) If no `x_u` satisfies the criterion (no row has `q_{iβ} < 0`), then the linear program is
unbounded: substituting `t` for `x_v` and `0` for the other nonbasic variables gives, for
every `t ≥ 0`, a feasible solution, and its objective value tends to `+∞` as `t → ∞`.
Standing assumption of §4.2 (p. 44): `n ≥ m` and `A` has rank `m`. -/
theorem pivot_step {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
    (c : Fin n → ℝ) (hmn : m ≤ n) (hrank : A.rank = m) (B : Finset (Fin n)) (hB : B.card = m)
    (hfeas : IsFeasibleBasisOf A b B hB) (β : Fin (n - m)) (hr : 0 < tableauR A c B hB β) :
    (∀ α : Fin m, IsEnteringLeaving A b c B hB β α →
        IsFeasibleBasis A b (pivotBasis B hB β α)) ∧
      ((∀ i : Fin m, 0 ≤ tableauQ A B hB i β) →
        IsUnbounded A b c ∧
        ∃ x : ℝ → Fin n → ℝ,
          (∀ t, A *ᵥ x t = b ∧ x t (lIdx B hB β) = t ∧
            ∀ j, j ≠ β → x t (lIdx B hB j) = 0) ∧
          (∀ t, 0 ≤ t → MatousekLP.BFS.IsFeasible A b (x t)) ∧
          Tendsto (fun t => c ⬝ᵥ x t) atTop atTop) := by sorry

end MatousekLP.Simplex
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 68, Lemma 5.6.1 (criteria on pp. 67–68, rule (5.3))
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