# Sets of vectors related by a rotation

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.

-

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.

-
and how is "check if it extends to a rotation" polynomial-checkable? I don't see it. – J. Martel Jul 9 '12 at 13:46
@J. Martel: You need to check compare two sets of vectors, reorder them lexicographically and you are done. – Anton Petrunin Jul 9 '12 at 16:49
@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$. – Piotr Migdal Jul 10 '12 at 12:44
@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.] – Anton Petrunin Jul 10 '12 at 14:11
@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$. – Piotr Migdal Jul 10 '12 at 16:45

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.

-
Graph isomorphism is not known to be NP-complete. – Noah Stein Jul 12 '12 at 13:42
@NoahStein My mistake and thx for pointing this out. I've fixed it. – Piotr Migdal Jul 12 '12 at 13:46