Claim in the proof of Theorem 5.8.1 — a cycle of the simplex method stays at one basic feasible solution
ProvedMatousekLP.Simplex.cycle_same_bfsLet be a real matrix of rank with , , . Suppose the simplex method, with any pivot rule, cycles: there are bases
where each arises from the feasible basis by a pivot step (an entering variable with positive coefficient in the last row of and a leaving variable satisfying the ratio rule (5.3)). Call a variable fickle if it enters the basis at some step of the cycle. Then there is a single feasible solution that is the basic feasible solution of every , , and for every fickle variable .
This is the first step of the proof that Bland's rule prevents cycling: it reduces a cycle to a sequence of degenerate pivots at one vertex.
Formalization Note Indices are 0-based. The cycle is a function on ; a fickle variable is an index for some . The standing assumption of §4.2 is a hypothesis.
import Mathlib import Definitions.Def_MatousekLP_Simplex_Tableau open Matrix Filter
namespace MatousekLP.Simplex
/-- Claim in the proof of Theorem 5.8.1 (p. 73), valid for any pivot rule. Suppose the simplex
method cycles: `B₀, B₁, …, B_k = B₀` (`k ≥ 1`) with each `B_{t+1}` obtained from `B_t` by a pivot
step. Then all bases of the cycle yield the same basic feasible solution `x`, and every fickle
variable (one that enters the basis at some step of the cycle) is `0` in `x`.
Standing assumption of §4.2 (p. 44): `n ≥ m` and `A` has rank `m`. -/
theorem cycle_same_bfs {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (hmn : m ≤ n) (hrank : A.rank = m) (k : ℕ) (hk : 1 ≤ k)
(Bs : ℕ → Finset (Fin n)) (hstep : ∀ t, t < k → SimplexStep A b c (Bs t) (Bs (t + 1)))
(hcycle : Bs k = Bs 0) :
∃ x : Fin n → ℝ, MatousekLP.BFS.IsFeasible A b x ∧
(∀ t, t ≤ k → IsBasicSolutionFor A b (Bs t) x) ∧
∀ t, t < k → ∀ j, j ∈ Bs (t + 1) → j ∉ Bs t → x j = 0 := by sorry
end MatousekLP.Simplex
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.