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$
2

2 Answers 2

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$
2
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .