GeezerVison

The ⁠$2\times 2$⁠ real matrix

$𝐀=\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]$

may be diagonalized as ⁠${𝐐}^{-1}𝐀𝐐$⁠, where ⁠$𝐐$⁠ is a non-singular matrix to be determined:

$𝐐=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\in {ℝ}^{2\times 2}.$

Then ${\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]}^{-1}\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]=\left[\begin{array}{cc}x& 0\\ 0& y\end{array}\right],$

for some real numbers $x$ and ⁠$y$⁠.

Multiplying both sides of the equation on the left by ⁠$𝐐$⁠,

$\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{cc}x& 0\\ 0& y\end{array}\right].$

The above equation can be decomposed into two simultaneous equations:

$\{\begin{array}{c}\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{c}a\\ c\end{array}\right]=\left[\begin{array}{c}ax\\ cx\end{array}\right]\\ \left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{c}b\\ d\end{array}\right]=\left[\begin{array}{c}by\\ dy\end{array}\right].\end{array}$

Factoring out the eigenvalues ⁠$x$⁠ and ⁠$y$⁠,

$\{\begin{array}{c}\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{c}a\\ c\end{array}\right]=x\left[\begin{array}{c}a\\ c\end{array}\right]\\ \left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{c}b\\ d\end{array}\right]=y\left[\begin{array}{c}b\\ d\end{array}\right].\end{array}$

Letting

$𝐚=\left[\begin{array}{c}a\\ c\end{array}\right]\text{and}𝐛=\left[\begin{array}{c}b\\ d\end{array}\right]$

gives us a system of two vector equations:

$\{\begin{array}{c}𝐀𝐚=x𝐚\\ 𝐀𝐛=y𝐛.\end{array}$

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

$𝐀𝐮=\lambda 𝐮,$

where ⁠$\lambda$⁠ represents any of the eigenvalues, ⁠$x$⁠ or ⁠$y$⁠, and ⁠$𝐮$⁠ represents the corresponding eigenvector, ⁠$𝐚$⁠ or ⁠$𝐛$⁠.

Shifting ⁠$\lambda 𝐮$⁠ to the left-hand side and factoring ⁠$𝐮$⁠ out,

$(𝐀-\lambda 𝐈)𝐮=\mathrm{𝟎}.$

Since ⁠$𝐐$⁠ is non-singular, it is essential that ⁠$𝐮$⁠ is nonzero. Therefore,

$det(𝐀-\lambda 𝐈)=0.$

Thus

$(1-\lambda )(3-\lambda )=0,$

giving us the solutions of the eigenvalues for the matrix ⁠$𝐀$⁠ as ⁠$\lambda =1$⁠ or ⁠$\lambda =3$⁠. The resulting diagonal matrix from the eigendecomposition of ⁠$𝐀$⁠ is thus ⁠$\left[\begin{array}{cc}1& 0\\ 0& 3\end{array}\right]$⁠.

Putting the solutions back into the above simultaneous equations,

$\{\begin{array}{c}\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{c}a\\ c\end{array}\right]=1\left[\begin{array}{c}a\\ c\end{array}\right]\\ \left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{c}b\\ d\end{array}\right]=3\left[\begin{array}{c}b\\ d\end{array}\right].\end{array}$

Solving the equations, we have

$a=-2c\text{and}b=0,c,d\in ℝ\setminus \left\{0\right\}.$

Thus the matrix ⁠$𝐐$⁠ required for the eigendecomposition of ⁠$𝐀$⁠ is

$𝐐=\left[\begin{array}{cc}-2c& 0\\ c& d\end{array}\right],\text{where}c,d\in ℝ\setminus \left\{0\right\}.$

Finally, the diagonalization of ⁠$𝐀$⁠ is:

${\left[\begin{array}{cc}-2c& 0\\ c& d\end{array}\right]}^{-1}\left[\begin{array}{cc}1& 0\\ 1& 3\end{array}\right]\left[\begin{array}{cc}-2c& 0\\ c& d\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 3\end{array}\right],\text{where}c,d\in ℝ\setminus \left\{0\right\}.$

In this example, ⁠${𝐮}_1$⁠ and ⁠${𝐮}_2$⁠, eigenvectors associated with distinct eigenvalues, cannot be orthogonal to each other. Indeed:

