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.

Let $P$ be a strictly positive $n\times n$ stochastic matrix.

I hope to find out the stability of a system characterized by the matrix $(I-P)$. So I'm interested in knowing under what condition on the entries of $P$ do all the eigenvalues of the matrix $(I-P)$ lie (not necessarily strictly) within the unit disk in the complex plane? The set of eigenvalues of $P$ is shifted by $(1-\sigma(P))$, which would require additional conditions to be placed on $P$ so as to keep them within the unit disk.

Or can anybody point out a direction towards which I can look for the answer? I don't really know what subject of linear algebra I should go for...

share|improve this question
    
Are all the entries of $P$ strictly positive? –  dineshdileep Jan 3 '13 at 7:03
    
for a start, you can look at perron-frobenius theorem and also gerschgorin disks. –  dineshdileep Jan 3 '13 at 7:04
    
@dineshdileep Yes, they are. –  Vokram Jan 3 '13 at 7:09
    
I am adding the tag "linear-algebra" –  dineshdileep Jan 3 '13 at 7:25
    
@CalvinLin Sorry I deleted that. That happens to be another post by me, but since I'm getting more active answers here while but nothing on that side I thought maybe the question was more suited for SE.. –  Vokram Jan 3 '13 at 7:51

2 Answers 2

up vote 1 down vote accepted

One sufficient condition (that is not necessary) is that all diagonal entries of $P$ are greater than or equal to $1/2$. If this is the case, by Gersgorin disc theorem, all eigenvalues of $I-P$ will lie inside the closed disc centered at $1/2$ with radius $1/2$, and hence lie inside the closed unit disc as well.

share|improve this answer

This is a partial answer. OP asked for answer in terms of entries of the matrix. This is given in terms of its eigenvalues.

(Thanks to user CalvinLin for pointing out the mistake in previous answer in the comments).

Answer: All the eigenvalues of $P$ should lie in the intersection of circles $x^2+y^2=1$ and $(x-1)^2+y^2=1$.

Explanation: Since all entries of $P$ are strictly positive, and also it is a stochastic matrix, you can apply the perron-frobenius theorem (PFT) to it. Note that $P$ has $1$ as a eigenvalue (since it is stochastic). By PFT (since it is strictly positive), only other eigenvalues will be lying strictly inside the unit disk (whether real or complex).

Now $-P$ will have one negative eigenvalue at $-1$ and all others inside the unit circle. Now adding identity matrix $I$ to it has the effect of increasing every eigenvalue by $1$. On the 2-D plane, this is equivalent to shifting all eigenvalue towards right by 1. Thus if all eigenvalues were lying in intersection of unit-circle centered at (-1,0) and the unit-circle at origin, it will ensure that none of them move outside by unit-circle by shifting towards right. Thus eigenvalues of $P$ should lie in intersection of circles centered at $(1,0)$ and that at orgin

share|improve this answer
    
Judging by your argument, since OP wants eigenvalues of $I-P$ to lie in the unit disc, shouldn't the eigenvalues of $P$ then have to lie within the circles $x^2+y^2=1$ and $(x-1)^2+y^2=1$? I.e. positive real part isn't sufficient. –  Calvin Lin Jan 3 '13 at 7:28
    
oops--let me check it. –  dineshdileep Jan 3 '13 at 7:42
    
Thank you @dineshdileep . I think calvin meant that the eigenvalues of $P$ need to be in the union of $x^2+y^2=1$ and $(x-1)^2+y^2=1$. Although I would more like to have a condition on the entries on P instead of a condition on its eigenvalues directy... –  Vokram Jan 3 '13 at 7:43
    
Yes, my concern is that if P has eigenvalue $0.1 +0.9i$, then $I-P$ will have eigenvalue $1-(0.1+0.9i) = 0.9-0.9i$, which doesn't lie in the unit circle. Or am i just confused? –  Calvin Lin Jan 3 '13 at 7:44
    
@CalvinLin Ya, I guess you are right. I mistook adding 1 as equivalent to mirroring the eigenvalues around the y-axis. Thanks for the reply –  dineshdileep Jan 3 '13 at 7:51

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.