最小多項式的計算方法

本文的閱讀等級：高級

令 $A$ 為一個 $n\times n$ 階矩陣。若多項式 $p(t)$ 滿足 $p(A)=0$ ，則 $p(t)$ 稱為 $A$ 的一個消滅多項式。我們最常見的消滅多項式就是特徵多項式 $p_A(t)=\det(A-tI)$ ，此即 Cayley-Hamilton 定理 (見“Cayley-Hamilton 定理”)。最小多項式 $m_A(t)$ 是另一個特別的消滅多項式，它是 $A$ 的所有消滅多項式中次數最小者。如果設定多項式的領先係數為 $1$ ，稱為首一多項式，則 $A$ 有唯一的最小多項式。本文介紹三種最小多項式的計算方法：第一個方法來自定義；第二個方法計算 Jordan 形式的最大 Jordan 分塊階數；第三個方法基於循環子空間。為相互參照，我用下例解說這三種方法的計算過程：

$A=\left[\!\!\begin{array}{rccr} 1&1&0&-2\\ -2&1&3&2\\ 0&1&1&-2\\ -2&0&3&3 \end{array}\!\!\right]$ 。

(1) 定義

設 $A$ 有 $m$ 個相異特徵值 $\lambda_1,\ldots,\lambda_m$ ， $m\le n$ ，則特徵多項式 $p_A(t)$ 可分解為

$p_A(t)=(t-\lambda_1)^{\beta_1}\cdots(t-\lambda_m)^{\beta_m}$ ，

其中 $\beta_i$ 是 $\lambda_i$ 的重數，稱為代數重數， $\beta_1+\cdots+\beta_m=n$ 。方陣 $A$ 的最小多項式 $m_A(t)$ 滿足 $m_A(A)=0$ ，具有下列形式 (見“最小多項式 (上)”)：

$m_A(t)=(t-\lambda_1)^{r_1}\cdots(t-\lambda_m)^{r_m}$ ，

其中每一正整數 $r_i$ 滿足 $1\le r_1\le\beta_i$ 且 $r_1+\cdots+r_m$ 有最小值。明顯地， $m_A(t)$ 整除 $p_A(t)$ 。根據定義，我們可以設計一個簡易的最小多項式算法：先求出特徵多項式 $p_A(t)$ 、特徵值 $\lambda_i$ 和重數 $\beta_i$ ， $i=1,\ldots,m$ ，然後從 $r_1=\cdots=r_m=1$ 開始，逐次增加 $r_i$ 直到 $(A-\lambda_1I)^{r_1}\cdots(A-\lambda_mI)^{r_m}=0$ ，由所得的 $r_1,\ldots,r_m$ 即知 $m_A(t)$ 。

上例 $4\times 4$ 階矩陣 $A$ 的特徵多項式為

$p_A(t)=\begin{vmatrix} 1-t&1&0&-2\\ -2&1-t&3&2\\ 0&1&1-t&-2\\ -2&0&3&3-t \end{vmatrix}$ 。

直接展開上式或使用其他計算方法 (如“不使用行列式的特徵值和特徵向量算法 (上)”，“利用循環子空間計算特徵多項式”)，可得 $p_A(t)=(t-1)^2(t-2)^2$ ，故知 $A$ 有相異特徵值 $\lambda_1=1$ ， $\lambda_2=2$ ，重數分別為 $\beta_1=2$ ， $\beta_2=2$ 。最小多項式 $m_A(t)=(t-1)^{r_1}(t-2)^{r_2}$ 有最小的 $r_1+r_2$ 使得 $(A-I)^{r_1}(A-2I)^{r_2}=0$ 。以下計算步驟依序設 $(r_1,r_2)=(1,1), (2,1), (1,2), (2,2)$ 。若 $(r_1,r_2)=(1,1)$ ，

$(A-I)(A-2I)=\left[\!\!\begin{array}{rccr} 0&1&0&-2\\ -2&0&3&2\\ 0&1&0&-2\\ -2&0&3&2 \end{array}\!\!\right]\left[\!\!\begin{array}{rrrr} -1&1&0&-2\\ -2&-1&3&2\\ 0&1&-1&-2\\ -2&0&3&1 \end{array}\!\!\right]=\left[\!\!\begin{array}{rrrr} 2&-1&-3&0\\ -2&1&3&0\\ 2&-1&-3&0\\ -2&1&3&0 \end{array}\!\!\right]$ 。

再考慮 $(r_1,r_2)=(2,1)$ ，使用上面結果，

$\begin{aligned} (A-I)^2(A-2I)&=(A-I)((A-I)(A-2I))\\ &=\left[\!\!\begin{array}{rrrr} 0&1&0&-2\\ -2&0&3&2\\ 0&1&0&-2\\ -2&0&3&2 \end{array}\!\!\right]\left[\!\!\begin{array}{rrrr} 2&-1&-3&0\\ -2&1&3&0\\ 2&-1&-3&0\\ -2&1&3&0 \end{array}\!\!\right]=\left[\!\!\begin{array}{rrrr} 2&-1&-3&0\\ -2&1&3&0\\ 2&-1&-3&0\\ -2&1&3&0 \end{array}\!\!\right].\end{aligned}$

繼續試第三組數對 $(r_1,r_2)=(1,2)$ ，

$\begin{aligned} (A-I)(A-2I)^2&=((A-I)(A-2I))(A-2I)\\ &=\left[\!\!\begin{array}{rrrr} 2&-1&-3&0\\ -2&1&3&0\\ 2&-1&-3&0\\ -2&1&3&0 \end{array}\!\!\right]\left[\!\!\begin{array}{rrrr} -1&1&0&-2\\ -2&-1&3&2\\ 0&1&-1&-2\\ -2&0&3&1 \end{array}\!\!\right]=\left[\!\!\begin{array}{cccc} 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{array}\!\!\right].\end{aligned}$

一旦得到零矩陣，便可確定最小多項式，此例是 $m_A(t)=(t-1)(t-2)^2$ 。

(2) 指標

令 $J$ 代表 $A$ 的 Jordan 矩陣， $J$ 相似於 $A$ ，兩者有相同的特徵多項式和最小多項式 (見“Jordan 形式大解讀 (上)”)。最小多項式的因式 $(t-\lambda_i)^{r_i}$ 的次數 $r_i$ 就是對應 $\lambda_i$ 的最大 Jordan 分塊階數，稱為指標 (見“最小多項式 (下)”)。例如，

$J=\begin{bmatrix} 7&1&0& & & & & \\ 0&7&1& & & & &\\ 0&0&7& & & & & \\ & & &7&1& & & \\ & & &0&7& & & \\ & & & & &5&1 & \\ & & & & &0&5 &\\ & & & & & & &5 \end{bmatrix}$ ，

特徵值 $7$ 的指標是 $3$ ，特徵值 $5$ 的指標是 $2$ ，故最小多項式是 $m_J(t)=(t-7)^3(t-5)^2$ 。因此，只要算出每一 (相異) 特徵值 $\lambda_1,\ldots,\lambda_m$ 的指標便得到最小多項式。指標的計算方式如下 (見“Jordan 形式大解讀 (下)”)：對於特徵值 $\lambda_i$ ，依序計算 $\mathrm{rank}(A-\lambda_iI)^k$ ， $k=1,2,\ldots,\beta_i$ ，直到第一次發生 $\mathrm{rank}(A-\lambda_iI)^k=\mathrm{rank}(A-\lambda_iI)^{k+1}$ 方停止，指標即是 $r_i=k$ 。

上例中，對於 $\lambda_1=1$ ，

$\begin{aligned} A-I&=\left[\!\!\begin{array}{rrrr} 0&1&0&-2\\ -2&0&3&2\\ 0&1&0&-2\\ -2&0&3&2 \end{array}\!\!\right]~\Rightarrow~\mathrm{rank}(A-I)=2\\ (A-I)^2&=\left[\!\!\begin{array}{rrrr} 2&0&-3&-2\\ -4&1&6&2\\ 2&0&-3&-2\\ -4&1&6&2 \end{array}\!\!\right]~\Rightarrow~\mathrm{rank}(A-I)^2=2\end{aligned}$

