When tasked with finding the minimum sum of a matrix by selecting only one number from each row and column, we're delving into a classic problem in combinatorial optimization called the Assignment Problem. This article explains the problem, discusses the mathematical techniques used to solve it, and presents an example for clarity.

Understanding the Assignment Problem

The Assignment Problem in a matrix form can be described as follows: Given an $n \times n$ cost matrix, assign each row to a unique column such that the total cost is minimized, and each row and column in the matrix is exactly used once. This can be visualized as assigning jobs to workers such that the total cost or time of assignments is minimized.

Mathematical Formulation

Given a cost matrix $C = [c_{ij}]$, where $c_{ij}$ is the cost of assigning the $i^{th}$ row to the $j^{th}$ column, our goal is to find a permutation $\sigma$ of ${1, 2, ..., n}$ that minimizes the objective function:

$$\text{minimize} \sum\_{i=1}^{n} c\_{i,\sigma(i)}$$

This is subject to the condition that $\sigma$ is a permutation, thus reassures that each column and row is only selected once.

Hungarian Algorithm

One of the most efficient algorithms for solving the assignment problem is the Hungarian Algorithm. The method has a polynomial time complexity of $O(n^3)$ and is popular due to its efficiency and straightforward implementation. The cornerstone of this algorithm is transforming the matrix to uncover the optimal assignment using an iterative process of reducing the matrix:

1. Row Reduction: Subtract the smallest element in each row from all elements of that row.
2. Column Reduction: Subtract the smallest element in each column from all elements of that column.
3. Covering Zeros: Use the minimum number of lines to cover all zeros in the matrix.
4. Adjust the Matrix: If fewer than n lines are used, adjust the matrix by subtracting the smallest uncovered number from uncovered elements and adding it to elements at intersections of lines.
5. Repeat: Repeat the above steps until exactly $n$ lines are used to cover all zeros. The positions of zeros give the required assignments.

Example

Let's work through an example with the following $3 \times 3$ cost matrix $C$:

$$C = \begin{bmatrix} 4 & 1 & 3 \\ 2 & 0 & 5 \\ 3 & 2 & 2 \\ \end{bmatrix}$$

Step 1: Row Reduction

Subtract the smallest element of each row:

$$\begin{bmatrix} 3 & 0 & 2 \\ 2 & 0 & 5 \\ 1 & 0 & 0 \\ \end{bmatrix}$$

Step 2: Column Reduction

Subtract the smallest element of each column:

$$\begin{bmatrix} 2 & 0 & 2 \\ 1 & 0 & 5 \\ 0 & 0 & 0 \\ \end{bmatrix}$$

Step 3: Covering Zeros

Cover all zeros using a minimum number of lines:

• Two horizontal lines: one covering the first row zero and another covering the third row zero.

Step 4: Adjust the Matrix

Identify the smallest uncovered element (1), subtract it from all uncovered elements, and add it to elements at line intersections:

$$\begin{bmatrix} 1 & 0 & 2 \\ 0 & 0 & 4 \\ 0 & 1 & 0 \\ \end{bmatrix}$$

Repeat until a unique zero in each line is available. This results in the assignment: 1st row to 2nd column, 2nd row to 1st column, and 3rd row to 3rd column.

Conclusion

The minimum sum is obtained by following the derived assignments: $1 + 2 + 2 = 5$. It reflects the optimal way of assigning rows to columns to yield minimum costs.

Summary Table

The Hungarian algorithm provides a comprehensive process to efficiently resolve the assignment problem, thus making it a staple in various optimization tasks.