Author |
Topic: Distinct eigenvalues (Read 17406 times) |
|
comehome1981
Newbie
Posts: 20
|
 |
Distinct eigenvalues
« on: May 15th, 2009, 10:59am » |
 Quote  Modify
|
I have been looking the conditions for a matrix to have all distinct eigenvalues, but I could not fint it.
Is anyone know the condition to ensure all the eigenvalues are distinct?
Thanks so much to answer this.
Daniel
|
|
 IP Logged |
|
|
|
Obob
Senior Riddler
Gender: 
Posts: 489
|
|
Re: Distinct eigenvalues
« Reply #1 on: May 15th, 2009, 12:12pm » |
Quote Modify
|
By "distinct eigenvalues," I take it that you mean "distinct generalized eigenvalues." For instance, the matrix [[2,1],[0,2]] has a single eigenvector, with eigenvalue 2, so you could say that its eigenvalues are all distinct. However, despite the eigenspace corresponding to 2 being one-dimensional, we should view 2 as being a multiple eigenvalue.
In other words, we are simply asking for a criterion for the characteristic polynomial of the matrix to have distinct roots. But this is the case if and only if the discriminant of the characteristic polynomial is nonzero. The discriminant of the characteristic polynomial is just some polynomial in the entries of the matrix (much like the determinant of the matrix is), so this gives a simple test for determining if the matrix has a repeated eigenvalue.
http://en.wikipedia.org/wiki/Discriminant
|
| « Last Edit: May 15th, 2009, 12:18pm by Obob » |
IP Logged |
|
|
|
comehome1981
Newbie
Posts: 20
|
|
Re: Distinct eigenvalues
« Reply #2 on: May 15th, 2009, 1:20pm » |
Quote Modify
|
I am dealing with million times million matrix. Is there any simple rule to tell there are distinct eigenvalues?
Thanks a lot
Daniel
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Distinct eigenvalues
« Reply #3 on: May 15th, 2009, 1:33pm » |
Quote Modify
|
If by simple rule, you mean a test which will tell you with 100% certainty whether the eigenvalues are distinct or not, then the only thing I am aware of is what I said in my previous post. Calculating the discriminant of the characteristic polynomial is roughly as difficult as computing the determinant of the original matrix. Maybe if you knew something about the particular form of the matrix you could do something better, but if you want a simple algorithm that says if any matrix has distinct eigenvalues or not then I think this is the best you will do.
If your eigenvalues are not distinct, you can instead show that some generalized eigenspace is at least 2 dimensional.
A million by a million is ridiculously huge though. Even if the entries are all 1's or 0's, thats a terabit, or ~125 gigabytes, of data.
|
| « Last Edit: May 15th, 2009, 1:54pm by Obob » |
IP Logged |
|
|
|
comehome1981
Newbie
Posts: 20
|
|
Re: Distinct eigenvalues
« Reply #4 on: May 15th, 2009, 2:00pm » |
Quote Modify
|
It is roughly 5GB since it is sparse.
Thanks, that helps a lot
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Distinct eigenvalues
« Reply #5 on: May 15th, 2009, 2:27pm » |
Quote Modify
|
Certainly for a million by million matrix the test I suggested is of no help whatsoever; I don't know if you can do better because your matrix is sparse.
|
|
IP Logged |
|
|
|
comehome1981
Newbie
Posts: 20
|
|
Re: Distinct eigenvalues
« Reply #6 on: May 15th, 2009, 3:47pm » |
Quote Modify
|
What is the criteria for a matrix (not symmetric) to have real eigenvalues?
I heard if A[i , j] = f(i - j) >= 0 , A is not symmetric but f has a 2-sided exponential decay,
then
The eigenvalues are real!
Could someone give me some detail?
|
| « Last Edit: May 15th, 2009, 4:03pm by comehome1981 » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Distinct eigenvalues
« Reply #7 on: May 18th, 2009, 4:35am » |
Quote Modify
|
Is it real data? (i.e. floats)
Because the question whether all eigenvalues are equal is sensitive to small differences in the data. If the data is the result of a measurement with errors, or if there are rounding errors, then it is meaningless to ask whether some eigenvalues are equal.
I'd say for real-life data, only a coincidence can make 2 eigenvalues equal.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Distinct eigenvalues
« Reply #8 on: May 18th, 2009, 6:18am » |
Quote Modify
|
As Grimbal says, for an experimentally obtained matrix with reals as entries the question is not well-posed; the relevant question then is if two eigenvalues are very close. In general this could be measured by determining if the discriminant of the characteristic polynomial is "small", although for a million by million matrix this approach is intractable.
I don't know about your question about the criterion for real eigenvalues. For one thing, I don't know what you mean by two-sided exponential decay. These are finite matrices we are dealing with, so talking about the decay of a finite object seems strange.
|
| « Last Edit: May 18th, 2009, 6:20am by Obob » |
IP Logged |
|
|
|
comehome1981
Newbie
Posts: 20
|
|
Re: Distinct eigenvalues
« Reply #9 on: May 18th, 2009, 9:53am » |
Quote Modify
|
Like symmetric matrix always has real eigenvalues.
If a given real matrix is not symmetric, is there other condition (like stochastic matrix, toeplitz matrix for example) saying the eigenvalues of the matrix are all real (not neccessary distinct)?
I also do not quite understand the exponential decay stuff, I look up in the internet. Hope someone can give me some reference to read!
|
| « Last Edit: May 18th, 2009, 10:24am by comehome1981 » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print