Prove that adding a constant to a min-cost assignment problem will not change optimal matching?

Question

Given an assignment problem

$\min \sum_{i=1}^{n} \sum_{j=1}^{n} C_{ij} X_{ij}$ subject to $X^t e =e, Xe=e, 0 \leq X \leq 1$

where $e=(1,1,1....1)^t$

I want to prove that if an add an arbitrary $\alpha$ to all elements of matrix C (i.e: replace C by $C + \alpha e e^T$), then it will not change the optimal matching obtained from original problem.

Intuitively, I think it won't change because if add $\alpha$ to every element, then the sum $\sum \sum C_{ij} X_{ij}$ increases by just $\alpha$. I was wondering if my intuition is correct, and if there's a better way to show it.

Answer 1

That's right, except that the sum increases by $n\alpha$, not $\alpha$. The point is that $$\sum_i \sum_j (C_{ij}+\alpha) X_{ij} - \sum_i \sum_j C_{ij} X_{ij} = \sum_i \sum_j \alpha X_{ij} = \alpha e^T X e = \alpha e^T e = n \alpha$$