Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, one of the most important problems is designing efficient and stable
Numerical stability
In the mathematical subfield of numerical analysis, numerical stability is a desirable property of numerical algorithms. The precise definition of stability depends on the context, but it is related to the accuracy of the algorithm....
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
. These eigenvalue algorithms may also find eigenvectors.
Characteristic polynomial
Given a square matrix A, an eigenvalue λ and its associated eigenvector v are, by definition, a pair obeying the relation
where v is nonzero. Equivalently, (A−λI)v = 0 (where I is the identity matrix), implying det(A−λI) = 0. This determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of A. One common method for determining the eigenvalues of a small matrix is by finding roots of the characteristic polynomial.
Unfortunately, this method has some limitations. A general polynomial of order n > 4 cannot be solved by a finite sequence of arithmetic operations and radicals (see Abel–Ruffini theorem
Abel–Ruffini theorem
In algebra, the Abel–Ruffini theorem states that there is no general algebraic solution—that is, solution in radicals— to polynomial equations of degree five or higher.- Interpretation :...
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
s for higher order polynomials. However, finding the roots of the characteristic polynomial may be an ill-conditioned
Condition number
In the field of numerical analysis, the condition number of a function with respect to an argument measures the asymptotically worst case of how much the function can change in proportion to small changes in the argument...
problem even when the underlying eigenvalue problem is well-conditioned. For this reason, this method is rarely used.
The above discussion implies a restriction on all eigenvalue algorithms. It can be shown that for any polynomial, there exists a matrix (see companion matrix) having that polynomial as its characteristic polynomial (actually, there are infinitely many). If there did exist a finite sequence of arithmetic operations for exactly finding the eigenvalues of a general matrix, this would provide a corresponding finite sequence for general polynomials, in contradiction of the Abel–Ruffini theorem. Therefore, general eigenvalue algorithms are expected to be iterative
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
.
Power iteration
Let the eigenvalues of be . Assume that has absolute value strictly larger than that of . This is an essential restriction: for a matrix with real coefficients, if the eigenvalue with highest absolute value is not real, its complex conjugate is always an eigenvalue with the same absolute value.
With the preceding assumptions in mind, the idea of the method is to choose an (arbitrary) unit length vector and then repeatedly multiply it by the matrix and re-scale. One carries out the computation , , , .... Let the vector have a generalized eigenspace decomposition , where belongs to the generalized eigenspace corresponding to eigenvalue , belongs to the generalized eigenspace corresponding to eigenvalue , etc. Each iteration of the algorithm will decrease the "contribution" of the components in the eigenspaces of eigenvalues relative to the contribution of and therefore the vector will converge to a unit eigenvector of eigenvalue .
In mathematics, the power iteration is an eigenvalue algorithm: given a matrix A, the algorithm will produce a number λ and a nonzero vector v , such that Av = λv....
algorithm for finding the (largest) eigenvalue is simple to implement but is otherwise not very useful in practice. Its convergence is slow except for special cases of matrices. Without modification, it can only find the dominant eigenvalue (and the corresponding eigenvector), provided they exist.
A few of the more advanced eigenvalue algorithms are variations of power iteration. In addition, some of the better algorithms for the generalized eigenvalue problem are based on power iteration.
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, an important tool for describing eigenvalues of square matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
) has a non-zero solution v (namely an eigenvector), and so it is equivalent to the determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
det (A - λI) being zero. The function p(λ) = det (A - λI) is a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
in λ since determinants are defined as sums of products.
This is the characteristic polynomial of A: the eigenvalues of a matrix are the zeros of its characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
.
It follows that we can compute all the eigenvalues of a matrix A by solving the equation .
If A is an n-by-n matrix, then has degree n and A can therefore have at most n eigenvalues.
Conversely, the fundamental theorem of algebra
Fundamental theorem of algebra
The fundamental theorem of algebra states that every non-constant single-variable polynomial with complex coefficients has at least one complex root...
says that this equation has exactly n roots (zeroes), counted with multiplicity. All real polynomials of odd degree have a real number as a root, so for odd n, every real matrix has at least one real eigenvalue. In the case of a real matrix, for even and odd n, the non-real eigenvalues come in conjugate pairs.
An example of a matrix with no real eigenvalues is the 90-degree rotation
whose characteristic polynomial is and so its eigenvalues are the pair of complex conjugates i, -i.
In linear algebra, the Cayley–Hamilton theorem states that every square matrix over a commutative ring satisfies its own characteristic equation....
states that every square matrix satisfies its own characteristic polynomial, that is, .
Eigenvalues of 2×2 matrices
An analytic solution for the eigenvalues of 2×2 matrices can be obtained directly from the quadratic formula: if
then the characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
is
so the solutions are
Notice that the characteristic polynomial of a 2×2 matrix can be written in terms of the trace
Trace (linear algebra)
In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal of A, i.e.,...
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
. The solutions for the eigenvalues of a 2×2 matrix can thus be written as
Thus, for the very special case where the 2×2 matrix has zero determinant, but non-zero trace, the eigenvalues are zero and the trace (corresponding to the negative and positive roots, respectively). For example, the eigenvalues of the following matrix are 0 and ():
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of A is
Alternatively the characteristic polynomial of a 3×3 matrix can be written in terms of the trace
Trace (linear algebra)
In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal of A, i.e.,...
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...
.
The eigenvalues of the matrix are the roots of this polynomial, which can be found using the method for solving cubic equations.
A formula for the eigenvalues of a 4×4 matrix could be derived in an analogous way, using the formulae for the solutions of the quartic equation.
A programmatical approach to finding eigenvalues
In case you don’t have access to scientific software that has an eigenvalue function, below are a set of steps you could use as pseudo code to help you create a program to solve problems.
For a 2×2:
//we know there are two eigenvalues, so the equations from above can be hard-coded in with minimal effort
Eig11 = (a+d)/2 + sqrt(((a+d)*(a+d))/4 + bc – ad)
Eig12 = (a+d)/2 - sqrt(((a+d)*(a+d))/4 + bc – ad)
//eig11 is the value found using + and eig12 is the value using -
//or we get the same two eigenvalues with the modified equation
Eig21 = (a+d)/2 + sqrt(4bc + (a-d)(a-d))/2
Eig22 = (a+d)/2 - sqrt(4bc + (a-d)(a-d))/2
For a 3×3:
//a 3×3 is more complicated and requires several helper equations to accomplish due to the λ³ term.
//These steps should help you calculate eigen values for a matrix that has ***3 REAL eigen values***.
Define x,y,z
//Use the equation from above to get your cubic equation and combine all constant terms possible to
//give you a reduced equation we will use a, b, c and d to denote the coefficients of this equation.
//Eqn = aλ³ + bλ² + cλ + d = 0
x = ((3c/a) – (b²/a²))/3
y = ((2b³/a³) – (9bc/a²) + (27d/a))/27
z = y²/4 + x³/27
Define I, j, k, m, n, p (so equations are not so cluttered)
i = sqrt(y²/4 - z)
j = -i^(1/3)
k = arccos(-(y/2i))
m = cos(k/3)
n = sqrt(3)*sin(k/3)
p = b/3a
Define Eig1, Eig2, Eig3
Eig1 = 2j*m + p
Eig2 = -j *(m + n) + p
Eig3 = -j*(m - n) + p
Eigenvalues of a Symmetric 3x3 Matrix
(Reference: Oliver K. Smith: Eigenvalues of a symmetric 3 × 3 matrix. Commun. ACM 4(4): 168 (1961) )
Note: this method does not work for singular matrices (matrices with one or more zero eigenvalues).
This is a Matlab version:
% Given symmetric 3x3 matrix M, compute the eigenvalues
m = trace(M)/3;
K = M-m*eye(3);
q = det(K)/2;
p = 0
for i=1:3
for j=1:3
p = p + K(i,j)^2;
end
end
p = p/6;
phi = 1/3*acos(q/p^(3/2));
% NOTE: the follow formula assume accurate computation and therefor q/p^(3/2) should be in range of [1,-1],
% but in real code, because of numerical errors, it must be checked. Thus, in case abs(q) >= abs(p^(3/2)), set phi = 0;
if(abs(q) >= abs(p^(3/2)))
phi = 0;
end
if(phi<0)
phi=phi+pi/3;
end
eig1 = m + 2*sqrt(p)*cos(phi)
eig2 = m - sqrt(p)*(cos(phi) + sqrt(3)*sin(phi))
eig3 = m - sqrt(p)*(cos(phi) - sqrt(3)*sin(phi))
Or here is a version in python that uses numpy:
def smith_eigenvals(mat):
"""Returns the eigenvalues of a 3x3 symmetric matrix.
Or can use numpy.linalg.eigvals function.
"""
import numpy
m = numpy.trace(mat) / 3.
K = mat - m*numpy.eye(3)
q = numpy.linalg.det(K) / 2.
p = numpy.sum(K*K) / 6.
# NB in Smith's paper he uses phi = (1./3.)*arctan(sqrt(p**3 - q**2)/q), which is equivalent to below:
phi = (1./3.)*numpy.arccos(q/(p**(3./2.)))
print "m", m
print "p", p
print "q", q
print "phi", phi
if abs(q) >= abs(p**(3./2.)):
phi = 0.
if phi < 0.:
phi = phi + numpy.pi/3.
eig1 = m + 2.*numpy.sqrt(p)*numpy.cos(phi)
eig2 = m - numpy.sqrt(p)*(numpy.cos(phi) + numpy.sqrt(3.)*numpy.sin(phi))
eig3 = m - numpy.sqrt(p)*(numpy.cos(phi) - numpy.sqrt(3.)*numpy.sin(phi))
return eig1, eig2, eig3
Eigenvalues and eigenvectors of special matrices
For matrices satisfying one can write explicit formulas for the possible eigenvalues and the projectors on the corresponding eigenspaces.
with
and
This provides the following resolution of identity
The multiplicity of the possible eigenvalues is given by the rank of the projectors.
Example computation
The computation of eigenvalue/eigenvector can be realized with the following algorithm.
Consider an n-square matrix A
1. Find the roots of the characteristic polynomial of A. These are the eigenvalues.
If n different roots are found, then the matrix can be diagonalized.
2. Find a basis for the kernel of the matrix given by . For each of the eigenvalues. These are the eigenvectors
The eigenvectors given from different eigenvalues are linearly independent.
The eigenvectors given from a root-multiplicity are also linearly independent.
Let us determine the eigenvalues of the matrix
which represents a linear operator R³ → R³.
Identifying eigenvalues
We first compute the characteristic polynomial of A:
This polynomial factors to . Therefore, the eigenvalues of A are 2, 1 and −1.
Identifying eigenvectors
With the eigenvalues in hand, we can solve sets of simultaneous linear equations to determine the corresponding eigenvectors. Since we are solving for the system , if then,
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
matrix, the characteristic polynomial will have real coefficients, but its roots will not necessarily all be real. The complex
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
In mathematics, complex conjugates are a pair of complex numbers, both having the same real part, but with imaginary parts of equal magnitude and opposite signs...
s. For a real matrix, the eigenvectors of a non-real eigenvalue z , which are the solutions of , cannot be real.
If v1, ..., vm are eigenvectors with different eigenvalues λ1, ..., λm, then the vectors v1, ..., vm are necessarily linearly independent.
In mathematics, particularly linear algebra and functional analysis, the spectral theorem is any of a number of results about linear operators or about matrices. In broad terms the spectral theorem provides conditions under which an operator or a matrix can be diagonalized...
for symmetric matrices states that if A is a real symmetric n-by-n matrix, then all its eigenvalues are real, and there exist n linearly independent eigenvectors for A which are mutually orthogonal. Symmetric matrices are commonly encountered in engineering.
Our example matrix from above is symmetric, and three mutually orthogonal eigenvectors of A are
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
of R³. With respect to this basis, the linear map represented by A takes a particularly simple form: every vector x in R³ can be written uniquely as
and then we have
Advanced methods
A popular method for finding eigenvalues is the QR algorithm
QR algorithm
In numerical linear algebra, the QR algorithm is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in the late 1950s by John G.F. Francis and by Vera N. Kublanovskaya , working independently...
In linear algebra, a QR decomposition of a matrix is a decomposition of a matrix A into a product A=QR of an orthogonal matrix Q and an upper triangular matrix R...
In linear algebra, a Householder transformation is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. Householder transformations are widely used in numerical linear algebra, to perform QR decompositions and in the first step of the QR algorithm...
In linear algebra, LU decomposition is a matrix decomposition which writes a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear...
In numerical linear algebra, the QR algorithm is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in the late 1950s by John G.F. Francis and by Vera N. Kublanovskaya , working independently...
In numerical analysis, inverse iteration is an iterative eigenvalue algorithm. It allows to find an approximateeigenvector when an approximation to a corresponding eigenvalue is already known....
Rayleigh quotient iteration is an eigenvalue algorithm which extends the idea of the inverse iteration by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates....
In numerical linear algebra, the QR algorithm is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a matrix. The QR transformation was developed in the late 1950s by John G.F. Francis and by Vera N. Kublanovskaya , working independently...
In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of iterative methods. Arnoldi finds the eigenvalues of general matrices; an analogous method for Hermitian matrices is the Lanczos iteration. The Arnoldi iteration was invented by W. E...
In numerical linear algebra, the Jacobi eigenvalue algorithm is an iterative method for the calculation of the eigenvalues and eigenvectors of a real symmetric matrix...
Divide-and-conquer eigenvalue algorithms are a class of eigenvalue algorithms for Hermitian or real symmetric matrices that have recently become competitive in terms of stability and efficiency with more traditional algorithms such as the QR algorithm. The basic concept behind these algorithms is...
Most eigenvalue algorithms rely on first reducing the matrix A to Hessenberg
Hessenberg matrix
In linear algebra, a Hessenberg matrix is a special kind of square matrix, one that is "almost" triangular. To be exact, an upper Hessenberg matrix has zero entries below the first subdiagonal, and a lower Hessenberg matrix has zero entries above the first superdiagonal...
or tridiagonal form. This is usually accomplished via reflections.
See also
List of eigenvalue algorithms
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
be 
. Assume that 
has absolute value strictly larger than that of 
. This is an essential restriction: for a matrix with real coefficients, if the eigenvalue with highest absolute value is not real, its complex conjugate is always an eigenvalue with the same absolute value.
and then repeatedly multiply it by the matrix 
and re-scale. One carries out the computation 
, 
, 
, .... Let the vector 
have a generalized eigenspace decomposition 
, where 
belongs to the generalized eigenspace corresponding to eigenvalue 
, 
belongs to the generalized eigenspace corresponding to eigenvalue 
, etc. Each iteration of the algorithm will decrease the "contribution" of the components in the eigenspaces of eigenvalues 
relative to the contribution of 
and therefore the vector 
will converge to a unit eigenvector of eigenvalue 
.
.
has degree n and A can therefore have at most n eigenvalues.
and so its eigenvalues are the pair of complex conjugates i, -i.
.
and determinant
as
is the 2×2 identity matrix
):
and determinant
as
is the 3×3 identity matrix
one can write explicit formulas for the possible eigenvalues and the projectors on the corresponding eigenspaces.
. Therefore, the eigenvalues of A are 2, 1 and −1.
, if 
then,
to row echelon form
:
is a valid eigenvector with eigenvalue 
:
. For each of the eigenvalues. These are the eigenvectors
.
, cannot be real.
