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

\[\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*} \]

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\)