§1, Preliminaries, bracket, p. 33 — the zeros starred in the Preliminaries are independent
ProvedMunkresAlg.Assignment.prelim_starred_independentassignment-problemindependent-zerosinvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let be a start state of Munkres' algorithm for , obtained from the Preliminaries with any order of considering the zeros. Then the starred zeros of form a set of independent zeros of the reduced matrix of :
This is the base case of the invariant that the starred zeros are always a set of independent zeros.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Preliminaries, p. 33: the zeros starred by the Preliminaries are independent (and are
zeros of the reduced matrix), whatever order the zeros are considered in. -/
theorem prelim_starred_independent {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s : State n)
(hs : IsStart A s) :
IsIndepZeros s.A s.starred := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 33, §1, Preliminaries, bracket
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.