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


$$ 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.

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 30, 2017 at 21:44

1 Answer 1


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

  • $\begingroup$ arrays can be up to 100x100 $\endgroup$
    – Alter
    Commented Jun 30, 2017 at 22:42
  • 2
    $\begingroup$ Your problems are tiny compared to the sizes of assignment problems that are frequently solved. $\endgroup$ Commented Jul 1, 2017 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.