How to find a canonical member of an equivalence class of matrices under row and column swaps? 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?
 A: 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.
A: 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.
