A max-min inequality for a rank-1 perturbed symmetric matrix

Question

Can someone explain why the underlined inequality is true? Thank you for your time.

Answer 1

I just realized that this is just a consequence of the Courant-Fischer theorem for symmetric matrices which states that $\substack{\text{max}\\\text{dim}(L)=k}\substack{\text{min}\\x\in L\\x\neq0}\dfrac{x^\text{T}Ax}{x^\text{T}x}=\lambda_k(A)$ with the eigenvalues ordered as $\lambda_1(A)\geq\lambda_2(A)\geq\cdots\geq\lambda_n(A).$

Answer 2

In the first underlined statement, the minimum is taken over a $k-1$ dimensional space. That is the space selected by the max operator minus $p$. In the second underlined statement, the minimum is again taken over a $k-1$ dimensional space. However, the max operator can now select that space, and it may include a direction not perpendicular to $p$. Therefore, the max operator may be able to achieve a higher value than before. The value is always at least as good, since it can always select the same space as before minus $p$.