Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
mmm, yes, I guess that could work -- in fact, I could even recover A back and compute its spectrum, but I want something much simpler, if there is one... I don't care about the whole spectrum, just about the largest eigenvalue being smaller than 1. –  kloop Oct 5 '12 at 0:35
    
@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. –  tomasz Oct 5 '12 at 0:41
add comment

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...

share|improve this answer
    
Can you provide a link explaining this in more detail? I know eigenvalues act nicely with powers, but I thought for some reason they didn't play nice with sums. –  nullUser Oct 5 '12 at 1:39
    
Sums only for powers of $A$. Since the terms share the same spectrum (same eigenvectors, not eigenvalues) the corresponding eigenvalues coincide and combine in the sum. As far as links go, i must apologize as I do more of my research with books. Try cayley-hamilton, or characteristic polynomial as search terms. –  adam W Oct 5 '12 at 2:43
    
@nullUser I forgot to include your user name in the previous comment. This comment is only here to do that, just in case. –  adam W Apr 1 '13 at 17:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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