# 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 & 0\\ 1 & 1\end{matrix}\right)$ is equivalent to $\left(\begin{matrix}0 & 0\\ 0 & 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)$?

• What is the motivation for this problem? – Radu GRIGore Nov 5 '14 at 8:26
• @Radu GRIGore: Recognizing equivalent formulations of SAT (and similar) problems. Swapping rows corresponds to associativity and commutativity of conjunction (i.e., the order of clauses is irrelevant); permuting integers corresponds to renaming of variables. – user188895 Nov 6 '14 at 10:28
• Note that the complexity of testing two SAT formulas for equivalence (computing the same Boolean function) or isomorphism (computing same function up to renaming variables) have been studied. Isomorphism of Boolean formulas is a candidate to be intermediate between the first and second levels of the polynomial hierarchy. – Joshua Grochow Aug 17 '16 at 3:59