# Normalizing a matrix with row and column swapping

How do you canonicalize a matrix over column- and row-swap operations?

Or more specifically, does there exist a function f(M) such that f(M)=f(N) iff there is set of column- and row-swap operations (i.e. a permutation matrix A) on M that would transform M into N (i.e. AMA')?

@Coffeemath and I are discussing a few ways to isolate the problem:

Delete duplicate rows or columns
| 1  3  2  2  2 |      | 1  3  2  2 |
| 1  4  2  2  2 |  =>  | 1  4  2  2 |
| 0  1  0  1  1 |      | 0  1  0  1 |
| 0  1  1  0  0 |      | 0  1  1  0 |

Sorting rows based on lexicographical order of their multisets
| 1  3  2  2 |      |[0  1  0  1]|
| 1  4  2  2 |  =>  |[0  1  1  0]|
| 0  1  0  1 |      | 1  3  2  2 |
| 0  1  1  0 |      | 1  4  2  2 |
but... the remaining top two rows' order is undefined by this step

Sorting cols based on lexicographical order of their multisets
| 0  1  0  1 |      | 0 [0  1] 1 |
| 0  1  1  0 |  =>  | 0 [1  0] 1 |
| 1  3  2  2 |      | 1 [2  2] 3 |
| 1  4  2  2 |      | 1 [2  2] 4 |
but... the remaining mid two cols' order is undefined by this step

Recurse for any sections not defined:
| 0  0  1  1 |    | .  0  1  . |
| 0  1  0  1 | => | .  1  0  . |
| 1  2  2  3 |    | .  .  .  . |
| 1  2  2  4 |    | .  .  .  . |
but... the remaining mid two cols' order is undefined by this step

Recurse for any sections not defined:
| 0  0  1  1 |    | .  0  1  . |
| 0  1  0  1 | => | .  1  0  . |
| 1  2  2  3 |    | .  .  .  . |
| 1  2  2  4 |    | .  .  .  . |
but... the remaining mid two cols' order is undefined by this step

But how to handle this?
123456789
215347698 => This can be sorted into a specific pattern
341268957    But considering M(1,1) could be the "1" from
432179865    any of the nine rows, this becomes messy.
568912374
657891243    Note: not every matrix with rows & cols having
789524136    identical multisets and no duplicated
896735412    rows or columns must be a square matrix.
974683521

• I have the same question about binary matrices (specifically, I'd like to put an arbitrary $t\times n$ $d$-separable matrix into some "canonical" form). This problem is going to be difficult (but technically not NP-hard), because you can reduce the difficult problem of graph isomorphism to the problem of canonicalizing-and-then-comparing the graphs' adjacency matrices. (Thanks math.stackexchange.com/questions/2880751 for pointing that out!) Jan 7, 2020 at 17:33
• @Quuxplusone Are you dealing with the specific case where the multisets of each row are equal and the multisets of each column are equal? Jan 10, 2020 at 19:29
• "Are you dealing with the specific case where the multisets of each row are equal and the multisets of each column are equal?" No, I'm not. (What did you have in mind, though?) Jan 10, 2020 at 19:40

The following is only an idea, which maybe can be made into some kind of algorithm, and may need some tweaking...

Let $M$ be an $m \times n$ matrix. Each row of $M$ may be ordered as a multiset, and one may choose the lexicographically least of these and require that the first row of $f(M)$ should be that multiset (in order). Of course there may be several rows of $M$ whose multisets give this same "lex-least" multiset. One then looks at each such row and asks what the rows below it would look like if that row were placed on top, and column swaps were done in any way preserving the multiset.

Suppose e.g. two rows had lex-least multisets $[1,1,1,2,2,3].$ In $M$ itself these rows might appear as respectively $a=[1,1,2,1,2,3]$ and $b=[2,2,3,1,1,1].$ In either case we can initially do a row swap to put that row on top and then a column swap so the first row is now $[1,1,1,2,2,3].$ The appearance of rows beyond the first will likely be different depending on whether $a$ or $b$ was initially put on top, and we need do decide which to do.

Now note that irrespective to which of $a$ or $b$ was initially placed on top, the first three columns have the same number $1$ on top, and so these first three columns may be permuted among themselves without disturbing the first row $[1,1,1,2,2,3]$. Similarly one may permute the two rows underneath the two $2$'s. Then we can try each of rows $a$ and $b$, with all ways of permuting the columns not disturbing the pattern $[1,1,1,2,2,3]$ of the first row, and see for which one the rest of the matrix is lexicographically least, as a "tie-breaker" on whether to select row $a$ or row $b$ to swap initially to the top row.

What needs work is to choose in which sense the matrix from rows 2 on should be lexicographically ordered. I think it should be based on the fact that row swaps only should be done once row 1 is fixed by the initial single row swap and the column swaps to put it into order. On the other hand maybe one needs something more elaborate such as calling a part of the algorithm recursively.

Added: More detail is needed to see which of the initial rows having the minimal lexicographic multiset one should move to the top via one row swap and a choice of column swaps to put the chosen row 1 into lex order. Suppose the rows of $M$ having the min lex order are put into a collection $R$ of rows. For each $r$ in $R$ we do a subcalculation like the following: We form a copy of $M$ with row $r$ placed at the top via a row switch. We do some column swaps so now row 1 is in nondecreasing order.

Now any columns which are under a block of identical elements of row 1 may be permuted among themselves, still keeping row 1 as it is. Call these "allowable column swaps". Then for each row beyond the first, determine which of the allowable column swaps would put that row in least lex order. Choose the least among these now lex-ordered rows, and call that the "score" of the chosen $r$. We do the above for each candidate $r \in R,$ and see which $r$ gives us the minimal "score". This tells us which $r$ in $R$ we should switch to the top, and also which column swaps to carry out to put the now chosen row 1 into lex order.

I think now that we have row 1 chosen and in order, the same kind of procedure can be used to get row 2, only now we have restricted all column swaps to those keeping row 1 in its (fixed by now) lex order. It may not be the case that say row 2 is in lex order, only that each of its substrings under a constant block from row 1 is in lex order.

• This is a good start. The "compare multisets lexicographically" is a clear first step as well as the trivial step of removing duplicate rows (actual duplicates, not duplicate from the multiset), and recursing into the region where R/C have the same score. Feb 18, 2014 at 16:34
• The remaining part: Does [0 1; 1 0] or [1 0; 0 1] come first lexicographically, and how would we differentiate it in general? Feb 18, 2014 at 16:35
• I'd say by top row it would be [0 1; 1 0] first. But note if both were second and third rows under a first row which (for one of its choices) began with [0,0,...] then since further rows can be switched and also columns 1, 2 we should look at these as the same, since either could be obtained via row/column switches not involving a re-switch of the first row. Feb 18, 2014 at 20:03
• @FullDecent I just added some more ideas about choosing which row to initially switch to row 1, and something about once this is done how it restricts further manipulations of rows below the first. Still work to be done, and maybe at least some pseudocode. Subgoal: to give a description of what a matrix would look like for which $f(M)=M$, i.e. what type of $M$ is already reduced. Feb 18, 2014 at 20:36
• Thanks again for all your help. FYI I have posted a more specific version of the problem at math.stackexchange.com/questions/2182734/… which addresses some of the sticking points here. Mar 12, 2017 at 3:31

Since the number of possible row-and-column-permutations of any given matrix is finite (namely, a $$t\times n$$ matrix has at most $$t!\times n!$$ possible permutations), one way to canonicalize a matrix over row-and-column-swaps would be to take the lexicographical minimum of those possible permutations. For example, your sample matrix

| 1  3  2  2  2 |
| 1  4  2  2  2 |
| 0  1  0  1  1 |
| 0  1  1  0  0 |


can be unambiguously represented as the concatenation of all its rows:

13222142220101101100


And then we can compute all possible permutations of its rows and columns, for example using a brute-force Python program like this:

import itertools

def canonicalize(NROWS, NCOLS, m):
possibilities = set()
for rows in itertools.permutations(range(NROWS)):
for cols in itertools.permutations(range(NCOLS)):
p = ''.join(m[r*NCOLS+c] for r in rows for c in cols)
for p in sorted(possibilities):
print(p)
return min(possibilities)

canonicalize(4, 5, '13222142220101101100')


This gives us 1440 possible permutations for 13222142220101101100. (Notice that 1440 is much smaller than $$(4\times 5)! \sim 2.4\times 10^{18}$$. It happens to be exactly half of $$4!\times 5! = 2880$$ because your matrix has those two duplicate columns; but I don't think that's a useful observation in general.) Those 1440 possible permutations, in order from lexicographically least to greatest, are:

00011011011222312224
00011011011222412223
00011011101223212242
[...skip a few...]
42221322211100010110
42221322211101010100
42221322211110010010


So if we canonicalize matrices by taking the lexicographical minimum possible permutation, then the canonical form of your matrix would be

| 0  0  0  1  1 |
| 0  1  1  0  1 |
| 1  2  2  2  3 |
| 1  2  2  2  4 |


Unfortunately there is no known algorithm that can perform this canonicalization quickly for arbitrary matrices. Brute force gets prohibitively slow for large matrices. You can think up tricks (such as "If the matrix has a unique least element, that element must appear in the upper left corner"); however, these tricks don't work for arbitrary matrices (such as your example matrix with five 0s and seven 1s. It is mere coincidence that your unique greatest element 4 ended up in the lower right corner).

I know there is no known algorithm to perform this canonicalization quickly, because if there were, then we could use that algorithm to perform graph isomorphism quickly: just canonicalize the adjacency matrix of each graph and see if they're canonically identical. For example, if we're given these two graphs... ...then we just compute the adjacency matrices for the left-hand graph and the right-hand graph...

0 1 1 0 0 0 0 0 0 1         0 1 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0 1 0         1 0 1 0 0 0 1 0 0 0
1 0 0 1 1 0 0 0 0 0         0 1 0 1 0 0 0 1 0 0
0 1 1 0 0 1 0 0 0 0         0 0 1 0 1 0 0 0 1 0
0 0 1 0 0 1 1 0 0 0         0 0 0 1 0 1 0 0 0 1
0 0 0 1 1 0 0 1 0 0         1 0 0 0 1 0 1 0 0 0
0 0 0 0 1 0 0 1 1 0         0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 1 1 0 0 1         0 0 1 0 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 1         0 0 0 1 0 0 0 1 0 1
1 0 0 0 0 0 0 1 1 0         1 0 0 0 1 0 0 0 1 0


...and then we run them through our canonicalization algorithm...

>>> left
'0110000001100100001010011000000110010000001001100000011001000000100110000001100101000010011000000110'
>>> right
'0100010001101000100001010001000010100010000101000110001010000100010100001000101000010001011000100010'
>>> canonicalize(10, 10, left)
'0000000111000011100000010110000010000011011000000110010010001001100000011000010001000001101000110000'
>>> canonicalize(10, 10, right)
'0000000111000011100000010110000010000011011000000110010010001001100000011000010001000001101000110000'
>>> assert canonicalize(10, 10, left) == canonicalize(10, 10, right)


Yep, these graphs are isomorphic! But the graph of a pentagonal prism (swapping a couple of edges in the Moebius graph) is not isomorphic to either one, because its canonicalization is different:

>>> pentagonal_prism
'0110000010100100000110011000000110010000001001100000011001000000100110000001100110000010010100000110'
>>> canonicalize(10, 10, pentagonal_prism)
'0000000111000011100000010110000010000011011000000110010010001001000100011010000001001100001000000110'
>>> assert canonicalize(10, 10, pentagonal_prism) != canonicalize(10, 10, left)


The existence of this reduction indicates that canonicalize cannot be polynomial-time in every case, because if it were polynomial-time, then we would have a proof that GI was in P, and in fact no such proof has been discovered yet. The Python implementation of canonicalize that I sketched above has factorial complexity — much greater than polynomial complexity.

The Nauty/Traces library has an ad-hoc algorithm to "efficiently" (on average, for non-pathological inputs) find a canonicalization of any graph, which means that it can "efficiently" find a canonicalization of any matrix whose entries are only 0 or 1. However, Nauty/Traces' chosen canonicalization is not related to lexicographical comparison. I don't have any special knowledge of Nauty/Traces' algorithm. For more technical information, see my blog post "Canonicalizing {0,1}-matrices with Nauty/Traces" (2020-01-11).

The code in my blog post happens to canonicalize left and right into

'1110000000000111000000011010000001010100000001110000001011000010000011010000001111000000101010000001'


and pentagonal_prism into

'1110000000000100101000001001010000110100000101100000011100000010000101010000101010100000011100000010'


I do not know how to reduce your problem "canonicalize a general matrix" to "canonicalize a {0,1}-matrix." If you can find such a reduction, then you could use Nauty/Traces' {0,1}-canonicalization algorithm to solve your problem "efficiently" for general matrices. I expect that the reduction exists, but I don't know how to do it.