How to find the eigenvalues of a matrix

[curiously enough]

I need a practical method to find the eigenvalues of a matrix in C++ because the one I know(the only one I know) is to subtract the elements of the diagonal by the eigenvalue and then find the determinant of this matrix: |A-xI|=0, and in C++ I do this by checking every float value with one digit after the decimal between -10000.0 and 10000.0, and I can already find the determinant.
This is its code:

float ev=-10000;
while(ev<=10000)
{
/*subtract the diagonal elements of the matrix by ev*/
if(determinant(matrix)==0)
    {
        /*store the value ev in a one dimensional array*/
        ev=ev+0.1;
    }
}
 

and of course if this worked I wouldn't have posted the question. I AM NOT asking for the code, I just want a practical way to find the eigenvalues in C++.
Thank you for reading the question.
PS: If you could tell how to find the order of an eigenvalue too that would be great.

[TamusJRoyce]

If you are looking for a better method, I can suggest a book that has it in it... Numerical Recipies in C++ .

The link may not be the book I'm thinking of, but I'm sure it still has excellent information about how to do matrix math.

Also, research how gnu gsl produces it's eigenvalues. gsl is among the fastest open-source libraries, and I'm sure googling for specifics on how gsl works is available.

[arnaudk]

To say that answering your question would require a chapter of a book would be an understatement. I think you'd be a bit loopy to try to write your own code for this unless you intend to make a career out of writing numerical routines. Indeed, the "Numerical Recipes in C++" book does contain some routines but after introducing a lot of theory it states

You have probably gathered by now that the solution of eigensystems is a fairly complicated business. It is. It is one of the few subjects covered in this book for which we do not recommend that you avoid canned routines. On the contrary, the purpose of this chapter is precisely to give you some appreciation of what is going on inside such canned routines, so that you can make intelligent choices about using them, and intelligent diagnoses when something goes wrong.

The routines you require are covered in a series of academic articles published in a collection edited by J. H. Wilkinson and C. Reinsch called "Handbook for Automatic Computation, vol. 2, Linear algebra." They have since been implemented in FORTRAN, in the EISPACK set of routines, which has been ported to C in CLAPACK and GSL and commercial C++ packages like NAG. If you actually want to implement them yourself, then invest in a copy of that handbook or Numerical Recipes in C++ because you'll really need it.

An improvement on what you're currently doing would be to derive the characteristic equation symbolically and solve for the roots of the resulting polynomial (numerically or symbolically), which will also tell you the multiplicity of degenerate eigenvalues but that will require a fundamental rewrite you your code and I'm not sure it will be feasible for any sizable matrices. If you want to embark on that magical journey, then research symbolic computation.

[curiously enough]

If you are looking for a better method, I can suggest a book that has it in it... Numerical Recipies in C++ .

The link may not be the book I'm thinking of, but I'm sure it still has excellent information about how to do matrix math.

Also, research how gnu gsl produces it's eigenvalues. gsl is among the fastest open-source libraries, and I'm sure googling for specifics on how gsl works is available.

Thanks, the book says that there is a lot of other ways to find the eigenvalues(and of course not mentioning what those ways are and making me look for them, which I still am), and hopefully they can be applicable to C++.

[curiously enough]

To say that answering your question would require a chapter of a book would be an understatement. I think you'd be a bit loopy to try to write your own code for this unless you intend to make a career out of writing numerical routines. Indeed, the "Numerical Recipes in C++" book does contain some routines but after introducing a lot of theory it states

The routines you require are covered in a series of academic articles published in a collection edited by J. H. Wilkinson and C. Reinsch called "Handbook for Automatic Computation, vol. 2, Linear algebra." They have since been implemented in FORTRAN, in the EISPACK set of routines, which has been ported to C in CLAPACK and GSL and commercial C++ packages like NAG. If you actually want to implement them yourself, then invest in a copy of that handbook or Numerical Recipes in C++ because you'll really need it.

An improvement on what you're currently doing would be to derive the characteristic equation symbolically and solve for the roots of the resulting polynomial (numerically or symbolically), which will also tell you the multiplicity of degenerate eigenvalues but that will require a fundamental rewrite you your code and I'm not sure it will be feasible for any sizable matrices. If you want to embark on that magical journey, then research symbolic computation.

