Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
1  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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