可知 $r_1=1$ 。對於 $\lambda_2=2$ ，

$\begin{aligned} A-2I&=\left[\!\!\begin{array}{rrrr} -1&1&0&-2\\ -2&-1&3&2\\ 0&1&-1&-2\\ -2&0&3&1 \end{array}\!\!\right]~\Rightarrow~\mathrm{rank}(A-2I)=3\\ (A-2I)^2&=\left[\!\!\begin{array}{rrrr} 3&-2&-3&2\\ 0&2&0&-2\\ 2&-2&-2&2\\ 0&1&0&-1 \end{array}\!\!\right]~\Rightarrow~\mathrm{rank}(A-2I)^2=2\\ (A-2I)^3&=\left[\!\!\begin{array}{rrrr} -3&2&3&-2\\ 0&-2&0&2\\ -2&2&2&-2\\ 0&-1&0&1 \end{array}\!\!\right]~\Rightarrow~\mathrm{rank}(A-2I)^3=2 \end{aligned}$

可知 $r_2=2$ 。所以， $m_A(t)=(t-1)(t-2)^2$ 。

(3) 循環子空間

前面兩個方法必須事先知道特徵多項式，通過循環子空間我們不需要算出特徵多項式。對於任一非零向量 $\mathbf{x}\in\mathbb{C}^n$ (稱為種子)，所謂循環子空間是指 $\mathbf{x}$ 累乘 $A$ 所得到的全部向量擴張而成的子空間：

$\mathcal{X}=\mathrm{span}\{\mathbf{x},A\mathbf{x},A^2\mathbf{x},\ldots\}$ 。

設 $k$ 為最小正整數使 $\{\mathbf{x},A\mathbf{x},\ldots,A^{k-1}\mathbf{x}\}$ 是線性獨立集，即存在唯一數組 $a_0,a_1,\ldots,a_{k-1}$ 使得

$a_0\mathbf{x}+a_1A\mathbf{x}+\cdots+a_{k-1}A^{k-1}\mathbf{x}+A^k\mathbf{x}=\mathbf{0}$ 。

將上式改寫成

$\left(A^k+a_{k-1}A^{k-1}+\cdots+a_1A+a_0I\right)\mathbf{x}=\mathbf{0}$ 。

令 $p(t)=t^k+a_{k-1}t^{k-1}+\cdots+a_1t+a_0$ ，則 $p(A)\mathbf{x}=\mathbf{0}$ 。我們說「 $p(t)$ 是向量 $\mathbf{x}$ 相對於 $A$ 的一個消滅多項式」。運用類似最小多項式的論證方式可推論：給定矩陣—向量對 $(A,\mathbf{x})$ ，次數最小的首一消滅多項式唯一存在，記為 $m(t)$ ，就有 $m(A)\mathbf{x}=\mathbf{0}$ 。既然 $k$ 是最小正整數使得 $\mathbf{x},A\mathbf{x},\ldots,A^k\mathbf{x}$ 線性相關，故 $m(t)=p(t)$ 。

矩陣 $A$ 的最小多項式 $m_A(t)$ 與向量 $\mathbf{x}$ 相對於 $A$ 的最小多項式 $m(t)$ 有甚麼關係？直觀上，如果我們知道足夠多的相異向量 $\mathbf{x}$ 相對於 $A$ 的最小多項式似乎能引領出 $A$ 的最小多項式。的確如此，具體陳述見下面的定理。

最小公倍式定理：令 $\{\mathbf{x}_1,\ldots,\mathbf{x}_n\}$ 為 $\mathbb{C}^n$ 的一組基底。若 $m_i(t)$ 是 $\mathbf{x}_i$ 相對於 $A$ 的最小多項式，則 $A$ 的最小多項式 $m_A(t)$ 是 $m_1(t),\ldots,m_n(t)$ 的最小公倍式。

