Eigenvalue algorithm


In numerical analysis, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors.

Eigenvalues and eigenvectors

Given an square matrix of real or complex numbers, an eigenvalue and its associated generalized eigenvector are a pair obeying the relation
where is a nonzero column vector, is the identity matrix, is a positive integer, and both and are allowed to be complex even when is real. When, the vector is called simply an eigenvector, and the pair is called an eigenpair. In this case,. Any eigenvalue of has ordinary eigenvectors associated to it, for if is the smallest integer such that for a generalized eigenvector, then is an ordinary eigenvector. The value can always be taken as less than or equal to. In particular, for all generalized eigenvectors associated with.
For each eigenvalue of, the kernel consists of all eigenvectors associated with , called the eigenspace of, while the vector space consists of all generalized eigenvectors, and is called the generalized eigenspace. The geometric multiplicity of is the dimension of its eigenspace. The algebraic multiplicity of is the dimension of its generalized eigenspace. The latter terminology is justified by the equation
where is the determinant function, the are all the distinct eigenvalues of and the are the corresponding algebraic multiplicities. The function is the characteristic polynomial of. So the algebraic multiplicity is the multiplicity of the eigenvalue as a zero of the characteristic polynomial. Since any eigenvector is also a generalized eigenvector, the geometric multiplicity is less than or equal to the algebraic multiplicity. The algebraic multiplicities sum up to, the degree of the characteristic polynomial. The equation is called the characteristic equation, as its roots are exactly the eigenvalues of. By the Cayley–Hamilton theorem, itself obeys the same equation:. As a consequence, the columns of the matrix must be either 0 or generalized eigenvectors of the eigenvalue, since they are annihilated by. In fact, the column space is the generalized eigenspace of.
Any collection of generalized eigenvectors of distinct eigenvalues is linearly independent, so a basis for all of can be chosen consisting of generalized eigenvectors. More particularly, this basis can be chosen and organized so that
  • if and have the same eigenvalue, then so does for each between and, and
  • if is not an ordinary eigenvector, and if is its eigenvalue, then .
If these basis vectors are placed as the column vectors of a matrix, then can be used to convert to its Jordan normal form:
where the are the eigenvalues, if and otherwise.
More generally, if is any invertible matrix, and is an eigenvalue of with generalized eigenvector, then. Thus is an eigenvalue of with generalized eigenvector. That is, similar matrices have the same eigenvalues.

Normal, Hermitian, and real-symmetric matrices

The adjoint of a complex matrix is the transpose of the conjugate of :. A square matrix is called normal if it commutes with its adjoint:. It is called Hermitian if it is equal to its adjoint:. All Hermitian matrices are normal. If has only real elements, then the adjoint is just the transpose, and is Hermitian if and only if it is symmetric. When applied to column vectors, the adjoint can be used to define the canonical inner product on :. Normal, Hermitian, and real-symmetric matrices have several useful properties:
  • Every generalized eigenvector of a normal matrix is an ordinary eigenvector.
  • Any normal matrix is similar to a diagonal matrix, since its Jordan normal form is diagonal.
  • Eigenvectors of distinct eigenvalues of a normal matrix are orthogonal.
  • The null space and the image of a normal matrix are orthogonal to each other.
  • For any normal matrix, has an orthonormal basis consisting of eigenvectors of. The corresponding matrix of eigenvectors is unitary.
  • The eigenvalues of a Hermitian matrix are real, since for a non-zero eigenvector.
  • If is real, there is an orthonormal basis for consisting of eigenvectors of if and only if is symmetric.
It is possible for a real or complex matrix to have all real eigenvalues without being Hermitian. For example, a real triangular matrix has its eigenvalues along its diagonal, but in general is not symmetric.

Condition number

Any problem of numeric calculation can be viewed as the evaluation of some function for some input. The condition number of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base-10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best-case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well-conditioned. However, the problem of finding the roots of a polynomial can be very ill-conditioned. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill-conditioned even when the problem is not.
For the problem of solving the linear equation where is invertible, the matrix condition number is given by, where is the operator norm subordinate to the normal Euclidean norm on. Since this number is independent of and is the same for and, it is usually just called the condition number of the matrix. This value is also the absolute value of the ratio of the largest singular value of to its smallest. If is unitary, then, so. For general matrices, the operator norm is often difficult to calculate. For this reason, other matrix norms are commonly used to estimate the condition number.
For the eigenvalue problem, Bauer and Fike proved that if is an eigenvalue for a diagonalizable matrix with eigenvector matrix, then the absolute error in calculating is bounded by the product of and the absolute error in. As a result, the condition number for finding is. If is normal, then is unitary, and. Thus the eigenvalue problem for all normal matrices is well-conditioned.
The condition number for the problem of finding the eigenspace of a normal matrix corresponding to an eigenvalue has been shown to be inversely proportional to the minimum distance between and the other distinct eigenvalues of. In particular, the eigenspace problem for normal matrices is well-conditioned for isolated eigenvalues. When eigenvalues are not isolated, the best that can be hoped for is to identify the span of all eigenvectors of nearby eigenvalues.

Algorithms

The most reliable and most widely used algorithm for computing eigenvalues is John G. F. Francis' and Vera N. Kublanovskaya's QR algorithm, considered one of the top ten algorithms of 20th century.
Any monic polynomial is the characteristic polynomial of its companion matrix. Therefore, a general algorithm for finding eigenvalues could also be used to find the roots of polynomials. The Abel–Ruffini theorem shows that any such algorithm for dimensions greater than 4 must either be infinite, or involve functions of greater complexity than elementary arithmetic operations and fractional powers. For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices. For general matrices, algorithms are iterative, producing better approximate solutions with each iteration.
Some algorithms produce every eigenvalue, others will produce a few, or only one. However, even the latter algorithms can be used to find all eigenvalues. Once an eigenvalue of a matrix has been identified, it can be used to either direct the algorithm towards a different solution next time, or to reduce the problem to one that no longer has as a solution.
Redirection is usually accomplished by shifting: replacing with for some constant. The eigenvalue found for must have added back in to get an eigenvalue for. For example, for power iteration,. Power iteration finds the largest eigenvalue in absolute value, so even when is only an approximate eigenvalue, power iteration is unlikely to find it a second time. Conversely, inverse iteration based methods find the lowest eigenvalue, so is chosen well away from and hopefully closer to some other eigenvalue.
Reduction can be accomplished by restricting to the column space of the matrix, which carries to itself. Since is singular, the column space is of lesser dimension. The eigenvalue algorithm can then be applied to the restricted matrix. This process can be repeated until all eigenvalues are found.
If an eigenvalue algorithm does not produce eigenvectors, a common practice is to use an inverse iteration based algorithm with set to a close approximation to the eigenvalue. This will quickly converge to the eigenvector of the closest eigenvalue to. For small matrices, an alternative is to look at the column space of the product of for each of the other eigenvalues.
A formula for the norm of unit eigenvector components of normal matrices was discovered by Robert Thompson in 1966 and rediscovered independently by several others.
If is an normal matrix with eigenvalues and corresponding unit eigenvectors whose component entries are, let be the matrix obtained by removing the -th row and column from, and let be its -th eigenvalue. Then
If are the characteristic polynomials of and, the formula can be re-written as
assuming the derivative is not zero at.