4
$\begingroup$

Call two matrices "swap-equivalent" if one matrix can be transformed into the other via some sequence of row swaps and column swaps.

I'd like a computationally efficient algorithm that can transform a matrix into a canonical swap-equivalent matrix (so that all members of an equivalence class give the same result).

I've been first sorting the rows and then sorting the columns, using the following comparison function:

A list (row or column) $a$ is considered greater than a list $b$ if when sorted, $a$ comes before $b$ lexicographically, with ties broken by the lexicographic order of (unsorted) $a$ and $b$.

For example:

$\begin{matrix} 1 & 0 & 3 \\ 0 & 4 & 2 \\ 2 & 0 & 4 \end{matrix}$

becomes

$\begin{matrix} 2 & 0 & 4 \\ 0 & 4 & 2 \\ 1 & 0 & 3 \end{matrix}$

after sorting the rows, and then

$\begin{matrix} 4 & 0 & 2 \\ 2 & 4 & 0 \\ 3 & 0 & 1 \end{matrix}$

after sorting the columns.

This is efficient enough, but I haven't been able to figure out if it's right.

EDIT: Turns out this doesn't work.

$\begin{matrix} 2 & 1 & 0 \\ 1 & 0 & 2 \end{matrix}$

gets transformed to

$\begin{matrix} 2 & 0 & 1 \\ 1 & 2 & 0 \end{matrix}$

but

$\begin{matrix} 2 & 1 & 0 \\ 0 & 2 & 1 \end{matrix}$

gets transformed to

$\begin{matrix} 1 & 2 & 0 \\ 2 & 0 & 1 \end{matrix}$

even though they're equivalent.

Sorting the rows again fixes it though. Is that enough? Maybe iterate until a stable state is reached?

$\endgroup$
4
$\begingroup$

The question linked to by David Speyer in a comment has an answer that points out that this is equivalent to finding a canonical representation of a bipartite graph, since the matrices can be viewed as biadjacency matrices. This problem is not known to be in P. However, the nauty program can usually find such a form quickly.

$\endgroup$
1
$\begingroup$

Determining whether two matrices are swap-equivalent is the graph isomorphism problem for bipartite graphs -- which is asymptotically as hard as the graph isomorphism problem for general graphs (it is GI-complete). There is no known algorithm with a worst-case polynomial running time, but there are algorithms that empirically seem to be efficient on most graphs you're likely to run into in practice.

You are asking for something a bit more: an algorithm to compute a representative for the equivalence class, i.e., a canonical form for the graph. This is at least as hard as the graph isomorphism problem, and potentially harder. However, the existing tools for graph isomorphism also tend to provide a way to do this as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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