Eigenvector Perturbation with a symmetric matrix

Question

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$?

Answer 1

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