Skip to main content

Unit 9.5.2 Summary

Definition 9.5.2.1. Eigenvalue, eigenvector, and eigenpair.

Let \(A \in \C^{m \times m} \text{.}\) Then \(\lambda \in \C \) and nonzero \(x \in \C^{m} \) are said to be an eigenvalue and corresponding eigenvector if \(A x = \lambda x \text{.}\) The tuple \(( \lambda, x ) \) is said to be an eigenpair.

For \(A \in \mathbb C^{m \times m} \text{,}\) the following are equivalent statements:

  • \(A \) is nonsingular.

  • \(A \) has linearly independent columns.

  • There does not exist \(x \neq 0 \) such that \(A x = 0 \text{.}\)

  • \(\Null( A ) = \{ 0 \} \text{.}\) (The null space of \(A \) is trivial.)

  • \(\dim(\Null( A )) = 0 \text{.}\)

  • \(\det( A ) \neq 0 \text{.}\)

For \(A \in \mathbb C^{m \times m} \text{,}\) the following are equivalent statements:

  • \(\lambda \) is an eigenvalue of \(A \)

  • \(( \lambda I - A ) \) is singular.

  • \(( \lambda I - A ) \) has linearly dependent columns.

  • There exists \(x \neq 0 \) such that \(( \lambda I - A ) x = 0 \text{.}\)

  • The null space of \(\lambda I - A \) is nontrivial.

  • \(\dim(\Null( \lambda I - A )) \gt 0 \text{.}\)

  • \(\det( \lambda I - A ) = 0 \text{.}\)

Definition 9.5.2.2. Spectrum of a matrix.
The set of all eigenvalues of \(A \) is denoted by \(\Lambda( A ) \) and is called the spectrum of \(A \text{.}\)
Definition 9.5.2.3. Spectral radius.

The spectral radius of \(A \text{,}\) \(\rho( A ) \text{,}\) equals the magnitude of the largest eigenvalue, in magnitude:

\begin{equation*} \rho( A ) = \max_{\lambda \in \Lambda( A )} \vert \lambda \vert. \end{equation*}

Some useful facts for \(A \in \C^{m \times m} \text{:}\)

  • \(0 \in \Lambda( A ) \) if and only \(A \) is singular.

  • The eigenvectors corresponding to distinct eigenvalues are linearly independent.

  • Let \(A \) be nonsingular. Then \(( \lambda, x ) \) is an eigenpair of \(A \) if and only if \(( 1/\lambda, x ) \) is an eigenpair of \(A^{-1} \text{.}\)

  • \(( \lambda, x ) \) is an eigenpair of \(A \) if and only if \(( \lambda - \rho, x ) \) is an eigenpair of \(A - \rho I \text{.}\)

Some useful facts for Hermitian \(A \in \C^{m \times m} \text{:}\)

  • All eigenvalues are real-valued.

  • \(A \) is HPD if and only if all its eigenvalues are positive.

  • If \(( \lambda, x ) \) and \(( \mu, y ) \) are both eigenpairs of Hermitian \(A \text{,}\) then \(x\) and \(y \) are orthogonal.

Definition 9.5.2.6.

The determinant of

\begin{equation*} A = \left( \begin{array}{c c} \alpha_{00} \amp \alpha_{01} \\ \alpha_{10} \amp \alpha_{11} \end{array} \right) \end{equation*}

is given by

\begin{equation*} \det( A ) = {\alpha_{00} \alpha_{11} - \alpha_{10} \alpha_{01}}. \end{equation*}

The characteristic polynomial of

\begin{equation*} A = \left( \begin{array}{c c} \alpha_{00} \amp \alpha_{01} \\ \alpha_{10} \amp \alpha_{11} \end{array} \right) \end{equation*}

is given by

\begin{equation*} \det( \lambda - I A ) = {( \lambda - \alpha_{00} ) ( \lambda - \alpha_{11} ) - \alpha_{10} \alpha_{01}}. \end{equation*}

This is a second degree polynomial in \(\lambda \) and has two roots (multiplicity counted). The eigenvalues of \(A \) equal the roots of this characteristic polynomial.

The characteristic polynomial of \(A \in \mathbb C^{m \times m} \) is given by

\begin{equation*} \det( \lambda - I A ). \end{equation*}

This is a polynomial in \(\lambda \) of degree \(m \) and has \(m \) roots (multiplicity counted). The eigenvalues of \(A \) equal the roots of this characteristic polynomial. Hence, \(A \) has \(m\) eigenvalues (multiplicity counted).

Definition 9.5.2.7. Algebraic multiplicity of an eigenvalue.

