If $A$ has eigenvalue $\lambda_A$ $$B = I - c\frac{I-rA}{I-\bar{r}A}$$

How to derive the eigenvalue $\lambda_B$? $$\lambda_B=1-c\frac{1-r\lambda_A}{1-\bar{r}\lambda_A}$$

where $c, r, \bar{r}$ are constants.

This formula occurs at the derivation of speedup modified Newton iteration in solving DAE. There are no details in the paper for the derivation of this linear algebra piece.

  • 1
    Is this a homework problem? If so, you should indicate that in your post. What have you tried so far to show this relationship? – Bill Greene Oct 10 at 10:34
  • no it's not homework, it's the spectral radius of iterative function in solving ODE, c is use to speed up the newton iteration, I just want to know how to derive it – Chen Ziv Oct 10 at 10:34
  • Have a look at Higham's Functions of Matrices (my.siam.org/books/ot104/OT104HighamChapter1.pdf), there are several ways to properly define functions of matrices like your $B=B(A)$, and when $B$ is an analytic function as here, the eigenvalues will be $B(\lambda)$. The easiest way to do this without functions of matrices I think is to diagonalize $A=XDX^{-1}$ and expand everything, you get $X(I-c(1-r D)(1-\bar r D)^{-1})X^{-1}$, where the eigenvalues can be computed easily. – Kirill Oct 10 at 21:33
  • 1
    @WolfgangBangerth Can you clarify what you mean? The matrices $I-r A$ and $(I-\tilde r A)^{-1}$ commute, as far as I can tell. – Kirill Oct 11 at 8:42
  • 1
    Even if they commute it's rather bad style to write matrix-over-matrix. – Wolfgang Bangerth Oct 11 at 22:09

It's just some easy matrix algebra. If $Av=\lambda_A v$ then $(I-rA)v= (1-r\lambda_A)v$ and (multiplying by inverses on both sides) $(I-rA)^{-1}v= (1-r\lambda_A)^{-1}v$, which is valid also if you replace $r$ with $\bar{r}$.

Then you just expand $Bv = (I-c(I-rA)(I-\bar{r}A)^{-1})v=\dots$

[EDIT: wim's answer carries out this computation in more detail.]

Let $(\lambda,x)$ be an eigenpair of matrix $A$, so $A x=\lambda x$. Now we compute $B x$, and see if it is equal to $\left(1-c\frac{1-r\lambda}{1-\bar{r}\lambda}\right)x$.

$$ \begin{align} B x & = \left( I - c\frac{I-rA}{I-\bar{r}A} \right) x\\ & = x - c\frac{x-rAx}{I-\bar{r}A} = x - c\frac{x-r \lambda x}{I-\bar{r}A}\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A}x\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A} \, \frac{I-\bar{r}\lambda}{I-\bar{r}\lambda}x\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A} \, \frac{x-\bar{r}Ax}{I-\bar{r}\lambda}\\ & = x - c\frac{1-r \lambda }{I-\bar{r}A} \, \frac{I-\bar{r}A}{I-\bar{r}\lambda}x\\ & = \left( 1 - c\frac{1-r \lambda }{I-\bar{r}\lambda}\right)x\\ \end{align} $$

Hence, we may conclude that following relationship between the eigenvalues of $A$ and $B$ holds: $$\lambda_B = 1 - c\frac{1-r \lambda_A }{I-\bar{r}\lambda_A} ,$$

as long as $I-\bar{r}A$ is invertible. Note that it is not necessary that $A$ is diagonalizable.


In the comments there has been some discussion whether or not $(I-\alpha A)^{-1}$ commutes with $I-\beta A$. If we assume that $I-\alpha A$ is invertible, then

$$ \begin{align} (I-\alpha A)^{-1}(I-\beta A) & = (I-\alpha A)^{-1}(I-\beta A)(I-\alpha A)(I-\alpha A)^{-1}\\ & = (I-\alpha A)^{-1}(I-\beta A -\alpha A +\alpha \beta A^2)(I-\alpha A)^{-1}\\ & = (I-\alpha A)^{-1}(I-\alpha A)(I-\beta A)(I-\alpha A)^{-1}\\ & = (I-\beta A)(I-\alpha A)^{-1} ,\\ \end{align} $$ which shows that indeed $(I-\alpha A)^{-1}$ commutes with $I-\beta A$. Therefore we can write $\frac{I-\beta A}{I-\alpha A}$ instead of $(I-\alpha A)^{-1}(I-\beta A)$ or $(I-\beta A)(I-\alpha A)^{-1}$.

From a quick look at your problem, it seems to me that this should follow by writing $(I - \bar{r} A)^{-1}$ as a geometric series, expanding its product with $I - r A$, and then applying the Spectral Mapping Theorem (which says that if $p$ is a polynomial/power series, then the eigenvalues of $B = p(A)$ are the eigenvalues of $A$ transformed by $p$).

  • 1
    Aren't you assuming that $\|rA\|<1$ to get the power series to converge? – Kirill Oct 10 at 21:29
  • Yes, of course. Otherwise the expansion does not hold. – Juan M. Bello-Rivas Oct 10 at 23:41
  • 1
    But the formula is valid in general, so there’s a gap in the proof, isn’t there? – Kirill Oct 10 at 23:43

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.