Complexity of: One matrix is row/col permutation of another matrix

Question

1. Given two m x n matrices A and B whose elements belong to a set S. Problem: Can the rows and columns of A be permuted to give B? What is the complexity of algorithms to solve this problem? Determinants partially help (when m=n): a necessary condition is that det(A) = +/- det(B).

2. Also allow A to contain "don't cares" that match any element of B.

3. Also, if S is finite allow permutations of elements of A.

This is not homework - it is related to the solved 17x17 puzzle.

Answer 1

See below example of permuting rows and columns of a matrix:

Observe the start matrix and end matrix. All elements in a row or column are retained its just that their order has changed. Also the change in relative positions is uniform across rows and columns

eg. see 1 in start matrix and end matrix. Its row has elements 12, 3 and 14 along with it. Also its column has 5, 9 and 2 along with it. This is maintained across the transformations.

Based on this fact I am putting forward this basic algo to find for a given matrix A, can its rows and columns of A be permuted to give matrix B.

 1. For each row in A, sort all elements in the row. Do same for B.
 2. Sort all rows of A (and B) based on its columns. ie. if row1 is {5,7,16,18} and row2 is {2,4,13,15}, then put row2 above row1
 3. Compare resultant matrix A' and B'. 
 4. If both equal, then do (1) and (2) but for columns on ORIGINAL matrix A & B instead of rows.
 5. Now compare resultant matrix A'' and B''