In linear algebra, eigendecomposition (also known as eigenvalue decomposition or EVD) is a factorization of a matrix into a canonical form given by is a diagonal matrix containing the eigenvalues is a matrix whose columns are the corresponding eigenvectors of . Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is a normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem.

Fundamental theory of matrix eigenvectors and eigenvalues

A nonzero vector of dimension is an eigenvector of a square matrix if it satisfies a linear equation of the form

for some scalar . Then, is called the eigenvalue corresponding to . Geometrically speaking, the eigenvectors of are the vectors that merely elongates or shrinks, and the amount that each of them elongates/shrinks by is the corresponding eigenvalue. The above equation is called the eigenvalue equation or the eigenvalue problem.

This yields an equation for the eigenvalues:

We call this equation the characteristic equation of ; it is an th-order polynomial equation in the unknown . We call the characteristic polynomial of .

The present article only considers algebraically closed fields of scalars. Then, the characteristic equation will have distinct solutions, where . The set of solutions, that is, of eigenvalues, is called the spectrum of .

We can factor as

and the characteristic equation becomes

The integer is termed the algebraic multiplicity of the eigenvalue . The algebraic multiplicities sum to :

For each eigenvalue , we have a specific eigenvalue equation in the unknown :

There will be linearly independent solutions to each eigenvalue equation. The linear combinations of the solutions (except the one which gives the zero vector) are the eigenvectors associated with the eigenvalue . The integer is termed the geometric multiplicity of . It is important to keep in mind that the algebraic multiplicity and geometric multiplicity may or may not be equal, but we always have . The simplest case is of course when . The total number of linearly independent eigenvectors, , can be calculated by summing the geometric multiplicities:

The eigenvectors can be indexed by eigenvalues, using a double index, with being the th eigenvector for the th eigenvalue. The eigenvectors can also be indexed using the simpler notation of a single index , with .

Eigendecomposition of a matrix

Let be a square matrix with linearly independent eigenvectors (where ). Then can be factored as

where is the square matrix whose th column is the eigenvector of , and is the diagonal matrix whose diagonal elements are the corresponding eigenvalues, . Note that only diagonalizable matrices can be factorized in this way. For example, the defective matrix (which is a shear matrix) cannot be diagonalized.

The eigenvectors are usually normalized, but they do not have to be. A non-normalized set of eigenvectors can also be used as the columns of . That can be understood by noting that the magnitude of the eigenvectors in gets canceled in the decomposition by the presence of . If one of the eigenvalues has multiple linearly independent eigenvectors (that is, the geometric multiplicity of is greater than ), then the eigenvectors for this eigenvalue can be chosen to be mutually orthogonal. However, if two eigenvectors belong to two different eigenvalues, it may be impossible for them to be orthogonal to each other. For instance, the matrix cannot be diagonalized in an orthogonal basis (see Example below). One special case is when is a normal matrix; then by the spectral theorem, it is always possible to diagonalize in an orthonormal basis .

The decomposition can be derived from the fundamental property of eigenvectors:

The linearly independent eigenvectors with nonzero eigenvalues form a basis (not necessarily orthonormal) for all possible products , for , which is the same as the image (or range) of the corresponding matrix transformation, and also the column space of the matrix . The number of linearly independent eigenvectors with nonzero eigenvalues is equal to the rank of the matrix , and also the dimension of the image (or range) of the corresponding matrix transformation, as well as its column space.

The linearly independent eigenvectors with an eigenvalue of zero form a basis (which can be chosen to be orthonormal) for the null space (also known as the kernel) of the matrix transformation .

Example

The real matrix

may be diagonalized as , where is a non-singular matrix to be determined:

and .

Multiplying both sides of the equation on the left by ,

The above equation can be decomposed into two simultaneous equations:

Factoring out the eigenvalues and ,

Letting

gives us a system of two vector equations:

This can be represented by a single vector equation involving two solutions as eigenvalues:

