wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        general >> complex analysis >> Distinct eigenvalues
        
(Message started by: comehome1981 on May 15^th, 2009, 10:59am)

Title: Distinct eigenvalues
Post by comehome1981 on May 15^th, 2009, 10:59am

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

Title: Re: Distinct eigenvalues
Post by Obob on May 15^th, 2009, 12:12pm

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

Title: Re: Distinct eigenvalues
Post by comehome1981 on May 15^th, 2009, 1:20pm

I am dealing with million times million matrix. Is there any simple rule to tell there are distinct eigenvalues?

Thanks a lot

Daniel

Title: Re: Distinct eigenvalues
Post by Obob on May 15^th, 2009, 1:33pm

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.

Title: Re: Distinct eigenvalues
Post by comehome1981 on May 15^th, 2009, 2:00pm

It is roughly 5GB since it is sparse.

Thanks, that helps a lot

Title: Re: Distinct eigenvalues
Post by Obob on May 15^th, 2009, 2:27pm

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.

Title: Re: Distinct eigenvalues
Post by comehome1981 on May 15^th, 2009, 3:47pm

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?

Title: Re: Distinct eigenvalues
Post by Grimbal on May 18^th, 2009, 4:35am

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.

Title: Re: Distinct eigenvalues
Post by Obob on May 18^th, 2009, 6:18am

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.

Title: Re: Distinct eigenvalues
Post by comehome1981 on May 18^th, 2009, 9:53am

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!