Given two real rectangular matrices, $A$ and $B$, how can I tell if they are equal up to a permutation of their rows/column without trying all possible permutations?
(This is closely related to the question I asked yesterday, Algorithm to determine matrix equivalence, but which seems too specific/complicated to receive a response. Maybe I'll be luckier with this simpler one!
On
For square matrices, invertible, this is easy to show. Assume some (yet unknown) permutation matrix $P$ with the property that $$ P \cdot A = B$$ then if $A$ is invertible one can find $P$ by $$ P = B\cdot A^{-1} $$ and simply inspect, whether it is a proper permutation-matrix.
If A and/or B are not invertible one can do (pivoted) Gaussian elimination from the right side until $P$ becomes visible. If the $A$ and $B$ are not square, one can try to use the pseudoinverse.
On
[Update 2] With respect to the earlier question to which the OP has linked it becomes more important to mention, that the following method is only simple, if there is some function over the element of the rows of of the columns, which provides unique "keys" for each row/column. Matrices with restricted entries, for instance $0,1$ or $-1,0,1$ might have no such functions. The problem will become much more complicated - but this was not apparent from the question in the OP... [/Update 2]
Here is a worked example for the case, that rows & columns are both permuted, so $$ B = P_L \cdot A \cdot P_R ' $$ where the $P_L,P_R$ are permutation matrices and the apostroph indicates the transpose. Our goal is, to find $P_L,P_R$ given $A,B$. By the logic of the procedure it is clear, that the matrices need not be square, any rectangular form is possible.
The key-idea is that of the sorting which was introduced in he answer of @xavier
The improvement of that proposal is that -when we sort the rows- we do not refer to values in a single column as sorting key, but to a key, made from the whole row instead. The most simple idea is to use the row-sum; and to overcome possible ambiguities we may add to square-sums/cube-sums along the rows or even more sophisticated keys but which are insensitive to the order of the columns. In the example I've provided the sums and the squaresums (but I only used the sums, because they were sufficient/unique in that example).
Here is the excerpt done in my matrix-language MatMate (I think it is very near to selfexplanatory pseudocode)
A = randomu(4,4) // generate some 4x4 randommatrix
B = A[ 4´2´1´3 , 2´4´3´1 ] // extract columns/rows given by index-lists
Here $B$ is a reorganisation of the matrix $A$ in rows and columns simultaneously; the first list gives the indices from where the rows, the second, from where the columns are taken. This means: $B$ is a left- and right-permutation of $A$. And the goal is to reconstruct that permutation from the data in A and B in terms of permutation-matrices $P_L,P_R$.
Data:
A :
91.73 69.77 16.26 82.57
36.79 84.42 32.95 27.90
77.47 71.80 46.60 48.18
32.79 30.66 24.67 14.92
B :
30.66 14.92 24.67 32.79
84.42 27.90 32.95 36.79
69.77 82.57 16.26 91.73
71.80 48.18 46.60 77.47
First we build the sorting keys for $A$. We prepare the sorting of the rows and for this we introduce the matrix $AA$ which contains the sums and the squaresums of each row:
[152] AA = sumzl(A)||sqsumzl(A)
AA :
260.33 20363.50
182.06 10344.05
244.04 15648.79
103.04 2846.58
Now to get a permuation-matrix we need the sorting-index; that is we need an indirect sorting which gives a list which can then be used as index rowwise into $A$ (or into $AA$) as result:
[153] idxA = isortsp(AA)
idxA :
4.00 2.00 3.00 1.00
From this we generate a permutation-matrix $T_{l1}$
[154] TL1 = einh(4)[idxA',*]
TL1 :
0.00 0.00 0.00 1.00
0.00 1.00 0.00 0.00
0.00 0.00 1.00 0.00
1.00 0.00 0.00 0.00
and test, whether this index /this permutation gives indeed the rows-sorted $AA$ (or $A$):
[155] chk = TL1 * AA
chk :
103.04 2846.58
182.06 10344.05
244.04 15648.79
260.33 20363.50
Now we do the same with the matrix $B$ :
[156] BB = sumzl(B)||sqsumzl(B)
BB :
103.04 2846.58
182.06 10344.05
260.33 20363.50
244.04 15648.79
[157] idxB = isortsp(BB)
idxB :
1.00 2.00 4.00 3.00
[158] TL2 = einh(4)[idxB',*]
TL2 :
1.00 0.00 0.00 0.00
0.00 1.00 0.00 0.00
0.00 0.00 0.00 1.00
0.00 0.00 1.00 0.00
[159] chk = TL2 * BB
chk :
103.04 2846.58
182.06 10344.05
244.04 15648.79
260.33 20363.50
and indeed, also $BB$ (and thus $B$) gets sorted by that permutation. Now to arrive at $B$ starting from $A$ we need the first permutation in its order and the second as inverse/transpose:
[160] chk = TL2' * TL1 * AA
chk :
103.04 2846.58
182.06 10344.05
260.33 20363.50
244.04 15648.79
and this shows, that we get the rows of $AA$ into the rows of $BB$ (and thus that of $A$ into that of $B$). We put that two permutation together in one permutation-matrix $P_L$
[161] PL = Tl2' * TL1
PL :
0.00 0.00 0.00 1.00
0.00 1.00 0.00 0.00
1.00 0.00 0.00 0.00
0.00 0.00 1.00 0.00
[162] chk = PL * A
chk :
32.79 30.66 24.67 14.92
36.79 84.42 32.95 27.90
91.73 69.77 16.26 82.57
77.47 71.80 46.60 48.18
and we see, that the columns are not yet in the same order as in $B$ but the rows are now in the same order (compare the documented matrices $A$ and $B$ at the beginning of this excerpt)
Now we do the same for the columns. To make things easier I just use the transposed of $A$ and $B$ and do then the same procedure as before:
[163] AA = sumzl(A')||sqsumzl(A') // use the transposes of A
// to apply the logic to the columns
AA :
238.78 16844.07
256.65 18089.03
120.48 4130.28
173.57 10139.54
[164] idxA = isortsp(AA)
idxA :
3.00 4.00 1.00 2.00
[165] TL1 = einh(4)[idxA',*]
TL1 :
0.00 0.00 1.00 0.00
0.00 0.00 0.00 1.00
1.00 0.00 0.00 0.00
0.00 1.00 0.00 0.00
[166] chk = TL1*AA
chk :
120.48 4130.28
173.57 10139.54
238.78 16844.07
256.65 18089.03
[167] BB = sumzl(B')||sqsumzl(B') // use the transpose of B to allow to
// apply the logic to the columns
BB :
256.65 18089.03
173.57 10139.54
120.48 4130.28
238.78 16844.07
[168] idxB = isortsp(BB)
idxB :
3.00 2.00 4.00 1.00
[169] TL2 = einh(4)[*,idxB']
TL2 :
0.00 0.00 1.00 0.00
0.00 1.00 0.00 0.00
0.00 0.00 0.00 1.00
1.00 0.00 0.00 0.00
[170] chk = TL2 * BB
chk :
120.48 4130.28
173.57 10139.54
238.78 16844.07
256.65 18089.03
[171] chk = TL2' * TL1 * AA
chk :
256.65 18089.03
173.57 10139.54
120.48 4130.28
238.78 16844.07
[172] PR = Tl2' * TL1
PR :
0.00 1.00 0.00 0.00
0.00 0.00 0.00 1.00
0.00 0.00 1.00 0.00
1.00 0.00 0.00 0.00
Now we check the complete permutation:
[173] chk = PL * A * PR'
chk :
30.66 14.92 24.67 32.79
84.42 27.90 32.95 36.79
69.77 82.57 16.26 91.73
71.80 48.18 46.60 77.47
and the result equals the matrix $B$, so we've indeed found the solution.
Because we needed only sorting this applicable also to nonsquare matrices, and there is also no more question of invertibility.
A complete script for the task. Here I use n of rows = 16 and n of columns=12 but is easily configurable:
;****** MatMate Version 0.1108 Beta *****************************
nr,nc=16,12 // number rows, number columns
A = randomu(nr,nc)
idxr,idxc = randomindex(nr),randomindex(nc)
B = A[idxr,idxc] // B is then a random permutation of A
// by rows and by columns
//========== Adaption of rows ======================
AA = sumzl(A) // or: sqsumzl(A)
// or take something else if not unique
idxA = isortsp(AA) // I(ndirect) SORT (along) SP (=column)
TL1 = einh(nr)[idxA , * ] // "einh(n)" is n x n unit-matrix
// chk = TL1 * AA
BB = sumzl(B) // use the same function as for A
idxB = isortsp(BB)
TL2 = einh(nr)[idxB , * ]
// chk = TL2 * BB
//
// chk = TL2' * TL1 * AA
PL = Tl2'*TL1
// chk = PL * A
//========== Adaption of columns ======================
AA = sumzl(A') // or: sqsumzl(A')
// or take something else if not unique
idxA = isortsp(AA)
TL1 = einh(nc)[idxA , * ]
// chk = TL1 * AA
BB = sumzl(B') // use the same function as for A'
idxB = isortsp(BB)
TL2 = einh(nc)[idxB , * ]
// chk = TL2 * BB
//
// chk = TL2' * TL1 * AA
PR = Tl2 ' * TL1
//========== Check result =============================
chk = PL * A * PR' - B // should be zero
// if indeed zero, then B = PL *A * PR
// and we have the solution
// ====================================================
This includes the graph isomorphism problem for bipartite graphs, so is likely to be hard. (To see this, lookat the adjacency matrix A which is $1$ at position $(i,j)$ if vertex number $i$ on the left side is connected to vertex number $j$ on the right side.)
Some heuristics from GIP carry over to this case. Of course, for most matrices just looking at column and row sums will help. In greater generality computing the spectrum of both matrices can help (although not in finding an actual rearrangement).
You can sort the rows / columns and then check equality. And to sort, you can use the lexicographical order.