Author 
Topic: Distinct eigenvalues (Read 16835 times) 

comehome1981
Newbie
Posts: 20


Distinct eigenvalues
« on: May 15^{th}, 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 15^{th}, 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 onedimensional, 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 15^{th}, 2009, 12:18pm by Obob » 
IP Logged 



comehome1981
Newbie
Posts: 20


Re: Distinct eigenvalues
« Reply #2 on: May 15^{th}, 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 15^{th}, 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 15^{th}, 2009, 1:54pm by Obob » 
IP Logged 



comehome1981
Newbie
Posts: 20


Re: Distinct eigenvalues
« Reply #4 on: May 15^{th}, 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 15^{th}, 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 15^{th}, 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 2sided exponential decay, then The eigenvalues are real! Could someone give me some detail?

« Last Edit: May 15^{th}, 2009, 4:03pm by comehome1981 » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7517


Re: Distinct eigenvalues
« Reply #7 on: May 18^{th}, 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 reallife data, only a coincidence can make 2 eigenvalues equal.


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Distinct eigenvalues
« Reply #8 on: May 18^{th}, 2009, 6:18am » 
Quote Modify

As Grimbal says, for an experimentally obtained matrix with reals as entries the question is not wellposed; 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 twosided exponential decay. These are finite matrices we are dealing with, so talking about the decay of a finite object seems strange.

« Last Edit: May 18^{th}, 2009, 6:20am by Obob » 
IP Logged 



comehome1981
Newbie
Posts: 20


Re: Distinct eigenvalues
« Reply #9 on: May 18^{th}, 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 18^{th}, 2009, 10:24am by comehome1981 » 
IP Logged 



