ALG1_L19

Recall

Theorem 1(Lemma).

The characteristic Polynomial of a linear operator is independent of the basis.

Proof

$$\det (Ix-PA{P}^{-1})=\det (P(Ix-A)P^{-1})=\det (Ix-A)$$

Theorem 2(Corollary).

Similar Matrices have the same eigenvalues.

Exercise: Let $K$ and $W$ be the kernel and the image of a linear operator $T:V\to V$. Show that the following are equivalent:

• $V\cong K\oplus W$;
• $K\cap W=\{0\}$;
• $V=K+W$.

---

Complex vs Real vector spaces

Theorem 3(Proposition).

Let $V$ be a nontrivial vector space over $\mathbb{C}$. Then any linear operator $T:V\to V$ will have at least one eigenvalue, and hence at least one eigenvector.

Proof
The characteristic polynomial of $T$ will be of degree $\ge 1$. By the Fundamental Theorem of Algebra, this will have at least one complex root. Hence proved.

Info

The fundamental theorem of algebra states that every non-constant polynomial with complex coefficients has at least one complex root. This implies that any polynomial of degree $n\ge 1$ with complex coefficients has exactly $n$ complex roots counting multiplicity. So, any operator in a complex vector space has exactly $n$ eigenvalues counting multiplicity.

Example 4(Example).

On the other hand, it is easy to construct a linear map in a real vector space with no real eigenvalues. Consider the rotation map, $R_{\theta }:{\mathbb{R}}^2\to {\mathbb{R}}^2$. It’s characteristic polynomial $x^2-2\cos \theta x+1$ does not have real roots for $\theta \ne n\pi$. But $R_{\theta }:{\mathbb{C}}^2\to {\mathbb{C}}^2$ has eigenvalues $e^{i\theta }$ and $e^{-1\theta }$.

Theorem 5(Proposition).

Every complex $n\times n$ matrix is similar to an upper triangular matrix.

Proof
We want to show that for every complex $n\times n$ matrix $A$ there exists a complex $n\times n$ invertible matrix $P$ such that $PA{P}^{-1}$ is upper triangular.

$A$ has at least one eigenvalue, call it $\lambda$ and its corresponding eigenvector $\mathbf{v}$. Extend $\{\mathbf{v}\}$ to a basis $\mathcal{B}$ of $V$. Observe that

$$[A{]}_{\mathcal{BB}}=\left[\begin{array}{cccc}\lambda & \ast & \cdots & \ast \\ 0& & & \\ ⋮& & D& \\ 0& & & \end{array}\right]$$

for some $(n-1)\times (n-1)$ matrix $D$. By induction hypothesis on $D$, there exists an $(n-1)\times (n-1)$ invertible matrix $Q$ such that $QD{Q}^{-1}$ is upper triangular. Define

$$G\equiv \left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& & & \\ ⋮& & Q& \\ 0& & & \end{array}\right]G^{-1}=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& & & \\ ⋮& & Q^{-1}& \\ 0& & & \end{array}\right]$$

Using block multiplication of matrices it is evident that $G^{-1}$ has the above form and that $G[A{]}_{\mathcal{BB}}{G}^{-1}$ will be upper triangular.

If we denote the standard basis by $\mathcal{S}$, we can write $[A{]}_{\mathcal{BB}}=[I{]}_{\mathcal{BS}}[A{]}_{\mathcal{SS}}[I{]}_{\mathcal{SB}}$. Observe that

$$G[A{]}_{\mathcal{BB}}{G}^{-1}=G[I{]}_{\mathcal{BS}}[A{]}_{\mathcal{SS}}[I{]}_{\mathcal{SB}}{G}^{-1}=(G[I{]}_{\mathcal{BS}})A(G[I{]}_{\mathcal{BS}}{)}^{-1},$$

where we have used the fact that $A=[A{]}_{\mathcal{SS}}$ and $[I{]}_{\mathcal{BS}}^{-1}=[I{]}_{\mathcal{SB}}$. Put $P=G[I{]}_{\mathcal{BS}}$. ❏

Remark

If $A$ is an $n\times n$ matrix over a field $\mathbb{F}$ such that its characteristic polynomial is a product of linear factors in $\mathbb{F}$, then there exists an invertible matrix $P$ (with entries in $\mathbb{F}$) such that $PA{P}^{-1}$ is upper triangular.

---

Diagonalization

Diagonalization of a linear operator $T:V\to V$ entails finding a basis $B$ of $V$ such that $[T{]}_{BB}$ is a diagonal matrix. Such a basis does not always exist, i.e, not all operators can be diagonalized.

For operators in ${\mathbb{F}}^n$, the diagonalizability of $A$ implies $A$ can be expressed as $A=SD{S}^{-1}$, where $D$ is a diagonal matrix and $S$ is an invertible matrix with entries in $\mathbb{F}$, i.e, $A$ is similar to a diagonal matrix.

Theorem 6(Proposition).

A $n\times n$ matrix $A$ (with values in $\mathbb{F}$) is diagonalizable $⟺$ there exists a basis of ${\mathbb{F}}^n$ that consists of eigenvectors of $A$.

Proof of $⟹$
Let $A=SD{S}^{-1}$ for some diagonal matrix $D=\text{diag}\{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\}$ and invertible matrix $S$. Let ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ be the column vectors of $S$. Note that $S{\mathbf{e}}_k={\mathbf{v}}_k⟹S^{-1}{\mathbf{v}}_k={\mathbf{e}}_k$. Notice what happens when we compute $A{\mathbf{v}}_k$:

$$\begin{array}{r}A{\mathbf{v}}_k=SD{S}^{-1}{\mathbf{v}}_k=SD{\mathbf{e}}_k=S({\alpha }_k{\mathbf{e}}_k)={\alpha }_k{\mathbf{v}}_k.\end{array}$$

So, the column vectors of $S$ are eigenvectors of $A$ (with ${\alpha }_k$‘s being the eigenvalues, but this is not important for the proof). Since the column vectors of $S$ form a basis of ${\mathbb{F}}^n$, we are done.

Proof of $⟸$
Suppose there exists a basis of ${\mathbb{F}}^n$ that consists of eigenvectors of $A$, i.e, $\mathcal{B}=\{{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n\}$ such that $A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$. Then

$$[A{]}_{\mathcal{BB}}=\left[\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right].$$

If we represent the standard basis by $\mathcal{S}$, we have $A=[A{]}_{\mathcal{SS}}=[I{]}_{\mathcal{SB}}[A{]}_{\mathcal{BB}}[I{]}_{\mathcal{BS}}$. We have shown above that $[A{]}_{\mathcal{BB}}$ is diagonal, and we know that $[I{]}_{\mathcal{SB}}=[I{]}_{\mathcal{BS}}^{-1}$. ❏

Obviously, an abstract operator $T:V\to V$ is diagonalizable iff its matrix in any basis is diagonalizable. Thus, it follows that $T$ is diagonalizable iff there exists a basis of $V$ that consists of eigenvectors of $T$.

A simple sufficient condition for an operator to be diagonalizable

Theorem 7(Theorem).

If an operator $T:V\to V$ has exactly $n=\dim V$ distinct eigenvalues, then $T$ is diagonalizable.

Proof
Let ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ be the distinct eigenvalues. For each eigenvalue ${\lambda }_i$, let ${\mathbf{v}}_i$ be a corresponding eigenvector. Then, ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ are linearly independent. Hence, they form a basis of $V$. ❏

Example 8(Example).

$$A=\left[\begin{array}{cc}4& 1\\ -2& 1\end{array}\right]$$

The characteristic polynomial will be $\det (A-xI)=(x-2)(x-3)$.

2-Eigenspace:

$$\ker \left(\left[\begin{array}{cc}4& 1\\ -2& 1\end{array}\right]-\left[\begin{array}{cc}2& 0\\ 0& 2\end{array}\right]\right)=\text{span}\left(\left[\begin{array}{c}1\\ -2\end{array}\right]\right)$$

3-Eigenspace:

$$\ker \left(\left[\begin{array}{cc}4& 1\\ -2& 1\end{array}\right]-\left[\begin{array}{cc}3& 0\\ 0& 3\end{array}\right]\right)=\text{span}\left(\left[\begin{array}{c}1\\ -1\end{array}\right]\right)$$

Sanity Check

$$G=\left[\begin{array}{cc}1& 1\\ -2& -1\end{array}\right]$$

So $G^{-1}AG$ must give a diagonalized matrix

$$G^{-1}AG={\left[\begin{array}{cc}1& 1\\ -2& -1\end{array}\right]}^{-1}\left[\begin{array}{cc}4& 1\\ -2& 1\end{array}\right]\left[\begin{array}{cc}1& 1\\ -2& -1\end{array}\right]=\left[\begin{array}{cc}2& 0\\ 0& 3\end{array}\right]$$

BEHOLD! THE DIAGONALISED MATRIX !!!!!11!!!

Multiplicity of an eigenvalue

To arrive at a stronger criterion of diagonalizability, we need to understand multiplicities of eigenvalues.

Definition 9(Definition).

Let $\lambda$ be an eigenvalue of an operator $A$.
The Geometric Multiplicity of $\lambda$ is the dimension of the $\lambda$-eigenspace, $\dim (\ker (A-\lambda I))$.
The Algebraic Multiplicity of $\lambda$ is the number of times $(x-\lambda )$ appears in the factored characteristic polynomial of $A$.

Let $\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_{\gamma }\}$ be the distinct eigenvalues for $A$ (over $\mathbb{C}$). Denote the geometric multiplicity of ${\lambda }_i$ by $g_i$ and the algebraic multiplicity of the same by $a_i$.

Theorem 10(Theorem).

$a_i\ge g_i$ for each $i$.

Proof
Fix $i$, call ${\lambda }_i=\lambda ,g_i=g,a_i=a$. Take $v_1,v_2,\dots ,v_g$ to be the basis of $\ker A-\lambda I$. Extend this to a basis of $V$ by appending $v_{g+1},v_{g+2},\dots ,v_n$. By writing the matrix of $T$ in this basis we get

$$\left[\begin{array}{cc}\lambda I_g& \ast \\ 0& \ast \end{array}\right]$$

The characteristic polynomial of $T$ will be of the form $p_{{}_T}(x)=(x-\lambda {)}^{g}h(x)$. Now, $h(x)$ may contain a factor of $(x-\lambda )$. Hence the number of times $(x-\lambda )$ appears in $p_{{}_T}(x)$ will be $g+r$ for some $r\in \mathbb{N}$. Hence Proved.

Criterion of diagonalizability

This theorem holds for vector spaces over general fields.

Theorem 11(Theorem).

Let an operator $A:V\to V$ have exactly $n=\dim V$ eigenvalues (counting multiplicities) (Since any operator in a complex vector space has exactly $n$ eigenvalues, this assumption is moot in the complex case). Then, $A$ is diagonalizable if and only if for each eigenvalue $\lambda$, the geometric multiplicity of $\lambda$ coincides with the algebraic multiplicity of $\lambda$.

We know that $g_i\le a_i\forall i$ and the hypothesis requires $\sum a_i=n$. Thus, this theorem boils down to

$$A\text{ is diagonalizable}⟺\sum _{i=1}^{\gamma }{g}_i=\dim V.$$

Proof of $⟹$
If $A$ is diagonalizable, $[A{]}_{\mathcal{BB}}$ is diagonal for some basis $\mathcal{B}$. Observe that geometric and algebraic multiplicities coincide for diagonal matrices. It follows that they must coincide for $A$ too.

Proof of $⟸$
Let ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_{\gamma }$ be the distinct eigenvalues of $A$, and let $E_k$ be the ${\lambda }_k$-eigenspace for $1\le k\le \gamma$. We know that these subspaces are linearly independent, i.e, ${\bigcap }_i{E}_i=\varnothing$. Let ${\mathcal{B}}_k$ be a basis of $E_k$. It follows that $\mathcal{B}\equiv {\bigcup }_i{\mathcal{B}}_i$ is linearly independent. Also,

$$\begin{array}{r}|\mathcal{B}|=\sum _{i=1}^{\gamma }|{\mathcal{B}}_i|=\sum _{i=1}^{\gamma }\dim (\ker (A-{\lambda }_{i}I))=\sum _{i=1}^{\gamma }{g}_i=n.\end{array}$$

A linearly independent system of size $n$ is a basis. Thus, $\mathcal{B}$ is a basis of $V$. ❏

The theorem can be restated specifically for real matrices:

Theorem 12(Theorem).

A real $n\times n$ matrix $A$ admits real factorization (i.e representation as $A=SD{S}^{-1}$ where $S$ and $D$ are real matrices, $D$ is diagonal and $S$ is invertible) iff it admits complex factorization and all eigenvalues of $A$ are real.

Note:

• The requirement of having $n$ eigenvalues is not moot for real matrices.
• The eigenvalues being real forces the eigenvectors to be real, which in turn forces $S$ to be real.