20060309, 05:29  #1 
Mar 2006
3_{16} Posts 
Finding number of eigenvalues of general nxn matrix?
My professor asked us to give a way to find the number of eigenvalues of a general n by n matrix. I'm starting to think there is no easy way to do this. Can someone either tell me how to do this or point me in the right direction, or tell me there's no right direction to point in?
Ideas so far: 1. Find the minimal or characteristic polynomial, and then find roots. That, or find the invariant factors, and then find roots. (Extracting roots of a general mth degree polynomial in finite time... is that even possible?) 3. Find a sequence that converges to an eigenvalue or eigenvector, or soem other nonterminating sequence of steps. (Definitely not what he wants.) In case I'm not clear, I'm saying that given a matrix A, I want to find the number of distinct eigenvalues for this matrix. No nonterminating processes are allowed. Does someone know whether this is actually a difficult problem in general (given only pen and paper)? Is finding roots of the minimal or characteristic polynomial or invariant factors the best way? 
20060309, 05:54  #2 
Mar 2006
3 Posts 
I found a solution. I couldn't delete the post, so I guess I'll just leave it as an open question for all and I'll post a solution if there's enough interest.
Last fiddled with by 10MDIGITPRIME on 20060309 at 05:59 
20060309, 06:26  #3 
Mar 2006
11_{2} Posts 
I was wrong about having a solution. I don't think it can be fixed either.

20060309, 08:34  #4 
Jul 2004
Potsdam, Germany
3×277 Posts 
I don't know whether it helps in your case, but you could take a look at "eigenvalue (resp. singular value) decomposition".

20060309, 08:53  #5  
Aug 2002
2^{6}·5 Posts 
Quote:
Just find all the roots of the characteristic polynomial. It will work, but it probably won't be efficient, but you didn't mention anything about your professor requiring a certain efficiency. 

20060309, 08:56  #6 
Cranksta Rap Ayatollah
Jul 2003
641_{10} Posts 
I would say it depends very heavily on what field your matrix entries are from.

20060309, 15:54  #7  
Nov 2003
7460_{10} Posts 
Quote:
trying to compute the polynomial. Indeed, it is almost always a bad idea to do so. If the matrix is even mildly illconditioned, the coefficients of the polynomial become very sensitive to FP rounding error. One introduces more error by then computing the roots. > Better to do it directly. See e.g. Golub & Van Loan "Matrix Computations" However, if an nxn matrix is nonsinglular, then it will have (indeed must have) n nonzero eigenvalues. Some of these can be identical, but they are still different eigenvalues. Consider a matrix A that is pos. def. x^T A x = 1 is the equation of an ellipsoid. It is obtained by stretching a sphere. The eigenvectors determine the DIRECTIONS the sphere is streched. The eigenvalues determine HOW MUCH they are stretched in each direction. It is possible to stretch the sphere by the same amount, but in different directions. The value of the eigenvalues is the same, but they are still different because they correspond to different eigenvectors. 

20060309, 17:28  #8 
"Phil"
Sep 2002
Tracktown, U.S.A.
3×373 Posts 
The discriminant of your characteristic polynomial will tell you whether you have repeated roots or not.

20060309, 17:43  #9 
∂^{2}ω=0
Sep 2002
República de California
2^{2}×5×11×53 Posts 
#eigenvalues = rank of matrix
To actually find the eigenvalues (more precisely, to find numerical approximations to them, hopefully decently accurate ones, but that depends on the matrix condition, quality of the software implementation and accuracy of the hardware arithmetic used), you'll want to use something along the lines of the QR algorithm  there are good implementations in the LAPACK and older EISPACK algorithms packages. Numerical Recipes also has a halfwaydecent implementation. Note that the above packages ain't perfect  my PhD research made very heavy use of numerical eigensystems work (in my case, finding the eigenvalues of discrete approximations to the hydrodynamic stability equations that arose in my area of research). One immediate problem I ran into was that in numerical approximation of the kinds of differential equations I was dealing with, one typically has a combination of equations and suitable boundary conditions. The boundary conditions don't generally involve the (unknown) eigenvalues of the problem, leading to a rankdeficient matrix eigensystem. EISPACK had no way of handling that, so I wrote some custom code that first carefully reduced the numerical eigensystem to an equivalent one (i.e. having the same eigenvalues, within numerical error) of full rank, and fed that to EISPACK. Later at some point I got a chance to try the newandsupposedlyvastlyimproved LAPACK package, which had routines to handle rankdeficient systems. Problem was, they were absolutely dismal in terms of numerical accuracy, which was crucially important to me, since my work involved highly illconditioned eigensystems (technically, ones arising from nonnormal linear differential operators, which have many nearly degenerate eigenvalues and which are thus highly sensitive to perturbations, be they of the physical or numericalroundingerror variety  cf. Tosio Kato's classic Perturbation theory for linear operators  Bob will be amused that a certain L. de Branges is among those quoted on the aforelinked page.) So I stuck with my handrolled version, and was in the end glad that when I'd started on my work, I didn't have the absolute latestgreatest software available to me. Thus endeth today's trip down memory lane... 
20060309, 18:45  #10  
Nov 2003
1D24_{16} Posts 
Quote:
the roots for an even moderate degree polynomial (say degree 100?) Better just to compute the eigenvalues directly via (say) Jordan decomp or Shur Decomp, or QR, etc. 

20060309, 19:04  #11 
"Phil"
Sep 2002
Tracktown, U.S.A.
3·373 Posts 
The original poster's comment about pen and paper led me to believe that this was more of a pure math question than a computational one. If so, here is an "easy" algorithm to find the number of distinct eigenvalues:
Let f(x) be the characteristic polynomial. GCD(f(x),f'(x)) can be found by the polynomial Euclidean algorithm and will contain all the repeated roots, so the number of distinct roots is the degree of f(x)/GCD(f(x),f'(x)). No need to actually find the roots. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding prime factors for 133bit number  noodles  YAFU  2  20170512 14:00 
Finding multiples of a real number that are close to a whole number  mickfrancis  Math  16  20170301 07:17 
Chance of finding new prime number formulas?  columbus  Information & Answers  49  20130307 22:36 
fastest general number primalityproving algorithm?  ixfd64  Math  3  20031217 17:06 
Probability of finding a prime number  Deamiter  Software  4  20021011 16:36 