§1, Step 3, first bracket, p. 34 — lines containing all the zeros are at least the maximal number of independent zeros
ProvedMunkresAlg.Assignment.lines_ge_independentassignment-problemindependent-zeroskonigp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix, and let be a set of rows and a set of columns such that every zero entry of lies in a row of or a column of . Then, with the maximal number of independent zeros of ,
Any set of lines containing all the zeros of a matrix has at least as many lines as the maximal number of independent zeros.
This is the easy half of König's theorem in matrix form; it is the step that turns the count "covered lines = starred zeros" at Step 3 into the optimality of both.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Step 3, first bracket, p. 34: any set of lines containing all the zeros of a matrix has
at least as many lines as the maximal number of independent zeros. -/
theorem lines_ge_independent {n : ℕ} (B : Matrix (Fin n) (Fin n) ℝ) (R C : Finset (Fin n))
(hcov : CoversZeros B R C) :
maxIndepZeros B ≤ R.card + C.card := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 34, §1, Step 3, first bracket, third sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.