# 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

## 1 Answer

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 kS, 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.