From PCA formulation, we know that
\[ \max_{x^T x=1} x^T M x = \lambda_{\max}(M) \]
So the problem reduces to finding the largest eigenvalue of \(M\).
Important property: Non-zero eigenvalues of \(AB\) and \(BA\) are the same.
Hence, non-zero eigenvalues of \(\mathbf{1}\mathbf{1}^T\) will be the same as \(\mathbf{1}^T\mathbf{1}\).
Notice that, $ \mathbf{1}\mathbf{1}^T = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & \dots & 1 \end{bmatrix} $, $ \mathbf{1}\mathbf{1}^T$ is a matrix of $n \times n $.
And $ \mathbf{1}^T\mathbf{1} = \begin{bmatrix} 1 & 1 & \dots & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} $, is scalar ( or think like a matrix of $1 \times 1$).
\[ \mathbf{1}^T\mathbf{1} = 1+1+\dots+1 = n \]
$ \mathbf{1}^T\mathbf{1} $ is a \(1\times1\) matrix (a scalar). Its only eigenvalue is \(n\).
Therefore, \(\mathbf{1}\mathbf{1}^T\) has exactly one non-zero eigenvalue: $ n $
All remaining eigenvalues of \(\mathbf{1}\mathbf{1}^T\) are \(0\).
Now consider $ M = I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T $
Scaling by \( \frac{1}{n} \) scales eigenvalues, so $ \frac{1}{n}\mathbf{1}\mathbf{1}^T $ has eigenvalues $ 1, 0, 0, \dots, 0 $
So eigenvalues of \(M\) are $1 \text{ (multiplicity } n-1), \quad 0 $
Hence the highest eigenvalue of \(M\) is $ \boxed{1} $.
