# Why does the cost matrix need to be nonnegative when applying the Hungarian algorithm?

In the "Setting" section of the Wikipedia page for the Hungarian algorithm, it says:

"We are given a nonnegative $n×n$ matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that has minimum cost."

Why does the cost matrix have to be nonnegative?

• I bet in some step of the algorithm you have to take a minimum with respect to some of those values/sums of those values and if the numbers were negative, you could keep on adding a specific cost that the solution would always be getting better. – RGS Nov 30 '16 at 0:44
• if you get a problem with some negative entries, you add a constant to all the entries. This does not change the optimal assignment, – Will Jagy Nov 30 '16 at 1:06
• @WillJagy Thanks, I understand that. However, I would like to know why it is required (if it really is) for the cost matrix to be nonnegative rather than how to modify a matrix to make it satisfy the requirement. – user3731622 Dec 1 '16 at 1:12