For context this is for a room assigner for a house where each housemate ranks their favourite rooms 1st to Nth. The data is arranged in a matrix where each row represents a person and each column represents a room. The entries are the ranking score a particular person has given a particular room. The sorter finds the sum of the elements where each person has 1 room, which means each row and column has only one chosen element in the sum. The sorter finds the arrangements with the minimum sum to give the fairest room allocation.
The problem mathematically reduces to finding the arrangements of columns and rows which give the minimum trace.
for example
$$
\begin {pmatrix} & Rm1 & Rm2 \\ P1 & 2 & 1 \\ P2 & 1 & 2 \end {pmatrix}
$$ has trace 4. This would mean giving person 1 (row 1) room 1 (column 1), and person 2 room 2
but by swapping the rows or columns along with their labels we get
$$
\begin {pmatrix} & Rm1 & Rm2 \\ P2 & 1 & 2 \\ P1 & 2 & 1 \end {pmatrix}
$$
this has trace 2 and is the fairest arrangement. This corresponds to person 1 with room 2 and person 2 with room 1.
This case is trivial, but for N people in N rooms there are N! arrangements and I haven't found a way to be certain I have found the minimum trace and the best arrangements without brute force.
I have already written a python script which does this by brute forcing checking every permutation, but I want to know if there is an analytic solution to this problem.
My intuition is that we choose the permutations with the most '1s' in the sum or leading diagonal, then '2's and so on, but I don't know how to prove this. I also know the minimum estimate would be the sum of the minimum values of each column, but I think it can be smaller than the minimum trace.
Best Answer
This is called the assignment problem. There are polynomial-time algorithms for it, such as the Hungarian algorithm, and many library implementations, such as
scipy.optimize.linear_sum_assignment.