Take the 2-minute tour ×
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.

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?

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

1 Answer 1

up vote 1 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|improve this answer

Your Answer

 
discard

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.