3
$\begingroup$

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)?

$\endgroup$
7
  • $\begingroup$ what is $\text{diag}(\alpha_i) ?$ is $\alpha$ a scalar ? So $O$ is of dimension $n-1\times n-1 ?$ $\endgroup$
    – dezdichado
    Oct 23, 2023 at 19:07
  • $\begingroup$ Thanks for the comment. I introduced clarifications in the post. $\endgroup$
    – MonteNero
    Oct 23, 2023 at 19:27
  • $\begingroup$ 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. $\endgroup$
    – dezdichado
    Oct 23, 2023 at 19:30
  • $\begingroup$ 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} $$ ) $\endgroup$
    – dezdichado
    Oct 23, 2023 at 19:32
  • $\begingroup$ I clarified that $\text{diag}(\alpha_i)$ is a diagonal submatrix of $A$. This diagonal submatrix is the result of $Q^TAQ$. $\endgroup$
    – MonteNero
    Oct 23, 2023 at 19:35

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – MonteNero
    Oct 24, 2023 at 20:15
  • $\begingroup$ @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. $\endgroup$
    – dezdichado
    Oct 24, 2023 at 21:12
  • $\begingroup$ also - en.wikipedia.org/wiki/Weyl%27s_inequality is a good reference it looks like. $\endgroup$
    – dezdichado
    Oct 24, 2023 at 21:13
  • $\begingroup$ Excellent answer! What is the relation of the formula you derived to the secular equation, e.g. as described in this answer math.stackexchange.com/a/3625609/443030 $\endgroup$
    – V.S.e.H.
    Oct 24, 2023 at 23:15
  • $\begingroup$ what is a secular equation ? $\endgroup$
    – dezdichado
    Oct 25, 2023 at 15:15

You must log in to answer this question.

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