Is there an efficient algorithm to check whether a matrix is symmetrizable using only permutation matrix?

Question

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.

Answer 1

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.

Answer 2

The problem can be solved via ILP by treating elements of $P$ as binary variables with constraints: $$\begin{cases} \sum_{i=1}^d P_{i,j} = 1 & \forall j\in[d],\\ \sum_{j=1}^d P_{i,j} = 1 & \forall i\in[d],\\ \sum_{k=1}^d P_{i,k}A_{k,j} = \sum_{k=1}^d P_{j,k}A_{k,i} & \forall i,j \in[d],\ i<j. \end{cases} $$

Here is a sample Sage code that constructs a random symmetric $01$-matrix of a given, randomly permutes its rows, and then tries to find a suitable $P$ that would permute it back into a symmetric matrix.

Answer 3

For many NP-complete problems, there is a heuristic algorithm that solves the problem in most cases. For NP-complete optimization problems, there is often a heuristic algorithm that gives a nearly optimal solution. These heuristic algorithms are often evolutionary algorithms or simulated annealing algorithms that either minimize or maximize some function.

Let $\|\cdot\|$ be any matrix norm, and if $g$ is a permutation, then let $\phi(g)$ denote its corresponding permutation matrix. Given a matrix $A$, define a loss function $L_A:S_n\rightarrow\mathbb{R}$ by letting $L_A(g)$ by letting $L_A(\phi(g))=\|\phi(g)A-(\phi(g)A)^T\|$.

The goal is to minimize the loss function $L_A$ through evolutionary computation or simulated annealing, and once one has $L_A(g)=0$, the matrix $\phi(g)A$ is symmetric. In these algorithms, one wants to mutate a permutation $g$ by replacing the permutation $g$ with $(a,b)\circ g$ where $(a,b)$ is a randomly selected transposition.