Eigendecomposition of a matrix

In linear algebra, eigendecomposition or sometimes spectral decomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way.
Fundamental theory of matrix eigenvectors and eigenvalues.
A (non-zero) vector of dimension is an eigenvector of a square matrix if it satisfies the linear equation
where is a scalar, termed the eigenvalue corresponding to . That is, the eigenvectors are the vectors that the linear transformation merely elongates or shrinks, and the amount that they elongate/shrink by is the eigenvalue. The above equation is called the eigenvalue equation or the eigenvalue problem.
This yields an equation for the eigenvalues
We call the characteristic polynomial, and the equation, called the characteristic equation, is an th order polynomial equation in the unknown . This equation will have distinct solutions, where . The set of solutions, that is, the eigenvalues, is called the spectrum of .
We can factor as
The integer is termed the algebraic multiplicity of eigenvalue . If the field of scalars is algebraically closed, the algebraic multiplicities sum to :
For each eigenvalue , we have a specific eigenvalue equation
There will be linearly independent solutions to each eigenvalue equation. The linear combinations of the solutions 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 factorized 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 formula_8 (which is a shear matrix) cannot be diagonalized.
The eigenvectors are usually normalized, but they need not 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 .
The decomposition can be derived from the fundamental property of eigenvectors:
Example.
The 2 × 2 real matrix 
may be decomposed into a diagonal matrix through multiplication of a non-singular matrix 
Then
for some real diagonal matrix formula_13.
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
this gives us two vector equations:
And can be represented by a single vector equation involving two solutions as eigenvalues:
where represents the two eigenvalues and , and represents the vectors and .
Shifting to the left hand side and factoring out
Since is non-singular, it is essential that is non-zero. Therefore,
Thus
giving us the solutions of the eigenvalues for the matrix as or , and the resulting diagonal matrix from the eigendecomposition of is thus formula_23.
Putting the solutions back into the above simultaneous equations
Solving the equations, we have
Thus the matrix required for the eigendecomposition of is
that is:
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
If formula_29 is a symmetric matrix, since formula_30 is formed from the eigenvectors of formula_29 it is guaranteed to be an orthogonal matrix, therefore formula_32. 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.
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 is given by
then we know that
Because is a diagonal matrix, functions of are very easy to calculate:
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, using
from above. Once again, we find that
Examples.
which are examples for the functions formula_41. Furthermore, formula_42 is the matrix exponential.
Decomposition for special matrices.
Normal matrices.
A complex-valued square matrix is normal (meaning , where is the conjugate transpose) if and only if it can be decomposed as
where is a unitary matrix (meaning ) and is a diagonal matrix. The columns u1, …, u"n" of form an orthonormal basis and are eigenvectors of with corresponding eigenvalues "λ"1, …, "λ""n".
If is restricted to be a Hermitian matrix (), then has only real valued entries. If is restricted to a unitary matrix, then takes all its values on the complex unit circle, that is, .
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 eigenvectors of , and is a diagonal matrix whose entries are the eigenvalues of .
Useful facts.
Useful facts regarding eigenvalues.
<ul>
<li>
The sum of the eigenvalues is equal to the trace of 
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.
Once the eigenvalues are computed, the eigenvectors could be calculated by solving the equation
using Gaussian elimination or any other method for solving matrix equations.
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 (1st sense), which is the nullspace of the matrix for "any sufficiently large ". That is, it is the space of "generalized eigenvectors" (first sense), where a generalized eigenvector is any vector which "eventually" becomes 0 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 of the linear transformation. The coneigenvectors and coneigenvalues represent essentially the same information and meaning as the regular eigenvectors and eigenvalues, but arise when an alternative coordinate system is used. The corresponding equation is
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 vector that obeys
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 must obey the following equation
If linearly independent vectors can be found, such that for every , , then we define the matrices and such that
Then the following equality holds
And the proof is
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 is invertible, then the original problem can be written in the form
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 defined above satisfies
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".