# 喬丹標準型

Jordan canonical form

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_good_matrix

## Main idea

A **Jordan block** $J_{\lambda,m}$ is an $m\times m$ matrix

$$
J_{\lambda,m} =
\begin{bmatrix}
\lambda & 1 & 0 & \cdots & 0 \\
0 & \lambda & 1 & \ddots & \vdots \\
0 & 0 & \lambda & \ddots & 0 \\
\vdots & ~ & \ddots & \ddots & 1 \\
0 & \cdots & 0 & 0 & \lambda
\end{bmatrix}.
$$

A Jordan block $J_{\lambda,m}$ has only one eigenvalue $\lambda$ with $\am(\lambda) = m$ and $\gm(\lambda) = 1$.
Therefore, it is not diagonalizable whenever $m\geq 2$.

##### Theorem (Jordan canonical form)

For any square matrix $A$ over $\mathbb{C}$ there is a basis $\beta$ such that $[f_A]_\beta^\beta$ is a block diagonal matrix whose diagonal blocks are Jordan blocks.

A **generalized eigenvector** of $A$ with respect to $\lambda$ is a nonzero vector $\bv$ such that

$$
(A - \lambda I)^k\bv = \bzero
$$

for some $k$.
Equivalently, $p(A)\bv = \bzero$ for $p(x) = (x - \lambda)^k$.
Therefore, $m_{A,\bv}(x) \mid (x - \lambda)^k$ and $p(x)$ can be chosen as $m_{A,\bv}(x) = (x - \lambda)^d$ for some $d \leq n$ instead.
Consequently, the set of all generalized eigenvectors of $A$ with respect to $\lambda$ are exactly the nonzero vectors in

$$
F_\lambda = \ker(A - \lambda I)^n,
$$

and we call $F_\lambda$ as the **generalized eigenspace** of $A$ with respect to $\lambda$.

A subspace $W$ is called an $A$-invariant subspace if

$$
\{A\bw: \bw\in W\} \subseteq W.
$$

If $W$ is an $A$-invariant subspace, then the restriction $f_A\big|_W: W \rightarrow W$ defined as $f_A(\bw) = A\bw$ is a well-defined function with $\spec(f_A\big|_W) \subseteq \spec(f_A)$.
Indeed, if $\alpha$ is a basis of $W$ and $\beta\supseteq\alpha$ is an extendsion of $\alpha$ as a basis of $\mathbb {R}^n$, then

$$
[f_A]_\beta^\beta =
\begin{bmatrix}
A_W & B \\
O & C
\end{bmatrix},
$$

where $A_W = [f_A\big|_W]_\alpha^\alpha$.

Therefore, $F_\lambda$ is an $A$-invariant subspace.
A foundation of the theorem of Jordan canonical form is the following.

##### Theorem (Generalized eigenspace decomposition)

Let $A$ be an $n\times n$ matrix over $\mathbb{C}$ with distinct eigenvalues $\lambda_1,\ldots,\lambda_q$.
Then $\{F_{\lambda_1}, \ldots, F_{\lambda_q}\}$ is linearly independent, and

$$
\mathbb{R}^n = F_{\lambda_1} \oplus \cdots \oplus F_{\lambda_q}.
$$

That is to say, if we pick a basis $\beta_{\lambda_i}$ of $F_{\lambda_i}$ for $i = 1,\ldots, q$ and
set $\beta = \beta_{\lambda_1} \cup \cdots \cup \beta_{\lambda_q}$, then

$$
[f_A]_\beta^\beta =
\begin{bmatrix}
N_1 & O & \cdots & O \\
O & N_2 & \ddots & \vdots \\
\vdots & \ddots & \ddots & O \\
O & \cdots & O & N_q
\end{bmatrix}.
$$

Here we may set $f_{\lambda_i}$ as the resetriction $f_A\big|_{E_{\lambda_i}}$ such that $N_i = [f_{\lambda_i}]_{\beta_i}^{\beta_i}$.

