5
$\begingroup$

We have a two sets of vectors ($\mathbb{C}^d$), $A=\{ v_1, \ldots v_n\}$ and $B=\{u_1, \ldots u_n\}$.

The question is if there is an efficient solution (polynomial in $n$) for checking whether $A$ and $B$ are related by an unitary rotation, i.e. if there exists an $U\in \text{U}(d)$ and a permutation $\sigma$, such that for every $i$ $$u_i = U v_{\sigma(i)}.$$

Notes:

If it simplifies the task, I'm interested in $d=2$. (Or equivalently, $d=3$ for real vectors.)

I have been tying using Gram matrices for $A$ and $B$, however in a general case there are problems with sorting entries, so that one could compare.

$\endgroup$

2 Answers 2

4
$\begingroup$

Since $d$ is small, you can do the following.

Choose a maximal linearly independed system $A'$ in $A$. Consider all maps $A'\to B$ (since $|A'|\le d$, there are roughly $n^d$ of them). For each check if it extends to a rotation.

$\endgroup$
7
  • 1
    $\begingroup$ and how is "check if it extends to a rotation" polynomial-checkable? I don't see it. $\endgroup$
    – JHM
    Jul 9, 2012 at 13:46
  • $\begingroup$ @J. Martel: You need to check compare two sets of vectors, reorder them lexicographically and you are done. $\endgroup$ Jul 9, 2012 at 16:49
  • $\begingroup$ @AntonPetrunin Unfortunately, it's not that easy. If for a given set $A'$ they may be plenty of possible rotations which map $A$ to some (different) subsets of $B$. $\endgroup$ Jul 10, 2012 at 12:44
  • $\begingroup$ @Piotr Migdal, as I wrote, there are $n^d$ of them --- yes you have to check all. [For sure there is a smarter way, I only wanted to say that it can be solved in polynomial time.] $\endgroup$ Jul 10, 2012 at 14:11
  • $\begingroup$ @AntonPetrunin Thanks, now I see it. I will wait before accepting, as I was counting on something more invariant-related and (the best) working for any $d$. $\endgroup$ Jul 10, 2012 at 16:45
1
$\begingroup$

Now I see that in general (i.e. for any $d$) its special case is equivalent to the graph isomorphism problem.

For a given $d$ there is a polynomial-time solution pointed out by @AntonPetrunin.

For $i$-th vector let's $j$-th coordinate be $1$ if $i$-th node is connected to $j$-th edge (otherwise - $0$). That is, $v_{ij}$ are elements of the incidence matrix and its adjacency matrix ($V V^T$) is just the Gram matrix for $\{v_1, \ldots, v_n \}$.

Consequently, deciding if two sets of vectors are related by a rotation is at least as hard as the graph isomorphism problem. As we can easily check the solution, the proposed problem is NP.

$\endgroup$
2
  • $\begingroup$ Graph isomorphism is not known to be NP-complete. $\endgroup$
    – Noah Stein
    Jul 12, 2012 at 13:42
  • $\begingroup$ @NoahStein My mistake and thx for pointing this out. I've fixed it. $\endgroup$ Jul 12, 2012 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.