So in short you are saying is that there is no other method unless I want to be a math proffessor. I don't mind if the method is long or difficult, if you could show me a direct link to it that would solve the problem.

And I don't really understand how I should derive the chrachteristic polynomial in the algorithm, neither do I know what numerically or symbolically mean. If you could clearify a bit(since you seem to know a lot about it).

[arnaudk]

I've always used canned routines so I don't know what it really involves but it seems like a complex and time consuming task. Since it looks like you're really getting into heavy numerics so you should invest in a good book on the subject like Numerical Recipes where you'll find detailed answers to many such problems. Why reinvent the wheel?

The characteristic equation is det(A - x*I) = 0 where A is an nxn matrix and I is the nxn identity matrix (a matrix with ones on the diagonal and zeros elsewhere). Expanding the determinant results in a polynomial equation in x

a_n*x^n + ... + a_1*x + a_0 = 0

There is often a slow sloppy way to do things and in this spirit I suggested that you could try to determine your characteristic equation symbolically, namely, to determine the coefficients a_0, a_1, ... a_n. This means that you will need to evaluate your determinant not by plugging in values for x but by working with the symbol x, keeping track of its powers and coefficients as the determinant is evaluated. In the end you will have reduced the eigenvalue problem to the simpler problem of finding the roots of an n-degree polynomial. For the latter you can use a basic bracketing scheme or something more sophisticated like Laguerre's method. Or you could again symbolically do polynomial long-division to factorize it into (x - x_0)(x - x_1)...(x - x_n) where your eigenvalues would then be x_0,...,x_n and you'll know how many repeated eigenvalues (multiplicity of the eigenvalues) you have.

By far the slowest and sloppiest way would be to find roots of det(A - x*I)=0 directly, using standard methods like bracketing, or Brent's method and evaluating your determinant for each iteration of the root finder. Coupled with your slow minors-expansion method of finding the determinant, I believe this will be unfeasible for matrices of any reasonable size, and you will most likely miss eigenvalues outside your search region and imaginary eigenvalues and eigenvalues which are too close to each other, but it will better than your random search method proposed above.

I should reiterate that the standard methods presented in books like NR are vastly superior, they are faster and treat difficulties like two roots being close to each other, imaginary roots, etc.

[arnaudk]

Thanks, the book says that there is a lot of other ways to find the eigenvalues(and of course not mentioning what those ways are and making me look for them, which I still am), and hopefully they can be applicable to C++.

If you want names, in NR the Given's method or Householder methods are used to bring real, symmetric matrices to tridiagonal form. Then the QR or "QL with implicit shifts" algorithms are used to find the eigenvalues or, also mentioned but not discussed are the "divide-and-conquer" and MRRR (Multiple Relative Robust Representation) methods. Non-symmetric matrices are reduced to Hessenberg form using the Householder method or Gaussian elimination with pivoting and then the QR algorithm is applied. Then there are methods for complex matrices....

[JosAH]

Also check the power method: x_i+1 == A*x_i, normalize the x_i's until both the
x_i+1 and x_i are a (near) multiple of each other. That multiple is the largest
eigen value and the last x_i+1 value is an eigen vector. Given this eigen vector
and value you can fiddle diddle a bit with matrix A in order to find the next largest
eigen value and vector. Google is your friend.

kind regards,

Jos

[TamusJRoyce]

Tip: Never forget about precision when coding equations. Especially with eigenvalues (where the more rows/columns you have, the more messy the precision can get). Numerical Recipies in C++ contains that as well, but any Numerical Calculus book/online resource should have calculating precision included.

I'm sure other methods than simply using the determinant will help on this regard, but don't let precision slip by...I guess it's one reason I try to stick to using libraries like gsl such as arnaudk does : )

Another type of book that is good is Linear and Nonlinear Programming. It uses matrices & eigenvalues on optimization problems. Maybe something you would want to learn to take your C++ eigenvalue code to the next level?

[happyrockz]

// EigRSvalo - Program for calculating the Eigenvalues ONLY of a N X N real, symmetric matrix.