mersenneforum.org Finding number of eigenvalues of general nxn matrix?
 Register FAQ Search Today's Posts Mark Forums Read

 2006-03-09, 05:29 #1 10MDIGITPRIME   Mar 2006 38 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?
 2006-03-09, 05:54 #2 10MDIGITPRIME   Mar 2006 316 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 2006-03-09 at 05:59
 2006-03-09, 06:26 #3 10MDIGITPRIME   Mar 2006 38 Posts I was wrong about having a solution. I don't think it can be fixed either.
 2006-03-09, 08:34 #4 Mystwalker     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".
2006-03-09, 08:53   #5
ColdFury

Aug 2002

26×5 Posts

Quote:
 Extracting roots of a general mth degree polynomial in finite time... is that even possible?)
Yes, there are a variety of numerical methods to do so.

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.

 2006-03-09, 08:56 #6 Orgasmic Troll Cranksta Rap Ayatollah     Jul 2003 641 Posts I would say it depends very heavily on what field your matrix entries are from.
2006-03-09, 15:54   #7
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by ColdFury Yes, there are a variety of numerical methods to do so. 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.
Methods exist [they are O(n^3)] that will find the eigenvalues without
trying to compute the polynomial. Indeed, it is almost always a bad idea
to do so. If the matrix is even mildly ill-conditioned, 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 non-singlular, then it will have (indeed must
have) n non-zero 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.

 2006-03-09, 17:28 #8 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 22·32·31 Posts The discriminant of your characteristic polynomial will tell you whether you have repeated roots or not.
 2006-03-09, 17:43 #9 ewmayer ∂2ω=0     Sep 2002 República de California 22·33·7·13 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 halfway-decent 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 rank-deficient 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 new-and-supposedly-vastly-improved LAPACK package, which had routines to handle rank-deficient systems. Problem was, they were absolutely dismal in terms of numerical accuracy, which was crucially important to me, since my work involved highly ill-conditioned eigensystems (technically, ones arising from non-normal linear differential operators, which have many nearly degenerate eigenvalues and which are thus highly sensitive to perturbations, be they of the physical or numerical-rounding-error 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 afore-linked page.) So I stuck with my hand-rolled version, and was in the end glad that when I'd started on my work, I didn't have the absolute latest-greatest software available to me. Thus endeth today's trip down memory lane...
2006-03-09, 18:45   #10
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by philmoore The discriminant of your characteristic polynomial will tell you whether you have repeated roots or not.
Certainly. But how will you compute the discriminant without knowing
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.

 2006-03-09, 19:04 #11 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 22·32·31 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post noodles YAFU 2 2017-05-12 14:00 mickfrancis Math 16 2017-03-01 07:17 columbus Information & Answers 49 2013-03-07 22:36 ixfd64 Math 3 2003-12-17 17:06 Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 07:21.

Thu Nov 26 07:21:53 UTC 2020 up 77 days, 4:32, 3 users, load averages: 1.33, 1.34, 1.38