4.6 Exercises

1. In this question we will prove part (ii) of ????????????? Result 5.1 in the lecture notes.
   • Define \[ b_{ij}=(\mathbf x_i-\bar{\mathbf x})^\top (\mathbf x_j-\bar{\mathbf x}), \quad i,j=1, \ldots , n, \] and write \(\mathbf B=(b_{ij})_{i,j=1}^n\). Prove that \[\mathbf B=(\mathbf H\mathbf X)(\mathbf H\mathbf X)^\top,\] where \(\mathbf H\) is the \(n \times n\) centering matrix and \(\mathbf X= (\mathbf x_1, \ldots , \mathbf x_n)^\top\) is the data matrix.
   • Show that \(\mathbf B\) is positive semi-definite (in which case part (ii) of Result 5.1 holds). Hint: explain why, for all \(n \times 1\) vectors \(\mathbf a\), \[ \mathbf a^\top \mathbf B\mathbf a=\mathbf a^\top (\mathbf H\mathbf X) (\mathbf H\mathbf X)^\top \mathbf a\geq 0. \]
2. In this question we will prove part (iii) of Result 5.1.?????????????

- Prove Property 7. of Section \@ref(centering-matrix).  Specifically: if $\bA$ is a  symmetric $n \times n$ matrix, and $\bH=\bI_n -n^{-1} {\bf 1}_n{\bf 1}_n^\top$ is the $n \times n$ centering matrix, show that $\bB$ defined by

\[\mathbf B= \mathbf H\mathbf A\mathbf H\] has elements given by \[ b_{ij}=a_{ij}-\bar{a}_{i+}-\bar{a}_{+j}+\bar{a}_{++}, \qquad i,j=1, \ldots , n, \] where
\[\bar{a}_{i+}= \frac{1}{n} \sum_{j=1}^n a_{ij}, \quad \bar{a}_{+j}=\frac{1}{n} \sum_{i=1}^n a_{ij}, \quad\mbox{and} \quad\bar{a}_{++} = \frac{1}{n^2} \sum_{i,j=1}^n a_{ij}.\]

- Assume that $\bB$ is positive semi-definite with $k$ strictly positive eigenvalues and let

\[ \mathbf B= \sum_{j=1}^k \lambda_j \mathbf q_j\mathbf q_j^\top =\mathbf Q\boldsymbol \Lambda\mathbf Q^\top, \] where \(\boldsymbol \Lambda=\text{diag}\{\lambda_1, \ldots , \lambda_k\}\) and \(\mathbf Q\) is \(n \times k\) and satisfies \(\mathbf Q^\top \mathbf Q=\mathbf I_k\). Now define a ‘new’ \(n \times k\) data matrix \[ \mathbf X=[\mathbf x_1, \ldots , \mathbf x_n]^\top=\mathbf Q\boldsymbol \Lambda^{1/2}. \] Show that \(b_{ij}=\mathbf x_i^\top \mathbf x_j\) for all \(i,j=1, \ldots , n\).
Hint: check that for \(\mathbf X\) defined as above, \(\mathbf X\mathbf X^\top =\mathbf B\).

- We now need to show that $\bD=(d_{ij})$ represents the set of inter-point distances for this new data matrix.  Recall that $a_{ij}=-d_{ij}^2/2$.  Deduce that

\[ (\mathbf x_i -\mathbf x_j)^\top (\mathbf x_i-\mathbf x_j)= b_{ii} + b_{jj}-2b_{ij}; \] and so, using the first part of this question, show that \[ (\mathbf x_i -\mathbf x_j)^\top (\mathbf x_i-\mathbf x_j)=-2a_{ij}=d_{ij}^2. \] Hence the new inter-point distances are the same as the original ones, and part (iii) of Result 5.1 is proved.