What's the complexity of recognizing equivalence for the following relation?
The recognition problem is equivalent to the graph isomorphism (recognition) problem, and the invariant problem is equivalent to the graph isomorphism invariant problem.

To reduce the current problem to graph isomorphism, given an m×n matrix A, let S be the set of integers which appear as an entry of A at least once.  We construct a graph G(A) with m+mn+|S| labeled vertices as follows.


For each row i, the graph has a vertex ui labeled as “row.”
For each cell (i, j), the graph has a vertex vij labeled as “cell in column j.”
For each integer k∈S, the graph has a vertex wk labeled as “entry.”
For each cell (i, j), connect ui and vij by an edge, and connect vij and waij by an edge.


Then it is not hard to see that two matrices A and B are equivalent in the sense stated in the question if and only if there is an isomorphism between G(A) and G(B) which preserves labels.  But the isomorphism problem of vertex-labeled graphs is known to be equivalent to the isomorphism problem of usual, unlabeled graphs.

To reduce graph isomorphism to the current problem, given a graph G=(V, E), consider each edge as two directed edges, and construct a 2|E|×2 matrix M(G) by writing the two endpoints of each directed edge in one row.  Then again it is not hard to see that two graphs G and H are isomorphic if and only if M(G) and M(H) are equivalent in the sense stated in the question.