# Linear Algebra II. Canonical Form
> [2023 Spring, Linear Algebra for Study Cycle](https://sites.google.com/view/linear-algebra-analysis-junwei/linear-algebra-for-study-cycle)

## Chap I. Elementary Canonical Form
### 1. Introducttion

在上學期我們的主要目標是研究linear transformation在vector spaces的理論與性質(大部分是在finite dimension下)，以及linear transformation如何用matrix做「具象化」的表示。而之前有討論過$\mathcal{L}(V,W)$和$M_{m\times n}(F)$之間是isomorphism的關係，其中特別的例子是$\mathcal{L}(V,V)$和$M_{n}(F)$之間用不同的ordered basis來表示，而它前面的差異就在對於dimension的要求是要相同的，這時候我所畫出來的將會是square matrix。也就是說：

**Conclusion.** (Linear Transformation vs Matrix Representation)
Let $T\in\mathcal{L}(V,W)$ and $\beta,\gamma$ be ordered basis for $V,W$ with $\dim(V)=n,\dim(W)=m$, then
1. If $V\neq W$, then $[T]_\beta^\gamma\in M_{m\times n}(F)$.
2. If $V=W$, then $[T]_\beta^\gamma\in M_{n}(F)$, is a square matrix.

而關於matrix的Diagonalization的想法就是對於上面的特例(square matrix)，做出一個比較好計算的形式(canonical form)，例如之前所學過的upper triangular matrix就是很好的例子，它延伸出了一個著名的運算方法「LU decomposition」。

**Recall.** (Upper Triangular Matrix)
We say $A\in M_n(F)$ is the **upper triangular matrix** if it satisfies $$ A_{ij}=\left\lbrace
\begin{array}{cc}
A_{ij}, &\text{if~}j\geq i \\
0, &\text{if~}j<i
\end{array}
\right.$$
In particular, the upper triangular matrix is form
$$A=\left(
\begin{array}{ccccc}
A_{11} & A_{12} & A_{13} & \cdots & A_{1n} \\
& A_{22} & A_{23} & \cdots & A_{2n} \\
& & A_{33} & \cdots & A_{3n} \\
& O & & \ddots & \vdots \\
& & & & A_{nn}
\end{array}
\right)$$

而diagonalization則是更進一步將整個square matrix轉換成diagonal matrix，利用diagonal matrix的特性去解決更多複雜的問題。例如著名的「Fibonacci sequence問題」，在這之中我們可以利用diagonalization去建構出此sequence的通式。

**Definition** (Diagonal Matrix)
We say $A\in M_n(F)$ is the **diagonal matrix** if it satisfies
$$
A_{ij}=\left\lbrace
\begin{array}{cc}
A_{ij}, &\text{if }i=j \\
0, &\text{if }j\neq i
\end{array}
\right.
$$
We usually use $\lambda_i:=A_{ii}$ for all $i$, denoted by
$$
A=\text{diag}(\lambda_1,\lambda_2,...,\lambda_n)=\left(
\begin{array}{cccc}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n
\end{array}
\right)
$$

至於diagonal matrix想必各位在高中就有遇到一些這種類型的題目了，在這裡先練習看看一道以前的題目，你可以更清楚的看到diagonal matrix在運算上的方便性:

**Problem**.
If $A=\left(
\begin{array}{cc}
1 & 1 \\
0 & 2
\end{array}
\right)$ and $Q=\left(
\begin{array}{cc}
1 & 1 \\
0 & 1
\end{array}
\right)$, then we solve the following:
1. If $QD=AQ$, then find the matrix $D$.
2. Find the matrix $A^{10}$.

在高中的時候通常題目會你matrix $Q$ 讓你去做出diagonal matrix，而到了linear algebra我們需要自行去找這個matrix $Q$，至於這個matrix $Q$ 它的想法就是前面我們學過的「Replacement Theorem」和「Change of Coordinate」。

**Recall.** (Replacement Theorem and Change of Coordinate)
* Replacement Theorem. [FIS, thm 1.10]
Let $V$ be a vector space over $F$ with a basis $\beta$ and $|\beta|=n$. If $S=\lbrace y_1,...,y_m \rbrace\subseteq V$ be a linear independent with $m\leq n$. then there exists $S_1\subseteq\beta$ with $|S_1|=n-m$ such that $\text{span}(S\cup S_1)=V$ (and $S\cup S_1$ is linear independent).
* Change of Coordinates Theorem. [FIS, thm 2.23]
Let $V$ be vector space over $F$ with $\dim(V)<\infty$, and let $\beta,\beta'$ be ordered basis for $V$.
If $Q=[I_{dV}]_{\beta'}^\beta$, then $[T]_{\beta'}=Q^{-1}[T]_\beta Q$.

以上的證明可以參考[FIS]。我們把上面提到的內容歸納並定義出下列的事實。

**Definition.** (Diagonalizable)
Let $T\in\mathcal{L}(V,V)$ with $\dim(V)<\infty$, then $T$ is called **diagonalizable** if there exists an ordered basis $\beta$ for $V$ such that $[T]_\beta$ is a **diagonal matrix**.

而這整個過程就稱之為diagonalization。而diagonal matrix也稱為elementary canonical form。順帶一提，看到這個名稱你應該知道還有其他的canonical form吧!在這裡先請各位記住不是所有square matrix都可以diagonalization!!如下面這個經典的問題。

**Question.**
Let $T\in\mathcal{L}(V,V)$ be given with $\dim(V)<\infty$, is $T$ diagonalizable?
> May not be true !![name=junwei2023]

If it is true, then there exists $\beta=\lbrace v_1,...,v_n \rbrace$ basis for $V$ such that $[T]_\beta$ is diagonal matrix. That is, if $T(v_i)=\lambda_i$ for all $i\in[1,n]\cap\mathbb{N}$, then we have
$$
[T]_\beta=\left(
\begin{array}{cccc}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n \\
\end{array}
\right)
$$

基本上diagonalization的題目並不難，因為它的核心還是在找diagonal matrix，而接下來我們將會介紹一些基本的notion(§2)，然後帶入theory進行架構(§3)，再來會介紹整個canonical form的重點「Cayley-Hamiltion theorem」(§4)，最後去探討它calculation與test的部分(§5)。我們在整個canonical form的theory中，除了使用「Replacement Theorem」和「Change of Coordinate」之外，事實上還有一個很重要的理論依據，就是「Direct-Sum Decomposition」。更進一步來說，整個linear algebra都是將觀點放在「Decomposition theory」，在這邊我們先簡單的recall一下Direct-Sum，然後介紹一些重要的theorem：

**Definiton.** (Sum of Subspace)
Let $V$ be vector space and $W_1,W_2$ be subspace with $\dim(W_1),\dim(W_2)<\infty$, then we defined the **sum** of $W_1$ and $W_2$ by $$ \lbrace w_1+w_2 : w_1\in W_1, w_2\in W_2 \rbrace $$. We denoted by $W_1+W_2$. $$
\begin{array}{ccccc}
& & V & & \\
& & \mid & & \\
& & W_1+W_2 & & \\
& \diagup & & \diagdown & \\
W_1 & & & & W_2 \\
& \diagdown & & \diagup & \\
& & W_1\cap W_2 & & \\
& & \mid & & \\
& & \lbrace 0_V \rbrace & &
\end{array} $$

**Remark.**
Let $V$ be vector space and $W_1,W_2$ be subspace with $\dim(W_1),\dim(W_2)<\infty$, then $W_1+W_2$ and $W_1\cap W_2$ are the subspace of $V$.

**Definition.** (Direct Sum)
Let $V$ be vector space with $\dim(V)<\infty$ and $W_1,W_2\subseteq V$ be subspace of $V$, then the space $V$ is called the $direct sum$ of $W_1$ and $W_2$ if it satisfies the following:$$ W_1\cap W_2=\lbrace 0_V \rbrace\quad\&\quad W_1+W_2=V $$. We denoted by $W_1\oplus W_2$.

**Recall.** (Inclusion–Exclusion Principle for Subspace)
* Sum-Space Dimension Theorem. [FIS, Ex 1.6.29(a)]
If $W_1$ and $W_2$ are subspace of vector space $V$ with $\dim(W_1),\dim(W_2)<\infty$, then the subspace $W_1+W_2$ is finite-dimensional and $$\dim(W_1+W_2)=\dim(W_1)+\dim(W_2)-\dim(W_1\cap W_2)$$
* Direct-Sum-Space Dimension Theorem. [FIS, Ex 1.6.29(b)]
If $W_1$ and $W_2$ are subspace of vector space $V$ with $\dim(V)<\infty$ and $V=W_1+W_2$, then we have $$V=W_1\oplus W_2\text{ if and only if }\dim(V)=\dim(W_1)+\dim(W_2)$$

這個Direct-Sum-Space Dimension Theorem，又稱為「Corollay to Inclusion–Exclusion Principle for Subspace」。這個theorem有個很好用的equivalent result [FIS, Ex1.6.33]，我們可以利用這個新的result，加上replacement theorem去建構出下面這個corollary：

**Theorem.** [FIS, Ex1.6.33]
Let $V$ be vector space with $\dim(V)<\infty$ and $W_1,W_2\subseteq V$ be subspace of $V$. \\
If $\beta_1$ is the basis for $W_1$ and $\beta_2$ is the basis for $W_2$, then we have $$V=W_1\oplus W_2\text{ if and only if }\beta_1\cap\beta_2=\phi\text{ and }\beta_1\cup\beta_2\text{ is the basis for }V$$

**Corollary.** [FIS, Ex1.6.34]
Let $V$ be vector space with $\dim(V)<\infty$ and $W_1\subseteq V$ be subspace of $V$, then there exists a subspace $W_2$ of $V$ such that $V=W_1\oplus W_2$.

以上的證明可以參考\cite{ref04}。我們可以利用這個corollary，去延伸出下列的這個theorem，又稱為「Direct-Sum Decomposition Theorem」。首先，先將direct sum做擴充，再看看這的定理再說什麼。

**Definition.** (General Direct Sum)
Let $W_1,...,W_k$ be subspaces of a vector space $V$, then we defined the following:
1. We defined the \textcolor{violet}{\textbf{sum}} by $W_1+W_2+\cdots+W_k=\lbrace v_1+v_2+\cdots+v_k : v_i\in W_i, \forall i\in[1,k]\rbrace$.
2. $V=W_1\oplus W_2\oplus\cdots\oplus W_k$ is called the **direct sum** if it satisfies $$V=W_1+\cdots +W_k\text{ and }W_j\cap(\sum_{i\neq j}{W_i})=\lbrace 0_V \rbrace$$ for all $j\in[1,k]\cap\mathbb{N}$.

**Theorem.**
Let $W_1,...,W_k$ be subspaces of a vector space $V$, the followings are equivalence:
1. $V=W_1\oplus W_2\oplus\cdots\oplus W_k$.
2. If $V=\sum_{i=1}^{k} {W_i}$ and $v_1+\cdots+v_k=0_V$ for all $v_i\in W_i$, then $v_i=0_V$ for all $i$.
3. For all $v\in V$, there exists unique written as $v=v_1+v_2+\cdots+v_{k-1}+v_k$.
4. If $\gamma_i$ is the ordered basis for $W_i$ for all $i$, then $\gamma_1\cup\cdots\cup\gamma_k$ is also an ordered basis for $V$.
5. For all $i\in[1,k]\cap\mathbb{N}$, there exists ordered basis $\gamma_i$ for $W_i$ for all $i$ such that $\gamma_1\cup\cdots\cup\gamma_k$ is an ordered basis for $V$.

基本上，有此theorem可以看出decomposition的強大之處，接下來我們將會一步一步解析至我們想要看到的形式。(關於direct sum的部分會作為補充放在後續的章節(§7))

### 2. Eigenvector and Eigenvalue

在前面我們提到對任意的linear operator可以選定特定ordered basis $\beta$使得$[T]_\beta$是一個diagonal matrix，換句話說，我們有
$$\begin{array}{ccc}
T\text{ is diagonalizable } & \Leftrightarrow & T(v)=\lambda v\text{ for some }\lambda\in F \\
\Updownarrow & & \Updownarrow \\
{[T]_\beta}\text{ is diagonal for some ordered basis }\beta & \Leftrightarrow & [T(v)]_\beta=[T]_\beta[v]_\beta=\lambda [v]_\beta\text{ for some }\lambda\in F \\
\end{array}$$

對所有vector在這個特定的ordered basis，同時我們可以發現到value $\lambda$是這個diagonal matrix $[T]_\beta$的diagonal entry。而我們將這些valuec和所對應到vector做出以下的定義：

**Definition.** (Eigenvalue and Eigenvector)
Let $T\in\mathcal{L}(V,V)$, if $T(v)=\lambda v$ for some $v\in V\backslash\lbrace 0_V \rbrace$, $\lambda\in F$, then we defined the following:
1. The scalar $\lambda\in F$ is called the **eigenvalue** of $T$.
2. The vector $v\in V$ is called the **eigenvector** of $T$.

It is customary to say "$v\in V$ is an eigenvector of $T$ corresponding to eigenvalue $\lambda$."

**Notation.** The zero vector is \textcolor{red}{not} eigenvector, but zero value may be eigenvalue.

在這裡我們稍判別eigenvector和eigenvalue的差異從大學的思維去看看，你會發現到eigenvalue所對到的eigenvector並不唯一，而eigenvector會對到唯一的eigenvalue。我們可以從下面兩個問題來看看：

**Question.**
If $v$ is an eigenvector of $T$ corresponding to eigenvalue $\lambda$, then is $\lambda\longmapsto v$ one-to-one.
*Proof.*
Let $f:F\rightarrow F^n$ be a map with $f(\lambda)=v$ for all $T(v)=\lambda v$, then we have $$k\cdot v=f(\lambda)=v$$ for all $k\neq 0$, and hence $f$ is not one-to-one.

**Question.**
If $v$ is an eigenvector of $T$, then is $v\longmapsto v$ one-to-one.
*Proof.*
Let $f:F^n\rightarrow F^n$ be a map with $f(v)=\lambda v$ for some $\lambda\in F$. Now, we let $f(v)=\alpha v$ and $f(v)=\beta v$, then we have $$0_V=f(v)-f(v)=\alpha v-\beta v=(\alpha-\beta) v$$ Since $v\neq 0_V$, then we get $\alpha-\beta=0$, and hence $\alpha=\beta$. Thus, we know that $f$ is one-to-one.

如果你用中學的思維去思考，你會發現到eigenvector和eigenvalue的關係很像vector被matrix送過去成為一個伸縮過且平行的vector。事實上，中學的伸縮矩陣就是diagonal matrix form。(看來以前就學過了也不必要特別的重教了。)，接下來我們來一些簡單的example，帶各位做個review。

**Example.**
We find the eigenvalues and eigenvectors of $A$: $$A=\left(
\begin{array}{cc}
1 & 3 \\
4 & 2
\end{array}
\right)\in M_2(\mathbb{R}), v_1=\binom{1}{-1}, v_2=\binom{3}{4}$$
*Proof.*
We calculate the following: $$\begin{split}
Av_1&=\left(
\begin{array}{cc}
1 & 3 \\
4 & 2
\end{array}
\right)\binom{1}{-1}=(-2)\binom{1}{-1} \\
Av_2&=\left(
\begin{array}{cc}
1 & 3 \\
4 & 2
\end{array}
\right)\binom{3}{4}=5\binom{3}{4}
\end{split}$$ Thus, we know that $\lambda_1=-2$ and $\lambda_2=5$ are the eigenvalue of $A$, and hence we get $$A=\left(
\begin{array}{cc}
-2 & 0 \\
0 & 5
\end{array}
\right):=\text{diag}(-2,5)$$

**Example.**
We find the eigenvalues and eigenvectors of $A=\left(
\begin{array}{cc}
0 & 1 \\
-1 & 0
\end{array}
\right)$:
*Proof.*
We consider that the following: $$\left(
\begin{array}{cc}
0 & 1 \\
-1 & 0
\end{array}
\right)\binom{a}{b}=\lambda\binom{a}{b}\Rightarrow\binom{b}{-a}=\binom{a}{b}$$. Thus, we get $b=\lambda a=\lambda(-\lambda b)=-\lambda^2b$.
1. If $b=0$, then we get $a=0$. But $(0,0)$ is not eigenvector.
2. If $b\neq 0$, then we get $\lambda=0$ implies that $a=0$. This is contradiction to $b\neq 0$.

Hence, we know that it does not exist the eigenvector.

從上述兩個example我們可以看到一定需要找到eigenvalue才能去做eigenvector的確認。因此，如何找eigenvalue就成為這裡至關重要的部分，至於怎麼找Ur......，事實上各位中學就學過了哈哈，可以回去翻翻晟景的對話式講義(新舊課綱都有)、龍騰的課本也有(我記得舊綱放在附錄)、甚至補習班幾乎都會教。

但是中學時大部分要你去用背的，只有對話式講義(舊綱，新綱我不知道等我拿到書)是給你定義去推証的。以下是我們在中學時期學過的內容：

**Recall.** (Two-Ordered Characteristic Polynomial)
Suppose that $A=\left(
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right)$, then we have $$ch_A(t)=t^2-(a+d)t+(ad-bc)=t^2-tr(A)t+\det(A)=\det(A-tI_2)$$.