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

• I guess you also need to assume $u$ normalized? Then Cauchy Schwartz gives a trivial bound. Jan 3 at 11:40
• Yes, $u$ is normalized. But, I need a lower bound for $\langle u, x \rangle$ Jan 3 at 11:51
• There is no way to constrain whether $\langle x,u\rangle$ is positive or negative since if $u$ is a top eigenvector, then so is $-u$. The best we can hope for is to get a lower bound to $|\langle x,u\rangle|$. Jan 4 at 14:59

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

• Thanks for your solution! I have a question regarding the final bound you derived. If $\lambda_2 > \lambda_1/2$, then this bound would be trivial. What can we say in that case? And, are there any conditions that we can impose to make this bound tighter? Jan 5 at 10:58
• @Rostam22 I that case, there is no statement that can be made with the same kind of generality as the bound that I give. We can make the bound tighter if something is known about $x^TAx$. For instance, if $x^TAx \geq 0$, then we end up with $(\lambda_1 - \lambda_2)/\lambda_1$ instead. Jan 5 at 14:44
• @Rostam22 Actually, I'm probably wrong to say that there is no other such statement. In any case, I've added a bit to my answer: $\lambda_2 < \frac 23 \lambda_1^2$ is enough to guarantee that $\langle u,x \rangle \neq 0$. Jan 5 at 16:00
• For 2, I think I've fixed the error. For 3, no I don't know of such a reference. Jan 5 at 19:17
• Regarding 1: $u$ is an eigenvector of $S$, so the Courant Fischer theorem implies that $x^TSx$ is at most equal to the second largest eigenvalue of $S$ and at least equal to the smallest. Moreover, because $S$ is symmetric, $\|S\|_F^2$ is equal to the sum of the squares of the eigenvalues of $S$. Jan 5 at 19:21