How to calculate eigenvalues of a matrix

[nimacasino]

Hi everybody

I want to calculate spectral radius of matrix A, which is in a two dimension array. as you know, for doing that, i need to calculate eigenvalues of this matrix, but i don't know how can i do that. does anybody have experience with this problem? i mean, how can i calculate eigenvalues of a n*n matrix?
i am using g++-4.3 compiler

[tition]

Dear nimacasino,

Certainly there is no standard function to do that in C++.
You said that your matrix is in a two dimensional array - how is that an n by n matrix?
For what purpose/application do you need to find eigenvalues?

[Edit:]

Just found a very useful article in wikipedia on the topic: this is actually implementable:

http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm


Finding the eigenvectors of a matrix larger than or equal to 5 by 5 cannot be done "algebraically" (i.e. using radicals). This is explained in rather technical terms here:

http://en.wikipedia.org/wiki/Eigenvalue_algorithm#Characteristic_polynomial

You have to use some sort of approximation theory to find eigenvalues. If your problem comes from Markov chains/probabilities (your username is nimacasino - that sounds kinda gamble-like), then you might have some use for the Power iteration algorithm. A very bad explanation
of it may be found here
http://en.wikipedia.org/wiki/Eigenvalue_algorithm#Power_iteration
but I assure you will run into big troubles trying to implement it, whenever your eigenvalues are complex and/or you don't have convergence. For example, you do not have convergence using that method for the matrix

0 -1
1 0

(which has eigenvalues i and -i).

Also, the method only tells you how to find the largest eigenvalue. To find the remaining eigenvalues (if they exist), you will need to transform your matrix to a smaller one (using the found eigenvalue and the original matrix) and repeat the algorithm. I cannot tell you exactly how off the top of my head (needs some more thought).

In other words, if you want a function to find eigenvalues of an n by n matrix, you will need to do a lot of mathematical work besides programming.

[nimacasino]

Dear tition

I impressed by your complete answer, i really appreciate it.
to be clear about some vague that i made before, i should correct some assumptions. i have a n*n matrix A. i need the spectral radius of that to use it in direct of calculation of bandwidth capacity of a wireless link in a Network simulator (some expert issue).
as you mentioned above, i have a transition matrix (let it be A, for example) for a markov chain and as a part of whole project, i should calculate the greatest eigenvalue of matrix A that is the spectral radius of this matrix. spectral radius ρ(A) can be defined as :

ρ(A) = max_i (|λ_i|)

if we have λ1, ..., λn as eigenvalues of matrix A.

i had a little study about this issue and i know we have to use an approximation approach to calculate the eigenvalues. is there any library for doing that and has anybody have experience with using it?

[tition]

Unfortunately, I do not know of any library (not saying there isn't, I am just the type of person who likes to program anything himself).

Did you try posting on other forums?

Other than that, the fact that you are looking for

ρ(A) = maxi (|λi|)

suggests that your matrices will satisfy the conditions needed to run the Power iteration algorithm; the output of that algorithm is exactly what you are looking for. The algorithm is really simple to implement, and is also very simple to prove that, if it converges, the answer you get is correct.

What I would do if I were you is
1) try posting at another forum.
2) in the meantime implement the power iteration algorithm and see whether it works.

Do you need to have the answer for one particular example, for a fixed set of examples, or to create a program that runs for an arbitrary user input example?

The whole implementation would take some time between 30 minutes (if you are skillful with C++ and have good math libraries) and 3-4 days, if you have to write everything from scratch (including the linear algebra).

I would gladly try to help with point 2), if I can.

i have a transition matrix (let it be A, for example) for a markov chain

I believe that matrices coming from Markov chains very often satisfy the conditions needed for the power iteration algorithm to converge. I tried to decode that from the Markov chain page on Wikipedia, but I couldn't figure it out - you need to ask a specialist on the subject.

I think, without being sure, the question of whether the power iteration algorithm works is related to the notion of periodicity and/or ergodicity of a Markov chain, but unfortunately my knowledge on the subject ends here :(

[Edit:] If your matrix is right stochastic, then you don't need to write a program for it: the largest eigenvalue is 1:
http://en.wikipedia.org/wiki/Right_stochastic_matrix#Definition_and_properties

, so I presume you will want to run the program for non-stochastic matrices.

[nimacasino]

Sorry for replying late. I forgot to subscribe on this topic.

In past days i searched this issue and find ARPACK++( http://www.ime.unicamp.br/~chico/arpack++/ ), the best fit library for solving problems around eigenvalues and eigenvectors. i tried power method too, but it seems not working in some conditions based on the nature of my transition matrices.

Anyway, I'm trying on ARPACK++ and as soon as getting some results, i will post my comment about it here to get use in the future.