Eigenvalues

The n by n matrix A has n eigenvalues l_i , i=1,...,n, which satisfy

If this equation is expanded out it can be represented as

If the matrix A has real entries then the a_i are real numbers, and the eigenvalues are either real numbers or occur in pairs as complex numbers with their complex conjugates. The Hamilton-Cayley theorem [Amundson, 1966, p. 127] states that the matrix A satisfies its own characteristic equation.

A laborious way to find the eigenvalues of a matrix is to solve the n-th order polynomial for the l_i , but that is far too time consuming. Instead the matrix is transformed into another form whose eigenvalues are easier to find. In the Givens method and Household method the matrix is transformed into tridiagonal form, and then in a fixed number of calculations the eigenvalues can be found [Press, et al., 1986]. The Givens method takes 4n³/3 operations to transform a real symmetric matrix to tridiagonal form, while the Householder method takes half that number [Isaacson and Keller, 1966]. Once the tridiagonal form is found a Sturm sequence is applied to find the eigenvalues. These methods are especially useful when only a few eigenvalues of the matrix are desired.

If all the eigenvalues are needed the QR algorithm is preferred. In the QR algorithm [Watkins, 1982] a modified Householder transformation is applied to A, transforming it to the form

A = Q R

where Q is orthogonal, and R is upper triangular. If A is banded then Q and R are banded.

The eigenvalues of a certain tridiagonal matrix can be found analytically. If A is a tridiagonal matrix with

then the eigenvalues of A are [Carey and Sepehrnoori, 1980].

This result is useful when finite difference methods are applied to the diffusion equation.