Is there any known efficient algorithm (something that works better than brute-force algorithm) to check that given a $(0,1)$-$d \times d$ matrix $A$, is there a permutation matrix $P$ of the same size such that $PA$ is a symmetric matrix? I believe this question might have been done in the past (probably even for a more general matrix), however I can not find any literature that is connected to this problem.

  • 1
    $\begingroup$ Bhat, Kabekode VS. "An algorithm for matrix symmetrization." Journal of the Franklin Institute 312.1 (1981): 89-93. $\endgroup$ – Waldemar Jan 23 '14 at 10:04

The problem is NP-complete, see C. Colbourn and B. D. McKay, A correction to Colbourn's paper on the complexity of matrix symmetrizability, Information Processing Letters, 11 (1980) 96-97. Here is a scan.

Interestingly, if we ask instead whether there is a permutation matrix $P$ such that $PA$ is the transpose of $A$, that is equivalent to the graph isomorphism problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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