Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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


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

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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