How to tell if two matrices are equal up to a permutation Given two real rectangular matrices A, 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 but which seems too specific/complicated to receive a response. Maybe I'll be luckier with this simpler one!)
 A: 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).
A: 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.
A: You can sort the rows / columns and then check equality. And to sort, you can use the lexicographical order.
A: I think this problem is related to the problem of equivalence of two graphs (just as Darij Grinberg mentioned above), and I think I've found a pretty fast polynomial solution for the graphs. I wrote up the explanation starting with http://babkin-cep.blogspot.com/2018/06/graph-equivalence-1-overall-algorithm.html (the informal proof of why I think it works is in the parts 3 and 4, and in case if someone notices any errors in it, I would be interested to hear about them). It can probably be adapter to the matrices as well.
