How to recover a shuffled matrix

Question

Suppose that I have a matrix $A$. $A$ can be a rating matrix. That is, $A(i,j)$ is the rating user $i$ has given to item $j$.

Suppose that I shuffle the rows and columns of matrix $A$ and get $A_{\text{shuffle}}$.

Now, actually, both $A$ and $A_{\text{shuffle}}$ contains the same information. Because shuffling the columns or rows do not change the ratings the users give to items.

Is there an efficient way to show that $A$ and $A_{\text{shuffle}}$ contain the same users and items.

I.e., as suggested by polkjh, given matrices $A$ and $B$, how can I check efficiently if $B$ can be obtained by shuffling rows and columns of $A$?

Thanks

Answer 1

That is NP-problem about graph isomorphism. What kind of algorithm you consider "efficiently"? Some polynomial algo? You can sure use some heuristics, if you know something about $A$, but there is no polynomial algo for general case.

Answer 2

Let's reformulate the question:

If $A,B$ are two matrices of the same size (not necessarily square) over some alphabet, decide if there are permutation matrices $P,Q$ such that $A = PBQ$.

Though I don't remember a precise reference in the moment, I'm quite sure I've seen that this problem is NP-complete, meaning there is no efficient algorithm for this problem (assuming P $\neq$ NP).