11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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/… $\endgroup$ – Josiah Park Nov 14 '18 at 15:57
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Nov 14 '18 at 15:58
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.