最小多項式的計算方法

本文的閱讀等級:高級

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) 定義

Am 個相異特徵值 \lambda_1,\ldots,\lambda_mm\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_ir_1+\cdots+r_m 有最小值。明顯地,m_A(t) 整除 p_A(t)。根據定義,我們可以設計一個簡易的最小多項式算法:先求出特徵多項式 p_A(t)、特徵值 \lambda_i 和重數 \beta_ii=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)^kk=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}_im_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}_ij=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^jm_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

Advertisements
本篇發表於 線性代數專欄, 典型形式 並標籤為 , , , , , 。將永久鏈結加入書籤。

4 則回應給 最小多項式的計算方法

  1. 張晏誠 說道:

    還有個做法

    對Pa(t) 做行列運算

    做到對角線化

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

    則ann為最小多項式

    這裡要注意

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

  2. ayl 說道:

    最后,在循环子空间的例子中,有些地方不太明白:一,如何从 \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\}

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s