# Decide if a matrix is transposable

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?

• One way to interpret the problem alternatively is as in the proof of theorem 2.2 in this [paper][1] which recognizes whenever a matrix $A$ is transposable there is a correponding graph automorphism switching $V_1$ and $V_2$ on the edge-colored bipartite graph on $V_1\cup V_2$, where $V_1$ corresponds to the rows in $A$, $V_2$ the columns in $A$, and the labels corresponding to edges are just the matrix entries $A_{i,j}$. [1]: cambridge.org/core/services/aop-cambridge-core/content/view/… – Josiah Park Nov 14 '18 at 15:57
• You can check if the entries that appear in a row also appear in a column. However, that just rules out many easy infeasible cases. Gerhard "Unsure About Hard Infeasible Cases" Paseman, 2018.11.14. – Gerhard Paseman Nov 14 '18 at 15:58

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.