Let \(A \in \Cmxm \) and \(p_m( \lambda ) \) its characteristic polynomial. Then the (algebraic) multiplicity of eigenvalue \(\lambda_i \) equals the multiplicity of the corresponding root of the polynomial.

If

\begin{equation*} p_m( \chi ) = \alpha_0 + \alpha_1 \chi + \cdots + \alpha_{m-1} \chi^{m-1} + \chi^m \end{equation*}

and

\begin{equation*} A = \left( \begin{array}{ c c c c c c c c} - \alpha_{n-1} \amp - \alpha_{n-2} \amp - \alpha_{n-3} \amp \cdots \amp - \alpha_1 \amp - \alpha_{0} \\ 1 \amp 0 \amp 0 \amp \cdots \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp \cdots \amp 0 \amp 0 \\ 0 \amp 0 \amp 1 \amp \cdots \amp 0 \amp 0 \\ \vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\ 0 \amp 0 \amp 0 \amp \cdots \amp 1 \amp 0 \\ \end{array} \right) \end{equation*}

then

\begin{equation*} p_m( \lambda ) = \det( \lambda I - A ) . \end{equation*}

Let \(\lambda \) be an eigenvalue of \(A \in \mathbb C^{m \times m} \) and

\begin{equation*} {\cal E}_\lambda( A ) = \{ x \in \C^m \vert A x = \lambda x \}. \end{equation*}

bet the set of all eigenvectors of \(A \) associated with \(\lambda \) plus the zero vector (which is not considered an eigenvector). This set is a subspace.

The elements on the diagonal of a diagonal matrix are its eigenvalues. The elements on the diagonal of a triangular matrix are its eigenvalues.

Definition 9.5.2.10.

Given a nonsingular matrix \(Y \text{,}\) the transformation \(Y^{-1} A Y \) is called a similarity transformation (applied to matrix \(A \)).

Let \(A, B, Y \in \mathbb C^{m \times m} \text{,}\) where \(Y \) is nonsingular, \(B = Y^{-1} A Y \text{,}\) and \(( \lambda, x ) \) an eigenpair of \(A \text{.}\) Then \(( \lambda, Y^{-1} x ) \) is an eigenpair of \(B \text{.}\)

Definition 9.5.2.12.

Given a nonsingular matrix \(Q \) the transformation \(Q^H A Q \) is called a unitary similarity transformation (applied to matrix \(A \)).

Definition 9.5.2.16. Diagonalizable matrix.

A matrix \(A \in \Cmxm \) is said to be diagonalizable if and only if there exists a nonsingular matrix \(X \) and diagonal matrix \(D \) such that \(X^{-1} A X = D \text{.}\)

If \(A \in \Cmxm \) has distinct eigenvalues, then it is diagonalizable.

Definition 9.5.2.18. Defective matrix.

A matrix \(A \in \Cmxm \) that does not have \(m \) linearly independent eigenvectors is said to be defective.

Definition 9.5.2.20. Geometric multiplicity.

Let \(\lambda \in \Lambda( A ) \text{.}\) Then the geometric multiplicity of \(\lambda \) is defined to be the dimension of \({\cal E}_\lambda( A ) \) defined by

\begin{equation*} {\cal E}_\lambda( A ) = \{ x \in \C^m \vert A x = \lambda x \}. \end{equation*}

In other words, the geometric multiplicity of \(\lambda \) equals the number of linearly independent eigenvectors that are associated with \(\lambda \text{.}\)

Definition 9.5.2.21. Jordan Block.

Define the \(k \times k \) Jordan block with eigenvalue \(\mu \) as

\begin{equation*} J_k( \mu ) = \left( \begin{array}{c c c c c c } \mu \amp 1 \amp 0 \amp \cdots \amp 0 \amp 0 \\ 0 \amp \mu \amp 1 \amp \ddots \amp 0 \amp 0 \\ \vdots \amp \ddots \amp \ddots \amp \ddots \amp \vdots \amp \vdots \\ 0 \amp 0 \amp 0 \amp \ddots \amp \mu \amp 1 \\ 0 \amp 0 \amp 0 \amp \cdots \amp0 \amp \mu \end{array} \right) \end{equation*}

A practical Power Method for finding the eigenvector associated with the largest eigenvalue (in magnitude):

\begin{equation*} \begin{array}{l} \mbox{Pick } v^{(0)} \mbox{ of unit length} \\ {\bf for~} k = 0, \ldots \\ ~~~v^{(k+1)} = A v^{(k)} \\ ~~~ v^{(k+1)} = v^{(k+1)} / \| v^{(k+1)} \| \\ {\bf endfor} \end{array} \end{equation*}
Definition 9.5.2.23. Rayleigh quotient.

If \(A \in \Cmxm \) and \(x \neq 0 \in \Cm \) then

\begin{equation*} \frac{ x^H A x }{x^H x} \end{equation*}

is known as the Rayleigh quotient.

If \(x \) is an eigenvector of \(A \text{,}\) then

\begin{equation*} \frac{x^H A x}{x^H x} \end{equation*}

is the associated eigenvalue.

Definition 9.5.2.24. Convergence of a sequence of scalars.

Let \(\alpha_0, \alpha_1 , \alpha_2, \ldots \in \R \) be an infinite sequence of scalars. Then \(\alpha_k \) is said to converge to \(\alpha \) if

\begin{equation*} \lim_{k \rightarrow \infty} \vert \alpha_k - \alpha \vert = 0 . \end{equation*}
Definition 9.5.2.25. Convergence of a sequence of vectors.

Let \(x_0, x_1 , x_2, \ldots \in \C^m \) be an infinite sequence of vectors. Then \(x_k \) is said to converge to \(x \) if for any norm \(\| \cdot \| \)

\begin{equation*} \lim_{k \rightarrow \infty} \| x_k - x \| = 0. \end{equation*}
Definition 9.5.2.26. Rate of convergence.

Let \(\alpha_0, \alpha_1 , \alpha_2, \ldots \in \R \) be an infinite sequence of scalars that converges to \(\alpha \text{.}\) Then

  • \(\alpha_k \) is said to converge linearly to \(\alpha \) if for sufficiently large \(k \)

    \begin{equation*} \vert \alpha_{k+1} - \alpha \vert \leq C \vert \alpha_{k} - \alpha \vert \end{equation*}

    for some constant \(C \lt 1 \text{.}\)

  • \(\alpha_k \) is said to converge superlinearly to \(\alpha \) if for sufficiently large \(k \)

    \begin{equation*} \vert \alpha_{k+1} - \alpha \vert \leq C_k \vert \alpha_{k} - \alpha \vert \end{equation*}

    with \(C_k \rightarrow 0 \text{.}\)

  • \(\alpha_k \) is said to converge quadratically to \(\alpha \) if for sufficiently large \(k \)

    \begin{equation*} \vert \alpha_{k+1} - \alpha \vert \leq C \vert \alpha_{k} - \alpha \vert ^2 \end{equation*}

    for some constant \(C \text{.}\)

  • \(\alpha_k \) is said to converge superquadratically to \(\alpha \) if for sufficiently large \(k \)

    \begin{equation*} \vert \alpha_{k+1} - \alpha \vert \leq C_k \vert \alpha_{k} - \alpha \vert ^2 \end{equation*}

    with \(C_k \rightarrow 0 \text{.}\)

  • \(\alpha_k \) is said to converge cubically to \(\alpha \) if for large enough \(k \)

    \begin{equation*} \vert \alpha_{k+1} - \alpha \vert \leq C \vert \alpha_{k} - \alpha \vert ^3 \end{equation*}

    for some constant \(C \text{.}\)

The convergence of the Power Method is linear.

A practical Inverse Power Method for finding the eigenvector associated with the smallest eigenvalue (in magnitude):

\begin{equation*} \begin{array}{l} \mbox{Pick } v^{(0)} \mbox{ of unit length} \\ {\bf for~} k = 0, \ldots \\ ~~~v^{(k+1)} = A^{-1} v^{(k)} \\ ~~~ v^{(k+1)} = v^{(k+1)} / \| v^{(k+1)} \| \\ {\bf endfor} \end{array} \end{equation*}

The convergence of the Inverse Power Method is linear.

A practical Rayleigh quation iteration for finding the eigenvector associated with the smallest eigenvalue (in magnitude):

\begin{equation*} \begin{array}{l} \mbox{Pick } v^{(0)} \mbox{ of unit length} \\ {\bf for~} k = 0, \ldots \\ ~~~ \rho_k = v^{(k)\!H} A v^{(k)} \\ ~~~ v^{(k+1)} = ( A - \rho_k I )^{-1} v^{(k)} \\ ~~~ v^{(k+1)} = v^{(k+1)} / \| v^{(k+1)} \| \\ {\bf endfor} \end{array} \end{equation*}

The convergence of the Rayleigh Quotient Iteration is quadratic (eventually, the number of correct digits doubles in each iteration). If \(A \) is Hermitian, the convergence is cubic (eventually, the number of correct digits triples in each iteration).