2
$\begingroup$

I have a matrix $A$ $(n\times n)$ with eigenvalues $\lambda_i$, then I add another matrix to it as: $A+xx^\top$ where $x$ $(n\times 1)$ is a column vector.

and also $A=yy^\top$ with $y$ a $(n-1)$ rank matrix, so A is symmetric.

Is there any way to calculate the new eigenvalues and eigenvectors of $(xx^\top+yy^\top)$ using the information from the vector $x$ and the eigenvalues and eigenvectors of $yy^\top$

$\endgroup$
2
  • $\begingroup$ no, you will also need information on the eigenvectors of $yy^\top$, only having information on its eigenvalues is insufficient; $\endgroup$ Apr 12, 2023 at 5:57
  • $\begingroup$ Sorry, I didn't make the known conditions clear. If the eigenvalues and eigenvectors of yyT are known and x is known, can this go for the eigenvalues and eigenvectors of (xxT + yyT)? $\endgroup$
    – brant
    Apr 12, 2023 at 6:18

1 Answer 1

5
$\begingroup$

Given eigenvectors and eigenvalues of the symmetric matrix $A$, you can transform to a basis where $A$ is a diagonal matrix $D$; the vector $x$ in that basis transforms to $\tilde{x}$. Then the problem is that of computing the eigenvalues of a rank-one update $D+\tilde{x}\tilde{x}^\top$ of a diagonal matrix. An efficient algorithm is given in a paper by Golub, page 325. Once you have the eigenvalues the eigenvectors follow directly from the Bunch–Nielsen–Sorensen formula.

$\endgroup$
7
  • $\begingroup$ One thing that confuses me about Golub's article(page 325) is whether there are conditions on the vector \mathbf{u} that define its positivity or negativity. I don't quite understand the discussion about the positivity and negativity of \sigma. $\endgroup$
    – brant
    Apr 13, 2023 at 6:35
  • 1
    $\begingroup$ Golub writes the rank-one-update as $D+\sigma uu^\top$, and then considers separately the case of positive and negative $\sigma$; you can just set $\sigma=1$, and ignore the case of negative $\sigma$. $\endgroup$ Apr 13, 2023 at 7:55
  • 1
    $\begingroup$ this is really the same problem; given $A=xx^\top+yy^T$, seek the eigenvalues of $A-xx^\top$ -- so this is Golub's $D+\sigma uu^\top$ with $\sigma=-1$. $\endgroup$ Apr 13, 2023 at 12:53
  • 2
    $\begingroup$ for pointers to the literature on low-rank updates, see mathoverflow.net/a/143555/11260 $\endgroup$ Apr 14, 2023 at 8:46
  • 1
    $\begingroup$ @brant -- a new question needs a new post; one question per post, please. $\endgroup$ Jun 12, 2023 at 12:52

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.