MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Bhat, Kabekode VS. "An algorithm for matrix symmetrization." Journal of the Franklin Institute 312.1 (1981): 89-93. – Waldemar Jan 23 '14 at 10:04
Thanks! This is what I am looking for. – sweehong Jan 23 '14 at 10:26
up vote 8 down vote accepted

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.

share|cite|improve this answer
Thanks! This is really helpful. – sweehong Jan 23 '14 at 11:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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