# Derive the formula for eigenvalues

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.

• Is this a homework problem? If so, you should indicate that in your post. What have you tried so far to show this relationship? Oct 10 '18 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 Oct 10 '18 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. Oct 10 '18 at 21:33
• @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. Oct 11 '18 at 8:42
• Even if they commute it's rather bad style to write matrix-over-matrix. Oct 11 '18 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$$).

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