我們說首一多項式 $f(t)$ 是多項式 $m_1(t),\ldots,m_n(t)$ 的唯一最小公倍式，如果以下兩個條件成立：(1) 每一 $m_i(t)$ 整除 $f(t)$ ，(2) 如果每一 $m_i(t)$ 整除 $q(t)$ ，則 $f(t)$ 也整除 $q(t)$ 。首先證明如果 $f(t)$ 是 $m_1(t),\ldots,m_n(t)$ 的最小公倍式，則 $m_A(t)$ 整除 $f(t)$ ，然後反過來證明 $f(t)$ 也整除 $m_A(t)$ 。設 $f(t)$ 是 $m_1(t),\ldots,m_n(t)$ 的首一最小公倍式，則 $m_i(t)$ 整除 $f(t)$ ，就有 $f(t)=g_i(t)m_i(t)$ ，因此

$f(A)\mathbf{x}_i=g_i(A)(m_i(A)\mathbf{x}_i)=g_i(A)\mathbf{0}=\mathbf{0},~~~i=1,\ldots,n$ 。

換句話說， $\dim N(f(A))=n$ ，根據秩—零度定理， $\mathrm{rank}f(A)=n-\dim N(f(A))=0$ ，即有 $f(A)=0$ ，這表明 $f(t)$ 是 $A$ 的一個消滅多項式。最小多項式 $m_A(t)$ 整除 $A$ 的每一個消滅多項式，當然 $m_A(t)$ 整除 $f(t)$ 。再考慮相反方向的證明。對於每一 $\mathbf{x}_i$ ， $m_A(A)\mathbf{x}_i=0\mathbf{x}_i=\mathbf{0}$ ，最小多項式 $m_A(t)$ 也是 $\mathbf{x}_i$ 相對於 $A$ 的一個消滅多項式，則 $\deg[m_i(t)]\le\deg[m_A(t)]$ ，這裡 $\deg$ 代表多項式的次數。據此，存在多項式 $q_i(t)$ 和 $r_i(t)$ 使得 $m_A(t)=q_i(t)m_i(t)+r_i(t)$ ，其中 $\deg[r_i(t)]<\deg[m_i(t)]$ 。然而，

$\mathbf{0}=m_A(A)\mathbf{x}_i=q_i(A)m_i(A)\mathbf{x}_i+r_i(A)\mathbf{x}_i=g_i(A)\mathbf{0}+r_i(A)\mathbf{x}_i=r_i(A)\mathbf{x}_i$ ，

因此判定 $r_i(t)=0$ ，否則 $r_i(t)$ 的次數小於 $\mathbf{x}_i$ 相對於 $A$ 的最小多項式 $m_i(t)$ ，發生矛盾。所以，每一 $m_i(t)$ 整除 $m_A(t)$ ，推知最小公倍式 $f(t)$ 也整除 $m_A(t)$ 。首一多項式 $f(t)$ 和 $m_A(t)$ 互相整除對方，也就證明 $f(t)=m_A(t)$ 。

令 $\mathcal{X}_i=\mathrm{span}\{\mathbf{x}_i,A\mathbf{x}_i,A^2\mathbf{x}_i,\ldots\}$ 是種子 $\mathbf{x}_i$ 生成的循環子空間。向量 $\mathbf{x}_i$ 相對於 $A$ 的最小多項式 $m_i(t)$ 不僅消滅 $\mathbf{x}_i$ ，同時也消滅循環子空間 $\mathcal{X}_i$ 。對於任一 $\mathbf{v}\in\mathcal{X}_i$ ， $\mathbf{v}$ 可表示為 $A^j\mathbf{x}_i$ ， $j=0,1,2,\ldots$ ，的線性組合，但

$m_i(A)A^j\mathbf{x}_i=A^j(m_i(A)\mathbf{x}_i)=A^j\mathbf{0}=\mathbf{0},~~j=0,1,2,\ldots$ 。

