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

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

5 Answers 5

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Christian Remling
    Commented 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
    Commented 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$
    – Christian Remling
    Commented 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}$$

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I don't think this works for $B-vv^\top$, only for $B+vv^\top$. $\endgroup$
    – dohmatob
    Commented 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

Improve this answer
$\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. $$

Improve this answer
$\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
    Commented 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$
    – Federico Poloni
    Commented Jan 9, 2015 at 11:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .