finding the minimum number of lines to cover all zeros in an assignment problem I have been trying to follow the following steps to find the minimum number of horizontal and vertical lines that cover all the zeros in an assignment problem using Hungarian method:
Tick all unassigned rows.
If the ticked row has zeros, then tick the corresponding column.
Within the ticked column, if there is an assignment, then tick the corresponding row.
Draw a line through each un-ticked row and ticked column.
Repeat for each unassigned row.
Then find Theta (which is the smallest uncovered value)
The problem is when I do that, I still have zeros uncovered! causing Theta to be zero and go to an infinite loop!
The question is :
$$
        \begin{matrix}
        2 & 9 & 2 & 7 & 1 \\
        6 & 8 & 7 & 6 & 1 \\
        4 & 6 & 5 & 3 & 1 \\
        4 & 2 & 7 & 3 & 1 \\
        5 & 3 & 9 & 5 & 1 \\
        \end{matrix}
$$
After subtracting the row minimum from the corresponding row and column minimum from the corresponding column i got :
$$
        \begin{matrix}
        0 & 7 & 0 & 4 & 0 \\
        4 & 6 & 5 & 3 & 0 \\
        2 & 4 & 3 & 0 & 0 \\
        2 & 0 & 5 & 0 & 0 \\
        3 & 1 & 7 & 2 & 0 \\
        \end{matrix}
$$
Now when i used the algorithm given above for covering all the zeros i got:
$$
        \begin{matrix}
        \color{red}{0} & \color{red}{7} & \color{red}{0} & \color{red}{4} & \color{red}{0} \\
        4 & 6 & 5 & 3 & \color{red}{0} \\
        \color{red}{2} & \color{red}{4} & \color{red}{3} & \color{red}{0} & \color{red}{0} \\
        \color{red}{2} & \color{red}{0} & \color{red}{5} & \color{red}{0} & \color{red}{0} \\
        3 & 1 & 7 & 2 & \color{red}{0} \\ 
        \end{matrix}
$$
Red rows and columns represent the ones covered (found according to the above steps).
After this i added and subtracted $1$ from the relevant positions to get the following matrix:
$$
        \begin{matrix}
        0 & 7 & 0 & 4 & 1 \\
        3 & 5 & 4 & 2 & 0 \\
        2 & 4 & 3 & 0 & 1 \\
        2 & 0 & 5 & 0 & 1 \\
        2 & 0 & 6 & 1 & 0 \\
        \end{matrix}
$$
Using the same method given above for covering all zeros i got the following matrix:
$$
        \begin{matrix}
        \color{red}{0} & \color{red}{7} & \color{red}{0} & \color{red}{4} & \color{red}{1} \\
        3 & \color{red}{5} & 4 & 2 & \color{red}{0} \\
        \color{red}{2} & \color{red}{4} & \color{red}{3} & \color{red}{0} & \color{red}{1} \\
        2 & \color{red}{0} & 5 & \color{blue}{0} & \color{red}{1} \\
        2 & \color{red}{0} & 6 & 1 & \color{red}{0} \\
        \end{matrix}
$$
I don't understand why one zero is being left out (colored blue) ?
I figured that instead of striking out the third column if i striked out the fourth column then i would get an optimal solution.
But i don't understand why this doesn't happen, using the steps given above?
Where have i gone wrong ?
Any help would be appreciated.

The method given by you for covering all the zeros with minimum lines works in the later matrix as well.
If after assigning, we start with unassigned rows then the process goes as follows.
The 5th row is ticked.
Then 2nd and 5th column are ticked.
Then 2nd and 4th row are ticked as they have assignments.
Then 4th column is ticked as it has a 0 in the 4th row.
Then 3rd row are ticked as it has assignment.
This gives 1st row un-ticked and 2nd, 4th and 5th row ticked through which minimum lines can be drawn to cover all the zeroes.
