3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $? $\endgroup$ – Royi Jan 29 at 21:06
  • $\begingroup$ 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. $\endgroup$ – coudy Jul 3 at 14:20
1
$\begingroup$

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). $

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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 $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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