# 代數重數與幾何重數

Algebraic multiplicity and geometric multiplicity

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 have seen whether a matrix $A$ is diagonalizable depends on how many (independent) vectors we can find in $\ker(A - \lambda I)$ for each eigenvalue $\lambda\in\spec(A)$.
In this section, we will give some quantitative measures on how much a matrix is diagonalizable.

Let $A$ be an $n\times n$ matrix and $p_A(x)$ its characteristic polynomial.
For each $\lambda \in \spec(A)$,

- the **algebtraic multiplicity** of $\lambda$ is the multiplicity of $\lambda$ as a root of $p_A(x)$, denoted by $\am_A(\lambda)$, while
- the **geometric multiplicity** of $\lambda$ is the dimension of $\ker(A - \lambda I)$, denoted by $\gm_A(\lambda)$.

When the context is clear, the subscript $A$ can be omitted.

For any $n\times n$ matrix $A$ and $\lambda\in\spec(A)$, the following properties hold.

- $1 \leq \gm(\lambda) \leq \am(\lambda)$.
- The sum of $\am(\lambda)$ over all distinct eigenvalues $\lambda$ is $n$.
- The matrix $A$ is diagonalizable if and only $\gm(\lambda) = \am(\lambda)$ for all distinct eigenvalues $\lambda$.

The fact $1\leq\gm(\lambda)$ follows immediate from the definition that $A - \lambda I$ is singular when $\lambda$ is an eigenvalue.
The exercises contains a proof of $\gm(\lambda) \leq \am(\lambda)$.
The sum of $\am(\lambda)$ is equal to the degree of $p_A(x)$, which is $n$.

If $\gm(\lambda) < \am(\lambda)$ for some $\lambda$, then the sum of all geometric multiplicities is less than $n$, so it is impossible to find a basis composed of eigenvectors.
If $\gm(\lambda) = \am(\lambda)$ for all distinct eigenvalues $\lambda$, we will show in the next section that $A$ is diagonalizable.

##### Proposition

Let $A$ be an $n\times n$ matrix.
If the characteristic polynomial $p_A(x)$ has $n$ distinct roots, then $A$ is diagonalizable.

## Side stories

- Jordan block
- invariant subspace

## Experiments

##### Exercise 1

執行以下程式碼。

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

### code
set_random_seed(0)
print_ans = False

am1 = choice([2,3])
am2 = choice([2,3])
n = am1 + am2
while True:
    lam1, lam2 = random_int_list(2,3)
    if lam1 != lam2:
        break
gm1 = randint(1,am1)
gm2 = randint(1,am2)

block1 = [matrix([[lam1]]) for i in range(gm1 - 1)] + [jordan_block(lam1, am1 - gm1 + 1)]
block2 = [matrix([[lam2]]) for i in range(gm2 - 1)] + [jordan_block(lam2, am2 - gm2 + 1)]
D = block_diagonal_matrix(block1 + block2)
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))
print("rref of A - (%s)I:"%lam1)
pretty_print((A - lam1).rref())
print("rref of A - (%s)I:"%lam2)
pretty_print((A - lam2).rref())

if print_ans:
    print("lambda =", lam1)
    print("am(lambda) =", am1)
    print("gm(lambda) =", gm1)
    print("lambda =", lam2)
    print("am(lambda) =", am2)
    print("gm(lambda) =", gm2)
    print("Diagonalizable?", am1 == gm1 and am2 == gm2)

##### Exercise 1(a)

求 $A$ 的每一個特徵值的代數重數與幾何重數。

<!-- eng start -->
For each eigenvalue of $A$, find its algebraic and geometric multiplicities.
<!-- eng end -->

##### Exercise 1(b)

判斷 $A$ 是否可對角化。

<!-- eng start -->
Determine if $A$ is diagonalizable.
<!-- eng end -->

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

...
:::

## Exercises

##### Exercise 2

對以下矩陣，
計算每一個特徵值的代數重數與幾何重數，
並判斷其是否可以對角化。

<!-- eng start -->
For each of the following matrices, find the algebraic and geometric multiplicities of its eigenvalues, and determine if it is diagonalizable.
<!-- eng end -->

##### Exercise 2(a)

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

##### Exercise 2(b)

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

##### Exercise 3

對以下矩陣，
計算每一個特徵值的代數重數與幾何重數，
並判斷其是否可以對角化。

<!-- eng start -->
For each of the following matrices, find the algebraic and geometric multiplicities of its eigenvalues, and determine if it is diagonalizable.
<!-- 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}
1 & 3 & 2 \\
2 & 4 & 3 \\
-3 & -7 & -5
\end{bmatrix}.
$$

##### Exercise 4

以下矩陣稱為喬丹區塊矩陣（Jordan block）。
說明以下矩陣
不計算重數的話只有一個特徵值，
計算這個特徵值的代數重數與幾何重數。

因此大小大於等於 $2$ 的喬丹區塊矩陣皆不可對角化。

<!-- eng start -->
The following matrices are examples of Jordan blocks. Show that each of the following matrices only has one distinct eigenvalue. Find the algebraic and geometric multiplicities of this eigenvalue.
<!-- eng end -->

##### Exercise 4(a)

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

##### Exercise 4(b)

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

##### Exercise 5

找尋滿足以下條件的矩陣。

<!-- eng start -->
For each of the following exercises, find a matrix that meet the conditions.
<!-- eng end -->

##### Exercise 5(a)

找一個矩陣 $A$ 使得
$\spec(A) = \{2,2,3,3,3\}$、
$\gm(2) = 1$ 且 $\gm(3) = 2$。

