Minimal polynomial
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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
from linspace import mtov
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
By the Cayley–Hamilton Theorem, the minimal polynomial exists and has degree at most $n$.
The minimal polynomial of $A$ has the following properties:
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 minimal polynomial of $A$ at $\bv$ has the following properties:
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.
(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.
執行以下程式碼。
令
已知 $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$.
### 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())
以下討論對角矩陣的最小多項式。
The following exercises explore the minimal polynomial of a diagonal matrix.
令
$$ 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)$.
令
$$ 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)$.
若 $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)$.
以下討論喬丹標準型的最小多項式。
The following exercises explore the minimal polynomial of a Jordan form.
令
$$ 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)$.
令
$$ 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)$.
定義 $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}$.
令矩陣 $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$.
令
$$ 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}. $$計算 $A^0, A^1, A^2$,
並求出
Find $A^0, A^1, A^2$ and compute
$$ \Psi = \begin{bmatrix} | & | & | \\ [I]_\beta & [A]_\beta & [A^{2}]_\beta \\ | & | & | \\ \end{bmatrix}. $$令 $\bv = (2, -8, 22)$。
計算 $A^0\bv, A^1\bv, A^2\bv$,
並求出
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} $$令 $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 \}$.
令 $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)$.
若 $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.
令 $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)$.
若 $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)$。
說明每個矩陣在任一向量上的最小多項式是唯一的。
Show that the minimal polynomial at any given vector is unique for each matrix.
說明任何 $p_A(x)$ 的根也是 $m_A(x)$ 的根。
Show that any root of $p_A(x)$ is also a root of $m_A(x)$.
依照以下步驟證明以下敘述等價:
(由本節第 2 題已看出條件 1 會推得條件 2,所以以下著重在另一個方向的推導。)
Use the given instructions to show that the following are equivalent:
(From Problem 2 we can see Statement 1 implies Statement 2, so we focus on the other direction.)
令 $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$.
令 $\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$.
證明若 $A$ 的最小多項式沒有重根,則 $A$ 可對角化。
Show that if the minimal polynomial of $A$ has no repeated roots, then $A$ is a diagonalizable.
以下探討最小多項式的應用。
The following exercises demonstrates some applications of the minimal polynomial.
若一個 $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.
若一個 $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.