# 矩陣對角化

Diagonalization

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from lingeo import random_int_list, random_good_matrix

## Main idea

We know that an $n\times n$ matrix is diagonalizable if and only if there is a basis of $\mathbb{R}^n$ composed of eigenvectors.
We also know how to find the eigenvalues through the characteristic polynomial.
Indeed, that is all we need to perform the diagonalization of a matrix.

Let $A$ be an $n\times n$ matrix.
Here are the steps for its diagonalization:

1. Calculate the characteristic polynomial $p_A(x) = \det(A - xI)$ and solve the roots for $\spec(A)$.
2. For each $\lambda\in\spec(A)$, find a basis $\beta_\lambda$ for $\ker(A - \lambda I)$.
3. Let $\beta$ be the union of all such $\beta_\lambda$.
4. If $\beta$ is a basis of $\mathbb{R}^n$, then $A$ can be diagonalized through $\beta$.

That is, $[f_A]_\beta^\beta = D$ is a diagonal matrix.
Equivalently, $D = Q^{-1}AQ$, where $Q$ is the matrix whose columns are the vectors in $\beta$.

##### Remark

If $\beta = \{\bv_1, \ldots, \bv_n\}$ is a basis of $\mathbb{R}^n$ such $\bv_i$ is an eigenvector of $A$ with respect to $\lambda_i$ for all $i$.
Then the equalities $A\bv_i = \lambda_i\bv_i$ is equivalent to

$$
AQ =
A\begin{bmatrix}
| & ~ & | \\
{\bf v}_1 & \cdots & {\bf v}_n \\
| & ~ & |
\end{bmatrix}
=
\begin{bmatrix}
| & ~ & | \\
\lambda_1{\bf v}_1 & \cdots & \lambda_n{\bf v}_n \\
| & ~ & |
\end{bmatrix}
=
\begin{bmatrix}
| & ~ & | \\
{\bf v}_1 & \cdots & {\bf v}_n \\
| & ~ & |
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & ~ & ~ \\
~ & \ddots & ~ \\
~ & ~ & \lambda_n
\end{bmatrix}
= QD.
$$

##### Remark

The above process might not able to finish for a few different reasons:

- The root of $p_A(x)$ might not be real. If we instite the basis should be using real vectors, then it cannot be done.
- It is possible that $\beta_\lambda$ does not provide enough independent eigenvectors, so $\beta$ is not a bsis of $\mathbb{R}^n$.

Here is an example of diagonalizing

$$
A = \begin{bmatrix}
2 & 3 \\
3 & 2
\end{bmatrix}.
$$

_Solve for the eigenvalues_:

The characteristic polynomial of $A$ is

$$
p_A(x) =
\det\begin{bmatrix}
2 - x & 3 \\
3 & 2 - x
\end{bmatrix}
= x^2 - 4x - 5,
$$

which as roots $-1, 5$.

_Solve for the eigenvectors_:

For $\lambda = 5$, calculate the basis of $\ker(A - 5I)$ and get

$$
\ker(A - 5I) = \ker \begin{bmatrix} -3 & 3 \\ 3 & -3 \end{bmatrix} = \vspan\left\{\begin{bmatrix} 1 \\ 1 \end{bmatrix}\right\}.
$$

For $\lambda = -1$, calculate the basis of $\ker(A + I)$ and get

$$
\ker(A + I) = \ker \begin{bmatrix} 3 & 3 \\ 3 & 3 \end{bmatrix} = \vspan\left\{\begin{bmatrix} 1 \\ -1 \end{bmatrix}\right\}.
$$

By setting

$$
\beta = \left\{
\begin{bmatrix} 1 \\ 1 \end{bmatrix},
\begin{bmatrix} 1 \\ -1 \end{bmatrix}\right\}
\text{ and }
Q = \begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix},
$$

we get

$$
[f_A]_\beta^\beta = Q^{-1}AQ =
\begin{bmatrix}
5 & 0 \\
0 & -1
\end{bmatrix}.
$$

## Side stories

- Jordan block
- discrete Fourier transform

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False

n = 3
spec = random_int_list(n, 3)
D = diagonal_matrix(spec)
Q = random_good_matrix(n,n,n,2)
A = Q * D * Q.inverse()

pretty_print(LatexExpr("A ="), A)
pA = (-1)^n * A.charpoly()
print("characteristic polyomial =", pA)
print("                         =", factor(pA))

if print_ans:
    print("eigenvalues are:" + ", ".join("%s"%val for val in spec))
    print("corresponding eigenvectors are:")
    for i in range(n):
        pretty_print(LatexExpr(r"\lambda ="), spec[i], ", eigenvector =", Q[:,i])
    pretty_print(LatexExpr("Q ="), Q)

##### Exercise 1(a)

求出 $A$ 的所有特徵值。

<!-- eng start -->
Find all the eigenvalues of $A$.
<!-- eng end -->

##### Exercise 1(b)

對每個特徵值，求出對應的特徵向量。

<!-- eng start -->
For each of the eigenvalues, find the corresponding eigenvector.
<!-- eng end -->

##### Exercise 1(c)

求出 $Q$ 使得 $D = Q^{-1}AQ$ 是一個對角矩陣。

<!-- eng start -->
Find a matrix $Q$ such that $D = Q^{-1}AQ$ is a diagonal matrix.
<!-- eng end -->

:::info
What do the experiments try to tell you? (open answer)

...
:::

## Exercises

##### Exercise 2

將以下矩陣 $A$ 對角化。
（求出可逆矩陣 $Q$ 和對角矩陣 $D$ 使得 $D = Q^{-1}AQ$。）

<!-- eng start -->
Diagonalize the following matrices $A$. (That is, find an invertible matrix $Q$ and a diagonal matrix $D$ such that $D = Q^{-1}AQ$.)
<!-- eng end -->

##### Exercise 2(a)

$$
A = \begin{bmatrix}
0 & 1 \\
-6 & 5
\end{bmatrix}.
$$

##### Exercise 2(b)

$$
A = \begin{bmatrix}
0 & -1 \\
1 & 0
\end{bmatrix}.
$$

##### Exercise 3

將以下矩陣 $A$ 對角化。
（求出可逆矩陣 $Q$ 和對角矩陣 $D$ 使得 $D = Q^{-1}AQ$。）

<!-- eng start -->
Diagonalize the following matrices $A$. (That is, find an invertible matrix $Q$ and a diagonal matrix $D$ such that $D = Q^{-1}AQ$.)
<!-- eng end -->

##### Exercise 3(a)

$$
A = \begin{bmatrix}
4 & 0 & -1 \\
0 & 4 & -1 \\
-1 & -1 & 5
\end{bmatrix}.
$$

##### Exercise 3(b)

$$
A = \begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
6 & -11 & 6
\end{bmatrix}.
$$

##### Exercise 3(c)

$$
A = \begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}.
$$

##### Exercise 4

將以下矩陣 $A$ 對角化，
並說明 $f_A$ 的作用。

<!-- eng start -->
Diagonalize the following matrices $A$ and describe the effect of $f_A$.
<!-- eng end -->

##### Exercise 4(a)

$$
A = \begin{bmatrix}
\frac{2}{3} & -\frac{1}{3} & -\frac{1}{3} \\
-\frac{1}{3} & \frac{2}{3} & -\frac{1}{3} \\
-\frac{1}{3} & -\frac{1}{3} & \frac{2}{3}
\end{bmatrix}.
$$

##### Exercise 4(b)

$$
A = \begin{bmatrix}
\frac{1}{3} & -\frac{2}{3} & -\frac{2}{3} \\
-\frac{2}{3} & \frac{1}{3} & -\frac{2}{3} \\
-\frac{2}{3} & -\frac{2}{3} & \frac{1}{3}
\end{bmatrix}.
$$

##### Exercise 5

令

$$
A = \begin{bmatrix}
3 & 1 & 0 \\
0 & 3 & 1 \\
0 & 0 & 3
\end{bmatrix}.
$$

說明 $A$ 矩陣只有一個特徵值 $3$（重根三次），
但 $\ker(A - 3I)$ 的維度只有 $1$，
找不到足夠的特徵向量將 $A$ 對角化。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
3 & 1 & 0 \\
0 & 3 & 1 \\
0 & 0 & 3
\end{bmatrix}.
$$

Show that $A$ only has one eigenvalue $3$ (repeated three times), but $\ker(A - 3I)$ has dimension $1$ and we do not have enough independent eigenvectors to diagonalize $A$.
<!-- eng end -->

##### Exercise 6

令

$$
A = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0
\end{bmatrix}
$$

並令 $\zeta = e^{\frac{2\pi}{5}i}$ 為 $1$ 的五次方根。

這個練習告訴我們，如果運氣很好有找到所有的特徵向量，則不見得要解特徵多項式也可以找得到 $\spec(A)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0
\end{bmatrix}
$$

and let $\zeta = e^{\frac{2\pi}{5}i}$ be the fifth roots of $1$.

Through the following exercises, we will see that $\spec(A)$ can also be found by the eigenvectors (if we know them by luck) rather than the characteristic polynomial.
<!-- eng end -->

##### Exercise 6(a)

令

$$
Q = \begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & \zeta & \zeta^2 & \zeta^3 & \zeta^4 \\
1 & \zeta^2 & \zeta^4 & \zeta^6 & \zeta^8 \\
1 & \zeta^3 & \zeta^6 & \zeta^9 & \zeta^{12} \\
1 & \zeta^4 & \zeta^8 & \zeta^{12} & \zeta^{16} \\
\end{bmatrix}.
$$

驗證 $Q^*Q = 5I_5$，
因此 $Q$ 可逆且其行向量集合是一組 $\mathbb{C}^5$ 的基底。

（這裡 $Q^*$ 的意思是將 $Q$ 轉置後再逐項取共軛。）

<!-- eng start -->
Let

$$
Q = \begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & \zeta & \zeta^2 & \zeta^3 & \zeta^4 \\
1 & \zeta^2 & \zeta^4 & \zeta^6 & \zeta^8 \\
1 & \zeta^3 & \zeta^6 & \zeta^9 & \zeta^{12} \\
1 & \zeta^4 & \zeta^8 & \zeta^{12} & \zeta^{16} \\
\end{bmatrix}.
$$

Verify that $Q^*Q = 5I_5$. Therefore, $Q$ is invertible and it columns form a basis of $\mathbb{C}^5$.

(Here $Q^*$ is the conjugate transpose of $Q$.)
<!-- eng end -->

##### Exercise 6(b)

說明 $Q$ 的每個行向量都是 $A$ 的特徵向量，並找出對應的特徵值。
利用這點將 $A$ 對角化。

<!-- eng start -->
Show that each column of $Q$ is an eigenvector of $A$ and find the corresponding eigenvalue. Use them to diagonalize $A$.
<!-- eng end -->