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.



Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?
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](http://cs.anu.edu.au/~bdm/papers/ColbournMcKaySymmetrizability.pdf).


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.