上面使用了 $A^j$ 和 $m_i(A)$ 是可交換矩陣。根據這個結果，如果種子集 $\{\mathbf{x}_1,\ldots,\mathbf{x}_k\}$ ， $k\le n$ ，所生成的循環子空間的和 (這些子空間可能有交集) 充滿整個 $\mathbb{C}^n$ ，即 $\mathcal{X}_1+\cdots+\mathcal{X}_k=\mathbb{C}^n$ ，使用上述證明方法亦可推論 $m_1(t),\ldots,m_k(t)$ 的最小公倍式 $f(t)$ 等於 $m_A(t)$ 。這個改進性質可大大減少求解最小多項式的計算量。

最後以先前的例子展示計算過程。我們設計一個便於閱讀和計算的簿記方式：將 $A$ 和向量序列 $\mathbf{x}_i, A\mathbf{x}_i,\ldots$ 合併成一增廣矩陣。設 $\mathbf{x}_1=(1,0,0,0)^T$ ，

$\begin{bmatrix} A&\vline&\mathbf{x}_1&A\mathbf{x}_1&A^2\mathbf{x}_1&A^3\mathbf{x}_1 \end{bmatrix}=\left[\!\!\begin{array}{rccrccrrr} 1&1&0&-2&\vline&1&1&3&11\\ -2&1&3&2&\vline&0&-2&-8&-24\\ 0&1&1&-2&\vline&0&0&2&10\\ -2&0&3&3&\vline&0&-2&-8&-24 \end{array}\!\!\right]$ 。

因為 $(A^3-5A^2+8A-4I)\mathbf{x}_1=\mathbf{0}$ ，可得 $\mathcal{X}_1=\mathrm{span}\{\mathbf{x}_1,A\mathbf{x}_1,A^2\mathbf{x}_1\}$ 且 $m_1(t)=t^3-5t^2+8t-4=(t-1)(t-2)^2$ 。挑選新種子 $\mathbf{x}_2=(0,1,0,0)^T\notin\mathcal{X}_1$ ，

$\begin{bmatrix} A&\vline&\mathbf{x}_2&A\mathbf{x}_2&A^2\mathbf{x}_2&A^3\mathbf{x}_2 \end{bmatrix}=\left[\!\!\begin{array}{rccrccrrr} 1&1&0&-2&\vline&0&1& 2& 2\\ -2&1&3&2&\vline&1&1& 2& 6\\ 0&1&1&-2&\vline&0&1& 2& 2\\ -2&0&3&3&\vline&0&0& 1& 5 \end{array}\!\!\right]$ 。

因為 $(A^3-5A^2+8A-4)\mathbf{x}_2=\mathbf{0}$ ，可得 $\mathcal{X}_2=\mathrm{span}\{\mathbf{x}_2,A\mathbf{x}_2,A^2\mathbf{x}_2\}$ 且 $m_2(t)=t^3-5t^2+8t-4=(t-1)(t-2)^2$ 。由於 $\mathcal{X}_1+\mathcal{X}_2=\mathbb{C}^4$ ，計算至此停止， $m_1(t)$ 和 $m_2(t)$ 的最小公倍式就是 $A$ 的最小多項式，即得 $m_A(t)=(t-1)(t-2)^2$ 。

8 Responses to 最小多項式的計算方法

張晏誠 says:

04/24/2014 at 11:56 pm

還有個做法

對Pa(t) 做行列運算

做到對角線化

且要求a11 | a22 | a33…….| anan

則ann為最小多項式

這裡要注意

作行列運算元素要從k[t]裡取

- ccjou says:
  
  04/25/2014 at 9:17 am
  
  謝謝，他日我再將invariant factors的作法貼上來。
  
ayl says:

11/22/2014 at 9:21 pm

