# Gramian Determines Shape

Problem. Let $$\{v_1,\cdots,v_s\}$$ and $$\{w_1,\cdots,w_s\}$$ be two subsets of $$\mathbb{R}^n$$. Show that there exists $$A\in O(n)$$ such that $$Av_i=w_i\ (1\le i\le s)$$ iff $$\langle v_{i}, v_{j}\rangle=\langle w_{i}, w_{j}\rangle\ (1\le i,j\le s)$$, i.e., the two Gramians are equal.

Proof (Haosen CHEN).
$$(\Rightarrow):$$

\begin{align*}G(w_{1},\cdots,w_{s})&=(w_{1}\ \cdots\ w_{s})^{T}(w_{1}\ \cdots\ w_{s})\\&=(v_{1}\ \cdots\ v_{s})^{T}A^TA(v_{1}\ \cdots\ v_{s})\\&=(v_{1}\ \cdots\ v_{s})^{T}(v_{1}\ \cdots\ v_{s})=G(v_1,\cdots,v_s).\end{align*}

$$(\Leftarrow)$$:
Note that

\begin{align*}\text{rank}\,(v_{1}\ \cdots\ v_{s})&=\text{rank}\,G(v_1,\cdots,v_{s})\\ &=\text{rank}\, G(w_1,\cdots,w_s)=\text{rank}\,(w_{1}\ \cdots\ w_{s})\end{align*}

Denote $$r:=\text{rank}\,(v_{1}\ \cdots\ v_{s})$$. Without loss of generality, assume that $$v_1,\cdots,v_r$$ are linearly independent. We claim that $$w_1,\cdots,w_r$$ are linearly independent as well. Indeed,

\begin{align*} \text{Null}\,(w_1\ \cdots\ w_r)&=\text{Null}\,(w_1\ \cdots\ w_r)^T(w_1\ \cdots\ w_r)\\ &=\text{Null}\,(v_1\ \cdots\ v_r)^T(v_1\ \cdots\ v_r)=\text{Null}\,(v_1\ \cdots\ v_r)=0 \end{align*}

Therefore, there exist $$B,C\in M_{r\times (s-r)}(\mathbb{R})$$ such that

\begin{align*} (v_1\ \cdots\ v_s)&=(v_1\ \cdots\ v_r)(I_r\ |\ B)\\ (w_1\ \cdots\ w_s)&=(w_1\ \cdots\ w_r)(I_r\ |\ C) \end{align*}

Denote $$G:=G(v_1,\cdots,v_r)=G(w_1,\cdots,w_r)$$. Since $$\text{rank}(G)=\text{rank}(v_1\ \cdots\ v_r)=r$$, the matrix $$G$$ is invertible. Thus we have

$\begin{pmatrix} I_r\\\hline B^T \end{pmatrix}\,G\,(I_r\ |\ B)=\begin{pmatrix} I_r\\\hline C^T \end{pmatrix}\,G\,(I_r\ |\ C)\implies GB=GC\implies B=C$

Now, it suffices to find some $$A\in O(n)$$ such that

$A(v_1\ \cdots\ v_r)=(w_1\ \cdots\ w_r)$

By QR decomposition, we have

$(v_1\ \cdots\ v_r)=Q_1R_1,\quad (w_1\ \cdots\ w_r)=Q_2R_2$

where $$R_i\in M_{r\times r}(\mathbb{R})$$ is an upper triangular matrix with positive digonal entries and $$Q_i\in M_{n\times r}(\mathbb{R})$$ satisfies $$Q_i^TQ_i=I_r$$ (semi-orthogonal). Thus we have

$(Q_1R_1)^TQ_1R_1=(Q_2R_2)^TQ_2R_2\implies R_1^TR_1=R_2^TR_2$

By the uniqueness of Cholesky decompostion, we have $$R_1=R_2$$. Indeed, $$R_1R_2^{-1}=(R_1^{T})^{-1}R_2^T$$ is upper triangular and lower triangular at the same time, and hence a diagonal matrix, denoted by $$D$$. Then

$R_1=DR_2,\ R_2^T=R_1^TD\implies D=I_r\implies R_1=R_2$

Now it suffices to find some $$A\in O(n)$$ such that

$AQ_1=Q_2$

Since the columns of $$Q_i$$ forms an orthonormal subset of $$\mathbb{R}^n$$ and thus extends to an orthonormal basis of $$\mathbb{R}^n$$, there exists $$\widehat{Q}_i\in O(n)$$ such that $$\widehat{Q}_i=(Q_i\ |\ X_i)$$ for some $$X_i\in M_{n\times (n-r)}(\mathbb{R})$$. Now define $$A:=\widehat{Q}_2\widehat{Q}_1^{-1}$$. Then $$A\in O(n)$$ and $$AQ_1=Q_2$$, as desired. $$\blacksquare$$