Find smallest eigenvalue exactly

Question

I would like to find the smallest (in absolute value) non-zero eigenvalue of a matrix exactly. I can do this using floating point arithmetic using numpy but

• is there a way to get an exact answer?
• Do you have to use sympy for this or is there another way?

The matrices will be small (say less than 20 by 20) with integer values. When I say exact answers I mean similar to those in the answer of John Habert for example.

Answer 1

Eigenvalues are algebraic numbers, that is roots of some polynomial. The degree of that polynomial would be the matrix dimension. For polynomials up to degree 4 you are in principle able to write those numbers down as nested roots, but beyond that there is in general no way to represent the eigenvalues exactly. And even in cases where it would be possible, you surely don't want to see the exact value, here is an example for an innocently looking small matrix:

Answer 2

From your post it is not clear whether the matrix will be Hermitian. I don't know of methods for the general case.

But! If the matrix is Hermitian (symmetric positive definite) you can avoid computing ALL the eigenvalues, if you just need the smallest one (which will be positive). You can use Inverse iteration. http://en.wikipedia.org/wiki/Inverse_iteration

You can start the algorithm with mu = 0; and then use Rayleigh quotients http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration which will generally give you very fast convergence. The method involves the solution of a linear system of equations (or, somewhat equivalently, the computation of the inverse matrix), but if again, the matrix is Hermitian, you can produce a Cholesky decomposition for it, and then use the resulting triangular matrices to solve the systems.

In some cases the method converges to the incorrect eigenvalue (say, next to the smallest).

Also, an interesting observation is that the LARGEST eigenvalue of matrix A is equal to the norm of this matrix (square root of sum of squares of its elements). The SMALLEST eigenvalue of A is equal to 1 divided by the norm of the INVERSE of A. So, if your matrix is not very large and its inverse exists, you can afford to invert it, then just do it, and compute 1/norm(inv(A)). This value will be the SMALLEST eigenvalue of A.