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?