# Maximize sum(AI) for matrix A and any permutation of identity matrix I

I have a random binary matrix $A$

$$A=\left[\begin{array}{c c c c c}0&0&0&0&1\\0&1&0&1&0\\1&1&1&1&0\\0&1&1&0&0\\1&0&1&1&1 \end{array}\right]$$ and a permutation of the identity matrix (denoted later as $I_p$) that will filter it. I want to find the best permutation $I_p$ (using row/column swapping) so as to maximize $\text{sum}(AI_p)$

• $\text{sum}(AI_p)$ is computed using element-wise sum and multiplication

ex.

$$A=\left[\begin{array}{c c c}0&1&0\\1&0&1\\1&0&0 \end{array}\right]$$

the maximum $\text{sum}(AI)$ would be from $$I_p= \left[\begin{array}{c c c}0& 1& 0\\0& 0 &1\\1 &0& 0 \end{array}\right]$$

I am currently checking every possible column permutation of $I$, which scales terribly.

• by sum(AI), I take it that you mean the element-wise sum of the element-wise product of A and I, right? If you use conventional matrix multiplication, then AI is just a permuted version of A and the sum of the elements won't change. – Brian Borchers Jun 30 '17 at 21:44

## 1 Answer

This is an assignment problem. There are lots of fast algorithms for these problems. How big are your instances?

• arrays can be up to 100x100 – Alter Jun 30 '17 at 22:42
• Your problems are tiny compared to the sizes of assignment problems that are frequently solved. – Brian Borchers Jul 1 '17 at 4:08