There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a spreadsheet.
The problem is, I could not understand the argument of why this algorithm, in its matrix formalism, is polynomial in $n$. In particular, in the above presentation, I got stuck trying to prove that Step 5 (page 13) is executed $O(n)$ times, or more generally, $O(poly(n))$ times.
In step 5, we subtract a number $x$ from each uncovered row, and then add the same $x$ to each covered column. Since in this step, the size of the covering is less than $n$, there are more uncovered rows than covered columns, so we subtract $x$ more times than we add $x$. Hence, the sum of all elements in the matrix strictly decreases each time. Since the sum always remains positive, the algorithm must eventually end.
However, I could not understand why it must end after $O(poly(n))$ iterations.
What am I missing in the above argument?