how can I find a orthogonal matrix Q such that Q$x_i=y_i$

Question

How can I find a orthogonal matrix Q such that Q$x_i=y_i$ given that $\|x_i\|=\|y_i\|$ and $\|x_i-x_j\|= \|y_i-y_j\|$. I know that Householder reflectors would do the trick here Q=$I-2pp^T$ where p is ($x_i-y_i$)/$\|x_i-y_i\|$. but I am unable to understand how can someone please explain this to me.

Here $x_i , y_i \in R^n$

I also read this Rotation by Householder matrices solution but couldn't understand the how part.

Answer 1

The Householder reflection gives you a reflection across the hyperplane orthogonal to the unit vector $p$ (note that $pp^\top$ gives projection onto the line spanned by $p$, and so subtracting twice that leaves the hyperplane orthogonal to $p$ fixed and reflects across that hyperplane). That said, if you do a Householder reflection as you suggested with $p=\dfrac{x_i-y_i}{\|x_i-y_i\|}$, it switches $x_i$ and $y_i$ and leaves the hyperplane orthogonal to $x_i-y_i$ fixed. If the remaining $x_j$ and $y_j$ are not in that hyperplane, they will be messed up by this reflection. Thus, I don't see any good way to use this repeatedly with more vectors.

However, as Will Jagy pushed me to realize, the solution is easy. Let $A$ be the matrix whose columns are the $y_i$ and let $B$ be the matrix whose columns are the $x_i$. Observe that when we set $Q=AB^{-1}$, it will have property that $Qx_i = y_i$ for all $i$. The easiest way to see this is the following: If $e_j$ are the standard basis for $\Bbb R^n$, then by construction we have $Be_i=x_i$ and $Ae_i = y_i$. Therefore, $(AB^{-1})x_i = A(B^{-1}x_i) = Ae_i = y_i$, as required. Finally, as Will pointed out, the geometric hypotheses tell us that the $n$-dimensional pyramids formed by the $x_i$ and by the $y_i$ are congruent, and so $Q$ must be an isometry of $\Bbb R^n$. By a standard argument, $Q$ must be linear and, indeed, an orthogonal matrix. (For a proof, see, for example, pp. 114-115 of my differential geometry text.)

Answer 2

Assuming the vectors $x_i$ form a basis, let $Q$ be the unique linear transformation that maps $x_i$ to $y_i$.

We need to show that $Q$ is orthogonal, that is, respects the inner product.
But, by hypothesis the inner product of basis elements are preserved because if $i\ne j$ $$\langle x_i,x_j\rangle=-\frac12\big(\|x_i-x_j\|^2-\|x_i\|^2-\|x_j\|^2\big)\,.$$ if $i\ne j$.

If the given vectors $x_i$ are only linearly independent, then we can extend them, say by an orthonormal basis of $\big({\rm span}(x_i)_i\big)^\perp$ and similarly extend $y_i$ by an orthonormal basis of $\big({\rm span}(y_i)_i\big)^\perp$.