Decide if a matrix is transposable

Question

A matrix $M$ is called transposable if it can be transformed into its transpose $M^t$ via row and column permutations.

Is there an efficient a way/algorithm to decide if a given matrix is transposable and gives us a certificate?

Answer 1

There are polynomial-time reductions from your problem to Graph Isomorphism and vice-versa.

As a quick definition, when I speak of 'subdividing' an edge, I mean to replace each edge $u, v$ with a path $u, w, v$ where $w$ is a new 'midpoint' vertex.

Transposable $\rightarrow$ GI:

Convert your $n \times n$ matrix into a bipartite graph $H$ with coloured edges (using up to $n^2$ colours). Then let $G_1$ be the graph obtained from $H$ by adjoining an extra vertex connected to each element of the vertex-class $V_1$, and analogously for $G_2$. Then the transposability of the original matrix is equivalent to finding an isomorphism between $G_1$ and $G_2$.

If you don't like colouring edges, you can subdivide each edge and hang a motif (let's say, a large complete graph whose number of vertices encodes the colour of the edge) from the newly-created midpoint.

GI $\rightarrow$ Transposable:

Suppose $G_1$ and $G_2$ are two graphs, such that we wish to determine whether they're isomorphic. This question is trivial if $G_1$ and $G_2$ have different number of vertices/edges, and also trivial if one of them is a complete graph, so assume they're incomplete graphs with equal numbers of vertices ($n$) and equal numbers of edges ($m$).

We now subdivide each edge in each of $G_1$ and $G_2$, obtaining two bipartite graphs $B_1, B_2$ each with $m + n$ vertices. We adjoin another vertex in the 'edge' class of each bipartite graph, connected to every vertex in the 'vertex' class, so that each $B_i$ now has vertex-classes of sizes $m + 1$ and $n$. Observe that each $B_i$ is connected, and has a distinguished vertex $v_i$.

Then we take the disjoint union of $B_1$ and $B_2$, and connect $v_1$ and $v_2$ by an edge. This graph is still bipartite, and has $m + n + 1$ vertices in each class. Its biadjacency matrix $M$ is a $0-1$ matrix which I claim is transposable if and only if $G_1$ and $G_2$ were isomorphic. Clearly the 'if' direction is true, so let's tackle the 'only if'.

Suppose $M$ is transposable. This induces an automorphism of the bipartite graph which exchanges the two parts. The distinguished vertices $v_1$ and $v_2$ must be exchanged (because they're the endpoints of the only bridge which, when cut, divides the graph into two equally-sized connected components). But this means that the automorphism gives us an isomorphism between the bipartite graphs $B_1$ and $B_2$, which are isomorphic only if the original graphs $G_1$ and $G_2$ were.

The result follows.