# 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?

-
You might be interested in Young Tableux. Dictionary operations on Young Tableux matrices share a number of common properties with those for binary heaps. – user17794 Jun 18 '12 at 18:35
– David Speyer Jun 18 '12 at 23:00