This site is being phased out.
Diagonalization of matrices
Contents
Example
Examples: $A = \left[ \begin{array}{} 3 & 0 \\ 0 & 2 \end{array} \right]$.
This is diagonal already. In fact, $3$ and $2$ are the eigenvalues.
That's the final output of diagonalization: two eigenvalues are lined up on the diagonal.
So, if $A$ has complex eigenvalues, it's not diagonalizable: $\left[ \begin{array}{} 0 & 1 \\ -1 & 0 \end{array} \right]$ or $\lambda = \pm i$.
Example: $A = \left[ \begin{array}{} 0 & 1 \\ 1 & 0 \end{array} \right]$. Then the characteristic polynomial is
$$\chi_A(\lambda) = \det \left[ \begin{array}{} \lambda & 1 \\ 1 & \lambda \end{array} \right] = \lambda^2-1.$$
Its roots are $\pm 1$. So, $A \sim D = \left[ \begin{array}{} 1 & 0 \\ 0 & -1 \end{array} \right]$?
By hand: find a basis so that $D = P^{-1}AP$ is diagonal.
How?
What does $A$ do? Consider:
$$Ae_1 = \left[ \begin{array}{} 0 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{} 1 \\ 0 \end{array} \right] = \left[ \begin{array}{} 0 \\ 1 \end{array} \right] = e_2$$
$$Ae_2 = \left[ \begin{array}{} 0 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{} 0 \\ 1 \end{array} \right] = \left[ \begin{array}{} 1 \\ 0 \end{array} \right] = e_1.$$
So, $A$ reflects the plane about the diagonal $x=y$.
Then, what are the eigenvectors? Not $e_1,e_2$, as they shouldn't change $(\pm)$ directions under $A$.
Take $v_1=\left[ \begin{array}{} 1 \\ 1 \end{array} \right]$. For this one, $A(v_1)=v_1$, and for its multiples too. So, $\lambda = 1$.
Need one more.
File:ReflectionOfPlaneOverDiagonal.png
Try $v_2 = \left[ \begin{array}{} -1 \\ 1 \end{array} \right]$. Then $A(v_2) = -v_2$, and $\lambda=-1$.
So, the new basis is $\{v_1,v_2\}$.
And, the change of basis matrix is
$$P = \left[ \begin{array}{} 1 & -1 \\ 1 & 1 \end{array} \right],$$
find $P^{-1}$.
Compute $P^{-1}AP$.
Easier: matrix $D$ of the operator $A$ with respect to $\{v_1,v_2\}$: $D = $ made of columns, each $= A(v_1), A(v_2)$.
So $D = \left[ \begin{array}{} 1 & 0 \\ 0 & -1 \end{array} \right]$.
Written in terms $\{v_1,v_2\}$: $A(v_1)=v_1=\left[ \begin{array}{} 1 \\ 0 \end{array} \right]$, $A(v_2)=-v_2=\left[ \begin{array}{} 0 \\ -1 \end{array} \right]$.
That's the diagonalization of $A$.
The example suggests...
A general approach to diagonalization
Outline: Given matrix $A$.
Suppose
- $\lambda_1,\ldots,\lambda_n$ are the eigenvalues, all real.
- $v_1,\ldots, v_n$ are eigenvectors,
so that $$A(v_i)=\lambda_iv_i.$$
If $\{v_1,\ldots,v_n\}$ is a basis then, in terms of this basis, $v_1 = \left[ \begin{array}{} 1 \\ 0 \\ \vdots \\ 0 \end{array} \right], v_2 = \left[ \begin{array}{} 0 \\ 1 \\ \vdots \\ 0 \end{array} \right],$ etc.
So, we can write $A$ in terms of basis $\{v_1,\ldots,v_n\}$:
First column is $\lambda_1v_1 = \left[ \begin{array}{} \lambda_1 \\ 0 \\ \vdots \\ 0 \end{array} \right]$, second $\lambda_2v_2 = \left[ \begin{array}{} 0 \\ \lambda_2 \\ 0 \\ \vdots \\ 0 \end{array} \right]$, etc.
So, $D = \left[ \begin{array}{} \lambda_1 & 0 & 0 & \ldots \\ 0 & \lambda_2 & 0 & \ldots \\ \vdots \\ 0 & 0 & \ldots & \lambda_3 \\ \end{array} \right]$.
Problem: Is $\{v_1,\ldots,v_n\}$ really a basis?
- Case 1: All $\lambda_i$ are real and distinct.
Question: Suppose $\lambda_1 \neq \lambda_2$ are eigenvalues with eigenvectors $v_1,v_2$. Is it possible that $v_1, v_2$ are multiples?
Answer: No (otherwise plan doesn't work).
To prove, suppose $v_1=\mu v_2$ (*).
We also know this: $Av_1 = \lambda_1v_1$, $Av_1=\lambda_2v_2$.
- (1) Apply $A$ to (*), then
$$Av_1 = A\mu v_2 = \mu Av_2.$$
Then $\lambda_1v_1 = \mu \lambda_2v_2$.
- (2) Multiply (*) by $\lambda_2$, then $\lambda_2 v_1 = \lambda_2 \mu v_n$.
- (3) Match (1) and (2).
Then $\lambda_1v_1 = \lambda_2v_1$ implies $\lambda_1=\lambda_2$, contradiction.
That's the main idea of the proof. (3 steps)
This was only about $2$ vectors, and one being a multiple of the other.
Now $n$ vectors $v_1,\ldots,v_n$. Then this is about being linearly independent!
Theorem:
- Suppose $\lambda_1, \ldots, \lambda_m$ are eigenvalues of $A \colon {\bf R}^n \rightarrow {\bf R}^n$, $\lambda_1,\ldots,\lambda_m$ are real and distinct.
- Suppose $v_1,\ldots,v_m$ are eigenvectors corresponding to $\lambda_1,\ldots,\lambda_m$ respectively.
Then
- $v_1,\ldots,v_m$ are linearly independent.
Proof: Given $Av_i = \lambda_iv_i$, $i=1,\ldots,n$.
Proof by induction. Base $n=1$, done. Assume proven for $m-1$.
Suppose $r_1v_1 + \ldots + r_mv_m = 0$. (*)
The plan is to follow the three steps.
Do this to (*)
- apply $A_1$, and
- multiply by $\lambda_m$, then
- compare the results.
- (1)
$$A(r_1v_1+\ldots+r_mv_m)=0$$ or $$r_1Av_1 + \ldots + r_mAv_m = 0$$ or $$r_1\lambda_1v_1 + \ldots + r_m\lambda_mv_m = 0.$$
- (2)
$$\lambda_m r_1v_1 + \ldots + \lambda_m r_mv_m = 0.$$ The last terms in (1) and (2) match, so $$r_1\lambda_1v_1 + \ldots + r_{m-1}\lambda_{m-1}v_{m-1} = \lambda_mr_1v_1 + \ldots + \lambda_mr_{m-1}v_{m-1},$$ hence $$(\lambda_1-\lambda_m)r_1v_1 + (\lambda_2-\lambda_m)r_2v_2 + \ldots + (\lambda_{m-1} - \lambda_m)r_{m-1}v_{m-1} = 0.$$
Here we have $v_1,\ldots,v_{m-1}$, $m-1$ eigenvectors corresponding to different eigenvalues, so by the inductive assumption they are linearly independent.
Therefore, $$(\lambda_1 - \lambda_m)r_1=0, \ldots, (\lambda_{m-1}-\lambda_m)r_m=0.$$ Here $\lambda_i-\lambda_m \neq 0$, because they were chosen distinct.
Hence, $r_1=0, \ldots, r_{m-1}=0$.
Back to (*). What's left is $r_mv_m=0$.
Since $v_m \neq 0$, so $r_m = 0$. So, all $r_i=0$. Hence $v_1,\ldots,v_m$ are linearly independent. $\blacksquare$
Given $A \colon {\bf R}^n \rightarrow {\bf R}^n$, $\lambda_1,\ldots,\lambda_n$ are distinct real eigenvalues.
Then, by the theorem, any eigenvectors $v_1,\ldots,v_n$ chosen for $\lambda_1,\ldots,\lambda_n$ are linearly independent. Hence $\{v_1,\ldots,v_n\}$ is a basis.
Then $A$ expressed in this basis will be diagonal (with eigenvalues on the diagonal).
$$D = \left[ \begin{array}{} \lambda_1 & 0 & 0 & \ldots \\ 0 & \lambda_2 & 0 & \ldots \\ 0 & 0 & \ldots & \lambda_n \end{array} \right]$$
To summarize...
Corollary: If $A \colon {\bf R}^n \rightarrow {\bf R}^n$ has $n$ distinct real eigenvalues, then $A$ is diagonalizable: $D = P^{-1}AP$, here $D$ is diagonal.
Eigenvalues with multiplicities
it is of course possible that eigenvalues have multiplicities. Then the problem is that we don't have enough linearly independent eigenvectors: we need $n$ to form a basis.
We can still make it work...
Theorem: Suppose $A \colon {\bf R}^n \rightarrow {\bf R}^n$ is given and $\lambda_1,\ldots,\lambda_n$ are distinct real eigenvalues of $A$. Suppose $\{v_{i_1},\ldots,v_{i_{p_i}}\}$ are linearly independent eigenvectors of $\lambda_i$, for each $i=1,\ldots,m$. Then the combined set of these eigenvectors $$\{v_{11},\ldots,v_{1p_1},v_{21},\ldots,v_{2p_2},\ldots,v_{m1},\ldots,v_{mp_m}\}$$ is linearly independent.
Proof: Start with definition of linear dependence. Suppose
$$(r_{11}v_{11}+\ldots+r_{1p_1}v_{1p_1})+ \ldots + (r_{m1}v_{m1}+\ldots+r_{mp_m}v_{mp_m}=0.$$
Let's name these. We call the first term (in parentheses) $v_1$, the second $v_2$, and so forth until the last one is called $v_m$.
Then $v_1 + v_2 + \ldots + v_m=0$, a linear combination of $m$ vectors, one from each eigenspace:
$$v_1 \in E_A(\lambda_i), i=1,\ldots,m.$$
Therefore, $v_1, i=1,\ldots,m$ cannot be eigenvectors because eigenvectors are linearly independent, by the theorem.
So $v_i=0$ for each $i$!
In other words,
$$r_{11}v_{11}+\ldots+r_{1p_1}v_{1p_1}=0,\ldots,r_{m1}v_{m1}+\ldots+r_{mp_m}v_{mp_m}=0.$$
Observe that in each of these equations, the vectors are linearly independent; by assumption. Hence
$$r_{11}=\ldots=r_{1p_1}=0, \ldots, r_{m1}=\ldots=r_{mp_m}=0.$$
Therefore, $v_{11},\ldots,v_{mp_m}$ are linearly independent. $\blacksquare$
How to diagonalize
Plan: take a basis of each $E_A(\lambda_i)$. Suppose $\lambda_i$ are the real (no others) eigenvalues of $A$. Put them together, they are linearly independent by the theorem.
This is a basis if
$${\rm dim \hspace{3pt}}E_A(\lambda_1)+\ldots+{\rm dim \hspace{3pt}}E_A(\lambda_m)=n.$$
In that case we can diagonalize $A$.
Theorem: If the sum of the dimensions of the eigenspaces of real eigenvalues of $A$ add up to $n$, then $A$ is diagonalizable.
Example: Let $A = \left[ \begin{array}{} 2 & 1 \\ 0 & 2 \end{array} \right]$, then
$$\chi_A(\lambda) = {\rm det}\left[ \begin{array}{} 2-\lambda & 1 \\ 0 & 2-\lambda \end{array} \right] = (2-\lambda)^2.$$
Then the single eigenvalue is $\lambda=2$. Find $v$'s such that $Av=2v$. Solve
$$\left[ \begin{array}{} 2 & 1 \\ 0 & 2 \end{array} \right] \left[ \begin{array}{} x \\ y \end{array} \right] = 2\left[ \begin{array}{} x \\ y \end{array} \right] \rightarrow \left\{ \begin{array}{} 2x+y &= 2x \\ 2y &= 2y \end{array} \right..$$
This implies $y=0$ and $x$ is any. So
$$E_A(2) = \left\{ \left[ \begin{array}{} x \\ 0 \end{array} \right], x \in {\bf R} \right\}.$$
So ${\rm dim \hspace{3pt}}E_A(2)=1$. (Try $v=\left[ \begin{array}{} 1 \\ 0 \end{array} \right]$. That's not a basis.)
Hence $A$ is not diagonalizable!
Further analysis...
Here $\left[ \begin{array}{} 2 & 1 \\ 0 & 2 \end{array} \right]$ is a Jordan block corresponding to $\lambda=2$.
In dimension three, $\left[ \begin{array}{} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{array} \right]$, etc.
$p \times p$: $\left[ \begin{array}{} \lambda & 1 & 0 & \ldots \\ \vdots \\ 0 & 0 & \ldots & \lambda \end{array} \right]$ is a Jordan block of dimension $p$.
Any matrix (with real eigenvalues) is similar to a Jordan standard form:
with Jordan blocks along the diagonal and $0$'s elsewhere.
Note: Jordan blocks of sizes = multiplicites of the eigenvalues.
Exercise:
- 1.
- Consider $\chi_A(A)$. What is it?
- Prove $\chi_A(A)=0$. (Hamilton-Caley theorem)
- 2.
- Consider $V^{**}$. What is it?
- Prove $V^{**} \simeq V$ (even for infinite dimensional spaces).