In numerical analysis, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix.
Given an n × n square matrix A of real or complex numbers, an eigenvalue λ and its associated generalized eigenvector v are a pair obeying the relation[1] where v is a nonzero n × 1 column vector, I is the n × n identity matrix, k is a positive integer, and both λ and v are allowed to be complex even when A is real.l When k = 1, the vector is called simply an eigenvector, and the pair is called an eigenpair.
The latter terminology is justified by the equation where det is the determinant function, the λi are all the distinct eigenvalues of A and the αi are the corresponding algebraic multiplicities.
More particularly, this basis {vi}ni=1 can be chosen and organized so that If these basis vectors are placed as the column vectors of a matrix V = [v1 v2 ⋯ vn], then V can be used to convert A to its Jordan normal form: where the λi are the eigenvalues, βi = 1 if (A − λi+1)vi+1 = vi and βi = 0 otherwise.
When applied to column vectors, the adjoint can be used to define the canonical inner product on Cn: w ⋅ v = w* v.[note 3] Normal, Hermitian, and real-symmetric matrices have several useful properties: 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.
Any problem of numeric calculation can be viewed as the evaluation of some function f for some input x.
The condition number κ(f, x) 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.
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.
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 Av = b where A is invertible, the matrix condition number κ(A−1, b) is given by ||A||op||A−1||op, where || ||op is the operator norm subordinate to the normal Euclidean norm on Cn.
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 n × n matrix A with eigenvector matrix V, then the absolute error in calculating λ is bounded by the product of κ(V) and the absolute error in A.
The condition number for the problem of finding the eigenspace of a normal matrix A corresponding to an eigenvalue λ has been shown to be inversely proportional to the minimum distance between λ and the other distinct eigenvalues of A.
[3] In particular, the eigenspace problem for normal matrices is well-conditioned for isolated eigenvalues.
For this reason algorithms that exactly calculate eigenvalues in a finite number of steps only exist for a few special classes of matrices.
Redirection is usually accomplished by shifting: replacing A with A − μI for some constant μ.
Reduction can be accomplished by restricting A to the column space of the matrix A − λI, which A carries to itself.
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.
matrix obtained by removing the i-th row and column from A, and let λk(Aj) be its k-th eigenvalue.
Because the eigenvalues of a triangular matrix are its diagonal elements, for general matrices there is no finite method like gaussian elimination to convert a matrix to triangular form while preserving eigenvalues.
Hessenberg and tridiagonal matrices are the starting points for many eigenvalue algorithms because the zero entries reduce the complexity of the problem.
For example, a projection is a square matrix P satisfying P2 = P. The roots of the corresponding scalar polynomial equation, λ2 = λ, are 0 and 1.
For dimensions 2 through 4, formulas involving radicals exist that can be used to find the eigenvalues.
For the 2×2 matrix the characteristic polynomial is Thus the eigenvalues can be found by using the quadratic formula: Defining
The characteristic equation of a symmetric 3×3 matrix A is: This equation may be solved using the methods of Cardano or Lagrange, but an affine change to A will simplify the expression considerably, and lead directly to a trigonometric solution.
Thus If det(B) is complex or is greater than 2 in absolute value, the arccosine should be taken along the same branch for all three values of k. This issue doesn't arise when A is real and symmetric, resulting in a simple algorithm:[17] Once again, the eigenvectors of A can be obtained by recourse to the Cayley–Hamilton theorem.
is an eigenvalue of multiplicity 2, so any vector perpendicular to the column space will be an eigenvector.