How to find the minimal rotation matrix from a vector $x$ to a vector $y$? Given two vectors $x$ and $y$ with the same norm and number of dimensions, how do I find the matrix that rotates $x$ onto $y$?
Edit: It seems like this matrix isn't unique, so I'll have to add another constraint:
Let's say that all vectors $z$ orthogonal to $x$ and $y$ must stay intact after the  transformation (so the rotation must be "minimal" in this sense).
In math terms, we're given vectors $x$ and $y$ in $\mathbb{R}^n$ and that $\lVert x \rVert = \lVert y\rVert$, and we're trying to solve $A x = y$ for $A$, subject to:
    $$A^T A = I  \\
 \det A = 1  \\
 A z = z \iff z \cdot x = 0 \land z \cdot y = 0$$
 A: Without loss of generality, consider the above problem with $||\mathbf{x}|| = ||\mathbf{y}|| = 1$. Define $R(\mathbf{x}): \mathbb{R}^n \rightarrow \mathbb{R}^{n \times n}$ be the matrix that rotates $\mathbf{x}$ onto $\mathbf{e}_1$ (see below).
Step 1: Find $R_1 = R(\mathbf{x})$, i.e. $R_1 \mathbf{x} = \mathbf{e}_1$
Step 2: Find $R_2 = R(\mathbf{M_1 y})$, i.e. $R_2 R_1 \mathbf{y} = \mathbf{e}_1$
We now have $R_1 x = R_2 R_1 y$. Rearranging yields
\begin{equation}
y = R_1^T M_2^T M_1 x,
\end{equation}
hence
\begin{equation}
A = R_1^T M_2^T M_1.
\end{equation}
Details for $R(\mathbf{x})$:
This matrix can be built up by successive multiplications of basic rotation matrices from $i = n-1$ back to $i = 0$ of the form
\begin{equation}
\left( \begin{array}{ccc}
1 &  &  &  &  \\
 & \ddots &  &  &  \\
 & & \cos(\theta_i) & -\sin(\theta_i) \\
 & & \sin(\theta_i) & \cos(\theta_i) & \\
 & & & & \ddots & \\
 & & & & & 1 \end{array}\right),
\end{equation}
where $\theta_i = -\tan^{-1}(x_i/x_{i+1})$.
Code written in Dart for all of the above. Class implementations not included, though no surprises there.
Matrix rotationToE0(Vector v){
  if ((v.norm2() - 1.0).abs() > tol){
    throw new ArgumentError("v must be unit vector under 2-norm");
  }
  int n = v.length;
  var rFinal = new DenseMatrix.identity(n);
  for (int i = n-2; i >= 0; --i){
    var a = v[i];
    var b = v[i+1];
    var l = sqrt(a*a + b*b);
    var c = a/l;
    var s = b/l;
    var r = new DenseMatrix.identity(n);
    r[i][i] = c;
    r[i][i+1] = s;
    r[i+1][i] = -s;
    r[i+1][i+1] = c;
    rFinal = r*rFinal;
    v = r*v;
  }
  return rFinal;
}

Matrix rotationXToY(Vector x, Vector y){
  var xn2 = x.norm2();
  var xUnit = x / x.norm2();
  if ((y.norm2() - xn2).abs() > tol){
    throw new ArgumentError("x and y must be of the same length");
  }
  Vector yUnit = y / xn2;

  var M1 = rotationToE0(xUnit);
  var M2 = rotationToE0(M1*yUnit);

  return M1.transpose() * M2.transpose() * M1;
}

//test client
void main() {
  var x = new DenseVector.random(5);
  x = x / (x.norm2() * 3);
  var y = new DenseVector.random(5);
  y = y / (y.norm2() * 3);

  var A = rotationXToY(x, y);
}

Note: I'm sure there's a more efficient method of implementing this, but if performance isn't critical and $n$ isn't too large, this should do the trick.
A: Hint: Use rotation matrix. Solve system of equations to find the degree needed. 
