mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2006-03-09, 05:29   #1
10MDIGITPRIME
 
Mar 2006

38 Posts
Default 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?
10MDIGITPRIME is offline   Reply With Quote
Old 2006-03-09, 05:54   #2
10MDIGITPRIME
 
Mar 2006

316 Posts
Default

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
10MDIGITPRIME is offline   Reply With Quote
Old 2006-03-09, 06:26   #3
10MDIGITPRIME
 
Mar 2006

38 Posts
Default

I was wrong about having a solution. I don't think it can be fixed either.
10MDIGITPRIME is offline   Reply With Quote
Old 2006-03-09, 08:34   #4
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3·277 Posts
Default

I don't know whether it helps in your case, but you could take a look at "eigenvalue (resp. singular value) decomposition".
Mystwalker is offline   Reply With Quote
Old 2006-03-09, 08:53   #5
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26×5 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2006-03-09, 08:56   #6
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

I would say it depends very heavily on what field your matrix entries are from.
Orgasmic Troll is offline   Reply With Quote
Old 2006-03-09, 15:54   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-03-09, 17:28   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

The discriminant of your characteristic polynomial will tell you whether you have repeated roots or not.
philmoore is offline   Reply With Quote
Old 2006-03-09, 17:43   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22·33·7·13 Posts
Default

#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...
ewmayer is offline   Reply With Quote
Old 2006-03-09, 18:45   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-03-09, 19:04   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

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.
philmoore is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.