# 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

• For the red lines, this is an application of orthonormal. For the blue lines, you just combine the fact that the $U$ are orthonormal with the definition of the trace. – Sycorax Sep 25 '20 at 22:02
• @Sycorax Hi, I'm still not sure about the red line as I did apply orthogonality, and the sum doesn't feel correct to me, and for the blue line, I can apply that $U^\top A U$ has the same eigenvalue as $A$, and trace is the sum of eigenvalues. However, $U$ does not necessarily have to be the n leading eigenvector of $A$, in fact any orthogonal matrix $U$ suffices for $U^\top AU$ to be a similarity transformation, so why is it not held with equality for any $U$ with orthonormal column? – Eldacar Hyarmendacil Sep 26 '20 at 0:05

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