# 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. Jun 30 '17 at 21:44
{"ft_lang_label":"__label__en","ft_lang_prob":0.7465695,"math_prob":0.9992071,"size":704,"snap":"2021-31-2021-39","text_gpt3_token_len":265,"char_repetition_ratio":0.11285714,"word_repetition_ratio":0.0,"special_character_ratio":0.39772728,"punctuation_ratio":0.026143791,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992663,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-18T11:19:29Z\",\"WARC-Record-ID\":\"<urn:uuid:3e21b4ee-de1b-4040-a0c8-187374a6600f>\",\"Content-Length\":\"169772\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:86274841-e4f5-4ab0-9935-58aba34d111b>\",\"WARC-Concurrent-To\":\"<urn:uuid:1647ef45-8849-4024-bfff-9fb762988412>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://scicomp.stackexchange.com/questions/27288/maximize-sumai-for-matrix-a-and-any-permutation-of-identity-matrix-i\",\"WARC-Payload-Digest\":\"sha1:B5HROGF2EUTDCCJKHAOOVSAKUX6BYZ34\",\"WARC-Block-Digest\":\"sha1:TEP7DYCDJMI6T57YTL4KGTW6JABDSDEG\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780056392.79_warc_CC-MAIN-20210918093220-20210918123220-00136.warc.gz\"}"}