# Eigenvalue relation of a symmetric matrix $A$ and $A + vv^T$

My question pertains to the material in the book "The Algebraic Eigenvalue Problem" by J.H. Wilkinson. Section "Symmetric matrix of rank unity", pages 96-97.

The setup is as follows. We have a symmetric $$n \times n$$ matrix $$A$$ and $$B = vv^T$$ is a rank one projector. It is possible to show that there exists an orthogonal matrix $$Q$$ such that $$Q^T(A + B)Q = \begin{bmatrix} \alpha & b^T \\ b & \text{diag}(\alpha_i) \\ \end{bmatrix} + \begin{bmatrix} \rho & O \\ O & O \\ \end{bmatrix}. \tag{1}$$ Here $$\rho$$ is a non-zero eigenvalue of $$B$$, $$O$$ denotes blocks of zeroes, $$\alpha$$ is a scalar and $$\text{diag}(\alpha_i)$$ is a diagonal submatrix.

The eigenvalue of $$A$$ denoted as $$\lambda_i(A)$$ and eigenvalue $$\lambda_i(A+B)$$ of $$A+B$$ are therefore those of $$\begin{bmatrix} \alpha & b^T \\ b & \text{diag}(\alpha_i) \\ \end{bmatrix} \textrm{ and } \begin{bmatrix} \alpha + \rho & b^T \\ b & \text{diag}(\alpha_i) \\ \end{bmatrix}.\tag{2}$$

The claim is that $$\lambda_i(A+B)$$ satisfies the following relation: $$\lambda_i(A+B) = \lambda_i(A) + m_i \rho,$$ where $$0 \leq m_i \leq 1$$ and $$\sum m_i = 1.$$

I don't understand where this $$m_i$$ comes from and why all $$m_i \in [0,1]$$ add up to 1? How does this follow from (1) and (2)?

• what is $\text{diag}(\alpha_i) ?$ is $\alpha$ a scalar ? So $O$ is of dimension $n-1\times n-1 ?$ Oct 23, 2023 at 19:07
• Thanks for the comment. I introduced clarifications in the post. Oct 23, 2023 at 19:27
• no but what is $\alpha_i$ ? It makes it look like you are using eigen-decomposition of $A$ and $B$ separately when you talk about $\lambda_i(A)$ etc. But at the same time the $Q^T(A+B)Q$ is not guaranteed to work for both. Oct 23, 2023 at 19:30
• I am particularly curious of the line: The eigenvalue of $A$ denoted as $\lambda_i(A)$ and eigenvalue $\lambda_i(A+B)$ of $A+B$ are therefore those of $$\begin{bmatrix} \alpha & b^T \\ b & \text{diag}(\alpha_i) \\ \end{bmatrix} \textrm{ and } \begin{bmatrix} \alpha + \rho & b^T \\ b & \text{diag}(\alpha_i) \\ \end{bmatrix}.\tag{2}$$ ) Oct 23, 2023 at 19:32
• I clarified that $\text{diag}(\alpha_i)$ is a diagonal submatrix of $A$. This diagonal submatrix is the result of $Q^TAQ$. Oct 23, 2023 at 19:35

Let $$Q^TAQ = A_1$$ and $$Q^TBQ = B_1.$$ Consider the former's characteristic polynomial: $$p_{A_1}(x) = \det(xI-A_1) = \prod_{i=1}^n(x-\alpha_i) - \prod_{i=2}^n(x-\alpha_i)\sum_{i=2}^n\dfrac{b_i^2}{x-\alpha_i} = f(x)\left(x-\alpha-\sum_{i=2}^n\dfrac{b_i^2}{x-\alpha_i}\right)$$ with the notation $$\alpha = \alpha_1$$ and $$\text{diag}(\alpha_i) = \text{diag}(\alpha_2,\ldots ,\alpha_n)$$ and $$f(x) = (x-\alpha_2)\ldots (x-\alpha_n),$$ which is simply due to the Laplace expansion formula along the first row. So one also has: $$p_{A_1+B_1}(x) = f(x)\left(x-\alpha-\rho-\sum_{i=2}^n\dfrac{b_i^2}{x-\alpha_i}\right).$$
Now the conclusion should follow almost immediately. First, note that $$\dfrac{b_i^2}{x-\alpha_i}$$ is simply a notational convenience, since it is not defined at $$x = \alpha_i.$$ Second, if $$A_1$$ had an eigenvalue $$\lambda$$ with multiplicity greater than $$1,$$ then $$p_{A_1+B_1}$$ also has $$\lambda$$ as it's eigenvalue with multiplicity one less than the former, so we have: $$\lambda_{A+B} = \lambda_A + m_i\rho$$ with $$m_i = 0.$$ So let's only focus on simple eigenvalues from now on (this implies $$\alpha_i$$ cannot be an eigenvalue). If $$\lambda$$ is an eigenvalue of $$A$$, then (and assue WLOG $$\rho > 0$$): $$\dfrac{p_{A_1+B_1}(\lambda)}{f(\lambda)} = -\rho <0$$ and $$\dfrac{p_{A_1+B_1}(\lambda+\rho)}{f(\lambda+\rho)} = \lambda-\alpha-\sum_{i=2}^n\dfrac{b_i^2}{\lambda+\rho-\alpha_i} = \sum_{i=2}^n\left(\dfrac{b_i^2}{\lambda-\alpha_i}-\dfrac{b_i^2}{\lambda+\rho-\alpha_i}\right)>0.$$ Therefore, $$p_{A_1+B_1}(\mu) = 0$$ for some $$\mu\in(\lambda, \lambda+\rho),$$ which you can write as $$\mu = \lambda + m\rho$$ for some $$m\in(0,1).$$ This and the part about repeated eigenvalues finish the conclusion if you observe that: $$\text{Tr}(A_1+B_1) = \text{Tr}(A_1) + \rho.$$
Note: The solution isn't written perfectly here. Specifically, the notation short hand: $$\dfrac{f(x)}{x-\alpha_i} = \prod_{j=2, j\neq i}(x-\alpha_j)$$ could probably be made better.
• This is such a great argument! One thing I don't get is how you know that if $A_1$ has an eigenvalue with multiplicity above one then $A_1+B_1$ has the same eigenvalue but with multiplicity less one? Oct 24, 2023 at 20:15
• @MonteNero I found it it's explained more succinctly here. Essentially, the polynomials : $$\prod_{j\neq i}(x-\lambda_j)$$ will still have the linear factor $(x-\lambda_i)$ if $\lambda_i$ was repeated twice or more. Oct 24, 2023 at 21:12