Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1, Remark (2), p. 33 — replacing x_ij by x_ij − u_i − v_j does not change the optimal assignments

Proved
MunkresAlg.Assignment.remark_2_reduction

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

assignment-problemoptimal-assignmentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reduction

Let A=(xij)A=(x_{ij})A=(xij​) be a real n×nn\times nn×n matrix and let u1,…,unu_1,\dots,u_nu1​,…,un​ and v1,…,vnv_1,\dots,v_nv1​,…,vn​ be arbitrary real constants. Put yij=xij−ui−vjy_{ij}=x_{ij}-u_i-v_jyij​=xij​−ui​−vj​. For an assignment given by a permutation σ\sigmaσ of {1,…,n}\{1,\dots,n\}{1,…,n}, where σ(r)\sigma(r)σ(r) is the row assigned to column rrr, write cA(σ)=∑rxσ(r)rc_A(\sigma)=\sum_r x_{\sigma(r) r}cA​(σ)=∑r​xσ(r)r​. Then for every permutation σ\sigmaσ,

σ minimizes c(xij)  ⟺  σ minimizes c(yij).\sigma \text{ minimizes } c_{(x_{ij})} \iff \sigma \text{ minimizes } c_{(y_{ij})}.σ minimizes c(xij​)​⟺σ minimizes c(yij​)​.

That is, the solution of the assignment problem is not changed by subtracting constants from rows and columns.

This is the reason every matrix transformation of the algorithm (row and column reductions, and Step 3) preserves the solution: the final starred zeros are optimal for the original matrix.

Preamble
import Mathlib
import Definitions.Def_HeldWolfeCrowder_Assignment_Setting
Formal statement
namespace MunkresAlg.Assignment

/-- Munkres (1957), §1, Remark (2), p. 33: subtracting arbitrary row constants `u i` and column
constants `v j` from the matrix does not change the set of optimal assignments. -/
theorem remark_2_reduction {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (u v : Fin n → ℝ)
    (σ : Equiv.Perm (Fin n)) :
    HeldWolfeCrowder.Assignment.IsOptimalAssignment A σ ↔
      HeldWolfeCrowder.Assignment.IsOptimalAssignment (fun i j => A i j - u i - v j) σ := by sorry

end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 33, §1, Remark (2)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me