§1, Step 3, pp. 34–35 — h exists and is positive; non-covered −h, twice-covered +h; 0* and 0′ stay zeros; n_{k+1} ≥ n_k
ProvedMunkresAlg.Assignment.step3_transformationassignment-problemdual-updateinvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let be a state reachable by Munkres' algorithm from that is at Step 3, with current matrix , covered rows and covered columns . Then there is a real with:
- , and is the smallest non-covered element: for some , and whenever , ;
- each starred and each primed zero is once-covered (lies in exactly one covered line);
and for every state reached from by the Step 3 move, with matrix :
- if is non-covered, if it is twice-covered, and if it is once-covered;
- every starred and every primed zero of is still a zero of ;
- , where and are the maximal numbers of independent zeros of and .
Part 1 rules out the algorithm getting stuck at Step 3, and part 5 is the monotonicity used in the finiteness argument.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Step 3, pp. 34–35: at Step 3 the smallest non-covered element `h` exists and is positive;
the transformation decreases each non-covered element by `h`, increases each twice-covered element
by `h` and leaves each once-covered element unaltered; each starred and primed zero is
once-covered and is still a zero afterwards; and `n_{k+1} ≥ n_k`. -/
theorem step3_transformation {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s : State n)
(hs : Reachable A s) (hph : s.phase = Phase.step3) :
∃ h : ℝ, 0 < h ∧ (∃ p, NonCovered s p ∧ s.A p.1 p.2 = h) ∧
(∀ q, NonCovered s q → h ≤ s.A q.1 q.2) ∧
(∀ p ∈ s.starred ∪ s.primed,
(p.1 ∈ s.rowCov ∧ p.2 ∉ s.colCov) ∨ (p.1 ∉ s.rowCov ∧ p.2 ∈ s.colCov)) ∧
∀ t, Step s t →
(∀ i j, i ∉ s.rowCov → j ∉ s.colCov → t.A i j = s.A i j - h) ∧
(∀ i j, i ∈ s.rowCov → j ∈ s.colCov → t.A i j = s.A i j + h) ∧
(∀ i j, (i ∈ s.rowCov ∧ j ∉ s.colCov) ∨ (i ∉ s.rowCov ∧ j ∈ s.colCov) →
t.A i j = s.A i j) ∧
(∀ p ∈ s.starred ∪ s.primed, t.A p.1 p.2 = 0) ∧
maxIndepZeros s.A ≤ maxIndepZeros t.A := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), pp. 34–35, §1, Step 3 (second paragraph and second bracket)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.