最后，在循环子空间的例子中，有些地方不太明白：一，如何从 $\begin{bmatrix} A&\vline&\mathbf{x}_1&A\mathbf{x}_1&A^2\mathbf{x}_1&A^3\mathbf{x}_1 \end{bmatrix}$ 得到 $(A^3-5A^2+8A-4I)\mathbf{x}_1=\mathbf{0}$ 。二，如何从 $(A^3-5A^2+8A-4I)\mathbf{x}_1=\mathbf{0}$ 得到 $\mathcal{X}_1=\mathrm{span}\{\mathbf{x}_1,A\mathbf{x}_1,A^2\mathbf{x}_1\}$ 。

- ccjou says:
  
  11/23/2014 at 7:48 pm
  
  目視即可判定 $\mathbf{x}_1,A\mathbf{x}_1,A^2\mathbf{x}_1$ 構成一線性獨立集。考慮加入 $A^3\mathbf{x}_1$ 後的向量集，寫成矩陣形式，再使用基本列運算(初等行變換)化簡至簡約列梯形式(reduced row echelon form)：
  $\begin{bmatrix} 1&1&3&11\\ 0&-2&-8&-24\\ 0&0&2&10\\ 0&-2&-8&-24 \end{bmatrix}\to\begin{bmatrix} 1&1&3&11\\ 0&-2&-8&-24\\ 0&0&2&10\\ 0&0&0&0 \end{bmatrix}\to\begin{bmatrix} 1&0&0&4\\ 0&1&0&-8\\ 0&0&1&5\\ 0&0&0&0 \end{bmatrix}$
  由最末行可知 $A^3\mathbf{x}_1=4\mathbf{x}_1-8A\mathbf{x}_1+5A^2\mathbf{x}_1$ 。這意味 $A^3\mathbf{x}_1\in\text{span}\{\mathbf{x}_1,A\mathbf{x}_1,A^2\mathbf{x}_1\}$ 。上述算法的介紹請見
  https://ccjou.wordpress.com/2010/12/24/%E5%B7%A6%E4%B9%98%E9%82%84%E6%98%AF%E5%8F%B3%E4%B9%98%EF%BC%8C%E9%80%99%E5%B0%B1%E6%98%AF%E5%95%8F%E9%A1%8C%E6%89%80%E5%9C%A8/
  
mwvbx says:

07/21/2018 at 5:54 pm

最近重新学习线代，看到Jordan标准型理论有点昏头，想问老师几个问题。
1循环子空间为什么叫这个名字呢？–假如x的循环子空间以x Ax A^2x为基，那么确实有x映射到Ax, Ax射向A^2x，但是A^2x并不射向x，并没有构成循环啊？所以这个循环到底体现在哪儿呢？
2最小多项式的提出有什么意义呢？–当我学了特征多项式的cayley-hamilton定理，我觉得很开心，居然还有这样的规律，但是随之就引入了最小多项式的概念，摸不着头脑，都有特征多项式这么好的东西了，到底为什么要引入这个神秘又不好找的最小多项式呢？
3Jordan标准型理论，原来的一脸懵逼，看过老师的几篇文章有点感觉了，但是好像有些东西没介绍到。我看的书是这样建立Jordan标准型理论的，引入根子空间与广义特征向量，随即建立空间第一分解理论(V可以分解为所有特征值的根子空间的直和)；然后引入循环子空间，并建立空间第二分解理论(根子空间可以分解为循环子空间的直和)。证明过程晦涩难懂，我有点吃不消，我想知道这两个分解定理怎么从几何上去理解呢？
如能回复，不胜感激！

Zekui Jia says:

11/28/2018 at 10:57 am

第三种循环子空间方法的第二段“设k为最小正整数使\{\mathbf{x},A\mathbf{x},\ldots,A^{k-1}\mathbf{x}\}是线性独立集”，这里的k是否应该是最大整数使其线性独立呢？

林立人 says:

04/13/2021 at 1:42 am

剛讀完了最小多項式三部曲，真是感恩。這頁有一個小錯誤，有一個「最小公因式」應改為「最小公倍式」，搜尋一下就可找到。

- ccjou says:
  
  04/13/2021 at 9:36 pm
  
  謝謝, 已訂正。

	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨
	jeff85898 on 利用分塊矩陣證明 det(AB)=(det A)(det…