Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
Bhat, Kabekode VS. "An algorithm for matrix symmetrization." Journal of the Franklin Institute 312.1 (1981): 89-93. –  Waldemar Jan 23 at 10:04
    
Thanks! This is what I am looking for. –  sweehong Jan 23 at 10:26

1 Answer 1

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|improve this answer
    
Thanks! This is really helpful. –  sweehong Jan 23 at 11:53

Your Answer

 
discard

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.