Run-time of Hungarian algorithm - matrix formulation 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?
However, I could not understand why it must end after $(n)$ iterations.


Because it is not true. 

Check the following matrices, which are the initial matrix, the matrix at the end of step 2, and the matrices at the end of step 5. Here the steps are explained as in the notes mentioned in the question.

[[1, 1, 1, 1, 1]
 [1, 2, 11, 11, 11]
 [1, 3, 4, 11, 11]
 [1, 4, 6, 7, 11]
 [1, 5, 8, 10, 11]]

[[0, 0, 0, 0, 0]
 [0, 1, 10, 10, 10]
 [0, 2, 3, 10, 10]
 [0, 3, 5, 6, 10]
 [0, 4, 7, 9, 10]]

[[0, 0, 0, 0, 0]
 [0, 0, 9, 9, 9]
 [0, 1, 2, 9, 9]
 [0, 2, 4, 5, 9]
 [0, 3, 6, 8, 9]]

[[0, 0, 0, 0, 0]
 [0, 0, 9, 9, 9]
 [0, 0, 1, 8, 8]
 [0, 1, 3, 4, 8]
 [0, 2, 5, 7, 8]]

[[0, 0, 0, 0, 0]
 [0, 0, 8, 8, 8]
 [0, 0, 0, 7, 7]
 [0, 1, 2, 3, 7]
 [0, 2, 4, 6, 7]]

[[0, 0, 0, 0, 0]
 [0, 0, 8, 8, 8]
 [0, 0, 0, 7, 7]
 [0, 0, 1, 2, 6]
 [0, 1, 3, 5, 6]]

[[0, 0, 0, 0, 0]
 [0, 0, 7, 7, 7]
 [0, 0, 0, 7, 7]
 [0, 0, 0, 1, 5]
 [0, 1, 2, 4, 5]]

[[0, 0, 0, 0, 0]
 [0, 0, 7, 6, 6]
 [0, 0, 0, 6, 6]
 [0, 0, 0, 0, 4]
 [0, 1, 2, 3, 4]]


So, the number of times step 5 can be executed can be as big as $\frac12(n-2)(n-1)$.