Diagonalization

5.1 Eigenvalues and Eigenvectors

TipDefinition

A square matrix \(D = (d_{ij})\) is called a diagonal matrix if \[ d_{ij} = 0 \quad \text{whenever } i \ne j. \] Equivalently, all entries off the main diagonal are zero.

TipDiagonalizable

A linear operator \(T\) on a finite-dimensional vector space \(V\) is called diagonalizable if there is an ordered basis \(\beta\) for \(V\) such that \([T]_\beta\) is a diagonal matrix. A square matrix \(A\) is called diagonalizable if \(L_A\) is diagonalizable.

TipEigenvector and Eigenvalue

Let \(T\) be a linear operator on a vector space \(V\). A nonzero vector \(v \in V\) is called an eigenvector of \(T\) if there exists a scalar \(\lambda\) such that \(T(v) = \lambda v\). The scalar \(\lambda\) is called the eigenvalue corresponding to the eigenvector \(v\).

Let \(A\) be in \(M_{n \times n}(F)\). A nonzero vector \(v \in F^n\) is called an eigenvector of \(A\) if \(v\) is an eigenvector of \(L_A\); that is, if \(Av = \lambda v\) for some scalar \(\lambda\). The scalar \(\lambda\) is called the eigenvalue of \(A\) corresponding to the eigenvector \(v\).

Theorem 5.1 Let \(A \in M_{n \times n}(F)\). Then a scalar \(\lambda\) is an eigenvalue of \(A\) if and only if \[ \det(A - \lambda I_n) = 0. \]

TipCharacteristic Polynomial

Let \(A \in M_{n \times n}(F)\). The polynomial \(f(t) = \det(A - t I_n)\) is called the characteristic polynomial of \(A\).

• It is easily shown that similar matrices have the same characteristic polynomial.

• Let \(T\) be a linear operator on an \(n\)-dimensional vector space \(V\) with ordered basis \(\beta\). We define the characteristic polynomial \(f(t)\) of \(T\) to be the characteristic polynomial of \(A = [T]_\beta\). That is,

\[ f(t) = \det(A - t I_n). \]

• We often denote the characteristic polynomial of an operator \(T\) by \(f(t) = \det(T - t I)\).

Theorem 5.2 Let \(A \in M_{n \times n}(F)\).

\(\text{(a)}\quad\)The characteristic polynomial of \(A\) is a polynomial of degree \(n\) with leading coefficient \((-1)^n\).

\(\text{(b)} \quad A\) has at most \(n\) distinct eigenvalues.

Theorem 5.3 Let \(T\) be a linear operator on a vector space \(V\), and let \(\lambda\) be an eigenvalue of \(T\). A vector \(v \in V\) is an eigenvector of \(T\) corresponding to \(\lambda\) if and only if \(v \ne 0\) and \(v \in N(T - \lambda I)\).

5.2 Diagonalizability

Theorem 5.4 Let \(T\) be a linear operator on a vector space \(V\), and let \(\lambda_1, \lambda_2, \ldots, \lambda_k\) be distinct eigenvalues of \(T\). If \(v_1, v_2, \ldots, v_k\) are eigenvectors of \(T\) such that \(\lambda_i\) corresponds to \(v_i\) \((1 \le i \le k)\), then \(\{v_1, v_2, \ldots, v_k\}\) is linearly independent.

Corollay 1. Let \(T\) be a linear operator on an \(n\)-dimensional vector space \(V\). If \(T\) has \(n\) distinct eigenvalues, then \(T\) is diagonalizable.

TipDefinition

A polynomial \(f(t)\) in \(\text{P}(F)\) splits over \(F\) if there are scalars \(c, a_1, \ldots, a_n\) (not necessarily distinct) in \(F\) such that \[ f(t) = c(t - a_1)(t - a_2)\cdots(t - a_n). \] - If \(f(t)\) is the characteristic polynomial of a linear operator or a matrix over a field \(F\), then the statement that \(f(t)\) splits is understood to mean that it splits over \(F\).

Theorem 5.5 The characteristic polynomial of any diagonalizable linear operator splits.

TipDefinition

Let \(\lambda\) be an eigenvalue of a linear operator or matrix with characteristic polynomial \(f(t)\). The (algebraic) multiplicity of \(\lambda\) is the largest positive integer \(k\) for which \[ (t - \lambda)^k \]

is a factor of \(f(t)\).

TipEigenspace

Let \(T\) be a linear operator on a vector space \(V\), and let \(\lambda\) be an eigenvalue of \(T\). Define

\[ E_\lambda = \{ x \in V : T(x) = \lambda x \} = N(T - \lambda I_V). \]

The set \(E_\lambda\) is called the eigenspace of \(T\) corresponding to the eigenvalue \(\lambda\). Analogously, we define the eigenspace of a square matrix \(A\) to be the eigenspace of \(L_A\).

Theorem 5.6 Let \(T\) be a linear operator on a finite-dimensional vector space \(V\), and let \(\lambda\) be an eigenvalue of \(T\) having multiplicity \(m\). Then \[ 1 \le \dim(E_\lambda) \le m. \]

Theorem 5.7 Let \(T\) be a linear operator on a vector space \(V\), and let \(\lambda_1, \lambda_2, \ldots, \lambda_k\) be distinct eigenvalues of \(T\). For each \(i = 1,2,\ldots,k\), let \(S_i\) be a finite linearly independent subset of the eigenspace \(E_{\lambda_i}\). Then \[ S = S_1 \cup S_2 \cup \cdots \cup S_k \]

is a linearly independent subset of \(V\).

Theorem 5.8 Let \(T\) be a linear operator on a finite-dimensional vector space \(V\) such that the characteristic polynomial of \(T\) splits. Let \(\lambda_1, \lambda_2, \ldots, \lambda_k\) be the distinct eigenvalues of \(T\). Then:

\(\text{(a)}\quad T\) is diagonalizable if and only if the multiplicity of \(\lambda_i\) is equal to \(\dim(E_{\lambda_i})\) for all \(i\).

\(\text{(b)}\quad\)If \(T\) is diagonalizable and \(\beta_i\) is an ordered basis for \(E_{\lambda_i}\) for each \(i\), then

\[ \beta = \beta_1 \cup \beta_2 \cup \cdots \cup \beta_k \]

is an ordered basis for \(V\) consisting of eigenvectors of \(T\).

5.3 Applications

TipFast Matrix Exponentiation

If a matrix \(A\) is diagonalizable, there exists an invertible matrix \(P\) and a diagonal matrix \(D\) such that

\[ A = P D P^{-1}. \]

Then, for any positive integer \(n\),

\[ A^n = P D^n P^{-1}, \]

where

\[ D^n = \begin{pmatrix} \lambda_1^n & & 0 \\ & \ddots & \\ 0 & & \lambda_k^n \end{pmatrix} \]

if \(D = \operatorname{diag}(\lambda_1,\dots,\lambda_k)\). Thus computing \(A^n\) reduces to raising scalars \(\lambda_i\) to the \(n\)-th power.

TipSolving Linear Differential Equations

The system of differential equations is written in matrix form as

\[ x' = A x, \]

where \(x(t)\) is the vector of unknown functions and \(A\) is the coefficient matrix.

The main idea is to diagonalize \(A\). If

\[ A = Q D Q^{-1}, \]

then substituting into the system gives

\[ x' = Q D Q^{-1} x. \]

Define the new variable

\[ y(t) = Q^{-1} x(t), \]

which transforms the system into

\[ y' = D y. \]

Since \(D\) is diagonal, this gives three independent scalar differential equations, which are easy to solve. The solution to the original system is obtained by transforming back:

\[ x(t) = Q\, y(t). \]

5.4 Direct Sums

TipSum and Direct Sum

Let \(W_1, W_2, \ldots, W_k\) be subspaces of a vector space \(V\). We define the sum of these subspaces to be the set \[ \{\, v_1 + v_2 + \cdots + v_k : v_i \in W_i \text{ for } 1 \le i \le k \,\} \] which we denote by \(W_1 + W_2 + \cdots + W_k\) or \(\sum\limits_{i=1}^k W_i\)

• The sum of subspaces of a vector space is also a subspace.

Let \(W_1, W_2, \ldots, W_k\) be subspaces of a vector space \(V\). We call \(V\) the direct sum of the subspaces \(W_1, W_2, \ldots, W_k\) and write \(V = W_1 \oplus W_2 \oplus \cdots \oplus W_k\), if

\[ V = \sum_{i=1}^k W_i \] and

\[ W_j \cap \sum_{i \ne j} W_i = \{0\} \quad \text{for each } j \ (1 \le j \le k). \]

Theorem 5.9 Let \(W_1, W_2, \ldots, W_k\) be subspaces of a finite-dimensional vector space \(V\). The following conditions are equivalent.

\(\text{(a)}\quad V = W_1 \oplus W_2 \oplus \cdots \oplus W_k.\)

\(\text{(b)}\quad V = \sum_{i=1}^k W_i\) and, for any vectors \(v_1, v_2, \ldots, v_k\) such that \(v_i \in W_i\) \((1 \le i \le k)\), if \(v_1 + v_2 + \cdots + v_k = 0\) then \(v_i = 0\) for all \(i\).

\(\text{(c)}\quad\)Each vector \(v \in V\) can be uniquely written as \[ v = v_1 + v_2 + \cdots + v_k, \] where \(v_i \in W_i\).

\(\text{(d)}\quad\)If \(\gamma_i\) is an ordered basis for \(W_i\) \((1 \le i \le k)\), then \(\gamma_1 \cup \gamma_2 \cup \cdots \cup \gamma_k\) is an ordered basis for \(V\).

\(\text{(e)}\quad\)For each \(i = 1, 2, \ldots, k\), there exists an ordered basis \(\gamma_i\) for \(W_i\) such that \[ \gamma_1 \cup \gamma_2 \cup \cdots \cup \gamma_k \] is an ordered basis for \(V\).

Theorem 5.10 A linear operator \(T\) on a finite-dimensional vector space \(V\) is diagonalizable if and only if \(V\) is the direct sum of the eigenspaces of \(T\).

5.5 Invariant Subspaces and the Cayley–Hamilton Theorem

TipInvariant subspaces

Let \(T\) be a linear operator on a vector space \(V\). A subspace \(W\) of \(V\) is called a \(T\)-invariant subspace of \(V\) if \(T(W) \subseteq W\), that is, if \(T(v) \in W\) for all \(v \in W\).

TipDefinition

Let \(T\) be a linear operator on a vector space \(V\), and let \(x\) be a nonzero vector in \(V\). The subspace \[ W = \operatorname{span}(\{x,\, T(x),\, T^2(x),\, \ldots\}) \]

is called the \(T\)-cyclic subspace of \(V\) generated by \(x\). It is a simple matter to show that \(W\) is \(T\)-invariant.

• In fact, \(W\) is the “smallest’’ \(T\)-invariant subspace of \(V\) containing \(x\). That is, any \(T\)-invariant subspace of \(V\) containing \(x\) must also contain \(W\).

Theorem 5.11 Let \(T\) be a linear operator on a finite-dimensional vector space \(V\), and let \(W\) be a \(T\)-invariant subspace of \(V\). Then the characteristic polynomial of \(T_W\) divides the characteristic polynomial of \(T\).

Theorem 5.12 Let \(T\) be a linear operator on a finite-dimensional vector space \(V\), and let \(W\) denote the \(T\)-cyclic subspace of \(V\) generated by a nonzero vector \(v \in V\). Let \(k = \dim(W)\). Then:

\(\text{(a)}\quad \{v,\, T(v),\, T^2(v),\, \ldots,\, T^{k-1}(v)\}\) is a basis for \(W\).

\(\text{(b)}\quad\)If \[ a_0 v + a_1 T(v) + \cdots + a_{k-1} T^{\,k-1}(v) + T^{\,k}(v) = 0, \]

then the characteristic polynomial of \(T_W\) is \[ f(t) = (-1)^k \bigl(a_0 + a_1 t + \cdots + a_{k-1} t^{k-1} + t^k \bigr). \]

5.5.1 The Cayley–Hamilton Theorem

Theorem 5.13 (Cayley–Hamilton) Let \(T\) be a linear operator on a finite-dimensional vector space \(V\), and let \(f(t)\) be the characteristic polynomial of \(T\). Then \(f(T) = T_0\), the zero transformation. That is, \(T\) “satisfies’’ its characteristic equation.

Corollary 5.1 Let \(A\) be an \(n \times n\) matrix, and let \(f(t)\) be the characteristic polynomial of \(A\). Then \(f(A) = O\), the \(n \times n\) zero matrix.

Theorem 5.14 Let \(A\) be an \(n \times n\) matrix and \(f(x)\) be a polynomial such that \(f(A) = O\) (the zero matrix). Then, every eigenvalue \(\lambda\) of \(A\) must be a root of the scalar equation \(f(x) = 0\).

TipDefinition

Let \(B_1 \in M_{m \times m}(F)\), and let \(B_2 \in M_{n \times n}(F)\). We define the direct sum of \(B_1\) and \(B_2\), denoted \(B_1 \oplus B_2\), as the \((m+n) \times (m+n)\) matrix \(A\) such that \[ A_{ij} = \begin{cases} (B_1)_{ij} & \text{for } 1 \le i, j \le m, \\[6pt] (B_2)_{(i-m),(j-m)} & \text{for } m+1 \le i, j \le n+m, \\[6pt] 0 & \text{otherwise}. \end{cases} \]

If \(B_1, B_2, \ldots, B_k\) are square matrices with entries from \(F\), then we define the direct sum of \(B_1, B_2, \ldots, B_k\) recursively by \[ B_1 \oplus B_2 \oplus \cdots \oplus B_k = (B_1 \oplus B_2 \oplus \cdots \oplus B_{k-1}) \oplus B_k. \]

If \(A = B_1 \oplus B_2 \oplus \cdots \oplus B_k\), then we often write

\[ A = \begin{pmatrix} B_1 & O & \cdots & O \\ O & B_2 & \cdots & O \\ \vdots & \vdots & \ddots & \vdots \\ O & O & \cdots & B_k \end{pmatrix}. \]

Theorem 5.15 Let \(T\) be a linear operator on a finite-dimensional vector space \(V\), and suppose that \[ V = W_1 \oplus W_2 \oplus \cdots \oplus W_k, \] where \(W_i\) is a \(T\)-invariant subspace of \(V\) for each \(i\) \((1 \le i \le k)\). Suppose that \(f_i(t)\) is the characteristic polynomial of \(T_{W_i}\) \((1 \le i \le k)\). Then \[ f_1(t)\times f_2(t)\times \cdots\, \times f_k(t) \] is the characteristic polynomial of \(T\).