§1, Step 2, second bracket, p. 34 — after the exchange the starred zeros are independent and larger by one
ProvedMunkresAlg.Assignment.step2_starred_countassignment-problemaugmenting-pathinvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix, let be a state reachable by Munkres' algorithm from that is at Step 2, and let be the state after the Step 2 move (unstar each starred zero of the sequence, star each primed zero of the sequence, reset the marks). Then the starred zeros of form a set of independent zeros of the matrix of , and
Each pass through Step 2 therefore adds one independent zero; as there can be at most , Step 2 occurs at most times in a run.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Step 2, second bracket, p. 34: after exchanging stars and primes along the sequence, the
starred zeros are independent zeros and there is one more of them. -/
theorem step2_starred_count {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s t : State n)
(z₀ : Fin n × Fin n) (hs : Reachable A s) (hph : s.phase = Phase.step2 z₀)
(hst : Step s t) :
IsIndepZeros t.A t.starred ∧ t.starred.card = s.starred.card + 1 := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 34, §1, Step 2, second bracket
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.