The Assignment
Why It Works
The Hungarian method is not a visual trick; reductions preserve the ordering of complete assignments. The final zero assignment is therefore optimal for the original matrix. This lesson closes the certificate by comparing the result with brute force on the small example and by naming assignment as the one-to-one special case of transportation.
Reductions preserve order
Row and column reductions do not change which assignment is cheapest. Why: every complete assignment uses one entry from each row and one from each column. Subtracting a whole-row or whole-column constant therefore shifts every complete assignment by the same total, preserving the argmin exactly.
Brute-force check
The exact brute-force minimum over 6 permutations is 12. Why: the Hungarian result is checked against all assignments in this small example. The brute-force check is not how the method scales; it is a compact audit that the reductions preserved the true optimum here.
Method size
The Hungarian method is polynomial while brute force is factorial. Why: the method works through matrix reductions instead of testing every permutation. Conceptually, it exploits the zero structure created by safe row and column shifts instead of treating each complete matching as unrelated.
Diagram note
The assignment cells are recomputed by the Hungarian method and cross-checked by brute force. This is exact for the pinned square integer cost matrix. As a model, assignment is the zero-one one-to-one special case of transportation: each worker supplies one unit and each job demands one unit. Pixel positions are rounded for layout; every number shown is exact.