Note that each $N_i$ only has a single eigenvalue $\lambda_i$ whose algebraic multiplicity is the size of $N_1$.
In other words, $N_i - \lambda_i I$ is a matrix with a single eigenvalue $0$.

An $n\times n$ matrix $A$ such that $A^k = O$ for some $k$ is called a **nilpotent matrix**, whose eigenvalues are $0$ with multiplicity $n$.
The minimum integer $d\geq 0$ such that $A^d = O$ is called the **index** of $A$.
Therefore, $N_i - \lambda_i I$ is a nilpotent matrix, and we are going to focus on these matrices.

##### Theorem (Nilpotent matrix decomposition)

Let $N$ be an $n\times n$ nilpotent matrix.
Then there is a basis $\beta$ of $\mathbb{C}^n$ such that $[f_N]_\beta^\beta$ is a block diagonal matrix whose diagonal blocks are nilpotent Jordan blocks.

Let $N - \lambda I$ be an $n\times n$ nilpotent matrix of index $d$.
The steps for finding such a basis are as follows:

1. Find a basis $\beta_{d-1}$ for $\Col(A^{d-1})\cap \ker(A)$.
2. Expand $\beta_{d-1}$ to $\beta_{d-1}\cup\beta_{d-2}$ as a basis of $\Col(A^{d-2})\cap\ker(A)$.
Keep doing this until we find a basis $\beta_{d-1}\cup\cdots\cup\beta_0$ of $\Col(A^0)\cap\ker(A) = \ker(A)$.
3. Start with $\beta = \emptyset$.
For $k = d-1, \ldots, 0$ and each vector $\bv\in\beta_k$, solve $A^{k}\bx = \bv$ for $\bx$.
Then add $\bv = A^{d-1}\bx, A^{d-2}\bx, \ldots, \bx$ to $\beta$.

## Side stories

- read the minimal polynomial from the Jordan canonical form

## Experiments

##### Exercise 1

執行以下程式碼。

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

### code
set_random_seed(0)
print_ans = False

b = 4
h = 3
ms = [choice(list(range(1, h + 1))) for i in range(b)]
max_ms = max(ms)
D = block_diagonal_matrix([jordan_block(0,ms[i]) for i in range(b)])
n = sum(ms)
Q = random_good_matrix(n,n,n,2)
A = Q * D * Q.inverse()

print("n =", n)
pretty_print(LatexExpr("A ="), A)
for i in range(1, h + 1):
    pretty_print(LatexExpr(r"\operatorname{nul}(A - 0I)^{%s} ="%i), (A^i).nullity())


if print_ans:
    print("Jordan canonical form:")
    pretty_print(D)
    print("minimal polynomial =", x^max_ms)

##### Exercise 1(a)

求出 $A$ 的喬丹標準型。

<!-- eng start -->
Find the Jordan canonical form of $A$.
<!-- eng end -->

##### Exercise 1(b)

計算 $m_A(x)$。

<!-- eng start -->
Find $m_A(x)$.
<!-- eng end -->

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

...
:::

## Exercises

##### Exercise 2

令

$$
A = \begin{bmatrix}
3 & -17 & 23 & 1 & 5 \\
1 & 18 & -21 & 0 & -5 \\
5 & -3 & 5 & 3 & -1 \\
-10 & 69 & -90 & -6 & -17 \\
-19 & 56 & -69 & -13 & -7
\end{bmatrix}.
$$

已知 $A$ 的相異特徵值為 $2, 3$。
求出廣義特徵空間 $F_2$ 的一組基底 $\beta_2$、
及 $F_3$ 的一組基底 $\beta_3$、
並令 $\beta = \beta_2\cup\beta_3$。

求 $[f_A]_\beta^\beta$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
3 & -17 & 23 & 1 & 5 \\
1 & 18 & -21 & 0 & -5 \\
5 & -3 & 5 & 3 & -1 \\
-10 & 69 & -90 & -6 & -17 \\
-19 & 56 & -69 & -13 & -7
\end{bmatrix}.
$$

