Eigenvectors of rank one update matrix

eigenvalues-eigenvectorslinear algebramatrices

Let $D= \text{diag}\{d_1,d_2,\ldots,d_n\} \in \mathbb R^{n\times n}$ be the diagonal matrix, $v \in \mathbb R^{n}$ be the column vector. Then the eigenvalues of the rank one update matrix $D+\alpha vv^T$ can be found as roots of the secular equation:$$f(\lambda) = 1+\alpha \sum_{i=1}^n \frac{v_i^2}{d_i-\lambda}.$$ The corresponding eigenvectors can be found as $(D-\lambda I)^{-1}v.$ Here we assumed that $v_i\neq0$ and all $d_i$'s are different. When $v_i=0,$ the eigenvector of $D+\alpha vv^T$ will be the $i$-th standard vector. How do we find the eigenvectors when $d_i=d_{i+1}?$

Best Answer

This is a matter of making accurate case distinctions.

Some notation. Let $J=\{1,\ldots,n\}$ be our set of indices. Let $\Lambda=\{d_1,\ldots,d_n\}$ (we don't require $d_j$ be distinct, so $\Lambda$ may contain fewer than $n$ elements). For $\lambda\in\Lambda$, let $J_\lambda=\{j\in J : d_j=\lambda\}$. Finally let $$\Lambda'=\{\lambda\in\Lambda : v_j\neq 0\text{ for at least one }j\in J_\lambda\}.$$

Now let $(D+\alpha v v^\mathsf{T})x=\lambda x$ with $0\neq x\in\mathbb{R}^n$; that is, $(D-\lambda I)x=-\alpha(v^\mathsf{T}x)v$. Then the cases are:

  1. $\boxed{\lambda\notin\Lambda.}$ This corresponds to the "secular equation" in the question. Indeed, we have $\alpha(v^\mathsf{T}x)\neq 0$, and the vector $y=-x/(\alpha v^\mathsf{T}x)$ satisfies $(D-\lambda I)y=v$ (that is, $y_j=v_j/(d_j-\lambda)$ for $j\in J$) and $$\alpha(v^\mathsf{T}y)=-1\implies 1+\alpha\sum_{j\in J}\frac{v_j^2}{d_j-\lambda}=0.$$ Observe that (assuming $\alpha\neq 0$) this equation has exactly $|\Lambda'|$ roots (all of them real).
  2. $\boxed{\lambda\in\Lambda\setminus\Lambda'.}$ This extends the case "$v_i=0$" in the question. Any vector $x\neq 0$ with $x_j=0$ for $j\notin J_\lambda$ satisfies $(D-\lambda I)x=0$ and $v^\mathsf{T}x=0$; we have an eigenspace of dimension (at least) $|J_\lambda|$.
  3. $\boxed{\lambda\in\Lambda'.}$ This is the "how do we find" case of the question. Compared to the preceding case, $v^\mathsf{T}x=0$ is now an additional constraint, giving rise to an eigenspace of dimension $|J_\lambda|-1$ (if $|J_\lambda|=1$, there's no such $x$). This is the answer to the question: any basis of this space is the set of eigenvectors we need.

In total, we have found exactly $$|\Lambda'|+\sum_{\lambda\in\Lambda\setminus\Lambda'}|J_\lambda|+\sum_{\lambda\in\Lambda'}(|J_\lambda|-1)=\sum_{\lambda\in\Lambda}|J_\lambda|=|J|=n$$ eigenvectors. [Thus, all the cases are considered exhaustively.]

Related Question