Proving the positive semidefiniteness of a matrix

Question

In the recursive construction of the eigendecomposition for a symmetric real matrix $A$, the first step involves finding a vector $u$ that maximizes $u^TAu$ subject to $\|u\|=1$. Now, let $P_1 = u^TAu$. How would one show that the matrix $(P_1 I - A)$ is positive semidefinite?

Answer 1

For any vector $x$ with $\|x\| = 1$, we have:

$x^T(P_1I-A)x = P_1\|x\|^2 - x^TAx = P_1 - x^TAx \ge P_1 - \max\limits_{\|x\| = 1}x^TAx = P_1 - P_1 = 0$

where we used the fact that $P_1 = u^TAu = \max\limits_{\|x\| = 1}x^TAx$.

Since $x^T(P_1I-A)x \ge 0$ for all $x$ with $\|x\| = 1$, we have that $P_1I-A$ is positive semidefinite.