Normalizing a matrix with row and column swapping

Question

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 |
then follow below steps

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    

Answer 1

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.

Answer 2

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)
            possibilities.add(p)
    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.