2
$\begingroup$

I have a square matrix $A$.

Is it possible to determine if its largest eigenvalue is smaller (by magnitude) than 1 by inspecting the matrix $(I-A)^{-1}$?

(we can assume that $I-A$ is invertible.)

EDIT: My question is quite simple, if not more specific. Obviously you could recover $A$ and compute its spectrum. But I am looking for something which is algorithmically simple...

2 Answers 2

1

You can determine the eigenvalues exactly: $\operatorname{Spec}((I-A)^{-1})=\{(1-\lambda)^{-1}\vert \lambda\in \operatorname{Spec} A\}$ (consider Jordan form of $A$ and notice that $A$ and $I$ commute) and $\lambda \mapsto (1-\lambda)^{-1}$ is invertible.

In particular you can determine their magnitudes.

  • 0
    @kloop: using the same reasoning you can reduce the problem to checking if any eigenvalue of $(I-A)^{-1}$ is outside of the image of unit disk under $\lambda\mapsto (1-\lambda)^{-1}$. I don't believe you can make it any simpler. If you assumed that eigenvalues of $A$ are bounded away from $1$ by some constant, the image will be compact, so it won't be so bad, I guess. I don't really know much about computational complexity of that.2012-10-05
0

Any polynomial operation on a matrix $A$, i.e. any scalar sums of powers of $A$, including the identity matrix and negative (integer) powers of A, operate directly on the eigenvalues of $A$.

For example, if $2 \in \sigma(A)$ so that det($A - 2I)=0$ (2 is an eigenvalue of $A$), then $M=A^4 + I$ has as eigenvalu $2^4+1 = 17$. Thus, if you find that $(I-A)^{-1}$ seems to have a better form for finding an eigenvalue, call it $x$, then $\lambda$ the eigenvalue for A can be found by solving the equation $x = (1-\lambda)^{-1}$

For possibilities of estimating eigenvalues given some matrix, use Gerschgorin Circles, which gives bounds on eigenvalues by comparing diagonal elements to their respective row-sum (of absolute values in the row). Eigenvalues are near the value of the diagonal element, no further from it than the absolute sum of the other elements in its row.

I am thinking though that for your purposes you may want to use a matrix norm somehow...

  • 0
    @nullUser I forgot to include your user name in the previous comment. This comment is only here to do that, just in case.2013-04-01