# Linear Assignment Problem and Hungarian Algorithm

## Theorem

> If a number is added to/subtracted from a whole row/column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.

### Proof

Assume we are minimizing the total cost.

* $C$: Cost matrix
* $c_{i,j}$: Its elements
* $C^{i,j}$: Submatrix by deleting $i$-th row and $j$-th column
* $C'$: $C$ after adding a constant to its $0$-th row

WLOG, assume $c_{0,0}$ is in the optimal assignment.
We want to proof that adding a constant to the $0$-th row retains the optimal assignment. Let's name the resulted matrix as $C'$

We then have:
$$c_{0,0} + \text{mincost}(C^{0,0}) \leq c_{0,j} + \text{mincost}(C^{0,j})$$
Obviously,
$$(c_{0,0} + \text{const}) + \text{mincost}(C^{0,0}) \leq (c_{0,1} + \text{const}) + \text{mincost}(C^{0,1})$$
i.e.,
$$c'_{0,0} + \text{mincost}(C'^{0,0}) \leq c'_{0,j} + \text{mincost}(C'^{0,j})$$
So, for $C'$, $c'_{0,0}$ is including in its optimal assignment.
The identical remaining submatrices $C^{0,0} = C'^{0,0}$ will trivially have the same optimal assignment.
As a conclusion, $C$ and $C'$ have the same optimal assignment. The same proof applies to every row/column.

:::danger
TODO:

prove that Hungarian algorithm tries all the case!!!
:::

https://en.wikipedia.org/wiki/Hungarian_algorithm#Proof_that_the_algorithm_makes_progress