$\begin{array}{cc}⟨{𝐮}_1,{𝐮}_2⟩=0& ⟺-2c\times 0+cd=0\\ & ⟺c=0\text{or}d=0\\ & ⟺{𝐮}_1=0\text{or}{𝐮}_2=0,\end{array}$

which would make ⁠$𝐐$⁠ singular.

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

${𝐀}^{-1}=𝐐{𝜦}^{-1}{𝐐}^{-1}.$

If $𝐀$ is a symmetric matrix, since $𝐐$ is formed from the eigenvectors of ⁠$𝐀$⁠, then $𝐐$ is guaranteed to be an orthogonal matrix; therefore ⁠${𝐐}^{-1}={𝐐}^{𝖳}$⁠. Furthermore, because ⁠$𝜦$⁠ is a diagonal matrix, its inverse is easy to calculate:

${\left[{𝜦}^{-1}\right]}_{ii}=\frac{1}{{\lambda }_i}.$

$\begin{array}{cc}{𝐀}^2& =\left(𝐐𝜦{𝐐}^{-1}\right)\left(𝐐𝜦{𝐐}^{-1}\right)=𝐐𝜦\left({𝐐}^{-1}𝐐\right)𝜦{𝐐}^{-1}=𝐐{𝜦}^2{𝐐}^{-1}\\ {𝐀}^n& =𝐐{𝜦}^n{𝐐}^{-1}\\ \exp 𝐀& =𝐐\exp \left(𝜦\right){𝐐}^{-1}\end{array}$ which are examples for the functions $f\left(x\right)=x^2,f\left(x\right)=x^n,f\left(x\right)=\exp x$. Furthermore, $\exp 𝐀$ is the matrix exponential.

A complex-valued square matrix $A$ is normal (meaning ⁠${𝐀}^{\ast }𝐀=𝐀{𝐀}^{\ast }$⁠, where ${𝐀}^{\ast }$ is the conjugate transpose of ⁠$𝐀$⁠) if and only if it can be decomposed as ⁠$𝐀=𝐔𝜦{𝐔}^{\ast }$⁠, where $𝐔$ is a unitary matrix (meaning ⁠${𝐔}^{\ast }={𝐔}^{-1}$⁠) and $𝜦=diag({\lambda }_1,\dots ,{\lambda }_n)$ is a diagonal matrix.^[8] The columns ${𝐮}_1,\dots ,{𝐮}_n$ of $𝐔$ form an orthonormal basis and are eigenvectors of $𝐀$ with corresponding eigenvalues ⁠${\lambda }_1,\dots ,{\lambda }_n$⁠.^[9]

For example, consider the ⁠$2\times 2$⁠ normal matrix ⁠$𝐀=\left[\begin{array}{cc}1& 2\\ 2& 1\end{array}\right]$⁠.

The eigenvalues are ⁠${\lambda }_1=3$⁠ and ⁠${\lambda }_2=-1$⁠.

Possible normalized eigenvectors corresponding to these eigenvalues are ⁠${𝐮}_1=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]$⁠ and ⁠${𝐮}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{c}-1\\ 1\end{array}\right]$⁠.

The factorization is ⁠$𝐀=𝐔𝜦{𝐔}^{\ast }$⁠, where

⁠$𝐔=\left[\begin{array}{cc}1/\sqrt{2}& -1/\sqrt{2}\\ 1/\sqrt{2}& 1/\sqrt{2}\end{array}\right]$⁠, ⁠$𝜦=\left[\begin{array}{cc}3& 0\\ 0& -1\end{array}\right]$⁠, and ⁠${𝐔}^{\ast }={𝐔}^{-1}=\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ -1/\sqrt{2}& 1/\sqrt{2}\end{array}\right]$⁠.

The verification is $𝐔𝜦{𝐔}^{\ast }=$ $\left[\begin{array}{cc}1/\sqrt{2}& -1/\sqrt{2}\\ 1/\sqrt{2}& 1/\sqrt{2}\end{array}\right]\left[\begin{array}{cc}3& 0\\ 0& -1\end{array}\right]\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ -1/\sqrt{2}& 1/\sqrt{2}\end{array}\right]$ ⁠$=\left[\begin{array}{cc}1& 2\\ 2& 1\end{array}\right]=𝐀$⁠.

This example illustrates the process of diagonalizing a normal matrix $𝐀$ by finding its eigenvalues and eigenvectors, forming the unitary matrix ⁠$𝐔$⁠, the diagonal matrix ⁠$𝜦$⁠, and verifying the decomposition.

