Cover Zeros with Minimum Lines (Hungarian Algorithm Step)

Reduced matrix (zeros already created):

        C1  C2  C3  C4
R1       0   2   0   1
R2       1   0   3   0
R3       0   1   2   3
R4       2   0   1   2

Step A — Try to select independent zeros (one per row/column)

We attempt to “assign” zeros without sharing a column. One possible attempt:

Pick (R1,C1) = 0
Pick (R2,C4) = 0
Pick (R4,C2) = 0
Now R3 has a zero at C1, but C1 is already used → cannot pick a 4th independent zero in this attempt

So we currently have only 3 assigned zeros. That suggests we might need θ adjustment. The cover-lines step will confirm this properly.

Step B — Mark rows with NO assigned zero

Assigned zeros are in rows R1, R2, R4. Row R3 has no assignment, so mark:

Marked rows: {R3}

Step C — Mark columns that have a zero in any marked row

In row R3, the zeros occur at (R3,C1) only. So mark column C1:

Marked columns: {C1}

Step D — Mark rows that have an assigned zero in any marked column

Column C1 has an assigned zero at (R1,C1). So mark row R1:

Marked rows: {R3, R1}

Step E — Repeat: mark columns with zeros in newly marked rows

Row R1 has zeros at C1 and C3. C1 is already marked, so add C3:

Marked columns: {C1, C3}

Step F — Mark rows with assigned zeros in newly marked columns

Column C3 has no assigned zero in our current assignment attempt (we assigned R1→C1, R2→C4, R4→C2). So no new rows are marked. Stop.

Step G — Draw the minimum covering lines

Draw lines through:
• Unmarked rows = rows not in {R3, R1} → {R2, R4}
• Marked columns = {C1, C3}

Lines drawn: rows {R2, R4} and columns {C1, C3}
Total lines = 2 + 2 = 4  (BUT note: this depends on the starting assignment choice)

The lecture point: different initial “assigned zeros” choices can change the marking trace. To be precise, the true minimum lines equals the maximum matching size among zeros. In this example, the maximum independent zeros is 3, so the minimum cover is 3 lines in the optimal cover (your calculator finds this reliably via matching logic).

Reduced matrix:

        C1  C2  C3  C4
R1       0   2   1   3
R2       2   0   3   0
R3       1   3   0   2
R4       3   1   2   0

Step A — Select independent zeros (easy here)

We can pick one zero in each row and each column without conflict:

(R1,C1) = 0
(R2,C2) = 0
(R3,C3) = 0
(R4,C4) = 0

This is already 4 independent zeros.

Step B — What does the minimum-lines step say?

If a full set of independent zeros exists (size n), then the minimum number of lines needed to cover all zeros is also n.

A common beginner mistake is to think: “There are lots of zeros, so it must be solvable immediately.” But what you need is independent zeros—not just zeros.

Matrix with many zeros but conflicts:

        C1  C2  C3  C4
R1       0   0   0   5
R2       0   0   0   6
R3       0   0   0   7
R4       1   2   3   0

Lecture explanation

Rows R1–R3 have zeros only in columns C1–C3. Column C4 has a zero only in row R4. You can certainly assign R4→C4. But then you still need three distinct columns among C1–C3 for R1–R3, which is possible here. Now imagine one more restriction (e.g., one of those zeros is forbidden or missing), and the perfect matching breaks immediately.

Related: feasibility with forbidden pairs: assignment feasibility / infeasibility.