§1, p. 36 — after the Preliminaries each row and column contains a zero, and this never changes
ProvedMunkresAlg.Assignment.every_line_has_zeroassignment-probleminvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let be any state reachable by Munkres' algorithm from (including the start states), with current matrix . Then every row and every column of contains a zero:
The paper uses this fact in its operation count; it holds after the Preliminaries and is preserved by the Step 3 transformation.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, p. 36: after the Preliminaries each row and each column of the matrix contains at least
one zero, and this never changes. -/
theorem every_line_has_zero {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s : State n)
(hs : Reachable A s) :
(∀ i, ∃ j, s.A i j = 0) ∧ (∀ j, ∃ i, s.A i j = 0) := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 36, §1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.