wu :: forums « wu :: forums - Distinct eigenvalues » Welcome, Guest. Please Login or Register. Feb 8th, 2023, 6:39pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    general    complex analysis (Moderators: Grimbal, Eigenray, william wu, ThudnBlunder, towr, SMQ, Icarus)    Distinct eigenvalues « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Distinct eigenvalues  (Read 17033 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: 7522
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth => complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »