最小多項式 (上)

本文的閱讀等級：中級

給定一 $k$ 次多項式

$p(t)=a_kt^k+a_{k-1}t^{k-1}+\cdots+a_1t+a_0$

對於任意 $n$ 階方陣 $A$ ，我們可定義下列矩陣多項式：

$p(A)=a_kA^k+a_{k-1}A^{k-1}+\cdots+a_1A+a_0I$

多項式和矩陣之間存在重要的關係，這種關係表現在矩陣的消滅多項式 (annihilating polynomial)，亦即 $p(t)$ 使得 $p(A)=0$ 。線性代數學者最常碰到的多項式就是方陣 $A$ 的特徵多項式 $p_A(t)=\mathrm{det}(tI-A)$ ，我們不免好奇：特徵多項式 $p_A(t)$ 是否會消滅 $A$ ？答案是肯定的， $p_A(A)=0$ ，這個結果稱作 Cayley-Hamilton 定理 (證明見“Cayley-Hamilton 定理”和“Cayley-Hamilton 定理的一個代數證明方法”)。除了特徵多項式，還有其他可消滅方陣 $A$ 的多項式，最小多項式 (minimal polynomial) 是其中最特別的一個。

既然 $n$ 次特徵多項式 $p_A(t)$ 可消滅 $n$ 階方陣 $A$ ，那麼理當存在一個次數 (多項式中次數最高的項的次數即為此多項式的次數) 最小的多項式 $m(t)$ 使得 $m(A)=0$ ，且 $m(t)$ 的次數不大於 $n$ 。如果 $m(A)=0$ ，對於任意 $c$ ，也有 $cm(A)=0$ ，所以我們大可限制多項式最高次項的係數為 $1$ ，稱為首一多項式 (monic polynomial)。顯然，首一多項式不得為零多項式 (所有係數為零)。下面我們討論最小次數的消滅多項式 $m(t)$ 和特徵多項式 $p_A(t)$ 的關係。因為 $m(t)$ 的次數不大於 $p_A(t)$ 的次數，根據歐幾里得算法，就有多項式 $h(t)$ 和 $r(t)$ 滿足

$p_A(t)=m(t)h(t)+r(t)$

其中餘式 $r(t)$ 的次數小於 $m(t)$ 的次數。因為 $p_A(t)$ 和 $m(t)$ 同為 $A$ 的消滅多項式，

$0=p_A(A)=m(A)h(A)+r(A)=0h(A)+r(A)=r(A)$

得知 $r(A)=0$ 。如果 $r(t)$ 不為零多項式，將 $r(t)$ 的最高次項正規化即可得到次數比 $m(t)$ 的次數還小的首一消滅多項式，這與 $m(t)$ 次數最小的假設相矛盾，所以推論 $r(t)$ 為零多項式， $m(t)$ 整除 $p_A(t)$ 。如果存在兩個次數相同的首一多項式可消滅 $A$ ，按照上面的方法推知兩式可彼此整除，又因為兩式次數相同且首項係數都為 $1$ ，故可推斷兩式完全相同，也就證明了方陣 $A$ 的最小次數首一消滅多項式是唯一存在的，以下記作 $m_A(t)$ ，稱為最小多項式。

相似矩陣有相同的特徵多項式，事實上，相似矩陣也有相同的最小多項式。證明於下。設方陣 $A$ 相似於 $B$ ，也就有可逆矩陣 $S$ ，使得 $A=SBS^{-1}$ ，不難驗證 (見“就是要相似”)

$m_B(A)=m_B(SBS^{-1})=Sm_B(B)S^{-1}=0$

上式指出 $m_B(t)$ 可消滅 $A$ ，且其次數不小於 $A$ 的最小多項式 $m_A(t)$ 的次數。另一方面， $B=S^{-1}AS$ ，同樣也可以推得 $m_A(t)$ 可消滅 $B$ ，且其次數不小於 $m_B(t)$ 的次數。所以， $m_A(t)$ 和 $m_B(t)$ 的次數相同，而且兩者皆可消滅 $A$ 和 $B$ ，然而，消滅多項式是唯一的，也就證得 $m_A(t)=m_B(t)$ 。

既然最小多項式 $m_A(t)$ 整除特徵多項式 $p_A(t)$ ， $m_A(t)$ 的根當然也是 $p_A(t)$ 的根，但是 $p_A(t)$ 的根也都是 $m_A(t)$ 的根嗎？設方陣 $A$ 有特徵值 $\lambda$ ，對應的特徵向量為 $\mathbf{x}\neq\mathbf{0}$ ，設 $m_A(t)=t^k+a_{k-1}t^{k-1}+\cdots+a_1t+a_0$ ，利用性質 $A^r\mathbf{x}=\lambda^r\mathbf{x}$ ， $r\ge 1$ ，計算

