Question about the Proof of PCA in "Learning from Data" by Shwartz and Ben-David, P. 280-281 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

 A: 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}$.
