What's the complexity of recognizing equivalence for the following relation? Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers.

We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained from $B$ by


permuting (i.e., swapping) rows and
permuting integers (i.e., applying a bijection $\mathbb{Z} \to \mathbb{Z}$ to every element of $B$).


Example:
$\left(\begin{matrix}1 &amp; 0\\ 1 &amp; 1\end{matrix}\right)$ is equivalent to $\left(\begin{matrix}0 &amp; 0\\ 0 &amp; 1\end{matrix}\right)$.

What is the complexity of the recognition problem, i.e., given two matrices, decide whether they are equivalent?

What is the complexity of the invariant problem, i.e., given a matrix $A$, calculate a complete invariant $f(A)$, that is, a function such that $A$ and $B$ are equivalent only if $f(A) = f(B)$?
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.