Finding number of eigenvalues of general nxn matrix?

10MDIGITPRIME · 2006-03-09, 05:29

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?

10MDIGITPRIME · 2006-03-09, 05:54

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.

10MDIGITPRIME · 2006-03-09, 06:26

I was wrong about having a solution. I don't think it can be fixed either.

Mystwalker · 2006-03-09, 08:34

I don't know whether it helps in your case, but you could take a look at "eigenvalue (resp. singular value) decomposition".

ColdFury · 2006-03-09, 08:53

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.

Orgasmic Troll · 2006-03-09, 08:56

I would say it depends very heavily on what field your matrix entries are from.

R.D. Silverman · 2006-03-09, 15:54

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.

philmoore · 2006-03-09, 17:28

The discriminant of your characteristic polynomial will tell you whether you have repeated roots or not.

ewmayer · 2006-03-09, 17:43

#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...

R.D. Silverman · 2006-03-09, 18:45

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.

philmoore · 2006-03-09, 19:04

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.

2006-03-09, 05:29	#1
10MDIGITPRIME Mar 2006 3 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 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 2006-03-09 at 05:59

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Finding prime factors for 133bit number	noodles	YAFU	2	2017-05-12 14:00
Finding multiples of a real number that are close to a whole number	mickfrancis	Math	16	2017-03-01 07:17
Chance of finding new prime number formulas?	columbus	Information & Answers	49	2013-03-07 22:36
fastest general number primality-proving algorithm?	ixfd64	Math	3	2003-12-17 17:06
Probability of finding a prime number	Deamiter	Software	4	2002-10-11 16:36

2006-03-09, 06:26	#3
10MDIGITPRIME Mar 2006 3 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 1477₈ 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: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, 17:28	#8
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 1119₁₀ Posts	The discriminant of your characteristic polynomial will tell you whether you have repeated roots or not.

2006-03-09, 17:43	#9
ewmayer ∂²ω=0 Sep 2002 República de California 2×11×13×41 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, 19:04	#11
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 45F₁₆ 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.