Does two same dimensional, centered matrices $X, Y$ satisfying $X'X = Y'Y$ necessarily satisfy: $Y=RX$ for a rotation $R$?

Question

Let $X:=[x_1\dots x_n], Y:=[y_1\dots y_n] \in \mathbb{R}^{d\times n}, x_i, y_i \in \mathbb{R}^{d\times 1}$.

Assume $X,Y$ are centered, i.e. each of their $d$ row sums are zero. Mathematically, $X(I_n - \frac{1}{n}1_n1_n')= X, 1_n$ denoting the $n$ -dim column vectors of all one's. Let $X'X = Y'Y \in \mathbb{R}^{n\times n}$. Does this necessarily mean: $Y=RX$ for some rotation $R \in O(d)?$

The centrering above is not much of a big deal: if we don't assule centered, my question is: does there exist $R \in O(d), v \in \mathbb{R}^d$ so that $y_i = Rx_i + v$?

Answer 1

Let $X$ have the singular value decomposition $X = U \Sigma V'$ where $U$ and $V$ are orthogonal matrices of sizes $d \times d$ and $n \times n$ respectively, and $\Sigma$ is a $d \times n$ diagonal matrix. Since $Y' Y = X' X = V \Sigma' \Sigma V'$, we can write the singular value decomposition of $Y$ as $\tilde{U} \Sigma V'$ for some orthogonal $\tilde{U}$, with the same $\Sigma$ and $V$. Thus $Y = \tilde{U} U^{-1} X = R X$ where $R = \tilde{U} U^{-1}$ is orthogonal.

EDIT: The SVD is not unique, but in its construction $\Sigma$ and $V$ are obtained from the eigenvalues and eigenvectors of $X' X$ respectively. So if $X' X$ and $Y' Y$ are equal, you can use the same $\Sigma$ and $V$ for both.

Answer 2

The condition $X^TX = Y^TY$ is equivalent to $$\langle x_i,x_j \rangle = \langle y_i,y_j \rangle $$ for all $i,j$.

If $X=0$, then since $\|y_i\|^2 = \langle y_i,y_i \rangle = \langle x_i,x_i \rangle = 0$, so $y_i = 0$ for all $i$ so $X=Y$ and we can take the identity matrix as the orthogonal matrix.

Next assume $X \neq 0$ and wlog assume that $x_1,x_2,\dots,x_r$ form a basis of $\mathcal{C}(X)$ (where $\mathcal{C}(X)$ denotes the column space of $X$).

----------

Claim $y_1,\dots,y_r$ forms a basis of $\mathcal{C}(Y)$ and moreover if for any $i > r$ the linear relationship $$x_i = \alpha_1 x_1 + \alpha_2 x_2 + \dots + \alpha_r x_r$$ holds, the exact same linear relationship holds among the $y$'s, i.e., for the same set of $\alpha_i$'s we have $$y_i = \alpha_1 y_1 + \alpha_2 y_2 + \dots + \alpha_r y_r$$

Proof:

Since for any scalars $l_1,\dots,l_k$ we have $$\|l_1x_1 + l_2x_2 + \dots l_r x_r\|^2 = \sum_{ij} l_i l_j \langle x_i, x_j\rangle = \sum_{ij} l_i l_j \langle y_i, y_j\rangle = \|l_1y_1 + l_2y_2 + \dots l_r y_r\|^2,$$ it follows that $l_1x_1 + l_2x_2 + \dots l_r x_r = 0$ iff $l_1y_1 + l_2y_2 + \dots l_r y_r = 0$. Since no non-trivial linear combination of $x_1,\dots,x_r$ equals zero it follows than no non-trivial combination of $y_1,\dots,y_r$ equals zero and so $y_1,\dots,y_r$ are independent.

Since $x_1,\dots,x_r$ forms a basis for any $i >r$ we can find $\alpha_1,\dots,\alpha_r$ such that $$x_i = \alpha_1 x_1 + \dots + \alpha_r x_r$$ that is, $$\|x_i - \alpha_1 x_1 - \dots - \alpha_r x_r\|^2 = 0$$ As above, it is easy to see that $$\|y_i - \alpha_1 y_1 - \dots - \alpha_r y_r\|^2 =\|x_i - \alpha_1 x_1 - \dots - \alpha_r x_r\|^2 = 0$$ so, $$ y_i =\alpha_1 y_1 + \dots + \alpha_r y_r. $$ So the linear relationship between $y_i$ and $y_1,\dots,y_r$ is identical to the one between $x_i$ and $x_1,\dots,x_r$ and in particular $y_1,\dots,y_r$ forms a basis of $\mathcal{C}(Y)$.

----------

Claim There is a $d \times d$ orthogonal matrix $P$ such that $x_i = Py_i$ for $1 \leq i \leq n.$

Proof

Let $X_r = \begin{bmatrix} x_1 & \dots & x_r \end{bmatrix}$ and $Y_r = \begin{bmatrix} y_1 & \dots & y_r \end{bmatrix}$, we have $X_r^T X_r = Y_r^T Y_r$ moreover $X_r$ and $Y_r$ have independent columns.

Let $X_r = Q_1 T_1$ be the QR decomposition of $X_r$ where $Q_1$ is an $d \times d$ orthogonal matrix and $T_1 = \begin{bmatrix} R_1 \\ 0\end{bmatrix}$ where $R_1$ is an $r \times r$ non-singular upper triangular matrix.

Similarly let $Y_r = Q_2 T_2$ be the QR decompostion of $Y_r$ where where $Q_2$ is a $d \times d$ orthogonal matrix and $T_2 = \begin{bmatrix} R_2 \\ 0\end{bmatrix}$ where $R_2$ is an $r \times r$ non-singular upper triangular matrix.

We have $X_r^T X_r = R_1^T R_1$ and $Y_r^T Y_r = R_2^T R_2$, so $$ R_1^T R_1 = R_2^T R_2, $$ that is, $$ (R_2^T)^{-1} R_1^T = R_2 R_1^{-1}. $$

The left hand side of the above is an $r \times r$ lower triangular and the right hand side is an $r \times r$ upper triangular matrix, this is possible if both sides equal an $r \times r$ diagonal matrix $D$. So, $R_1^T =R_2^T D $ and $R_2 = D R_1$, i.e., $R_1 = D R_2$ and $R_2 = D R_1$. Substituting we have $R_2 = D^2 R_2$, so $D^2 = I$.

Now, $X_r = Q_1 \begin{bmatrix} R_1 \\ 0 \end{bmatrix} = Q_1 \begin{bmatrix} D R_2 \\ 0 \end{bmatrix} = Q_1 \begin{bmatrix} D & 0 \\ 0 & I \end{bmatrix} \begin{bmatrix}R_2 \\ 0 \end{bmatrix} = Q_1 \begin{bmatrix} D & 0 \\ 0 & I \end{bmatrix} Q_2^T Q_2 \begin{bmatrix}R_2 \\ 0 \end{bmatrix} = P Y_r$ where $P= Q_1 \begin{bmatrix} D & 0 \\ 0 & I \end{bmatrix} Q_2^T$. It is easy to verify $P^T P = I$ and hence $P$ is an orthogonal matrix.

So there is a $d \times d$ matrix orthogonal matrix $P$ such that $x_i = P y_i$ for $1 \leq i \leq r$.

For any $i > r$ we know there exist constants $\alpha_1,\dots,\alpha_r$ such that $ x_i = \alpha_1 x_1 + \dots + \alpha_r x_r$ and $ y_i = \alpha_1 y_1 + \dots + \alpha_r y_r$. So $P y_i = \alpha_1 Py_1 + \dots + \alpha_r Py_r = \alpha_1 x_1 + \dots + \alpha_r x_r = x_i.$

So, $x_i = Py_i$ for all $i$ and the result is proved.