Eigenvector Perturbation with a symmetric matrix Consider the matrix $ \mathbf{M} = \lambda_1 x x^T + \frac{\lambda_2}{2}(\mathbf{A}+\mathbf{A}^T)$, where $x \in \mathbb{R}^n$ is a unit norm vector, and $\mathbf{A}$ is a full rank matrix in $\mathbb{R}^{n \times n}$ with $\|\mathbf{A}\|_F = 1$. Let $u$ be the top eigenvector of $\mathbf{M}$, and suppose that $\lambda_1 > \lambda_2$, is there any theorem lower bounding $\langle x,u \rangle$?
 A: I assume that we have $\lambda_1 > \lambda_2 \geq 0$.
By the Rayleigh-Ritz theorem, we note that
$$
\lambda_{\max}(M) = \max_{\|y\|=1} y^TMy = \max_{\|y\|=1} \lambda_1 |x^Ty|^2 + 
\lambda_2\,y^TAy,
$$
and the vector $y$ for which this maximum is attained is an eigenvector. Thus, we see that
$$
\lambda_{\max}(M) \geq x^TMx = \lambda_1 + \lambda_2\,x^TAx.
$$
Because $y = u$ maximizes $y^TMy$ over the unit vectors $y$, we have
\begin{align}
u^TMu &\geq x^TMx \implies\\
\lambda_1|u^Tx|^2 + \lambda_2 u^TAu &\geq \lambda_1 + \lambda_2 x^TAx \implies\\
|u^Tx|^2 & \geq \frac{\lambda_1 + \lambda_2(x^TAx - u^TAu)}{\lambda_1}.
\end{align}
Now, because $\|A\|_F = 1$, we have $-1 \leq y^TAy \leq 1$ for all unit-vectors $y$. Thus, we can relax the above bound to get
$$
|u^Tx|^2 \geq \frac{\lambda_1 - 2\lambda_2}{\lambda_1}.
$$

Another approach: with the assumption with $u^Tx = 0$, we want a lower-bound to $\lambda_2$. Let $\lambda = \lambda_{\max}(M)$. Define $S = \frac {1}2(A + A^T)$. We know that
$$
Mu = \lambda u \implies \lambda_2 Su = \lambda u.
$$
That is, $\lambda$ is an eigenvalue of $\lambda_2 S$. However, $\|S\|_F \leq 1$ implies that $|\lambda| \leq \lambda_2$. Moreover, we note that
$$
|x^T(\lambda_2 S)x| \leq \sqrt{\lambda_2^2 - \lambda^2}.
$$
Now, we have
\begin{align}
u^TMu &\geq x^TMx \implies\\
\lambda &\geq \lambda_1 + \lambda_2 x^TSx \implies\\
\lambda & \geq \lambda_1 - \sqrt{\lambda_2^2 - \lambda^2}\implies\\
\lambda + \sqrt{\lambda_2^2 - \lambda^2}
& \geq \lambda_1.
\end{align}
For any $0\leq \lambda_2< \lambda_1$, consider the function
$$
f(x) = x + \sqrt{\lambda_2^2 - x^2}.
$$
We note that $f(0) = \lambda_2 < \lambda_1$, but $f(\lambda)\geq \lambda_1$. So,
$\lambda_2$ must be such that there is a solution to $f(x) = \lambda_1$ over the domain $0 \leq x \leq \lambda_2$. We rewrite
$$
x + \sqrt{\lambda_2^2 - x^2} = \lambda_1 \implies\\
\sqrt{\lambda_2^2 - x^2} = \lambda_1 - x \implies\\
\lambda_2^2 - x^2 = x^2 - 2 \lambda_1x + \lambda_1^2 \implies\\
2x^2 - 2\lambda_1 x + (\lambda_1^2 - \lambda_2^2) = 0.
$$
First of all, in order for a solution to this equation to exist, the discriminant  of the equation must be non-negative. We find
$$
(2\lambda_1)^2 - 8(\lambda_1^2 - \lambda_2^2) \geq 0 \iff 8\lambda_2^2 - 4\lambda_1^2 \geq 0,\\
$$
which is to say that we have $\lambda_2 \geq \lambda_1/\sqrt{2}$
so a solution $x \in \Bbb R$ to the above equation exists. This equation has two positive roots, and the smaller of these two roots must satisfy $x \leq \lambda_2$. In other words, $\lambda_2$ must be such that
$$
\frac{4\lambda_1^2 - \sqrt{8\lambda_2^2 - 4\lambda_1^2}}{4} \leq \lambda_2.
$$