<!-- eng start -->
Find a matrix $A$ such that $\spec(A) = \{2,2,3,3,3\}$, $\gm(2) = 1$, and $\gm(3) = 2$.
<!-- eng end -->

##### Exercise 5(a)

找一個每一項都不為零的矩陣 $A$ 使得
$\spec(A) = \{2,2,3,3,3\}$、
$\gm(2) = 1$ 且 $\gm(3) = 2$。

<!-- eng start -->
Find a matrix $A$ whose entries are all nonzero such that $\spec(A) = \{2,2,3,3,3\}$, $\gm(2) = 1$, and $\gm(3) = 2$.
<!-- eng end -->

##### Exercise 6

令 $A$ 為一 $n\times n$ 矩陣而 $\lambda$ 為其一特徵值。
依照以下步驟證明 $\gm(\lambda) \leq \am(\lambda)$。

<!-- eng start -->
Let $A$ be an $n\times n$ matrix and $\lambda$ one of its eigenvalues. Use the given instructions to show that $\gm(\lambda) \leq \am(\lambda)$.
<!-- eng end -->

##### Exercise 6(a)

令 $d = \gm(\lambda)$ 為 $\ker(A - \lambda I)$ 的維度。
找一組 $\ker(A - \lambda I)$ 的基底 $\alpha$，
並將其擴展為 $\mathbb{R}^n$ 的一組基底 $\beta$。
（所以 $\alpha\subseteq\beta$ 且 $|\alpha| = d$。）
說明 $[f_A]_\beta^\beta$ 會有以下型式

$$
\begin{bmatrix}
\lambda I_d & B \\
O_{n-d,d} & D
\end{bmatrix}.
$$

（這裡 $D$ 只是一個矩陣的符號，不一定是對角矩陣。）

<!-- eng start -->
Let $d = \gm(\lambda)$ be the dimension of $\ker(A - \lambda I)$. Let $\alpha$ be a basis of $\ker(A - \lambda I)$. Then extend it into a basis $\beta$ of $\mathbb{R}^n$. (Therefore, $\alpha\subseteq\beta$ and $|\alpha| = d$.) Show that $[f_A]_\beta^\beta$ has the form

$$
\begin{bmatrix}
\lambda I_d & B \\
O_{n-d,d} & D
\end{bmatrix}.
$$

(Here $D$ is just a matrix, which is not necessarily diagonal.)
<!-- eng end -->

##### Exercise 6(b)

由於 $[f_A]_\beta^\beta$ 和 $A$ 有相同的特徵多項式。
說明 $p_A(x)$ 中有 $(\lambda - x)^d$ 這個因式，
因此 $\gm(\lambda) \leq \am(\lambda)$。

<!-- eng start -->
Observe that $[f_A]_\beta^\beta$ and $A$ have the same characteristic polynomial. Show that $(\lambda - x)^d$ is a factor of $p_A(x)$. Therefore, $\gm(\lambda) \leq \am(\lambda)$.
<!-- eng end -->

##### Exercise 7

令 $A$ 為一 $n\times n$ 矩陣而 $W$ 為一 $\mathbb{R}^n$ 的子空間。
如果

$$
f_A(W) = \{A\bw: \bw\in W\} \subseteq W,
$$

則我們稱 $W$ 是一個 **$A$-不變子空間（$A$-invariant subspace）**。

同樣地，令 $f:V\rightarrow V$ 為一個線性函數
而 $W$ 是 $V$ 的一個子空間。
如果

$$
f(W) = \{f(\bw): \bw\in W\} \subseteq W,
$$

則我們稱 $W$ 是一個 **$f$-不變子空間（$f$-invariant subspace）**。

<!-- eng start -->
Let $A$ be an $n\times n$ matrix and $W$ a subspace of $\mathbb{R}^n$. If

$$
f_A(W) = \{A\bw: \bw\in W\} \subseteq W,
$$

then $W$ is called an **$A$-invariant subspace** .

Similarly, let $f:V\rightarrow V$ be a linear function and $W$ a subspace of $V$. If

$$
f(W) = \{f(\bw): \bw\in W\} \subseteq W,
$$

then $W$ is called a **$f$-invariant subspace** .
<!-- eng end -->

##### Exercise 7(a)

令 $A$ 為一 $n\times n$ 矩陣而 $W$ 為一 $A$-不變子空間。
令 $\alpha$ 為 $W$ 的一組基底
並將基擴展為 $\mathbb{R}^n$ 的一組基底 $\beta$。
說明 $[f_A]_\beta^\beta$ 會有以下型式

$$
\begin{bmatrix}
\lambda A' & B \\
O_{n-d,d} & D
\end{bmatrix}.
$$

（這裡 $D$ 只是一個矩陣的符號，不一定是對角矩陣。）

<!-- eng start -->
Let $A$ be an $n\times n$ matrix and $W$ an $A$-invariant subspace. Let $\alpha$ be a basis of $W$. Then extend it into a basis $\beta$ of $\mathbb{R}^n$. Show that $[f_A]_\beta^\beta$ has the form

$$
\begin{bmatrix}
\lambda A' & B \\
O_{n-d,d} & D
\end{bmatrix}.
$$

(Here $D$ is just a matrix, which is not necessarily diagonal.)
<!-- eng end -->

##### Exercise 7(b)

若 $A$ 為一矩陣，而 $\lambda$ 為其一特徵值。
說明 $\ker(A - \lambda I)$ 為一 $A$-不變子空間。

<!-- eng start -->
Let $A$ be an $n\times n$ matrix and $\lambda$ one of its eigenvalues. Show that $\ker(A - \lambda I)$ is an $A$-invariant subspace.
<!-- eng end -->