where represents any of the eigenvalues, or , and represents the corresponding eigenvector, or .

Shifting to the left-hand side and factoring out,

Since is non-singular, it is essential that is nonzero. Therefore,

Thus

giving us the solutions of the eigenvalues for the matrix as or . The resulting diagonal matrix from the eigendecomposition of is thus .

Putting the solutions back into the above simultaneous equations,

Solving the equations, we have

Thus the matrix required for the eigendecomposition of is

Finally, the diagonalization of is:

In this example, and , eigenvectors associated with distinct eigenvalues, cannot be orthogonal to each other. Indeed:

which would make singular.

Matrix inverse via eigendecomposition

If a matrix can be eigendecomposed and if none of its eigenvalues are zero, then is invertible and its inverse is given by

is formed from the eigenvectors of is guaranteed to be an orthogonal matrix; therefore . Furthermore, because is a diagonal matrix, its inverse is easy to calculate:

Practical implications

When eigendecomposition is used on a matrix of measured, real data, the inverse may be less valid when all eigenvalues are used unmodified in the form above. This is because as eigenvalues become relatively small, their contribution to the inversion is large. Those near zero or at the "noise" of the measurement system will have undue influence and could hamper solutions (detection) using the inverse.

Two mitigations have been proposed: truncating small or zero eigenvalues, and extending the lowest reliable eigenvalue to those below it. See also Tikhonov regularization as a statistically motivated but biased method for rolling off eigenvalues as they become dominated by noise.

The first mitigation method is similar to a sparse sample of the original matrix, removing components that are not considered valuable. However, if the solution or detection process is near the noise level, truncating may remove components that influence the desired solution.

The second mitigation extends the eigenvalue so that lower values have much less influence over inversion, but do still contribute, such that solutions near the noise will still be found.

The reliable eigenvalue can be found by assuming that eigenvalues of extremely similar and low value are a good representation of measurement noise (which is assumed low for most systems).

If the eigenvalues are rank-sorted by value, then the reliable eigenvalue can be found by minimization of the Laplacian of the sorted eigenvalues:

where the eigenvalues are subscripted with an to denote being sorted. The position of the minimization is the lowest reliable eigenvalue. In measurement systems, the square root of this reliable eigenvalue is the average noise over the components of the system.

Functional calculus

The eigendecomposition allows for much easier computation of power series of matrices. If Because is a diagonal matrix, functions of

The off-diagonal elements of are zero; that is, is also a diagonal matrix. Therefore, calculating reduces to just calculating the function on each of the eigenvalues.

A similar technique works more generally with the holomorphic functional calculus from above

Examples

is the matrix exponential.

Decomposition for spectral matrices

Spectral matrices are matrices that possess distinct eigenvalues and a complete set of eigenvectors. This characteristic allows spectral matrices to be fully diagonalizable, meaning they can be decomposed into simpler forms using eigendecomposition. This decomposition process reveals fundamental insights into the matrix's structure and behavior, particularly in fields such as quantum mechanics, signal processing, and numerical analysis.

Normal matrices

