3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ I guess you also need to assume $u$ normalized? Then Cauchy Schwartz gives a trivial bound. $\endgroup$ Jan 3 at 11:40
  • 1
    $\begingroup$ Yes, $u$ is normalized. But, I need a lower bound for $\langle u, x \rangle$ $\endgroup$
    – Rostam22
    Jan 3 at 11:51
  • 1
    $\begingroup$ 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|$. $\endgroup$ Jan 4 at 14:59
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Rostam22
    Jan 5 at 10:58
  • $\begingroup$ @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. $\endgroup$ Jan 5 at 14:44
  • $\begingroup$ @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$. $\endgroup$ Jan 5 at 16:00
  • 1
    $\begingroup$ For 2, I think I've fixed the error. For 3, no I don't know of such a reference. $\endgroup$ Jan 5 at 19:17
  • 1
    $\begingroup$ 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$. $\endgroup$ Jan 5 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.