View source for Eigendecomposition of a matrix

{{Short description|Matrix decomposition}}
In [[Linear algebra|linear algebra]], '''eigendecomposition''' is the factorization of a [[Matrix (mathematics)|matrix]] into a [[Canonical form|canonical form]], whereby the matrix is represented in terms of its [[Eigenvalues and eigenvectors|eigenvalues and eigenvectors]]. Only [[Diagonalizable matrix|diagonalizable matrices]] can be factorized in this way. When the matrix being factorized is a [[Normal matrix|normal]] or real [[Symmetric matrix|symmetric matrix]], the decomposition is called "spectral decomposition", derived from the [[Spectral theorem|spectral theorem]].

== Fundamental theory of matrix eigenvectors and eigenvalues ==

A (nonzero) vector {{math|'''v'''}} of dimension {{mvar|N}} is an eigenvector of a square {{math|''N'' × ''N''}} matrix {{math|'''A'''}} if it satisfies a [[Linear equation|linear equation]] of the form
:<math>\mathbf{A} \mathbf{v} = \lambda \mathbf{v}</math>

for some scalar {{mvar|λ}}. Then {{mvar|λ}} is called the eigenvalue corresponding to {{math|'''v'''}}. Geometrically speaking, the eigenvectors of {{math|'''A'''}} are the vectors that {{math|'''A'''}} 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
:<math> p\left(\lambda\right) = \det\left(\mathbf{A} - \lambda \mathbf{I}\right)= 0. </math>

We call {{math|''p''(''λ'')}} the [[Characteristic polynomial|characteristic polynomial]], and the equation, called the characteristic equation, is an {{mvar|N}}th-order polynomial equation in the unknown {{mvar|λ}}. This equation will have {{mvar|N<sub>λ</sub>}} distinct solutions, where {{math|1 ≤ ''N<sub>λ</sub>'' ≤ ''N''}}.  The set of solutions, that is, the eigenvalues, is called the [[Spectrum of a matrix|spectrum]] of {{math|'''A'''}}.<ref>{{harvtxt|Golub|Van Loan|1996|p=310}}</ref><ref>{{harvtxt|Kreyszig|1972|p=273}}</ref><ref>{{harvtxt|Nering|1970|p=270}}</ref>

If the field of scalars is [[Algebraically closed field|algebraically closed]], then we can [[Factorization|factor]] {{mvar|p}} as
:<math>p\left(\lambda\right) = \left(\lambda - \lambda_1\right)^{n_1}\left(\lambda - \lambda_2\right)^{n_2} \cdots \left(\lambda-\lambda_{N_{\lambda}}\right)^{n_{N_{\lambda}}} = 0. </math>
The integer {{mvar|n<sub>i</sub>}} is termed the algebraic multiplicity of eigenvalue {{mvar|λ<sub>i</sub>}}. The algebraic multiplicities sum to {{mvar|N}}: <math display="inline">\sum_{i=1}^{N_\lambda}{n_i} = N.</math>

For each eigenvalue {{mvar|λ<sub>i</sub>}}, we have a specific eigenvalue equation
:<math>\left(\mathbf{A} - \lambda_i \mathbf{I}\right)\mathbf{v} = 0. </math>

There will be {{math|1 ≤ ''m''<sub>''i''</sub> ≤ ''n''<sub>''i''</sub>}} linearly independent solutions to each eigenvalue equation.  The linear combinations of the {{math|''m''<sub>''i''</sub>}} solutions (except the one which gives the zero vector) are the eigenvectors associated with the eigenvalue {{math|''λ''<sub>''i''</sub>}}.  The integer {{math|''m''<sub>''i''</sub>}} is termed the geometric multiplicity of {{math|''λ''<sub>''i''</sub>}}.  It is important to keep in mind that the algebraic multiplicity {{math|''n''<sub>''i''</sub>}} and geometric multiplicity {{math|''m''<sub>''i''</sub>}} may or may not be equal, but we always have {{math|''m''<sub>''i''</sub> ≤ ''n''<sub>''i''</sub>}}.  The simplest case is of course when {{math|1=''m''<sub>''i''</sub> = ''n''<sub>''i''</sub> = 1}}.  The total number of linearly independent eigenvectors, {{math|''N''<sub>'''v'''</sub>}}, can be calculated by summing the geometric multiplicities
:<math>\sum_{i=1}^{N_{\lambda}}{m_i} = N_{\mathbf{v}}.</math>

The eigenvectors can be indexed by eigenvalues, using a double index, with {{math|'''v'''<sub>''ij''</sub>}} being the {{mvar|j}}th eigenvector for the {{mvar|i}}th eigenvalue.  The eigenvectors can also be indexed using the simpler notation of a single index {{math|'''v'''<sub>''k''</sub>}}, with {{math|1=''k'' = 1, 2, ..., ''N''<sub>'''v'''</sub>}}.

