<p>The recognition problem is equivalent to the graph isomorphism (recognition) problem, and the invariant problem is equivalent to the graph isomorphism invariant problem.</p>

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

<ul>
<li>For each row <i>i</i>, the graph has a vertex <i>u</i><sub><i>i</i></sub> labeled as “row.”</li>
<li>For each cell (<i>i</i>, <i>j</i>), the graph has a vertex <i>v</i><sub><i>i</i><i>j</i></sub> labeled as “cell in column <i>j</i>.”</li>
<li>For each integer <i>k</i>∈<i>S</i>, the graph has a vertex <i>w</i><sub><i>k</i></sub> labeled as “entry.”</li>
<li>For each cell (<i>i</i>, <i>j</i>), connect <i>u</i><sub><i>i</i></sub> and <i>v</i><sub><i>i</i><i>j</i></sub> by an edge, and connect <i>v</i><sub><i>i</i><i>j</i></sub> and <i>w</i><sub><i>a</i><sub><i>i</i><i>j</i></sub></sub> by an edge.</li>
</ul>

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

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

CC BY-SA 3.0
2014-11-01T03:09:44.747Z
2014-11-01T03:09:44.747Z
Tsuyoshi Ito
<p>Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers.</p>

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

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

<p>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)$.</p>

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

<p>What is the complexity of the <em>invariant problem</em>, 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)$?</p>

CC BY-SA 3.0
2014-11-05T08:26:31.520Z
What is the motivation for this problem?
Radu GRIGore
CC BY-SA 3.0
2014-11-06T10:28:40.067Z
@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
CC BY-SA 3.0
2016-08-17T03:59:49.080Z
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
<cc.complexity-theory><time-complexity><equivalence>
What's the complexity of recognizing equivalence for the following relation?
user188895
# What's the complexity of recognizing equivalence for the following relation?

(Asked by: username_0 on 2014-10-31)

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)$?

**Tags:** cc.complexity-theory, time-complexity, equivalence

> **Comments:**
> **username_1**: What is the motivation for this problem?  
> **username_0**: @username_1: 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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-11-01. Score: 9 | Accepted 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*+*m**n*+|*S*| labeled vertices as follows.

* For each row *i*, the graph has a vertex *u**i* labeled as “row.”
* For each cell (*i*, *j*), the graph has a vertex *v**i**j* labeled as “cell in column *j*.”
* For each integer *k*∈*S*, the graph has a vertex *w**k* labeled as “entry.”
* For each cell (*i*, *j*), connect *u**i* and *v**i**j* by an edge, and connect *v**i**j* and *w**a**i**j* 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.


---