It is known that the distinct eigenvalues of $A$ are $2, 3$. Find a basis $\beta_2$ for the generalized eigenspace $F_2$ and a basis $\beta_3$ for a generalized eigenspace $F_3$ and let $\beta = \beta_2\cup\beta_3$。

Find $[f_A]_\beta^\beta$.
<!-- eng end -->

##### Exercise 3

令

$$
A = \begin{bmatrix}
-2 & -9 & -1 & 5 & -5 \\
4 & 20 & 1 & -9 & 10 \\
-3 & -9 & -2 & 7 & -6 \\
-10 & -47 & -4 & 24 & -25 \\
-16 & -78 & -5 & 37 & -40
\end{bmatrix}.
$$

已知 $A$ 為一冪零矩陣。
求一基底 $\beta$ 使得 $[f_A]_\beta^\beta$ 是喬丹標準型。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
-2 & -9 & -1 & 5 & -5 \\
4 & 20 & 1 & -9 & 10 \\
-3 & -9 & -2 & 7 & -6 \\
-10 & -47 & -4 & 24 & -25 \\
-16 & -78 & -5 & 37 & -40
\end{bmatrix}.
$$

It is known that $A$ is a nilpotent matrix. Find a basis $\beta$ such that $[f_A]_\beta^\beta$ is the Jordan canonical form.
<!-- eng end -->

##### Exercise 4

凱力–漢米頓定理是證明喬丹標準型理論的關鍵之一。
然而假設已經知道每個複數矩陣都有喬丹標準型，
說明凱力–漢米頓定理在喬丹標準型的前提下是直觀的。

<!-- eng start -->
The theory of Jordan canonical form is an essential key to the proof of the Cayley–Hamilton theorem. However, suppose for some reason we already know that every complex matrix has the Jordan canonical form. Show that under this assumption, the Cayley–Hamilton theorem can be proved easily.
<!-- eng end -->

##### Exercise 5

令 $A$ 為一複數方陣。
說明 $e^A$ 會收斂。

<!-- eng start -->
Let $A$ be a complex square matrix. Show that $e^A$ converges.
<!-- eng end -->

##### Exercise 6

喬丹標準型的重要功用之一是判斷兩個矩陣是否相似。
在喬丹標準型的理論下不難發現以下敘述等價：

1. $A$ 和 $B$ 相似。
2. $A$ 和 $B$ 有相同的喬丹標準型。

判斷以下矩陣是否相似。

<!-- eng start -->
One of the most important applications of the Jordan canonical form is to determine if two matrices are similar. By the theory, it is not hard to see the following are equivalent:

1. $A$ and $B$ are similar.
2. $A$ and $B$ have the same Jordan canonical form.

Determine if the following pairs of matrices are similar.
<!-- eng end -->

##### Exercise 6(a)

$$
A = \begin{bmatrix}
2 & 0 \\
-1 & 3
\end{bmatrix}
\text{ and }
B = \begin{bmatrix}
1 & 1 \\
-2 & 4
\end{bmatrix}.
$$

##### Exercise 6(b)

$$
A = \begin{bmatrix}
6 & -2 & -2 \\
0 & 3 & 0 \\
6 & -4 & -1
\end{bmatrix}
\text{ and }
B = \begin{bmatrix}
4 & -2 & 0 \\
3 & 3 & 1 \\
-8 & 4 & 1
\end{bmatrix}.
$$

##### Exercise 7

令 $A$ 為一 $n\times n$ 矩陣且 $\lambda$ 為其一特徵值。
令 $F_\lambda$ 為其廣義特徵空間。
證明以下關於廣義特徵空間的性質。

<!-- eng start -->
Let $A$ be an $n\times n$ and $\lambda$ one of its eigenvalues. Let $F_\lambda$ be the generalized eigenspace with respect to $\lambda$. Prove the following basic properties about the generalized eigenspace.
<!-- eng end -->

