4
$\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$？

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ no, you will also need information on the eigenvectors of $yy^\top$, only having information on its eigenvalues is insufficient; $\endgroup$
    – Carlo Beenakker
    Commented 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
    Commented Apr 12, 2023 at 6:18

1 Answer 1

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

Improve this answer
$\endgroup$
9
  • $\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
    Commented 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$
    – Carlo Beenakker
    Commented 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$
    – Carlo Beenakker
    Commented Apr 13, 2023 at 12:53
  • 2
    $\begingroup$ for pointers to the literature on low-rank updates, see mathoverflow.net/a/143555/11260 $\endgroup$
    – Carlo Beenakker
    Commented Apr 14, 2023 at 8:46
  • 1
    $\begingroup$ @brant -- a new question needs a new post; one question per post, please. $\endgroup$
    – Carlo Beenakker
    Commented Jun 12, 2023 at 12:52

You must log in to answer this question.

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