== Eigendecomposition of a matrix ==
Let {{math|'''A'''}} be a square {{math|''n'' × ''n''}} matrix with {{mvar|n}} linearly independent eigenvectors {{mvar|q<sub>i</sub>}} (where {{math|1=''i'' = 1, ..., ''n''}}).  Then {{math|'''A'''}} can be [[Matrix decomposition|factorized]] as
:<math>\mathbf{A}=\mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^{-1}  </math>
where {{math|'''Q'''}} is the square {{math|''n'' × ''n''}} matrix whose {{mvar|i}}th column is the eigenvector {{mvar|q<sub>i</sub>}} of {{math|'''A'''}}, and {{math|'''Λ'''}} is the [[Diagonal matrix|diagonal matrix]] whose diagonal elements are the corresponding eigenvalues, {{math|1=''Λ<sub>ii</sub>'' = ''λ<sub>i</sub>''}}. Note that only [[Diagonalizable matrix|diagonalizable matrices]] can be factorized in this way. For example, the [[Defective matrix|defective matrix]] <math>\left[ \begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix} \right]</math> (which is a [[Shear matrix|shear matrix]]) cannot be diagonalized.

The {{mvar|n}} eigenvectors {{mvar|q<sub>i</sub>}} are usually normalized, but they need not be.  A non-normalized set of {{mvar|n}} eigenvectors, {{mvar|v<sub>i</sub>}} can also be used as the columns of {{math|'''Q'''}}.  That can be understood by noting that the magnitude of the eigenvectors in {{math|'''Q'''}} gets canceled in the decomposition by the presence of {{math|'''Q'''<sup>−1</sup>}}. If one of the eigenvalues {{math|1=''λ<sub>i</sub>''}} has multiple linearly independent eigenvectors (that is, the geometric multiplicity of {{math|1=''λ<sub>i</sub>''}} is greater than 1), then these eigenvectors for this eigenvalue {{math|1=''λ<sub>i</sub>''}} can be chosen to be mutually [[Orthogonality (mathematics)|orthogonal]]; however, if two eigenvectors belong to two different eigenvalues, it may be impossible for them to be orthogonal to each other (see Example below). One special case is that if {{math|'''A'''}} is a normal matrix, then by the spectral theorem, it's always possible to diagonalize {{math|'''A'''}} in an [[Orthonormal basis|orthonormal basis]] {{mvar|{q<sub>i</sub><nowiki>}</nowiki>}}.

The decomposition can be derived from the fundamental property of eigenvectors:
:<math>\begin{align}
\mathbf{A} \mathbf{v} &= \lambda \mathbf{v} \\
\mathbf{A} \mathbf{Q} &= \mathbf{Q} \mathbf{\Lambda} \\
\mathbf{A} &= \mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^{-1} .
\end{align}</math>
The linearly independent eigenvectors {{mvar|q<sub>i</sub>}} with nonzero eigenvalues form a basis (not necessarily orthonormal) for all possible products {{math|''A'''''x'''}}, for {{math|'''x''' ∈ '''C'''<sup>''n''</sup>}}, which is the same as the [[Image (mathematics)|image]] (or [[Range of a function|range]]) of the corresponding matrix transformation, and also the [[Column space|column space]] of the matrix {{math|'''A'''}}. The number of linearly independent eigenvectors {{mvar|q<sub>i</sub>}} with nonzero eigenvalues is equal to the [[Rank (linear algebra)|rank]] of the matrix {{math|'''A'''}}, and also the dimension of the image (or range) of the corresponding matrix transformation, as well as its column space.

The linearly independent eigenvectors {{mvar|q<sub>i</sub>}} 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 {{math|'''A'''}}.

=== Example ===
The 2 × 2 real matrix {{math|'''A'''}}
:<math>\mathbf{A} = \begin{bmatrix} 1 & 0 \\ 1 & 3 \\ \end{bmatrix}</math>
may be decomposed into a diagonal matrix through multiplication of a non-singular matrix {{math|'''B'''}}
:<math>\mathbf{B} = \begin{bmatrix}
    a & b \\
    c & d
  \end{bmatrix} \in \mathbb{R}^{2\times2}.
</math>

Then
: <math>\begin{bmatrix}
    a & b \\
    c & d 
  \end{bmatrix}^{-1}\begin{bmatrix}
    1 & 0 \\
    1 & 3
  \end{bmatrix}\begin{bmatrix}
    a & b \\
    c & d
  \end{bmatrix} =
  \begin{bmatrix}
    x & 0 \\
    0 & y
  \end{bmatrix},
</math>
for some real diagonal matrix <math>\left[ \begin{smallmatrix} x & 0 \\ 0 & y \end{smallmatrix} \right]</math>.

Multiplying both sides of the equation on the left by {{math|'''B'''}}:

: <math>\begin{bmatrix} 1 & 0 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} x & 0 \\ 0 & y \end{bmatrix}.</math>

The above equation can be decomposed into two simultaneous equations:

: <math> \begin{cases} \begin{bmatrix} 1 & 0\\ 1 & 3 \end{bmatrix} \begin{bmatrix} a \\ c \end{bmatrix} = \begin{bmatrix} ax \\ cx \end{bmatrix} \\ \begin{bmatrix} 1 & 0\\ 1 & 3 \end{bmatrix} \begin{bmatrix} b \\ d \end{bmatrix} = \begin{bmatrix} by \\ dy \end{bmatrix} \end{cases} .</math>

Factoring out the eigenvalues {{mvar|x}} and {{mvar|y}}:
: <math> \begin{cases} \begin{bmatrix} 1 & 0\\ 1 & 3 \end{bmatrix} \begin{bmatrix} a \\ c \end{bmatrix} = x\begin{bmatrix} a \\ c \end{bmatrix} \\ \begin{bmatrix} 1 & 0\\ 1 & 3 \end{bmatrix} \begin{bmatrix} b \\ d \end{bmatrix} = y\begin{bmatrix} b \\ d \end{bmatrix} \end{cases} </math>

Letting
:<math>\mathbf{a} = \begin{bmatrix} a \\ c \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} b \\ d \end{bmatrix},</math>
this gives us two vector equations:

: <math> \begin{cases}
\mathbf{A} \mathbf{a} = x \mathbf{a} \\
\mathbf{A} \mathbf{b} = y \mathbf{b}
\end{cases}</math>

And can be represented by a single vector equation involving two solutions as eigenvalues:
: <math>\mathbf{A} \mathbf{u} = \lambda \mathbf{u}</math>

where {{mvar|λ}} represents the two eigenvalues {{mvar|x}} and {{mvar|y}}, and {{math|'''u'''}} represents the vectors {{math|'''a'''}} and {{math|'''b'''}}.

Shifting {{math|''λ'''''u'''}} to the left hand side and factoring {{math|'''u'''}} out
: <math>(\mathbf{A} - \lambda \mathbf{I}) \mathbf{u} = \mathbf{0}</math>

Since {{math|'''B'''}} is non-singular, it is essential that {{math|'''u'''}} is nonzero. Therefore,
: <math>\det(\mathbf{A} - \lambda \mathbf{I}) = 0</math>

Thus
: <math>(1- \lambda)(3 - \lambda) = 0</math>

giving us the solutions of the eigenvalues for the matrix {{math|'''A'''}} as {{math|1=''λ'' = 1}} or {{math|1=''λ'' = 3}}, and the resulting diagonal matrix from the eigendecomposition of {{math|'''A'''}} is thus <math>\left[ \begin{smallmatrix} 1 & 0 \\ 0 & 3 \end{smallmatrix} \right]</math>.

Putting the solutions back into the above simultaneous equations
: <math> \begin{cases} \begin{bmatrix} 1 & 0 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} a \\ c \end{bmatrix} = 1\begin{bmatrix} a \\ c \end{bmatrix} \\ \begin{bmatrix} 1 & 0\\ 1 & 3 \end{bmatrix} \begin{bmatrix} b \\ d \end{bmatrix} = 3\begin{bmatrix} b \\ d \end{bmatrix} \end{cases} </math>

Solving the equations, we have
:<math>a = -2c \quad\text{and} \quad b = 0, \qquad c,d \in \mathbb{R}.</math>

Thus the matrix {{math|'''B'''}} required for the eigendecomposition of {{math|'''A'''}} is
:<math>\mathbf{B} = \begin{bmatrix} -2c & 0 \\ c & d \end{bmatrix},\qquad c, d\in \mathbb{R}, </math>
that is:
: <math>\begin{bmatrix}
-2c & 0 \\ c & d \end{bmatrix}^{-1} \begin{bmatrix} 1 & 0 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} -2c & 0 \\ c & d \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 3 \end{bmatrix},\qquad c, d\in \mathbb{R}</math>

=== Matrix inverse via eigendecomposition ===

If a matrix {{math|'''A'''}} can be eigendecomposed and if none of its eigenvalues are zero, then {{math|'''A'''}} is [[Invertible matrix|invertible]] and its inverse is given by
:<math>\mathbf{A}^{-1} = \mathbf{Q}\mathbf{\Lambda}^{-1}\mathbf{Q}^{-1}</math>

If <math>\mathbf{A}</math> is a symmetric matrix, since <math>\mathbf{Q}</math> is formed from the eigenvectors of <math>\mathbf{A}</math>, <math>\mathbf{Q}</math> is guaranteed to be an [[Orthogonal matrix|orthogonal matrix]], therefore <math>\mathbf{Q}^{-1} = \mathbf{Q}^\mathrm{T}</math>. Furthermore, because {{math|'''Λ'''}} is a [[Diagonal matrix|diagonal matrix]], its inverse is easy to calculate:
:<math>\left[\Lambda^{-1}\right]_{ii} = \frac{1}{\lambda_i}</math>

==== Practical implications ====
When eigendecomposition is used on a matrix of measured, real [[Data|data]], the [[Inverse function|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.<ref name=inverse>{{cite journal|last1=Hayde|first1= A. F. |last2=Twede|first2=D. R. |title=Observations on relationship between eigenvalues, instrument noise and detection performance|bibcode=2002SPIE.4816..355H|volume=4816|year=2002|pages=355|journal=Imaging Spectrometry VIII|doi=10.1117/12.453777|series=Proceedings of SPIE|s2cid= 120953647 |editor1-last=Shen|editor1-first=Sylvia S.}}</ref>

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 [[Laplace operator|Laplacian]] of the sorted eigenvalues:<ref name=inverse2>{{cite journal| last1=Twede|first1= D. R. |last2=Hayden|first2= A. F. |title=Refinement and generalization of the extension method of covariance matrix inversion by regularization|bibcode=2004SPIE.5159..299T| volume=5159| year=2004| pages=299| journal=Imaging Spectrometry IX| doi=10.1117/12.506993| series=Proceedings of SPIE|s2cid= 123123072 | editor1-last=Shen| editor1-first=Sylvia S| editor2-last=Lewis| editor2-first=Paul E}}</ref>

:<math>\min\left|\nabla^2 \lambda_\mathrm{s}\right|</math>

where the eigenvalues are subscripted with an {{math|s}} 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|power series]] of matrices. If {{math|''f''&thinsp;(''x'')}} is given by
:<math>f(x) = a_0 + a_1 x + a_2 x^2 + \cdots</math>

then we know that
:<math>f\!\left(\mathbf{A}\right) = \mathbf{Q}\,f\!\left(\mathbf{\Lambda}\right)\mathbf{Q}^{-1}</math>

Because {{math|'''Λ'''}} is a [[Diagonal matrix|diagonal matrix]], functions of {{math|'''Λ'''}} are very easy to calculate:
:<math>\left[f\left(\mathbf{\Lambda}\right)\right]_{ii} = f\left(\lambda_i\right)</math>

The off-diagonal elements of {{math|''f''&thinsp;('''Λ''')}} are zero; that is, {{math|''f''&thinsp;('''Λ''')}} is also a diagonal matrix. Therefore, calculating {{math|''f''&thinsp;('''A''')}} reduces to just calculating the function on each of the eigenvalues.

A similar technique works more generally with the [[Holomorphic functional calculus|holomorphic functional calculus]], using
:<math>\mathbf{A}^{-1} = \mathbf{Q}\mathbf{\Lambda}^{-1}\mathbf{Q}^{-1}</math>

from above. Once again, we find that
:<math>\left[f\left(\mathbf{\Lambda}\right)\right]_{ii} = f\left(\lambda_i\right)</math>

=== Examples ===
:<math>\begin{align}
  \mathbf{A}^2 &= \left(\mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^{-1}\right)\left(\mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^{-1}\right)
                = \mathbf{Q}\mathbf{\Lambda}\left(\mathbf{Q}^{-1}\mathbf{Q}\right)\mathbf{\Lambda}\mathbf{Q}^{-1}
                = \mathbf{Q}\mathbf{\Lambda}^2\mathbf{Q}^{-1} \\
  \mathbf{A}^n &= \mathbf{Q}\mathbf{\Lambda}^n\mathbf{Q}^{-1}
  \\
  \exp \mathbf{A}
  &= \mathbf{Q} \exp(\mathbf{\Lambda}) \mathbf{Q}^{-1}
\end{align}</math>
which are examples for the functions <math> f(x)=x^2, \; f(x)=x^n, \; f(x)=\exp{x} </math>. Furthermore, <math> \exp{\mathbf{A}} </math> is the [[Matrix exponential|matrix exponential]].

== Decomposition for special matrices ==
{{Main|Spectral theorem}}

[[Image:Taxonomy of Complex Matrices.svg|thumb|428x428px|right|Subsets of important classes of matrices]]


When {{math|'''A'''}} is normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem.

=== Normal matrices ===
A complex-valued square matrix  {{math|'''A'''}} is normal (meaning {{math|1='''A'''<sup>*</sup>'''A''' = '''AA'''<sup>*</sup>}}, where {{math|'''A'''<sup>*</sup>}} is the [[Conjugate transpose|conjugate transpose]]) if and only if it can be decomposed as

:<math>\mathbf{A} = \mathbf{U}\mathbf{\Lambda}\mathbf{U}^*</math>

where {{math|'''U'''}} is a [[Unitary matrix|unitary matrix]] (meaning {{math|'''U'''<sup>*</sup> {{=}} '''U'''<sup>−1</sup>}}) and {{math|'''Λ''' {{=}} diag(''λ''<sub>1</sub>, ..., ''λ''<sub>''n''</sub>)}} is a [[Diagonal matrix|diagonal matrix]].<ref>{{harvtxt|Horn|Johnson|1985}}, p. 133, Theorem 2.5.3</ref> The columns '''u'''<sub>1</sub>, ..., '''u'''<sub>''n''</sub> of {{math|'''U'''}} form an [[Orthonormal basis|orthonormal basis]] and are eigenvectors of {{math|'''A'''}} with corresponding eigenvalues ''λ''<sub>1</sub>, ..., ''λ''<sub>''n''</sub>.

If {{math|'''A'''}} is restricted to be a [[Hermitian matrix]] ({{math|1='''A''' = '''A'''*}}), then {{math|'''Λ'''}} has only real valued entries. If {{math|'''A'''}} is restricted to a unitary matrix, then {{math|'''Λ'''}} takes all its values on the complex unit circle, that is, {{math|1={{abs|''λ<sub>i</sub>''}} = 1}}.

=== Real symmetric matrices ===
As a special case, for every {{math|''n'' × ''n''}} real symmetric matrix, the eigenvalues are real and the eigenvectors can be chosen real and orthonormal. Thus a real symmetric matrix {{math|'''A'''}} can be decomposed as
:<math>\mathbf{A} = \mathbf{Q}\mathbf{\Lambda}\mathbf{Q}^\mathsf{T}</math>

where {{math|'''Q'''}} is an [[Orthogonal matrix|orthogonal matrix]] whose columns are the real, orthonormal eigenvectors of {{math|'''A'''}}, and {{math|'''Λ'''}} is a diagonal matrix whose entries are the eigenvalues of {{math|'''A'''}}.<ref>{{harvtxt|Horn|Johnson|1985}}, p. 136, Corollary 2.5.11</ref>

== Useful facts ==

=== Useful facts regarding eigenvalues ===
*The product of the eigenvalues is equal to the [[Determinant|determinant]] of {{math|'''A'''}} <math display="block">\det\left(\mathbf{A}\right) = \prod_{i=1}^{N_\lambda}{\lambda_i^{n_i} }</math> Note that each eigenvalue is raised to the power {{math|''n<sub>i</sub>''}}, the algebraic multiplicity.
*The sum of the eigenvalues is equal to the [[Trace (linear algebra)|trace]] of {{math|'''A'''}} <math display="block"> \operatorname{tr}\left(\mathbf{A}\right) = \sum_{i=1}^{N_\lambda}{ {n_i}\lambda_i}</math> Note that each eigenvalue is multiplied by {{math|''n<sub>i</sub>''}}, the algebraic multiplicity.
*If the eigenvalues of {{math|'''A'''}} are {{math|''λ''<sub>''i''</sub>}}, and {{math|'''A'''}} is invertible, then the eigenvalues of {{math|'''A'''<sup>−1</sup>}} are simply {{math|''λ''{{su|b=''i''|p=−1}}}}.
*If the eigenvalues of {{math|'''A'''}} are {{math|''λ''<sub>''i''</sub>}}, then the eigenvalues of {{math|''f''&thinsp;('''A''')}} are simply {{math|''f''&thinsp;(''λ''<sub>''i''</sub>)}}, for any [[Holomorphic function|holomorphic function]] {{mvar|f}}.

=== Useful facts regarding eigenvectors ===
* If {{math|'''A'''}} is [[Hermitian matrix|Hermitian]] and full-rank, the basis of eigenvectors may be chosen to be mutually orthogonal. The eigenvalues are real.
* The eigenvectors of {{math|'''A'''<sup>−1</sup>}} are the same as the eigenvectors of {{math|'''A'''}}.
* Eigenvectors are only defined up to a multiplicative constant. That is, if {{math|1='''Av''' = ''λ'''''v'''}} then {{math|''c'''''v'''}} is also an eigenvector for any scalar {{math|''c'' ≠ 0}}.  In particular, {{math|−'''v'''}} and {{math|1=''e''<sup>''iθ''</sup>'''v'''}} (for any ''θ'') are also eigenvectors.
* In the case of degenerate eigenvalues (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 an eigenvalue (in the degenerate subspace) is itself an eigenvector (in the subspace).

=== Useful facts regarding eigendecomposition ===
* {{math|'''A'''}} can be eigendecomposed if and only if the number of linearly independent eigenvectors, {{math|''N''<sub>'''v'''</sub>}}, equals the dimension of an eigenvector: {{math|1=''N''<sub>'''v'''</sub> = ''N''}}
* If the field of scalars is algebraically closed and if {{math|''p''(''λ'')}} has no repeated roots, that is, if <math>N_\lambda = N,</math> then {{math|'''A'''}} can be eigendecomposed.
* The statement "{{math|'''A'''}} can be eigendecomposed" does ''not'' imply that {{math|'''A'''}} has an inverse as some eigenvalues may be zero, which is not invertible.
* The statement "{{math|'''A'''}} has an inverse" does ''not'' imply that {{math|'''A'''}} can be eigendecomposed. A counterexample is <math>\left[ \begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix} \right]</math>, which is an invertible [[Defective matrix|defective matrix]].

=== Useful facts regarding matrix inverse ===
* {{math|'''A'''}} can be inverted [[If and only if|if and only if]] all eigenvalues are nonzero: <math display="block">\lambda_i \ne 0 \quad \forall \,i</math>
* If {{math|''λ<sub>i</sub>'' ≠ 0}} ''and'' {{math|1=''N''<sub>'''v'''</sub> = ''N''}}, the inverse is given by <math display="block">\mathbf{A}^{-1} = \mathbf{Q}\mathbf{\Lambda}^{-1}\mathbf{Q}^{-1}</math>

== Numerical computations ==
{{Details|eigenvalue algorithm}}

=== 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|characteristic polynomial]]. However, this is often impossible for larger matrices, in which case we must use a [[Numerical analysis|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 {{mvar|n}}th roots. Therefore, general algorithms to find eigenvectors and eigenvalues are [[Iterative method|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 error|round-off error]]s 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.<ref name=Trefethen>{{Cite book|author1-first=Lloyd N.|author1-last=Trefethen|author2-first=David|author2-last=Bau|title=Numerical Linear Algebra|isbn=978-0-89871-361-9|publisher=SIAM|year= 1997}}</ref>

A simple and accurate iterative method is the power method: a random vector {{math|'''v'''}} is chosen and a sequence of [[Unit vector|unit vector]]s is computed as
: <math>\frac{\mathbf{A}\mathbf{v}}{\left\|\mathbf{A}\mathbf{v}\right\|}, \frac{\mathbf{A}^2\mathbf{v}}{\left\|\mathbf{A}^2\mathbf{v}\right\|}, \frac{\mathbf{A}^3\mathbf{v}}{\left\|\mathbf{A}^3\mathbf{v}\right\|}, \ldots</math>

This [[Sequence|sequence]] will almost always converge to an eigenvector corresponding to the eigenvalue of greatest magnitude, provided that {{math|'''v'''}} 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, [[Company:Google|Google]] uses it to calculate the [[PageRank|page rank]] of documents in their search engine.<ref>Ipsen, Ilse, and Rebecca M. Wills, ''[https://www4.ncsu.edu/~ipsen/ps/slides_imacs.pdf Analysis and Computation of Google's PageRank]'', 7th IMACS International Symposium on Iterative Methods in Scientific Computing, Fields Institute, Toronto, Canada, 5–8 May 2005.</ref>  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 [[Linear span|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]].<ref name=Trefethen />  Alternatively, the important [[QR algorithm]] is also based on a subtle transformation of a power method.<ref name=Trefethen />

=== Numerical computation of eigenvectors ===
Once the eigenvalues are computed, the eigenvectors could be calculated by solving the equation
:<math>\left(\mathbf{A} - \lambda_i \mathbf{I}\right)\mathbf{v}_{i,j} = \mathbf{0} </math>

using [[Gaussian elimination]] or [[System of linear equations#Solving a linear system|any other method]] for solving [[System of linear equations|matrix equation]]s.

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|power iteration]], for example, the eigenvector is actually computed before the eigenvalue (which is typically computed by the [[Rayleigh quotient]] of the eigenvector).<ref name=Trefethen />  In the QR algorithm for a [[Hermitian matrix]] (or any normal matrix), the orthonormal eigenvectors are obtained as a product of the {{math|'''Q'''}} matrices from the steps in the algorithm.<ref name=Trefethen />  (For more general matrices, the QR algorithm yields the [[Schur decomposition]] first, from which the eigenvectors can be obtained by a backsubstitution procedure.<ref>{{Cite book|url=https://books.google.com/books?id=YVpyyi1M7vUC |publisher=Springer|chapter= section 5.8.2|title=Numerical Mathematics|pages=15 |first1=Alfio |last1=Quarteroni |first2=Riccardo |last2=Sacco |first3=Fausto |last3=Saleri |isbn=978-0-387-98959-4|year=2000}}</ref>)  For Hermitian matrices, the [[Divide-and-conquer eigenvalue algorithm]] is more efficient than the QR algorithm if both eigenvectors and eigenvalues are desired.<ref name=Trefethen />

== Additional topics ==

=== Generalized eigenspaces ===
Recall that the ''geometric'' multiplicity of an eigenvalue can be described as the dimension of the associated eigenspace, the [[Kernel (linear algebra)|nullspace]] of {{math|''λ'''''I''' − '''A'''}}. 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 {{math|(''λ'''''I''' − '''A''')<sup>''k''</sup>}} for ''any sufficiently large {{mvar|k}}''. That is, it is the space of ''[[Generalized eigenvector|generalized eigenvector]]s'' (first sense), where a generalized eigenvector is any vector which ''eventually'' becomes 0 if {{math|''λ'''''I''' − '''A'''}} 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
: <math>\mathbf{A}\mathbf{v} = \lambda \mathbf{v}^*.</math>

For example, in coherent electromagnetic scattering theory, the linear transformation {{math|'''A'''}} represents the action performed by the scattering object, and the eigenvectors represent polarization states of the electromagnetic wave. In [[Physics:Optics|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 [[Engineering:Radar|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 {{math|'''v'''}} that obeys
: <math> \mathbf{A}\mathbf{v} = \lambda \mathbf{B} \mathbf{v}</math>

where {{math|'''A'''}} and {{math|'''B'''}} are matrices. If {{math|'''v'''}} obeys this equation, with some {{mvar|λ}}, then we call {{math|'''v'''}} the ''generalized eigenvector'' of {{math|'''A'''}} and {{math|'''B'''}} (in the second sense), and {{mvar|λ}} is called the ''generalized eigenvalue'' of {{math|'''A'''}} and {{math|'''B'''}} (in the second sense) which corresponds to the generalized eigenvector {{math|'''v'''}}. The possible values of {{mvar|λ}} must obey the following equation
:<math>\det(\mathbf{A} - \lambda \mathbf{B})=0. </math>

If {{math|''n''}} linearly independent vectors {{math|{'''v'''<sub>1</sub>, …, '''v'''<sub>''n''</sub>}<nowiki/>}} can be found, such that for every {{math|''i'' ∈ {1, …, ''n''}<nowiki/>}}, {{math|1='''Av'''<sub>''i''</sub> = ''λ<sub>i</sub>'''''Bv'''<sub>''i''</sub>}}, then we define the matrices {{math|'''P'''}} and {{math|'''D'''}} such that
:<math>P = \begin{bmatrix}
    | & & | \\
    \mathbf{v}_1 & \cdots & \mathbf{v}_n \\
    | &  & | 
  \end{bmatrix} \equiv
  \begin{bmatrix}
    (\mathbf{v}_1)_1 & \cdots & (\mathbf{v}_n)_1 \\
    \vdots &  & \vdots   \\
    (\mathbf{v}_1)_n & \cdots & (\mathbf{v}_n)_n 
  \end{bmatrix}
</math>
:<math>(D)_{ij} = \begin{cases}
  \lambda_i,  & \text{if }i = j\\
  0,          & \text{otherwise}
\end{cases}</math>

Then the following equality holds
:<math>\mathbf{A} = \mathbf{B}\mathbf{P}\mathbf{D}\mathbf{P}^{-1}</math>

And the proof is
:<math>
  \mathbf{A}\mathbf{P}= \mathbf{A} \begin{bmatrix}
    | & & | \\
    \mathbf{v}_1 & \cdots & \mathbf{v}_n   \\
    | &  & | 
  \end{bmatrix} = \begin{bmatrix}
    | & & | \\
    A\mathbf{v}_1 & \cdots & A\mathbf{v}_n   \\
    | &  & | 
  \end{bmatrix} = \begin{bmatrix}
    | & & | \\
    \lambda_1B\mathbf{v}_1 & \cdots & \lambda_nB\mathbf{v}_n   \\
    | &  & | 
  \end{bmatrix} = \begin{bmatrix}
    | & & | \\
    B\mathbf{v}_1 & \cdots & B\mathbf{v}_n   \\
    | &  & | 
  \end{bmatrix}
  \mathbf{D} =
  \mathbf{B}\mathbf{P}\mathbf{D}
</math>

And since {{math|'''P'''}} is invertible, we multiply the equation from the right by its inverse, finishing the proof.

The set of matrices of the form {{math|'''A''' − ''λ'''''B'''}}, where {{mvar|λ}} is a complex number, is called a ''pencil''; the term ''[[Matrix pencil|matrix pencil]]'' can also refer to the pair {{math|('''A''', '''B''')}} of matrices.<ref name=Bai-GHEP>{{cite book|editor1-first=Z. |editor1-last=Bai |editor2-link=James Demmel|editor2-first=J. |editor2-last=Demmel |editor3-first=J. |editor3-last=Dongarra |editor4-first=A. |editor4-last=Ruhe |editor5-first=H. |editor5-last=Van Der Vorst |title=Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide|publisher=SIAM|location=Philadelphia|year= 2000|url=https://cs.utk.edu/~dongarra/etemplates/node156.html| chapter=Generalized Hermitian Eigenvalue Problems|isbn= 978-0-89871-471-5}}</ref>

If {{math|'''B'''}} is invertible, then the original problem can be written in the form
: <math>\mathbf{B}^{-1}\mathbf{A}\mathbf{v} = \lambda \mathbf{v}</math>

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 {{math|'''A'''}} and {{math|'''B'''}} are Hermitian matrices, since in this case {{math|'''B'''<sup>−1</sup>'''A'''}} is not generally Hermitian and important properties of the solution are no longer apparent.

If {{math|'''A'''}} and {{math|'''B'''}} are both symmetric or Hermitian, and {{math|'''B'''}} is also a [[Positive-definite matrix|positive-definite matrix]], the eigenvalues {{math|''λ<sub>i</sub>''}} are real and eigenvectors {{math|'''v'''<sub>1</sub>}} and {{math|'''v'''<sub>2</sub>}} with distinct eigenvalues are {{math|'''B'''}}-orthogonal ({{math|1='''v'''<sub>1</sub><sup>*</sup>'''Bv'''<sub>2</sub> = 0}}).<ref>{{cite book|last=Parlett|first=Beresford N.|title=The symmetric eigenvalue problem|date=1998|publisher=Society for Industrial and Applied Mathematics|location=Philadelphia|isbn=978-0-89871-402-9|page=345|url=https://epubs.siam.org/doi/book/10.1137/1.9781611971163|edition=Reprint.|doi=10.1137/1.9781611971163}}</ref> In this case, eigenvectors can be chosen so that the matrix {{math|'''P'''}} defined above satisfies

:<math>\mathbf{P}^* \mathbf B \mathbf{P} = \mathbf{I}</math>  or  <math>\mathbf{P}\mathbf{P}^*\mathbf B  = \mathbf{I}</math>,

and there exists a [[Basis (linear algebra)|basis]] of generalized eigenvectors (it is not a [[Defective matrix|defective]] problem).<ref name="Bai-GHEP" />  This case is sometimes called a ''Hermitian definite pencil'' or ''definite pencil''.<ref name="Bai-GHEP" />

== See also ==
* [[Eigenvalue perturbation]]
* [[Frobenius covariant]]
* [[Householder transformation]]
* [[Jordan normal form]]
* [[List of matrices]]
* [[Matrix decomposition]]
* [[Singular value decomposition]]
* [[Sylvester's formula]]

== Notes ==
{{Reflist}}

== References ==
* {{cite book|last= Franklin|first= Joel N.|year= 1968|title= Matrix Theory|publisher= Dover Publications|isbn= 978-0-486-41179-8|url-access= registration|url= https://archive.org/details/matrixtheory0000fran}}
* {{ citation | first1 = Gene H. | last1 = Golub | first2 = Charles F. | last2 = Van Loan | year = 1996 | isbn = 978-0-8018-5414-9 | title = Matrix Computations | edition = 3rd | publisher = Johns Hopkins University Press | location = Baltimore }}
* {{cite book|last1=Horn|first1= Roger A. |last2= Johnson|first2=Charles R.|year=1985|title=Matrix Analysis|publisher=Cambridge University Press|isbn= 978-0-521-38632-6}}
* {{cite book|last1=Horn|first1= Roger A. |last2= Johnson|first2=Charles R.|year=1991|title=Topics in Matrix Analysis|url=https://archive.org/details/topicsinmatrixan0000horn|url-access=registration|publisher= Cambridge University Press| isbn =978-0-521-46713-1}}
* {{citation | first1 = Erwin | last1 = Kreyszig | year = 1972 | isbn = 978-0-471-50728-4 | title = Advanced Engineering Mathematics | edition = 3rd | publisher = {{wipe|John Wiley & Sons}} | location = New York | url-access = registration | url = https://archive.org/details/advancedengineer00krey }}
* {{ citation | first1 = Evar D. | last1 = Nering | year = 1970 | title = Linear Algebra and Matrix Theory | edition = 2nd | publisher = {{wipe|John Wiley & Sons}} | location = New York | lccn = 76091646 }}
* {{cite book|last=Strang |first=G. |year=1998|title=Introduction to Linear Algebra|edition=3rd |publisher= Wellesley-Cambridge Press|isbn =978-0-9614088-5-5}}

== External links ==
* [https://people.revoledu.com/kardi/tutorial/LinearAlgebra/SpectralDecomposition.html Interactive program & tutorial of Spectral Decomposition].

[[Category:Matrix theory]]
[[Category:Matrix decompositions]]

{{Sourceattribution|Eigendecomposition of a matrix}}