Theta (θ) Adjustment Step (Hungarian Algorithm)

Reduced matrix M (after row + column reduction):

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

Suppose the minimum-line cover of zeros uses 3 lines (so it is < n=4), and one valid minimum cover is:
• Covered rows: {R1, R2}
• Covered columns: {C2}
(This cover hits all zeros: zeros are at (R1,C1), (R2,C1), (R2,C4), (R3,C2), (R4,C2).)

Step 1 — Identify uncovered cells

A cell is uncovered if its row is not covered AND its column is not covered. Here, uncovered rows are {R3,R4} and uncovered columns are {C1,C3,C4}. So uncovered cells are in rows R3,R4 and columns C1,C3,C4:

Uncovered cells:
R3C1=1, R3C3=2, R3C4=2
R4C1=2, R4C3=3, R4C4=1

Step 2 — Compute θ = minimum uncovered value

θ = min{1,2,2,2,3,1} = 1

Step 3 — Apply the θ update rules

Covered rows = {R1,R2}; covered columns = {C2}. Therefore:

• Uncovered cells (rows R3,R4 with cols C1,C3,C4): subtract 1
• Intersection cells (covered rows R1,R2 with covered col C2): add 1 to (R1,C2) and (R2,C2)
• All others (single-covered): unchanged

Step 4 — Write the adjusted matrix M′

Uncovered cells subtract 1:

R3C1: 1→0
R3C3: 2→1
R3C4: 2→1
R4C1: 2→1
R4C3: 3→2
R4C4: 1→0

Intersections add 1:

R1C2: 2→3
R2C2: 3→4

Adjusted matrix M′:

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

Start from this reduced matrix:

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

Zeros at: (R1,C1), (R2,C1), (R3,C2), (R4,C2). This often covers with 2 lines (C1 and C2), which is < 4, so θ is needed. Take the minimum-line cover:
• Covered columns: {C1, C2}
• Covered rows: { } (none needed here)

Iteration 1 — Compute θ from uncovered cells

Uncovered rows: {R1,R2,R3,R4} (all rows, since no covered rows) Uncovered columns: {C3,C4} (since C1,C2 are covered) So uncovered cells are all entries in columns C3 and C4:

Uncovered values:
Col C3: R1=1, R2=2, R3=2, R4=1
Col C4: R1=2, R2=1, R3=1, R4=1
θ = min = 1

Iteration 1 — Adjust matrix

Covered rows: none ⇒ no intersections. Covered cols: {C1,C2}. So:
• Subtract θ from uncovered cells (columns C3,C4)
• Add θ to intersections (none)
• Single-covered cells (columns C1,C2) unchanged

After θ=1:

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

Now there are more zeros in C3 and C4. Re-run “cover zeros with minimum lines.” In many cases you can now cover with 3 lines (still < 4), so we do one more θ iteration.

Iteration 2 — Choose a minimum-line cover (deterministic for this lecture)

Use this minimum cover of zeros (3 lines):
• Covered rows: {R1}
• Covered columns: {C1, C2}
(This hits all zeros in this matrix.)

Iteration 2 — Compute θ from uncovered cells

Uncovered rows: {R2,R3,R4} Uncovered columns: {C3,C4} Uncovered cells are rows R2–R4 and cols C3–C4:

Uncovered values:
R2C3=1, R2C4=0
R3C3=1, R3C4=0
R4C3=0, R4C4=0
θ = min uncovered = 0

Lecture conclusion: The purpose of θ is to create uncovered zeros. If you already have uncovered zeros, re-do the cover step properly. In the calculator, the matching/cover computation ensures θ is computed from true uncovered nonzero entries when lines < n.

θ adjustment is not the final goal. The goal is to reach a matrix where a full set of independent zeros exists. Here is a reduced matrix (after some θ steps) where that is possible:

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

Step A — Find independent zeros (one per row/column)

A simple systematic approach:

1. Look for rows with a single zero (or the fewest zeros) and assign them first.
2. After assigning a zero in column j, you cannot use column j again.

Row-by-row:

R4 has a zero at C2 only (in this matrix) → assign R4→C2
Now column C2 is used.

R2 has a zero at C4 → assign R2→C4
Now column C4 is used.

R1 has a zero at C1 → assign R1→C1
Now column C1 is used.

R3 now must use remaining column C3? But R3 has zeros at C1 and C2 only in this matrix.
So this particular choice set fails → we need a different selection order.

Try a different selection:

Assign R3→C1 (zero)
Assign R4→C2 (zero)
Assign R2→C4 (zero)
Now R1 must use C3 or C? but R1 has zero at C1 only, so again conflict.

If you want the exact extraction behavior, use: Hungarian solver and review the assignment table produced after “lines = n”.