# Prove That the Gram Matrix Determines Vectors Up to Isometry / Multiplication by Unitary Matrix

According to http://mathworld.wolfram.com/GramMatrix.html, the gram matrix determines a set of vectors up to an isometry. I'm trying to prove this statement.

More specifically, let $A, B \in \mathbb{R}^{m,n}$. Here, I'm thinking of $A$ and $B$ as a stacking of $m$ row vectors, each row vector living in $\mathbb{R}^{n}$. Given that $AA^T = BB^T$, I want to show there exists an orthonormal matrix $P$ such that $||Pa_i|| = ||b_i||$ for $i=1,...,m$, where $a_i$ (resp. $b_i$) denotes the $i$-th row of $A$ (resp. $B$).

Here's what I've tried. Let $A = U_1 \Sigma_1 V_1^T$ and $B = U_2 \Sigma_2 V_2^T$ be the SVDs of $A$ and $B$. Then, since $U_1$ is an orthonormal basis for $AA^T$ and likewise for $U_2$, there must exist a orthonormal matrix $P$ such that $U_2 = P U_1 = P U$. Furthermore, since $\sigma_i(A)^2 = \lambda_i(AA^T)$, $\Sigma_1 = \Sigma_2 = \Sigma$. So since $A V_1 = U \Sigma$, plugging into $B$'s SVD we get $B = P A V_1 V_2^T$.

This is where I got stuck, as I don't know how to deal with the $V_1 V_2^T$ on the right. I believe $V_1$ and $V_2$ will be orthonormal basis for the same subspace, but I don't think it's true that they will be the same basis. I could also make the same argument for the $U_i$'s and say there is some orthonormal $Q$ which maps between $V_1$ and $V_2$, leaving something like $B = P A Q$.

What you want to show is that if $A$, $B$ are $m\times n$ then
$$A\cdot A^T= B\cdot B^T$$ if and only if there exists $U$ $m\times m$ matrix so that $U\cdot U^T = I_m$ and $B = A \cdot U$

The implication $\Leftarrow$ is easy but instructive:

$$B \cdot B^T = A U U^T A^T = A (U U^T) A^T = A \cdot I_m \cdot A^T = A \cdot A^T$$

Let's do $\Rightarrow$. We'll use your idea with SVD. Let \begin{eqnarray*} A = U_1 \Sigma_1 V_1^T \\ B = U_2 \Sigma_2 V_2^T \end{eqnarray*} Then \begin{eqnarray*} AA^T = U_1 \Sigma_1 V_1^T\cdot V_1 \Sigma_1 U_1^T= U_1 \Sigma_1^2 U_1^T\\ BB^T = U_2 \Sigma_2 V_2^T\cdot V_2 \Sigma_2 U_2^T= U_2 \Sigma_2^2 U_2^T \end{eqnarray*} Let's recall the notion of a positive square root of a positive semidefinite matrix. Basically \begin{eqnarray*} \sqrt{AA^T} = U_1 \Sigma_1 U_1^T \\ \sqrt{BB^T} = U_2 \Sigma_2 U_2^T \end{eqnarray*} We have $AA^T = BB^T$ so $\sqrt{AA^T} = \sqrt{BB^T}$ or $$U_1 \Sigma_1 U_1^T = U_2 \Sigma_2 U_2^T$$ We are done now: \begin{eqnarray*} B = U_2 \Sigma_2 V_2^T= U_2 \Sigma_2 U_2^T \cdot U_2 V_2^T = U_1 \Sigma_1 U_1^T \cdot (U_2 V_2^T) = \\ = U_1 \Sigma_1 V_1^T \cdot (V_1 U_1^T) \cdot (U_2 V_2^T) = A \cdot U \end{eqnarray*}

Really this is about the polar decomposition $A = \sqrt{A A^T} \cdot W_1$ and similar for $B$.

• What about the case that we know that for any PSD matrix $P$ we have the equality ${A}^{T} P A = {B}^{T} P B$, can we say that $A = \pm B$? – Royi Jan 29 at 21:06
• The proof assumes that the matrices are square, for example, by considering $\Sigma_1^2$, where $\Sigma$ is an $m\times n$ matrix. I don't see how to make the proof work in the nonsquare case. – coudy Jul 3 at 14:20

Since the other proofs do not address the case $$n \neq m$$, let me provide a proof that does not rely on SVD.

Let $$u_1$$, ...$$u_m$$ the rows of $$A$$ and $$v_1$$, ..., $$v_m$$ the rows of $$B$$ and $$k$$ the dimension of the span of $$u_1$$,..., $$u_m$$. Without loss of generality, we may assume that this span is generated by $$u_1$$, ..., $$u_k$$.

Choose an orthonormal basis $$e_{k+1}, ..., e_m$$ of the space orthogonal to $$vect(u_1,..., u_k)$$ and an orthonormal family $$e'_{k+1}, ..., e'_m$$ in the space orthogonal to $$vect(v_1,..., v_k)$$. The linear map sending the $$u_i$$ to the $$v_i$$ and the $$e_j$$ to the $$e'_j$$ is the desired isometry.

For all $$x \in E$$, there exist $$\lambda_i$$, $$1 \leq i \leq m$$, such that $$x = \sum_{i=1}^{k} \lambda_i u_i + \sum_{i=k+1}^{m} \lambda_i e_i$$.

This implies $$\phi(x) = \sum_{i=1}^{k} \lambda_i v_i + \sum_{i=k+1}^{m} \lambda_i e'_i.$$.

We know that $$\langle u_i,e_j \rangle = 0$$ and $$\langle v_i, e'_j \rangle = 0$$, so $$\|x\|^2 = \sum_{i=1}^{k} \lambda_i \lambda_j \langle u_i, u_j \rangle + \sum_{i=k+1}^{m} \lambda_i^2 = \sum_{i=1}^{k} \lambda_i \lambda_j \langle v_i, v_j\rangle + \sum_{i=k+1}^{m} \lambda_i^2 = \| \phi(x) \|^2.$$ We are left to show that $$\phi(u_j) = v_j$$ for all $$j > k$$. We know that there exist $$\lambda_i$$, $$1 \leq i \leq k$$, such that $$u_j = \sum_{i=1}^k \lambda_i u_i.$$ Expanding the square of the norms gives $$\Bigl\| u_j - \sum_{i=1}^k \lambda_i u_i \Bigr\|^2 = \Bigl\| v_j - \sum_{i=1}^k \lambda_i v_i \Bigr\|^2$$ and we can conclude $$\displaystyle v_j = \sum_{i=1}^k \lambda_i v_i = \sum_{i=1}^k \lambda_i \phi(u_i) = \phi(u_j).$$

Start with full rank: if all nonsingular, $$I = A^{-1} A A^T (A^T)^{-1} = A^{-1} B B^T (A^T)^{-1},$$ $$I = (A^{-1} B ) (A^{-1} B )^T$$