Can you determine if a matrix can be made symmetric in poly time?

Question

Is there an efficient way to tell if a square binary matrix can be made symmetric by reordering its rows and columns?

I can't see how graph isomorphism can be reduced to this problem so maybe there is a polynomial time algorithm?

Motivation

I would like to determine if there is a member of the equivalence class that is the adjacency matrix of an undirected graph.

Failed attempt

We can make a bipartite graph from any binary matrix by making a set of nodes for the rows and a set of nodes for the columns and connecting a row node i to a column node j iff there is a 1 at (i, j) in the matrix. We would then need some way of solving the problem using the bipartite graph.

• D.W.: Can you share anything about the motivation or application or context in which you encountered this problem?
• Gribouillis: I suppose we are talking about a boolean matrix?
• Simd: @Gribouillis Yes. I have added that.
• Gribouillis: If it can be made symmetric, it can be made symmetric by reordering only the rows.

Answer 1

(Not a computer scientist here) but here is an approach to eliminate many matrices. Starting with the bipartite graph $G$ that you described, let us define by induction a sequence of more and more refined partitions of the set of vertices $V(G)$, so that \begin{equation} \forall p\in {\mathbb N},\ \forall u\in V(G), u\in K_p(u)\subset V(G) \end{equation} We start with $\forall u\in V(G),\ K_0(u) = V(G)$. Let us define the multiset \begin{equation} M_p(u) = [K_p(v),\ v\in N(u)] \end{equation} where $N(u)$ is the open neighborhood of the vertex $u$ and \begin{equation} K_{p+1}(u) = \{v\in K_p(u): M_p(u) = M_p(v)\} \end{equation} By induction on $p$ we have $v\in K_p(u)\Leftrightarrow K_p(u) = K_p(v)$. If at any level a class $K_p(.)$ does not contain the same number of rows and columns, then the matrix cannot be made symmetric.

When all the classes stabilize, i.e when $\forall u\in V(G)\ K_{p+1}(u) = K_p(u)$, we can try to make the matrix symmetric by mapping the columns in a class to the rows of the same class. Only these rows can be mapped to these columns. This does not solve the problem completely but it gives a filter to eliminate many matrices. Also this filter is polynomial because before the classes stabilize, the number of classes increases at least by 1 at each step, and the number of classes in a partition is bounded by the number of vertices of the graph.

I created a toy implementation in Python, which actually found a valid permutation for the first 5x5 matrix that I tried: the following matrix can be made symmetric by rewriting its columns in the order $(4, 2, 1, 3, 5)$ \begin{equation} \begin{pmatrix} 1& 1& 0& 1& 1\cr 0& 1& 0& 1& 0\cr 0& 0& 1& 1& 0\cr 1& 0& 1& 0& 1\cr 0& 0& 1& 1& 1 \end{pmatrix} \end{equation}

Edit: I discovered that this algorithm is essentially the same as the 1-dimensional Weisfeiler-Leman graph isomorphism test.