Let $M^0$ be a $n\times m$ matrix whose entries are natural numbers (including zero). Consider the following matrix score \begin{equation*} s(M)\triangleq \sum_{i=1}^{\min(n,m)} M_{ii} \end{equation*} where $M_{ii}$ is the element of row and column $i$ of the generic matrix $M$. I want to find the solution (score and optimal matrix) of the following optimization problem \begin{equation*} \max_{M\in \mathcal{M}^0} s(M) \end{equation*} where $\mathcal{M}_0$ is the space composed by all matrix obtained by permutating the columns of the given matrix $M_0$.
Example
Consider the following starting matrix \begin{equation*} M^0 \triangleq \left[\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right] \end{equation*} in this case the optimal matrix is \begin{equation*} M^* \triangleq \left[\begin{array}{cccc} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{array}\right] \end{equation*} with optimal score $s(M^*)=3$
Attempt 1 to solve the problem: brute force
A possible, but not so clever solution, for the current problem is brute force: just compute each possible permutation and then pick up the one with maximum score. The clear problem of this solution is its computational cost, that is in the order of $m!$. Hence, brute force can be used only for small values of $m$. Unfortunately, in my application typically $m$ can be in the order of $10^2$ or $10^3$, so brute force is unfeasable. Despite this fact, this solution is still usefull when $m$ is small because it can be used to prove the optimality of other approaches.
Attempt 2 to solve the problem: greedy optimization
Something clever is the following: build a "good" matrix $\hat{M}$ be forcing the diagonal elements $\hat{M}_{ii}$ to be large as possible. More precisely, the procedure to build $\hat{M}$ is given as follows.
- step 1: search in $M^0$ the column $M_{j}^0$, with $j\in\{1,\dots,m\}$, that maximizes its first component. Such column is the first column $\hat{M}_1$ of the proposed solution $\hat{M}$. \begin{equation*} \hat{M}_1 \triangleq \arg \max_{j\in\{1,\dots,m\}} M_{1j}^0 \end{equation*} In case of multiple optimal columns, just take it one randomly.
- step 2: remove from $M^0$ the column $\hat{M}_1$ and call the new matrix $M^1$. Now search in $M^1$ the column $M_j^1$, with $j\in\{1, \dots, m-1\}$, that maximes its second component. Such column is the second column $\hat{M}_2$ of the proposed solution $\hat{M}$. \begin{equation*} \hat{M}_2 \triangleq \arg \max_{j\in\{1,\dots,m-1\}} M_{2j}^1 \end{equation*} In case of multiple optimal columns, just take it one randomly.
- step 3: repeat until $\hat{M}$ has $m$ columns.
Now $\hat{M}$ requires the solution of $m-1$ trivial optimization problems, and so seems to feasible even when $m$ is not small. However the problem is that I'm not sure that $\hat{M}$ is optimal in a global sense.
Questions
- Is $\hat{M}$ optimal?
- Is there a non brute force algorithm that guarantees the optimality of the solution? If yes, is this one computational cheaper than my greedy algorithm?