$\begin{aligned} m_A(A)\mathbf{x}&=(A^{k}+a_{k-1}A^{k-1}+\cdots+a_1A+a_0I)\mathbf{x}\\ &=(\lambda^k+a_{k-1}\lambda^{k-1}+\cdots+a_1\lambda+a_0)\mathbf{x}=m_A(\lambda)\mathbf{x}\end{aligned}$

因為 $m_A(A)=0$ ，得知 $m_A(\lambda)=0$ ，方陣 $A$ 的特徵值 $\lambda$ 確實是最小多項式的根。這個結果告訴我們如果 $n$ 次特徵多項式 $p_A(t)$ 有 $m\le n$ 個相異根， $p_A(t)$ 可完全分解如下：

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

其中 $\beta_i$ 為對應特徵值 $\lambda_i$ 的相重數， $1\le\beta_i\le n$ ， $\beta_1+\cdots+\beta_m=n$ 。最小多項式必定具有以下型態：

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

其中對於所有 $i$ ， $1\le r_i\le\beta_i$ 。見下例，

$A=\begin{bmatrix} 2&1&0&0\\ 0&2&0&0\\ 0&0&1&1\\ 0&0&-2&4 \end{bmatrix}$

的特徵多項式為 $p_A(t)=(t-3)(t-2)^3$ ，最小多項式 $m_A(t)=(t-3)^{r_1}(t-2)^{r_2}$ 有最小次數 $r_1+r_2$ 使得 $m_A(A)=0$ 。依序設 $(r_1,r_2)=(1,1)$ ， $(1,2)$ ， $(1,3)$ ，將 $A$ 代入計算，細節從略，得到 $(A-3I)(A-2I)\neq 0$ ，而 $(A-3I)(A-2I)^2=0$ ，故 $m_A(t)=(t-3)(t-2)^2$ 。這個逐一檢查方法必須先將特徵多項式的因式分解出來，因此僅適用於計算小尺寸矩陣。

方陣的最小多項式和 Jordan 典型形式有著密切的關係，Jordan 形式可以用來計算最小多項式；相反的，由最小多項式也可以判斷 Jordan 形式的結構 (最大尺寸的 Jordan 分塊)，進而發展出可對角化矩陣的檢查條件，這部份將留待日後另文說明。

繼續閱讀：

最小多項式 (下)

6 Responses to 最小多項式 (上)

levinc says:

12/11/2010 at 7:38 pm

老師老師，（下）呢？ (意猶未盡催稿XDD)

ccjou says:

12/11/2010 at 8:45 pm

呵呵－
寫好了，星期一再貼吧
週六是 jazz time 人很懶

請問 says:

12/12/2010 at 12:39 am

假設Pa(t)=(t-3)(t-2)^3
那minimal polynomial為什麼不能單取(t-3)或單取(t-2)^2
而得用到所有的特徵值呢？

謝謝

ccjou says:

12/12/2010 at 5:53 pm

上文有一段提到矩陣 $A$ 的每一個特徵值 $\lambda$ 都是最小多項式的一根。我們論證出 $m_A(A)\mathbf{x}=m_A(\lambda)\mathbf{x}$ ，因為 $m_A(A)=0$ ，得知一定有 $m_A(\lambda)=0$ 。故 $m_A(t)$ 就不可能有 $(t-3)$ 或 $(t-2)^2$ 的情況。

- 延伸寸 says:
  
  09/22/2012 at 9:43 pm
  
  那 (r1,r2)=(1,1) or (1,2) or (1,3), 只能一個一個試嗎？ 98交大應數建模與科學計算碩士班入學考第9題是一個 4X4 的矩陣，特徵多項式尚可用點技巧求得 (x^2)(x-1)^2，但最小多項式就傻眼了。一個一個試？哪有那麼多時間？
  
  - ccjou says:
    
    09/23/2012 at 6:29 pm
    
    確實還有別的方法：計算每一相異特徵值的指標 (index)，也就是最大Jordan分塊的階數，見“最小多項式(下)”
    https://ccjou.wordpress.com/2010/12/13/%E6%9C%80%E5%B0%8F%E5%A4%9A%E9%A0%85%E5%BC%8F-%E4%B8%8B/
    本文例子特徵多項式是 $(t-3)(t-2)^3$ ，故最小多項式一定如 $(t-3)(t-2)^r$ ，其中 $r$ 即是 $\lambda=2$ 的指標，計算得到
    $\mathrm{rank}(A-2I)=2$
    $\mathrm{rank}(A-2I)^2=1$
    $\mathrm{rank}(A-2I)^3=1$
    當第一次發生 $\mathrm{rank}(A-2I)^k=\mathrm{rank}(A-2I)^{k+1}$ ，則 $k$ 即為指標，故最小多項式是 $(t-3)(t-2)^2$ 。
    關於指標的詳細計算過程見
    https://ccjou.wordpress.com/2010/11/17/jordan-%E5%BD%A2%E5%BC%8F%E5%A4%A7%E8%A7%A3%E8%AE%80-%E4%B8%8B/

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