Question about the Proof of PCA in “Learning from Data” by Shwartz and Ben-David, P. 280-281

Question

Does anyone know how to justify the red and blue line in the attached proof of PCA?

Red line: $B \in \mathbb{R}^{ d \times n}$, arrange $B = [B_{j,1} | B_{j,2} | \cdots | B_{j,n}]$, then $B^\top B = \sum_{j = 1}^d \sum_{i = 1}^n B_{j,i}^2$. Since the columns are orthonormal, therefore $\sum_{i = 1}^n B_{j,i}^2 = 1$, hence $B^\top B = \sum_{j = 1}^d 1 = d$ not equal to $n$ as claimed.

Blue line: I do not see where the equality comes from. Why is it that for every orthogonal matrix $U \in \mathbb{R}^{ d\times n}$ you have an inequality on the trace, but as soon as you have that all columns of $U$ are the leading eigenvector of $A = X^\top X$, you obtain an equality?

See below for the relevant parts of the proof

Answer 1

The red line is correct. $B \in \mathbb{R}^{d \times n}$ is an orthogonal matrix, so each column has an $\ell_2$-norm of 1. Because each column vector of a matrix has length equal to the number of rows ($d$ in this case) of the matrix, the sum of the squared elements of a column vector should be a sum with $d$ summands, not $n$ as you wrote. So the correct expression is $\sum_{j=1}^d B_{j,i}^2 = 1$ for $i = 1, \dots, n$, and hence $\sum_{i=1}^n \sum_{j=1}^d B_{j,i}^2 = n$ (the source writes these sums in the more confusing order).

The blue line supposes that $U$ is the matrix whose columns are the $n$ leading eigenvectors of $A$. An eigenvector of $A$ by definition is a vector $x \ne 0$ where $Ax = \lambda x$. Thus, if the columns $u_j$ of $U$ are the leading eigenvectors, $Au_j = \lambda_j u_j$. So you can derive \begin{align} U^\text{T} A U & = U^\text{T} A \left[ \begin{matrix} | & & | \\ u_1 & \dots & u_n \\ | & & |\end{matrix} \right] \\ & = U^\text{T} \left[ \begin{matrix} | & & | \\ A u_1 & \dots & A u_n \\ | & & |\end{matrix} \right] \\ & = U^\text{T} \left[ \begin{matrix} | & & | \\ \lambda_1 u_1 & \dots & \lambda_n u_n \\ | & & |\end{matrix} \right] \\ & = \left[ \begin{matrix} - & u_1 & - \\ & \vdots & \\ - & u_n & -\end{matrix} \right] \left[ \begin{matrix} | & & | \\ \lambda_1 u_1 & \dots & \lambda_n u_n \\| & & |\end{matrix} \right] \\ & = \left[ \begin{matrix} \lambda_1 & 0 & \dots & 0 \\ 0 & \lambda_2 & & \vdots \\ \vdots & & \ddots \\ 0 & \dots & & \lambda_n \end{matrix} \right] \\ & = \text{diag} (\lambda_1, \dots, \lambda_n) \end{align} and now you can apply the definition of the trace to see that $\text{trace} (U^\text{T} A U) = \sum_{j=1}^n \lambda_j = \sum_{j=1}^n D_{j, j}$.