is normal (meaning is the conjugate transpose of ) if and only if it can be decomposed as is a unitary matrix (meaning is a diagonal matrix. form an orthonormal basis with corresponding eigenvalues .

For example, consider the normal matrix .

The eigenvalues are and .

Possible normalized eigenvectors corresponding to these eigenvalues are and .

The factorization is , where

, , and .

.

by finding its eigenvalues and eigenvectors, forming the unitary matrix , the diagonal matrix , and verifying the decomposition.

Real symmetric matrices

As a special case, for every real symmetric matrix, the eigenvalues are real and the eigenvectors can be chosen real and orthonormal. Thus a real symmetric matrix can be decomposed as , where is an orthogonal matrix whose columns are the real, orthonormal eigenvectors of , and is a diagonal matrix whose entries are the eigenvalues of .

Diagonalizable matrices

Diagonalizable matrices can be decomposed using eigendecomposition, provided they have a full set of linearly independent eigenvectors. They can be expressed as is a matrix whose columns are eigenvectors of is a diagonal matrix consisting of the corresponding eigenvalues of .

Positive definite matrices

Positive definite matrices using the Cholesky decomposition is a lower triangular matrix.

Unitary and Hermitian matrices

Orthogonal matrices (real case) and unitary matrices denotes the transpose denotes the conjugate transpose of . They diagonalize using unitary transformations.

Hermitian matrices satisfy denotes the conjugate transpose of . They can be diagonalized using unitary or orthogonal matrices.

Useful facts

Useful facts regarding eigenvalues

• The product of the eigenvalues is equal to the determinant of Note that each eigenvalue is raised to the power , its algebraic multiplicity.

• The sum of the eigenvalues is equal to the trace of Note that each eigenvalue is multiplied by , its algebraic multiplicity.

• If the eigenvalues of are , and is invertible, then the eigenvalues of are simply .

• If the eigenvalues of are , then the eigenvalues of are simply , for any holomorphic function and any for which is well-defined.

Useful facts regarding eigenvectors

• If is a Hermitian matrix and has full-rank, then the basis of eigenvectors may be chosen to be mutually orthogonal. The eigenvalues are real.

• The eigenvectors of are the same as the eigenvectors of .

• Eigenvectors are only defined up to a multiplicative constant. That is, if , then is also an eigenvector for any scalar . In particular, and (for any ) are also eigenvectors.

• In the case of a degenerate eigenvalue (an eigenvalue having more than one eigenvector), the eigenvectors have an additional freedom of linear transformation; that is to say, any linear (orthonormal) combination of eigenvectors sharing this eigenvalue (in the degenerate subspace) is itself an eigenvector (in this subspace).

Useful facts regarding eigendecomposition

• can be eigendecomposed if and only if the number of linearly independent eigenvectors, , equals the dimension of an eigenvector: .

• If the field of scalars is algebraically closed and if then can be eigendecomposed.

• The statement " can be eigendecomposed" does not imply that has an inverse, as some eigenvalues may be zero, making not invertible.

• The statement " has an inverse" does not imply that can be eigendecomposed. A counterexample, which is an invertible defective matrix.

Useful facts regarding matrix inverse

• can be inverted if and only if

• If and

Numerical computations

Numerical computation of eigenvalues

Suppose that we want to compute the eigenvalues of a given matrix. If the matrix is small, we can compute them symbolically using the characteristic polynomial. However, this is often impossible for larger matrices, in which case we must use a numerical method.

In practice, eigenvalues of large matrices are not computed using the characteristic polynomial. Computing the polynomial becomes expensive in itself, and exact (symbolic) roots of a high-degree polynomial can be difficult to compute and express: the Abel–Ruffini theorem implies that the roots of high-degree (5 or above) polynomials cannot in general be expressed simply using th roots. Therefore, general algorithms to find eigenvectors and eigenvalues are iterative.

Iterative numerical algorithms for approximating roots of polynomials exist, such as Newton's method, but in general it is impractical to compute the characteristic polynomial and then apply these methods. One reason is that small round-off errors in the coefficients of the characteristic polynomial can lead to large errors in the eigenvalues and eigenvectors: the roots are an extremely ill-conditioned function of the coefficients.

A simple and accurate iterative method is the power method: a random vector is chosen and a sequence of unit vectors

This sequence will almost always converge to an eigenvector corresponding to the eigenvalue of greatest magnitude, provided that has a nonzero component of this eigenvector in the eigenvector basis (and also provided that there is only one eigenvalue of greatest magnitude). This simple algorithm is useful in some practical applications; for example, Google uses it to calculate the page rank of documents in their search engine. Also, the power method is the starting point for many more sophisticated algorithms. For instance, by keeping not just the last vector in the sequence, but instead looking at the span of all the vectors in the sequence, one can get a better (faster converging) approximation for the eigenvector, and this idea is the basis of Arnoldi iteration. Alternatively, the important QR algorithm is also based on a subtle transformation of a power method.

Numerical computation of eigenvectors

using Gaussian elimination or any other method for solving matrix equationss.

However, in practical large-scale eigenvalue methods, the eigenvectors are usually computed in other ways, as a byproduct of the eigenvalue computation. In power iteration, for example, the eigenvector is actually computed before the eigenvalue (which is typically computed by the Rayleigh quotient of the eigenvector). In the QR algorithm for a Hermitian matrix (or any normal matrix), the orthonormal eigenvectors are obtained as a product of the matrices from the steps in the algorithm. (For more general matrices, the QR algorithm yields the Schur decomposition first, from which the eigenvectors can be obtained by a backsubstitution procedure.) For Hermitian matrices, the Divide-and-conquer eigenvalue algorithm is more efficient than the QR algorithm if both eigenvectors and eigenvalues are desired.

Additional topics

Generalized eigenspaces

Recall that the geometric multiplicity of an eigenvalue can be described as the dimension of the associated eigenspace, the nullspace of . The algebraic multiplicity can also be thought of as a dimension: it is the dimension of the associated generalized eigenspace (in the first sense), which is the nullspace of the matrix for any sufficiently large . That is, it is the space of generalized eigenvectors (in the first sense), where a generalized eigenvector is any vector which eventually becomes if is applied to it enough times successively. Any eigenvector is a generalized eigenvector, and so each eigenspace is contained in the associated generalized eigenspace. This provides an easy proof that the geometric multiplicity is always less than or equal to the algebraic multiplicity.

This usage should not be confused with the generalized eigenvalue problem described below.

Conjugate eigenvector

A conjugate eigenvector or coneigenvector is a vector sent after transformation to a scalar multiple of its conjugate, where the scalar is called the conjugate eigenvalue or coneigenvalue For example, in coherent electromagnetic scattering theory, the linear transformation represents the action performed by the scattering object, and the eigenvectors represent polarization states of the electromagnetic wave. In optics, the coordinate system is defined from the wave's viewpoint, known as the Forward Scattering Alignment (FSA), and gives rise to a regular eigenvalue equation, whereas in radar, the coordinate system is defined from the radar's viewpoint, known as the Back Scattering Alignment (BSA), and gives rise to a coneigenvalue equation.

Generalized eigenvalue problem

A generalized eigenvalue problem (second sense) is the problem of finding a (nonzero) vector where and are matrices. If obeys this equation, with some , then we call the generalized eigenvector of and (in the second sense), and is called the generalized eigenvalue of and (in the second sense) which corresponds to the generalized eigenvector . The possible values of

If linearly independent vectors can be found, such that for every , , then we define the matrices and

And since is invertible, we multiply the equation from the right by its inverse, finishing the proof.

The set of matrices of the form , where is a complex number, is called a pencil; the term matrix pencil can also refer to the pair of matrices.

If which is a standard eigenvalue problem. However, in most situations it is preferable not to perform the inversion, but rather to solve the generalized eigenvalue problem as stated originally. This is especially important if and are Hermitian matrices, since in this case is not generally Hermitian and important properties of the solution are no longer apparent.

If and are both symmetric or Hermitian, and is also a positive-definite matrix, the eigenvalues are real and eigenvectors and with distinct eigenvalues are -orthogonal (). In this case, eigenvectors can be chosen so that the matrix and there exists a basis of generalized eigenvectors (it is not a defective problem). This case is sometimes called a Hermitian definite pencil or definite pencil.

See also

• Eigenvalue perturbation

• Frobenius covariant

• Householder transformation

• Jordan normal form

• List of matrices

• Matrix decomposition

• Singular value decomposition

• Sylvester's formula

Notes

References

External links

• Interactive program & tutorial of Spectral Decomposition.