# Eigen Values of Sum of Negative Definite Matrix and a rank-one Positive SemiDefinite Matrix , i.e. ($A+xx^{H}$)

Assume all matrices I discuss about are complex $N\times N$ matrices. I have a negative definite hermitian matrix $A$ whose eigen values are $(-c\lambda ,-\lambda,\ldots-\lambda)$ where $c$ and $\lambda$ are positive constants. I also have a rank one positive semi-definite hermitian Matrix $xx^{H}$ (whose eigen values clearly are $(||x||^{2},0,0...0)$. I am familiar with weyl's inequalities. I was wondering if one can find a exact formula for the eigen values of the matrix $B=A+xx^{H}$.

EDIT---

(thanks to users @adamW and @David) I have been able to reduce the problem to a seemingly simple one. There is a diagonal matrix $D$ such that all its entries are zero except for the one in the $(1,1)^{th}$ position, say $D(1,1)=c$ (hence eigen values are $(c,0,\ldots,0)$. I have another rank one positive-semi definite matrix $xx^H$ (again, whose eigen values clearly are $(||x||^{2},0,0...0)$. Even now I can't seem to find a clear solution for this seemingly simple problem. To put everything in perspective, I have the following matrix

\begin{align} B &=D+xx^H \\ D &= \left[ \begin{array}{cccc} c & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 \\ \ldots & 0 & 0 & 0 \\ 0 & \dots & 0 & 0 \end{array} \right] \end{align}

what are the eigen values of $B$

-
We can write $A=PDP^H$ and $x=Py$ for some $y$, where $P$ is unitary and $D$ is diagonal. –  Davide Giraudo Oct 13 '12 at 9:34
So the question should boil down to the eigen values of $D+y*y^{H}$ ie sum of a diagonal matrix and a rank-one matrix, is that what you wanted to point out (leaving the rest for me to figure out:):))? –  dineshdileep Oct 13 '12 at 9:41
There is an exact formula, it is a polynomial of the full degree $N$, so it is not a reduction in the problem. That it looks simpler in the form $D+yy^H$ is about it. –  adam W Oct 13 '12 at 11:34
@adamW I guess you are talking about the characteristic equation. I have no utility with it (ofcourse, no chance for N>5). I want to find a solution in terms of $c$, $\lambda$ and (||x||^2). Now I guess if you add a scalar multiple of Identity Matrix to a hermitian matrix, every eigen value gets added by the same scalar. Now the matrix I consider have all diagonal entries same except for the first one. So I was wondering if we could find a exact solution as we have for the case of scaled identity matrix. –  dineshdileep Oct 13 '12 at 18:57
Yes, I can fully understand the idea that it seems so close to being that simple, but the fact is that changing even one element of the identity matrix changes its spectrum, and things just aren't nice anymore, even though intuition might speak to otherwise. I hope someone does give you a good answer here, I would like to see it myself. –  adam W Oct 14 '12 at 0:40

The two matrices play more symmetric roles in this than is apparent from your formulation. We can state the problem more symmetrically and basis-independently as finding the eigensystem of

$$B=xx^H+yy^H\;,$$

where your formulation arises if we choose a basis in which $y$ is the first basis vector.

Choose a basis in which the first two basis vectors span $x$ and $y$, and solve the resulting two-dimensional eigenvalue problem exactly.

-
Do you mean to say that, I need to find a orthonormal basis whose first two vectors span $x$ and $y$ and hence find a decomposition for $B$ in terms of those vectors. Thus the eigen values will be the co-efficients in the rank-one decomposition of $B$ in terms of this orthonormal vectors. Seems like straight forward. I will try it and let you know. –  dineshdileep Oct 14 '12 at 7:10
@dineshdileep: Yes, that's what I mean. –  joriki Oct 14 '12 at 9:06

The original question (before the edit) involves a full rank matrix (specifically it is similar to $-\lambda \mathbf{I} + \vec{e_0}(\lambda-c\lambda) \vec{e_0}^T$ or in words the identity with the corner adjusted to be $-c$). Finding a rank one update to that is the same problem as the general rank one update for a full rank matrix. I believe they call it something different than the characteristic formula when talking rank one updates (but from what I read and understood it is a full scale polynomial also, just with poles as well as zeros).

Your after edit version involves a lesser rank, so if indeed that is the problem of interest, it is as easy as the 2nd order polynomial-- it is of rank two, your matrix $B = D +xx^H$.

Try this: if $B = yy^T + xx^T$ then solve for the eigenvectors a combination of the two (since any orthogonal to both $x$ and $y$ are obviously with eigenvalue of zero) $$\pmatrix{ax^T + by^T \\ cx^T + dy^T}(yy^T + xx^T) = \pmatrix{\lambda_0 & 0\\0 & \lambda_1}\pmatrix{ax^T + by^T \\ cx^T + dy^T}$$

A side note, a rank two matrix may be written as $\pmatrix{x & y}\pmatrix{a & b \\ c & d}\pmatrix{x^T\\ y^T}$ and what is left to diagonalize is the $2 \times 2$ matrix $\pmatrix{a &b \\ c & d}$

-
Yes it was indeed the way you showed, that the problem can be reduced. We skip the identity matrix portion from the $-\lambda \mathbf{I} + \vec{e_0}(\lambda-c\lambda) \vec{e_0}^T$, Hence we get the diagonal matrix with entry only in one corner. We can skip the identity matrix because adding a scaled identity matrix is equivalent to adding to every eigen value that same scale. Hence we have the reduced problem to find the eigen value of the problem after the EDIT. I will definitely try what you suggested and let you know. –  dineshdileep Oct 15 '12 at 2:26
That is called deflating the problem, when some eigenvalue(s) is(are) known. Maybe I was wrong to not consider that from your original problem statement. But a rank one update is not generally nice. Here it must fit with your original spectrum I think? –  adam W Oct 15 '12 at 12:37
Ah, I see, the deflation was indeed huge here, with the repeated $\lambda$! That has a large dimensional spectrum that can act nicely! –  adam W Oct 15 '12 at 13:27