最小多項式 - HackMD

# 最小多項式 Minimal polynomial ![Creative Commons License](https://i.creativecommons.org/l/by/4.0/88x31.png) 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}}$ ```python from lingeo import random_int_list, random_good_matrix from linspace import mtov ``` ## Main idea Let $A$ be an $n\times n$ matrix. Define the **minimal polynomial** of $A$ as the nonzero polynomial $m_A(x)$ with the smallest degree such that - the leading coefficient of $m_A(x)$ is $1$, and - $m_A(A) = O$. By the Cayley–Hamilton Theorem, the minimal polynomial exists and has degree at most $n$. The minimal polynomial of $A$ has the following properties: - If $p(x)$ is a polynomial with $p(A) = O$, then $m_A(x) \mid p(x)$. - The minimal polynomial of $A$ is unique. - $m_A(x) \mid p_A(x)$. Suppose $\bv$ is a vector in $\mathbb{R}^n$. Define the **minimal polynomial** of $A$ at $\bv$ as the nonzero polynomial $m_{A,\bv}(x)$ with the smallest degree such that - the leading coefficient of $m_{A,\bv}(x)$ is $1$, and - $m_{A,\bv}(A)\bv = \bzero$. The minimal polynomial of $A$ at $\bv$ has the following properties: - If $p(x)$ is a polynomial with $p(A)\bv = \bzero$, then $m_{A,\bv}(x) \mid p(x)$. - The minimal polynomial of $A$ is unique. - $m_A(x) \mid m_A(x)$. - If $\lambda$ is an eigenvalue of $A$, then $(x - \lambda)$ is a factor of $m_A(x)$. ##### Theorem (Minimal polynomial and diagonalizability) Let $A$ be an $n\times n$ real matrix. Then $A$ is diagonalizable (over $\mathbb{C}$) if and only if $m_A(x)$ has no repeated roots. Let $A$ be an $n\times n$ matrix. One may use standard techniques on a vector space to find the minimal polynomial. Let $\beta$ be the standard basis of the space of $n\times n$ matrices; see 210. 1. Calculate the $n^2\times n$ matrix $$ \Psi = \begin{bmatrix} | & | & ~ & | \\ [I]_\beta & [A]_\beta & \cdots & [A^{n-1}]_\beta \\ | & | & ~ & | \\ \end{bmatrix}. $$ 2. Use the row operation to find the smallest $d$ such that $$ A^d \in \vspan\{I, A, \ldots, A^{d-1}\}. $$ (Indeed, $d$ corresponds to the left-most free variable.) 3. If $$ A_d = c_1A_{d-1} + \cdots + c_dI, $$ then $$ m_A(x) = x^d - c_1x^{d-1} - c_2x^{d-2} - \cdots - c_d $$ is the minimal polynomial of $A$. The minimal polynomial of $A$ at $\bv$ can be found in a similar mannar but focusing on the $n\times n$ matrix $$ \Psi = \begin{bmatrix} | & | & ~ & | \\ I\bv & A\bv & \cdots & A^{n-1}\bv \\ | & | & ~ & | \\ \end{bmatrix} $$ instead. ## Side stories - Jordan block - nilpotent matrix - idempotent ## Experiments ##### Exercise 1 執行以下程式碼。令 $$ \Psi = \begin{bmatrix} | & | & ~ & | \\ [I]_\beta & [A]_\beta & \cdots & [A^{n-1}]_\beta \\ | & | & ~ & | \\ \end{bmatrix}. $$ 已知 $R$ 為 $\Psi$ 的最簡階梯型。  Run the code below. Let $$ \Psi = \begin{bmatrix} | & | & ~ & | \\ [I]_\beta & [A]_\beta & \cdots & [A^{n-1}]_\beta \\ | & | & ~ & | \\ \end{bmatrix}. $$ It is known that $R$ is the reduced echelon form of $\Psi$.  ```python ### code set_random_seed(0) print_ans = False n = 3 spec = random_int_list(n -1) spec.append(spec[-1]) Q = random_good_matrix(n,n,n,2) D = diagonal_matrix(spec) A = Q * D * Q.inverse() Psi = matrix([mtov(A^i) for i in range(n)]).transpose() R = Psi.rref() print("n =", n) pretty_print(LatexExpr("A ="), A) pretty_print(LatexExpr("R ="), R) if print_ans: pretty_print(LatexExpr(r"\Psi ="), Psi) print("minimal polynomial:", A.minpoly()) ``` ##### Exercise 1(a) 求 $\Psi$。  Find $\Psi$.  ##### Exercise 1(b) 計算 $m_A(x)$。  Find $m_A(x)$.  :::info What do the experiments try to tell you? (open answer) ... ::: ## Exercises ##### Exercise 2 以下討論對角矩陣的最小多項式。  The following exercises explore the minimal polynomial of a diagonal matrix.  ##### Exercise 2(a) 令 $$ A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}. $$ 求 $m_A(x)$。  Let $$ A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}. $$ Find $m_A(x)$.  ##### Exercise 2(b) 令 $$ A = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}. $$ 求 $m_A(x)$。  Let $$ A = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}. $$ Find $m_A(x)$.  ##### Exercise 2(c) 若 $r_1, \ldots, r_n$ 為 $n$ 個實數，而扣掉重覆元素後，其相異實數為 $\lambda_1, \ldots, \lambda_q$。令 $A$ 為一對角矩陣，其對角線上元素為 $r_1, \ldots, r_n$。求 $m_A(x)$。  Let $r_1, \ldots, r_n$ be $n$ real numbers. By removing repeated elements, we may assume $\lambda_1, \ldots, \lambda_q$ are the distinct values of them. Let $A$ be a diagonal matrix whose diagonal is composed of $r_1, \ldots, r_n$. Find $m_A(x)$.  ##### Exercise 3 以下討論喬丹標準型的最小多項式。  The following exercises explore the minimal polynomial of a Jordan form.  ##### Exercise 3(a) 令 $$ A = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{bmatrix}. $$ 求 $m_A(x)$。  Let $$ A = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \end{bmatrix}. $$ Find $m_A(x)$.  ##### Exercise 3(b) 令 $$ A = \begin{bmatrix} 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 3 \end{bmatrix}. $$ 求 $m_A(x)$。  Let $$ A = \begin{bmatrix} 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 3 \end{bmatrix}. $$ Find $m_A(x)$.  ##### Exercise 3(c) 定義 $J_{\lambda,m}$ 為一 $m\times m$ 矩陣，其對角線上的元素皆為 $\lambda$，而在每個 $\lambda$ 的上面一項放一個 $1$（除了第一行），其餘元素為 $0$。求 $J_{\lambda,m}$ 的最小多項式。  Let $J_{\lambda,m}$ be the $m\times m$ matrix whose diagonal entries are equal to $\lambda$ such that there is a $1$ above each $\lambda$ (except for the first column) and other entries are $0$. Find the minimal polynomial of $J_{\lambda,m}$.  ##### Exercise 3(d) 令矩陣 $A$ 是一個區塊對角矩陣，其對角區塊皆由一些 $J_{\lambda,m}$ 組成。說明 $A$ 的最小多項式為 $\prod_\lambda (x - \lambda)^h$，其中 $\lambda$ 跑過對角線上所有的相異 $\lambda$，而對每個 $\lambda$ 而言，$h$ 是所有 $J_{\lambda,m}$ 中最大的區塊的大小。  Let $A$ be a block diagonal matrix whose diagonal blocks are composed of $J_{\lambda,m}$'s. Show that the minimal polyonimial of $A$ is $\prod_\lambda (x - \lambda)^h$, where $\lambda$ runs through all distinct elements on the diagonal, while $h$ is the maximum size of $J_{\lambda,m}$ among all diagonal blocks with a given $\lambda$.  ##### Exercise 4 令 $$ A = \begin{bmatrix} 4 & 6 & 2 \\ -4 & -10 & -4 \\ 11 & 33 & 13 \end{bmatrix}. $$  Let $$ A = \begin{bmatrix} 4 & 6 & 2 \\ -4 & -10 & -4 \\ 11 & 33 & 13 \end{bmatrix}. $$  ##### Exercise 4(a) 計算 $A^0, A^1, A^2$，並求出 $$ \Psi = \begin{bmatrix} | & | & | \\ [I]_\beta & [A]_\beta & [A^{2}]_\beta \\ | & | & | \\ \end{bmatrix}. $$  Find $A^0, A^1, A^2$ and compute $$ \Psi = \begin{bmatrix} | & | & | \\ [I]_\beta & [A]_\beta & [A^{2}]_\beta \\ | & | & | \\ \end{bmatrix}. $$  ##### Exercise 4(b) 求 $m_A(x)$。  Find $m_A(x)$.  ##### Exercise 4(c) 令 $\bv = (2, -8, 22)$。計算 $A^0\bv, A^1\bv, A^2\bv$，並求出 $$ \Psi = \begin{bmatrix} | & | & | \\ I\bv & A\bv & A^{2}\bv \\ | & | & | \\ \end{bmatrix} $$  Let $\bv = (2, -8, 22)$. Find $A^0\bv, A^1\bv, A^2\bv$ and compute $$ \Psi = \begin{bmatrix} | & | & | \\ I\bv & A\bv & A^{2}\bv \\ | & | & | \\ \end{bmatrix} $$  ##### Exercise 4(d) 求 $m_{A,\bv}(x)$。  Find $m_{A,\bv}(x)$.  ##### Exercise 5 令 $A$ 為一 $n\times n$ 矩陣。說明若 $A^d \in \vspan\{I, A, \ldots, A^{d-1}\}$ 則對任何 $k\geq d$ 都有 $A^k \in \vspan\{I, A, \ldots, A^{d-1}\}$。因此若 $A$ 的最小多項式為 $d$ 次時， $\{I, A, \ldots, A^{d-1}\}$ 為 $\vspan\{I, A, A^2, \ldots \}$ 的一組基底。  Let $A$ be an $n\times n$ matrix. Show that if $A^d \in \vspan\{I, A, \ldots, A^{d-1}\}$, then $A^k \in \vspan\{I, A, \ldots, A^{d-1}\}$ for any $k\geq d$. Therefore, if the minimal polynomial of $A$ has degree $d$, then $\{I, A, \ldots, A^{d-1}\}$ is a basis of $\vspan\{I, A, A^2, \ldots \}$.  ##### Exercise 6 令 $A$ 為一 $n\times n$ 矩陣。以下探討 $m_A(x)$ 的一些基本性質。  Let $A$ be an $n\times n$ matrix. The following exercises studies some basic properties of $m_A(x)$.  ##### Exercise 6(a) 若 $p(x)$ 為一多項式且 $p(A) = O$，說明對於任何多項式 $a(x)$ 和 $b(x)$，把多項式 $a(x)p(x) + b(x)m_A(x)$ 代入 $A$ 也會是 $O$。因此把 $g(x) = \gcd(p(x), m_A(x))$ 代入 $A$ 也是 $O$。由於 $m_A(x)$ 已經是次方數最小的，$g(x) = m_A(x)$，且 $m_A(x) \mid p(x)$。提示：參考 312。  Let $p(x)$ be a polynomial with $p(A) = O$. Show that $a(x)p(x) + b(x)m_A(x)$ has value $O$ at $x = A$ is $O$ for any polynomials $a(x)$ and $b(x)$. Therefore, $g(x) = \gcd(p(x), m_A(x))$ is $O$ at $x = A$. However, since $m_A(x)$ has the minimum degree, it must be $g(x) = m_A(x)$ and $m_A(x) \mid p(x)$。 Hint: See 312.  ##### Exercise 6(b) 說明每個矩陣的最小多項式是唯一的。  Show that the minimal polynomial is unique for each matrix.  ##### Exercise 6(c) 說明 $m_A(x) \mid p_A(x)$。  Show that $m_A(x) \mid p_A(x)$.  ##### Exercise 7 令 $A$ 為一 $n\times n$ 矩陣、而 $\bv$ 為一 $\mathbb{R}^n$ 中的向量。以下探討 $m_{A,\bv}(x)$ 的一些基本性質。  Let $A$ be an $n\times n$ matrix and $\bv$ a vector in $\mathbb{R}^n$. The following exercises studies some basic properties of $m_{A,\bv}(x)$.  ##### Exercise 7(a) 若 $p(x)$ 為一多項式且 $p(A)\bv = \bzero$，說明對於任何多項式 $a(x)$ 和 $b(x)$，把多項式 $a(x)p(x) + b(x)m_{A,\bv}(x)$ 代入 $A$ 後再乘上 $\bv$ 也會是 $\bzero$。因此把 $g(x) = \gcd(p(x), m_{A,\bv}(x))$ 代入 $A$ 後再乘上 $\bv$ 也是 $\bzero$。由於 $m_{A,\bv}(x)$ 已經是次方數最小的，$g(x) = m_{A,\bv}(x)$，且 $m_{A,\bv}(x) \mid p(x)$。  Let $p(x)$ be a polynomial with $p(A)\bv = \bzero$. Show that the value of $a(x)p(x) + b(x)m_A(x)$ at $x = A$ multiplied by $\bv$ is $\bzero$ for any polynomials $a(x)$ and $b(x)$. Therefore, the value of $g(x) = \gcd(p(x), m_A(x))$ at $x = A$ multiplied by $\bv$ is $\bzero$. However, since $m_{A,\bv}(x)$ has the minimum degree, it must be $g(x) = m_{A,\bv}(x)$ and $m_{A,\bv}(x) \mid p(x)$。  ##### Exercise 7(b) 說明每個矩陣在任一向量上的最小多項式是唯一的。  Show that the minimal polynomial at any given vector is unique for each matrix.  ##### Exercise 7(c) 說明 $m_{A,\bv}(x) \mid m_A(x)$。  Show that $m_{A,\bv}(x) \mid m_A(x)$.  ##### Exercise 7(d) 說明任何 $p_A(x)$ 的根也是 $m_A(x)$ 的根。  Show that any root of $p_A(x)$ is also a root of $m_A(x)$.  ##### Exercise 8 依照以下步驟證明以下敘述等價： 1. $A$ 可以在複數中對角化。 2. $A$ 的最小多項式沒有重根。（由本節第 2 題已看出條件 1 會推得條件 2，所以以下著重在另一個方向的推導。）  Use the given instructions to show that the following are equivalent: 1. $A$ is diagonalizable over $\mathbb{C}$. 2. The minimal polyonimal of $A$ has no repeated roots. (From Problem 2 we can see Statement 1 implies Statement 2, so we focus on the other direction.)  ##### Exercise 8(a) 令 $B_1,\ldots, B_q$ 為 $n\times n$ 矩陣。證明若 $B_1\cdots B_q = O$，則 $\nul(B_1) + \cdots + \nul(B_q) \geq n$。  Let $B_1,\ldots, B_q$ be $n\times n$ matrices. Show that if $B_1\cdots B_q = O$, then $\nul(B_1) + \cdots + \nul(B_q) \geq n$.  ##### Exercise 8(b) 令 $\lambda_1,\ldots,\lambda_q$ 為 $A$ 的相異特徵值。若 $A$ 的最小多項式沒有重根，說明 $\gm(\lambda_1) + \cdots + \gm(\lambda_q) \geq n$。  Let $\lambda_1,\ldots,\lambda_q$ be the distinct eigenvalues of $A$. Suppose the minimal polynomial of $A$ has no repeated roots. Show that $\gm(\lambda_1) + \cdots + \gm(\lambda_q) \geq n$.  ##### Exercise 8(c) 證明若 $A$ 的最小多項式沒有重根，則 $A$ 可對角化。  Show that if the minimal polynomial of $A$ has no repeated roots, then $A$ is a diagonalizable.  ##### Exercise 9 以下探討最小多項式的應用。  The following exercises demonstrates some applications of the minimal polynomial.  ##### Exercise 9(a) 若一個 $n\times n$ 矩陣 $A$ 滿足 $A^2 = A$，則稱之為**冪等矩陣（idempotent matrix）** 。說明任何冪等矩陣一定可以對角化，並找出所有的相異特徵值。  An $n\times n$ matrix $A$ with $A^2 = A$ is called an **idempotent matrix** . Show that every idempotent matrix is diagonalizable and find all of its distinct eigenvalues.  ##### Exercise 9(a) 若一個 $n\times n$ 矩陣 $A$ 找得到一個整數 $k \geq 0$ 使得 $A^k = O$，則稱之為**冪零矩陣（nilpotent matrix）** 。找出一個冪等矩陣所有的相異特徵值。  An $n\times n$ matrix $A$ with $A^k = O$ for some integer $k$ is called an **nilpotent matrix** . Find all the distinct eigenvalues of a nilpotent matrix.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.