As a special case, for every ⁠$n\times n$⁠ 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 ⁠$𝐀$⁠.^[10]

Diagonalizable matrices can be decomposed using eigendecomposition, provided they have a full set of linearly independent eigenvectors. They can be expressed as ⁠$𝐀=𝐏𝐃{𝐏}^{-1}$⁠, where $𝐏$ is a matrix whose columns are eigenvectors of ⁠$𝐀$⁠, and $𝐃$ is a diagonal matrix consisting of the corresponding eigenvalues of ⁠$𝐀$⁠.^[9]

Positive definite matrices are matrices for which all eigenvalues are positive. They can be decomposed as $𝐀=𝐋{𝐋}^{𝖳}$ using the Cholesky decomposition, where $𝐋$ is a lower triangular matrix.^[11]

Orthogonal matrices satisfy $𝐐{𝐐}^{𝖳}=𝐈$ (real case) and unitary matrices satisfy $𝐔{𝐔}^{†}=𝐈$ (complex case), where ${𝐐}^{𝖳}$ denotes the transpose of $𝐐$ and ${𝐔}^{†}$ denotes the conjugate transpose of ⁠$𝐔$⁠. They diagonalize using unitary transformations.^[9]

Hermitian matrices satisfy ⁠$𝐇={𝐇}^{†}$⁠, where ${𝐇}^{†}$ denotes the conjugate transpose of ⁠$𝐇$⁠. They can be diagonalized using unitary or orthogonal matrices.^[9]

• The product of the eigenvalues is equal to the determinant of A: $det\left(𝐀\right)=\prod _{i=1}^{N_{\lambda }}{\lambda }_i^{n_i}.$ Note that each eigenvalue is raised to the power n_i, its algebraic multiplicity.
• The sum of the eigenvalues is equal to the trace of A: $\mathrm{tr}\left(𝐀\right)=\sum _{i=1}^{N_{\lambda }}{n}_i{\lambda }_i.$ Note that each eigenvalue is multiplied by n_i, its algebraic multiplicity.
• If the eigenvalues of A are λ_i, and A is invertible, then the eigenvalues of A⁻¹ are simply λ⁻¹
  _i.
• If the eigenvalues of A are λ_i, then the eigenvalues of f (A) are simply f (λ_i), for any holomorphic function f and any A for which f (A) is well-defined.

• If A 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 A⁻¹ are the same as the eigenvectors of A.
• Eigenvectors are only defined up to a multiplicative constant. That is, if Av = λv, then cv is also an eigenvector for any scalar c ≠ 0. In particular, −v and e^iθv (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).

• A can be eigendecomposed if and only if the number of linearly independent eigenvectors, N_v, equals the dimension of an eigenvector: N_v = N.
• If the field of scalars is algebraically closed and if p(λ) has no repeated roots, that is, if $N_{\lambda }=N,$ then A can be eigendecomposed.
• The statement "A can be eigendecomposed" does not imply that A has an inverse, as some eigenvalues may be zero, making A not invertible.
• The statement "A has an inverse" does not imply that A can be eigendecomposed. A counterexample is $\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$, which is an invertible defective matrix.

• A can be inverted if and only if all eigenvalues are nonzero: ${\lambda }_i\ne 0\forall i.$
• If λ_i ≠ 0 and N_v = N, the inverse is given by ${𝐀}^{-1}=𝐐{𝜦}^{-1}{𝐐}^{-1}.$

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 nth 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.^[12]

A simple and accurate iterative method is the power method: a random vector v is chosen and a sequence of unit vectors is computed as $\frac{𝐀𝐯}{\Vert 𝐀𝐯\Vert },\frac{{𝐀}^2𝐯}{\Vert {𝐀}^2𝐯\Vert },\frac{{𝐀}^3𝐯}{\Vert {𝐀}^3𝐯\Vert },\dots$

This sequence will almost always converge to an eigenvector corresponding to the eigenvalue of greatest magnitude, provided that 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, Google uses it to calculate the page rank of documents in their search engine.^[13] 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.^[12] Alternatively, the important QR algorithm is also based on a subtle transformation of a power method.^[12]