##### Exercise 7(a)

證明 $F_\lambda$ 是一個 $A$-不變子空間。

提示：$A(A - \lambda I)^k = (A - \lambda I)^k A$。

<!-- eng start -->
Show that $F_\lambda$ is an $A$-invariant subspace.

Hint: $A(A - \lambda I)^k = (A - \lambda I)^k A$.
<!-- eng end -->

##### Exercise 7(b)

令 $d$ 為 $(x - \lambda)$ 在 $m_A(x)$ 中的重數。
說明 $F_\lambda = \ker (A - \lambda I)^d$。

<!-- eng start -->
Let $d$ be the multiplicity of $(x - \lambda)$ in $m_A(x)$. Show that $F_\lambda = \ker (A - \lambda I)^d$.
<!-- eng end -->

##### Exercise 7(c)

令 $\alpha$ 為 $F_\lambda$ 的一組基底，
將其擴展為 $\mathbb{R}^n$ 的一組基底 $\beta$。
說明 $[f_A]_\beta^\beta$ 有以下型式

$$
[f_A]_\beta^\beta =
\begin{bmatrix}
N_\lambda & B \\
O & D
\end{bmatrix},
$$

其中 $N_\lambda$ 的特徵值均為 $\lambda$。
藉此說明 $\dim(F_\lambda) \leq \am(\lambda)$。

<!-- eng start -->
Let $\alpha$ be a basis of $F_\lambda$. Extend it into a basis $\beta$ of $\mathbb{R}^n$. Show that $[f_A]_\beta^\beta$ has the form

$$
[f_A]_\beta^\beta =
\begin{bmatrix}
N_\lambda & B \\
O & D
\end{bmatrix},
$$

where $N_\lambda$ is a matrix whose eigenvalues are all equal to $\lambda$. Use this fact to show that $\dim(F_\lambda) \leq \am(\lambda)$.
<!-- eng end -->

##### Exercise 7(d)

令 $A$ 的相異特徵值為 $\lambda_1, \ldots, \lambda_q$，
而 $F_{\lambda_1}, \ldots, F_{\lambda_q}$ 為它們的廣義特徵空間。
證明 $\{F_{\lambda_1}, \ldots, F_{\lambda_q}\}$ 線性獨立。

提示：令 $p_1(x)$ 為 $p_A(x)$ 中去掉所有 $(x - \lambda_1)$ 因式的多項式。
假設 $\bv_1 + \cdots + \bv_q = \bzero$ 且對於 $i = 1, \ldots, q$ 滿足 $\bv_i \in F_{\lambda_i}$。
將等號兩邊同乘 $p_1(A)$ 並利用 $m_{A,\bv}(x)$ 的性質來說明 $\bv_1 = \bzero$。

<!-- eng start -->
Let $\lambda_1, \ldots, \lambda_q$ be the distinct eigenvalues of $A$ and $F_{\lambda_1}, \ldots, F_{\lambda_q}$ the corresponding eigenspaces. Show that $\{F_{\lambda_1}, \ldots, F_{\lambda_q}\}$ is linearly independent.

Hint: Let $p_1(x)$ be the polynomial obtained from $p_A(x)$ by removing the factor $(x - \lambda_1)$. Suppose $\bv_1 + \cdots + \bv_q = \bzero$ with $\bv_i \in F_{\lambda_i}$ for $i = 1, \ldots, q$. Pre-multiply $p_1(A)$ to both sides and use some properties of $m_{A,\bv}(x)$ to show that $\bv_1 = \bzero$.
<!-- eng end -->

##### Exercise 7(e)

令

$$
p_A(x) = (\lambda_1 - x)^{\am(\lambda_1)} \cdots (\lambda_q - x)^{\am(\lambda_q)}
$$

且對每個 $i = 1,\ldots, q$ 計算 $B_i = (A - \lambda_i I)^{\am(\lambda_i)}$。

證明

$$
\nul(B_1) + \cdots + \nul(B_q) \geq n
$$
且

