4
$\begingroup$

If $B$ is a symmetric matrix then how do its eigenvalues compare to the eigenvalues of $B - vv^T$? ( where $v$ is a vector of the same dimension as $B$)


I guess that the eigenvalues of $B - vv^T$ will downward interlace the eigenvalues of $B$. Like $\lambda_{min} (B - vv^T) \leq \lambda_{min} (B)$.

$\endgroup$
2
  • 1
    $\begingroup$ I think your guess follows from the minimax characterization of eigenvalues. $\endgroup$ Jan 9, 2015 at 8:45
  • 1
    $\begingroup$ I would like to know of a proof of what exactly happens.. $\endgroup$
    – user6818
    Jan 9, 2015 at 8:47

5 Answers 5

3
$\begingroup$

I'm not sure if this is what you're looking for, but you could apply standard rank one theory to your problem. First of all, I want to assume that $v$ is cyclic for $B$; if this is not the case, then I can restrict attention to the reducing subspace $V$ that is spanned by the $B^nv$, $n\ge 0$. On $V^{\perp}$, the matrices $B$ and $A=B-vv^*$ agree.

Under this extra assumption, $v$ is then also cyclic for $A$. Write $F(z) = v^*(B-z)^{-1}v$, $G(z)=v^*(A-z)^{-1}v$ for the matrix elements of the resolvents. From the resolvent identity $$ (A-z)^{-1} - (B-z)^{-1} = (A-z)^{-1} vv^*(B-z)^{-1} $$ I obtain that $$ G(z) = \frac{F(z)}{1-F(z)} . $$ Thus the eigenvalues of $A$ are the points where $F=1$. This reproves the interlacing property (because $F$ increases from $-\infty$ to $\infty$ between two consecutive eigenvalues of $B$) and gives somewhat more explicit information.

$\endgroup$
4
  • $\begingroup$ sorry if this is well-known (don't know much about matrix resolvents), but why does $F(z)$ increase from $-\infty$ to $\infty$ between eigenvalues? $\endgroup$
    – Ivan
    Jun 14, 2019 at 5:32
  • $\begingroup$ @Ivan: The ev's are the poles, and the monotonicity can be confirmed by just taking the derivative (on the real line) of $F(z) = \sum g_j/(\lambda_j-z)$. $\endgroup$ Jun 14, 2019 at 6:33
  • $\begingroup$ thanks for getting back to me. What if the eigenvalues have even multiplicities or the coefficients in the Laurent series of $F$ are zero at some of the eigenvalues? $\endgroup$
    – Ivan
    Jun 14, 2019 at 15:29
  • $\begingroup$ @Ivan: That can't happen because $v$ is cyclic by assumption, so all ev's have multiplicity one. $\endgroup$ Jun 14, 2019 at 23:39
3
$\begingroup$

As suggested in the comments, this follows from the variational characterization of eigenvalues of symmetric matrices. For example, $\lambda_{\min}(A) = \min_{x\cdot x =1} x\cdot A x$.

Let $y$ minimize $y\cdot B y$, then:

$$\begin{aligned} \lambda_{\text{min}}(B-vv^T) &= \min x\cdot(B-vv^T)x\\ & \le y\cdot(B-vv^T)y\\ & = y\cdot By-(v\cdot y)^2\\ & = \lambda_{\text{min}} (B) - (v\cdot y)^2 \le \lambda_{\text{min}} (B) \end{aligned}$$

$\endgroup$
3
$\begingroup$

It seems to be "Cauchy's Interlacing Theorem" -- see Lemma 3.4 here: http://arxiv.org/pdf/1408.4421v1.pdf

$\endgroup$
1
  • $\begingroup$ I don't think this works for $B-vv^\top$, only for $B+vv^\top$. $\endgroup$
    – dohmatob
    Apr 19, 2021 at 22:22
1
$\begingroup$

Since $B-(B-vv^T)$ is positive semidefinite, the $j$-th largest eigenvalue of $B$ is no less then the $j$-th largest eigenvalue of $B-vv^T$. This is a pretty known result. The proof is a quick use of min-max theorem; see https://en.wikipedia.org/wiki/Min-max_theorem

$\endgroup$
1
0
$\begingroup$

An interlacing result is in Theorem 4.3.4 of Horn, Johnson, Matrix Analysis (first edition - sorry, I don't have a copy of the second): for each Hermitian $B$, $$ \lambda_k(B) \leq \lambda_{k+1}(B\pm vv^*) \leq \lambda_{k+2}(B), \quad k=1,2,\dots,n-2. $$

$\endgroup$
2
  • 1
    $\begingroup$ I had checked this before I posted this question. This above theorem is I think weaker than what the question asks. Like for positive semi-definite case a stronger statement is known to be true - theorem 1.1 here - ima.umn.edu/preprints/AUGUST1992/1018.pdf $\endgroup$
    – user6818
    Jan 9, 2015 at 10:26
  • $\begingroup$ @user6818 I agree with you that this is weaker and probably not satisfying. I don't know a stronger result though, sorry. $\endgroup$ Jan 9, 2015 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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