Once the eigenvalues are computed, the eigenvectors could be calculated by solving the equation $(𝐀-{\lambda }_i𝐈){𝐯}_{i,j}=\mathrm{𝟎}$ 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).^[12] In the QR algorithm for a Hermitian matrix (or any normal matrix), the orthonormal eigenvectors are obtained as a product of the Q matrices from the steps in the algorithm.^[12] (For more general matrices, the QR algorithm yields the Schur decomposition first, from which the eigenvectors can be obtained by a backsubstitution procedure.^[14]) For Hermitian matrices, the Divide-and-conquer eigenvalue algorithm is more efficient than the QR algorithm if both eigenvectors and eigenvalues are desired.^[12]

Recall that the geometric multiplicity of an eigenvalue can be described as the dimension of the associated eigenspace, the nullspace of ⁠$A-\lambda I$⁠. 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 ⁠$(A-\lambda I{)}^k$⁠ for any sufficiently large ⁠$k$⁠. That is, it is the space of generalized eigenvectors (in the first sense), where a generalized eigenvector is any vector which eventually becomes ⁠$0$⁠ if ⁠$A-\lambda I$⁠ 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.

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 $𝐀𝐯=\lambda {𝐯}^{\ast }.$ For example, in coherent electromagnetic scattering theory, the linear transformation A 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.

A generalized eigenvalue problem (second sense) is the problem of finding a (nonzero) vector v that obeys $𝐀𝐯=\lambda 𝐁𝐯$ where A and B are matrices. If v obeys this equation, with some λ, then we call v the generalized eigenvector of A and B (in the second sense), and λ is called the generalized eigenvalue of A and B (in the second sense) which corresponds to the generalized eigenvector v. The possible values of λ must obey the following equation $det(𝐀-\lambda 𝐁)=0.$

If n linearly independent vectors {v₁, …, v_n} can be found, such that for every i ∈ {1, …, n}, Av_i = λ_iBv_i, then we define the matrices P and D such that $P=\left[\begin{array}{ccc}|& & |\\ {𝐯}_1& \cdots & {𝐯}_n\\ |& & |\end{array}\right]\equiv \left[\begin{array}{ccc}({𝐯}_1{)}_1& \cdots & ({𝐯}_n{)}_1\\ ⋮& & ⋮\\ ({𝐯}_1{)}_n& \cdots & ({𝐯}_n{)}_n\end{array}\right]$ $(D{)}_{ij}=\{\begin{array}{cc}{\lambda }_i,& \text{if }i=j\\ 0,& \text{otherwise}\end{array}$ Then the following equality holds $𝐀=𝐁𝐏𝐃{𝐏}^{-1}$ And the proof is $𝐀𝐏=𝐀\left[\begin{array}{ccc}|& & |\\ {𝐯}_1& \cdots & {𝐯}_n\\ |& & |\end{array}\right]=\left[\begin{array}{ccc}|& & |\\ A{𝐯}_1& \cdots & A{𝐯}_n\\ |& & |\end{array}\right]=\left[\begin{array}{ccc}|& & |\\ {\lambda }_{1}B{𝐯}_1& \cdots & {\lambda }_{n}B{𝐯}_n\\ |& & |\end{array}\right]=\left[\begin{array}{ccc}|& & |\\ B{𝐯}_1& \cdots & B{𝐯}_n\\ |& & |\end{array}\right]𝐃=𝐁𝐏𝐃$

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

The set of matrices of the form A − λB, where λ is a complex number, is called a pencil; the term matrix pencil can also refer to the pair (A, B) of matrices.^[15]

If B is invertible, then the original problem can be written in the form ${𝐁}^{-1}𝐀𝐯=\lambda 𝐯$ 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 A and B are Hermitian matrices, since in this case B⁻¹A is not generally Hermitian and important properties of the solution are no longer apparent.

If A and B are both symmetric or Hermitian, and B is also a positive-definite matrix, the eigenvalues λ_i are real and eigenvectors v₁ and v₂ with distinct eigenvalues are B-orthogonal (v₁^*Bv₂ = 0).^[16] In this case, eigenvectors can be chosen so that the matrix P defined above satisfies ${𝐏}^{\ast }𝐁𝐏=𝐈$ or $𝐏{𝐏}^{\ast }𝐁=𝐈,$ and there exists a basis of generalized eigenvectors (it is not a defective problem).^[15] This case is sometimes called a Hermitian definite pencil or definite pencil.^[15]