$$
\mathbb{R}^n = F_{\lambda_1} \oplus \cdots \oplus F_{\lambda_q}.
$$

<!-- eng start -->
Let

$$
p_A(x) = (\lambda_1 - x)^{\am(\lambda_1)} \cdots (\lambda_q - x)^{\am(\lambda_q)}
$$

and let $B_i = (A - \lambda_i I)^{\am(\lambda_i)}$ for each $i = 1,\ldots, q$.

Show that

$$
\nul(B_1) + \cdots + \nul(B_q) \geq n
$$

and

$$
\mathbb{R}^n = F_{\lambda_1} \oplus \cdots \oplus F_{\lambda_q}.
$$
<!-- eng end -->

##### Exercise 8

令 $A$ 為一冪零矩陣且其深度（index）為 $d$。
證明以下關於冪零矩陣的性質。

<!-- eng start -->
Let $A$ be a nilpotent matrix with index $d$. Prove the following properties about a nilpotent matrix.
<!-- eng end -->

##### Exercise 8(a)

已知 $\{\bv_1,\bv_2,\bv_3\}$ 為 $\ker(A)$ 中的線性獨立集。
若存在 $\bx_1$ 及 $\bx_2$ 使得 $A\bx_1 = \bv_1$ 且 $A\bx_2 = \bv_2$。
說明 $\{\bv_1,\bv_2,\bv_3,\bx_1,\bx_2\}$ 線性獨立。

<!-- eng start -->
Suppose $\{\bv_1,\bv_2,\bv_3\}$ is an linearly independent set in $\ker(A)$. Suppose there are $\bx_1$ and $\bx_2$ such that $A\bx_1 = \bv_1$ and $A\bx_2 = \bv_2$. Show that $\{\bv_1,\bv_2,\bv_3,\bx_1,\bx_2\}$ is linearly independent.
<!-- eng end -->

##### Exercise 8(b)

定義函數一系列函數

$$
\mathbb{R}^n \xrightarrow{f_1} \Col(A) \xrightarrow{f_2} \Col(A^2) \xrightarrow{f_3}\cdots \xrightarrow{f_d} \Col(A^d) = \{\bzero\}
$$

其中對任意 $k = 1,\ldots, d$ 都定義 $f_k(\bx) = A\bx$。
證明對任意 $k = 1,\ldots, d$ 都有

$$
\rank(A^{k - 1}) = \rank(A^k) + \dim(\Col(A^{k-1})\cap\ker(A)),
$$

也就是

$$
\dim(\Col(A^{k-1})\cap\ker(A)) = \rank(A^{k - 1}) - \rank(A^k) = \nul(A^k) - \nul(A^{k - 1}).
$$

<!-- eng start -->
Define a sequence of functions

$$
\mathbb{R}^n \xrightarrow{f_1} \Col(A) \xrightarrow{f_2} \Col(A^2) \xrightarrow{f_3}\cdots \xrightarrow{f_d} \Col(A^d) = \{\bzero\}
$$

such that $f_k(\bx) = A\bx$ for $k = 1,\ldots, d$. Show that

$$
\rank(A^{k - 1}) = \rank(A^k) + \dim(\Col(A^{k-1})\cap\ker(A))
$$

for $k = 1,\ldots, d$. That is,

$$
\dim(\Col(A^{k-1})\cap\ker(A)) = \rank(A^{k - 1}) - \rank(A^k) = \nul(A^k) - \nul(A^{k - 1}).
$$
<!-- eng end -->

##### Exercise 8(c)

證明

$$
\rank(A^{k - 1}) - \rank(A^k) = \nul(A^k) - \nul(A^{k - 1})
$$

會隨著 $k$ 變大而遞減（或不變）。

<!-- eng start -->
Show that

$$
\rank(A^{k - 1}) - \rank(A^k) = \nul(A^k) - \nul(A^{k - 1})
$$

decreases (or stays the same) when $k$ increases.
<!-- eng end -->