I'm thinking about utilizing the Hungarian algorithm for a research problem. I need to better understand what's happening behinds the scenes. I'm utilizing the matrix version.
The algorithm proceeds first with a "Step 0" in which row/column minimums are subtracted out. It then proceeds with Steps 1 and 2, which repeat until a solution is found. See details here.
Here are some observations about the Hungarian algorithm that I'm trying to confirm:
It seems that Step 0 (the row/column subtractions) pins down at least one match that ends up in the final set of assignments. Once that's in the set, the algorithm never reconsiders the assignments made in Step 0.
I think the same is true for each iteration of Steps 1 and 2: Specifically, each interaction of Step 1+2 pins down at least one additional match that eventually ends up in the final assignment. Also: Once those are made, they are never un-done in later stages.
Are these intuitions correct? It would greatly help understand what's going on behind the scenes.
Observation 1 is true
Given a cost matrix $(a_{ij})$, the Hungarian algorithm computes potential vectors $(x_i), (y_j)$ such that $(b_{ij}) = (a_{ij} - x_i - y_j)$ is a nonnegative matrix containing a matching made of $0$s. Consider what step 0 does to the row $i$ containing the element $a_{ij}$ of the final matching with the smallest $y_j$: for every element $a_{ij'}$ in the row, $a_{ij'} \ge x_i + y_{j'} \ge x_i + y_j = a_{ij}$, so $a_{ij}$ will immediately become $0$.
Observation 2 is false
Here’s a counterexample. I’ve drawn boxes around elements of the final matching. Observe that the number of boxed $0$s sometimes decreases: $3, 3, 3, 2, 3, 4, 5, 6$.
$$\begin{bmatrix} \boxed{4} & 8 & 5 & \color{red}{0} & 8 & 8 \\ 3 & 5 & 2 & \color{red}{0} & \boxed{4} & 5 \\ 5 & 8 & 5 & \boxed{\color{red}{0}} & 8 & 8 \\ 3 & \boxed{4} & 1 & \color{red}{0} & 5 & 5 \\ \color{red}{0} & \color{red}{5} & \boxed{\color{red}{0}} & \color{red}{0} & \color{red}{4} & \color{red}{4} \\ \color{red}{1} & \color{red}{0} & \color{red}{1} & \color{red}{0} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{3} & 7 & 4 & \color{red}{0} & 7 & 7 \\ 2 & 4 & 1 & \color{red}{0} & \boxed{3} & 4 \\ 4 & 7 & 4 & \boxed{\color{red}{0}} & 7 & 7 \\ \color{red}{2} & \boxed{\color{red}{3}} & \color{red}{0} & \color{red}{0} & \color{red}{4} & \color{red}{4} \\ \color{red}{0} & \color{red}{5} & \boxed{\color{red}{0}} & \color{red}{1} & \color{red}{4} & \color{red}{4} \\ \color{red}{1} & \color{red}{0} & \color{red}{1} & \color{red}{1} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{2} & 6 & \color{red}{3} & \color{red}{0} & 6 & 6 \\ 1 & 3 & \color{red}{0} & \color{red}{0} & \boxed{2} & 3 \\ 3 & 6 & \color{red}{3} & \boxed{\color{red}{0}} & 6 & 6 \\ 2 & \boxed{3} & \color{red}{0} & \color{red}{1} & 4 & 4 \\ \color{red}{0} & \color{red}{5} & \boxed{\color{red}{0}} & \color{red}{2} & \color{red}{4} & \color{red}{4} \\ \color{red}{1} & \color{red}{0} & \color{red}{1} & \color{red}{2} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{\color{red}{1}} & 5 & \color{red}{3} & \color{red}{0} & 5 & 5 \\ \color{red}{0} & 2 & \color{red}{0} & \color{red}{0} & \boxed{1} & 2 \\ \color{red}{2} & 5 & \color{red}{3} & \boxed{\color{red}{0}} & 5 & 5 \\ \color{red}{1} & \boxed{2} & \color{red}{0} & \color{red}{1} & 3 & 3 \\ \color{red}{0} & 5 & \boxed{\color{red}{1}} & \color{red}{3} & 4 & 4 \\ \color{red}{1} & \color{red}{0} & \color{red}{2} & \color{red}{3} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{1} & 4 & 3 & \color{red}{0} & 4 & 4 \\ \color{red}{0} & \color{red}{1} & \color{red}{0} & \color{red}{0} & \boxed{\color{red}{0}} & \color{red}{1} \\ 2 & 4 & 3 & \boxed{\color{red}{0}} & 4 & 4 \\ \color{red}{1} & \boxed{\color{red}{1}} & \color{red}{0} & \color{red}{1} & \color{red}{2} & \color{red}{2} \\ \color{red}{0} & \color{red}{4} & \boxed{\color{red}{1}} & \color{red}{3} & \color{red}{3} & \color{red}{3} \\ \color{red}{2} & \color{red}{0} & \color{red}{3} & \color{red}{4} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{\color{red}{0}} & 3 & 2 & \color{red}{0} & 3 & 3 \\ \color{red}{0} & \color{red}{1} & \color{red}{0} & \color{red}{1} & \boxed{\color{red}{0}} & \color{red}{1} \\ \color{red}{1} & 3 & 2 & \boxed{\color{red}{0}} & 3 & 3 \\ \color{red}{1} & \boxed{\color{red}{1}} & \color{red}{0} & \color{red}{2} & \color{red}{2} & \color{red}{2} \\ \color{red}{0} & 4 & \boxed{1} & \color{red}{4} & 3 & 3 \\ \color{red}{2} & \color{red}{0} & \color{red}{3} & \color{red}{5} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{\color{red}{0}} & 2 & \color{red}{1} & \color{red}{0} & 2 & 2 \\ \color{red}{1} & \color{red}{1} & \color{red}{0} & \color{red}{2} & \boxed{\color{red}{0}} & \color{red}{1} \\ \color{red}{1} & 2 & \color{red}{1} & \boxed{\color{red}{0}} & 2 & 2 \\ \color{red}{2} & \boxed{1} & \color{red}{0} & \color{red}{3} & 2 & 2 \\ \color{red}{0} & 3 & \boxed{\color{red}{0}} & \color{red}{4} & 2 & 2 \\ \color{red}{3} & \color{red}{0} & \color{red}{3} & \color{red}{6} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$ $$\begin{bmatrix} \boxed{\color{red}{0}} & \color{red}{1} & \color{red}{1} & \color{red}{0} & \color{red}{1} & \color{red}{1} \\ \color{red}{2} & \color{red}{1} & \color{red}{1} & \color{red}{3} & \boxed{\color{red}{0}} & \color{red}{1} \\ \color{red}{1} & \color{red}{1} & \color{red}{1} & \boxed{\color{red}{0}} & \color{red}{1} & \color{red}{1} \\ \color{red}{2} & \boxed{\color{red}{0}} & \color{red}{0} & \color{red}{3} & \color{red}{1} & \color{red}{1} \\ \color{red}{0} & \color{red}{2} & \boxed{\color{red}{0}} & \color{red}{4} & \color{red}{1} & \color{red}{1} \\ \color{red}{4} & \color{red}{0} & \color{red}{4} & \color{red}{7} & \color{red}{0} & \boxed{\color{red}{0}} \\ \end{bmatrix}$$