Jordan 形式大解讀 (下)

Posted on 11/17/2010 by ccjou

本文的閱讀等級：高級

前文“Jordan 形式大解讀(上)”說明了 Jordan 矩陣 $J$ 蘊含的矩陣特徵訊息，本文將利用這些結果設計一個 Jordan 典型形式計算法。考慮以下問題：給定一 $n\times n$ 階矩陣 $A$ ，試求一 $n$ 階可逆矩陣 $M$ 使得 $A=MJM^{-1}$ ，其中 $J$ 為 Jordan 矩陣。我們假設已經得知 $A$ 的所有相異特徵值 $\lambda_i$ ， $i=1,\ldots,k$ ，但各個特徵值的相重數可以是未知的。下面介紹的演算法分為兩階段：先解出 Jordan 矩陣 $J$ ，再推算相似變換矩陣 $M$ 。

Jordan 矩陣 $J$ 由對應相異特徵值 $\lambda_i$ 的超級 Jordan 分塊 $J(\lambda_i)$ 的直和構成：

$\displaystyle J=J(\lambda_1)\oplus J(\lambda_2)\oplus\cdots\oplus J(\lambda_k)=\bigoplus_{i=1}^k J(\lambda_i)$

其中 $\beta_i\times\beta_i$ 階超級 Jordan 分塊 $J(\lambda_i)$ 的結構完全由 $\mathrm{rank}(J(\lambda_i)-\lambda_iI_{\beta_i})^p$ 決定， $p=1,2,\ldots,\beta_i$ ，第一階段的任務是設法從矩陣 $A$ 得到上述資訊。由相似變換 $A=MJM^{-1}$ 可知 $A-\lambda I=M(J-\lambda I)M^{-1}$ ，接著推得

$(A-\lambda I)^p=(M(J-\lambda I)M^{-1})^p=M(J-\lambda I)^pM^{-1}$

上式表明冪矩陣 $(A-\lambda I)^p$ 相似於 $(J-\lambda I)^p$ ，由於相似變換不改變矩陣秩，於是有 $\mathrm{rank}(A-\lambda I)^p=\mathrm{rank}(J-\lambda I)^p$ 。接下來的問題是超級 Jordan 分塊秩 $\mathrm{rank}(J(\lambda_i)-\lambda_i I_{\beta_i})^p$ 和 Jordan 矩陣秩 $\mathrm{rank}(J-\lambda_i I)^p$ 之間有什麼關係？考慮這個 $J$ 矩陣的直和表達式：

$\displaystyle J-\lambda_{i}I=\bigoplus_{j=1}^k J(\lambda_j)-\bigoplus_{j=1}^k \lambda_i I_{\beta_j}=\bigoplus_{j=1}^k(J(\lambda_j)-\lambda_i I_{\beta_j})$

直和的冪矩陣同樣也可表示為直和形式：

$\displaystyle (J-\lambda_i I)^p=\bigoplus_{j=1}^k(J(\lambda_j)-\lambda_i I_{\beta_j})^p$

明顯地，矩陣直和的秩等於各分塊秩之和：

$\mathrm{rank}(A\oplus B)=\mathrm{rank}\begin{bmatrix} A&0\\ 0&B \end{bmatrix}=\mathrm{rank}A+\mathrm{rank}B$

因此斷定

$\displaystyle \mathrm{rank}(J-\lambda_{i}I)^p=\sum_{j=1}^k\mathrm{rank}(J(\lambda_j)-\lambda_{i}I_{\beta_j})^p$

當 $j\neq i$ ， $(J(\lambda_j)-\lambda_{i}I_{\beta_j})^p$ 的主對角元皆不為零，也就是說，對於任意 $p$ ， $(J(\lambda_j)-\lambda_iI_{\beta_j})^p$ 都是滿秩的， $\mathrm{rank}(J(\lambda_j)-\lambda_{i}I_{\beta_j})^p=\beta_j$ 。因為 $\beta_1+\beta_2+\cdots+\beta_k=n$ ，可得

$r_p(\lambda_i)\equiv\mathrm{rank}(J-\lambda_{i}I)^p=n-\beta_i+\mathrm{rank}(J(\lambda_i)-\lambda_{i}I_{\beta_i})^p$

並定義 $r_0(\lambda_i)=n$ 。縱使我們不確知 $\beta_i$ ，由上式仍然可以算出矩陣秩差額，如下：

$\begin{aligned} d_p(\lambda_i)&=\mathrm{rank}(J(\lambda_i)-\lambda_{i}I_{\beta_i})^{p-1}-\mathrm{rank}(J(\lambda_i)-\lambda_{i}I_{\beta_i})^p\\ &=r_{p-1}(\lambda_i)-r_p(\lambda_i),~~ p=1,2,\ldots\end{aligned}$

對應特徵值 $\lambda_i$ ， $p\times p$ 階基本 Jordan 分塊的個數即為

$b_p(\lambda_i)\equiv d_p(\lambda_i)-d_{p+1}(\lambda_i),~~p=1,2,\ldots$

我們用一個例子展示 Jordan 形式 $J$ 的計算過程。考慮這個 $5$ 階方陣 (取自“Jordan 典型形式淺說(下)”)

$A=\begin{bmatrix} 8&0&0&8&8\\ 0&0&0&8&8\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&8 \end{bmatrix}$

上三角矩陣 $A$ 的主對角元即為特徵值， $A$ 有兩相異特徵值 $\lambda_1=8$ ， $\lambda_2=0$ ，因此 Jordan 矩陣 $J$ 由兩個超級 Jordan 分塊的直和構成：

$J=\begin{bmatrix} J(8)&0\\ 0&J(0) \end{bmatrix}$

首先計算 $r_p(8)=\mathrm{rank}(A-8I)^p$ 和 $r_p(0)=\mathrm{rank}(A-0I)^p$ ，從 $p=1$ 開始，直到 $r_p(\lambda_i)=r_{p+1}(\lambda_i)$ ，如下：

$\lambda_1=8$ ：

$\begin{aligned} r_0(8)&\equiv 5\\ r_1(8)&=\mathrm{rank}(A-8I)=4\\ r_2(8)&=\mathrm{rank}(A-8I)^2=3\\ r_3(8)&=\mathrm{rank}(A-8I)^3=3\end{aligned}$

$\lambda_2=0$ ：

$\begin{aligned} r_0(0)&\equiv 5\\ r_1(0)&=\mathrm{rank}(A-0I)=3\\ r_2(0)&=\mathrm{rank}(A-0I)^2=2\\ r_3(0)&=\mathrm{rank}(A-0I)^3=2\end{aligned}$

冪矩陣秩 $r_p(\lambda_i)$ 停止改變表示 $\mathrm{rank}(J(\lambda_i)-\lambda_i I_{\beta_i})^p=0$ ，此 $p$ 值即為 $\lambda_i$ 的指標，亦即最大的基本 Jordan 分塊尺寸，本例中， $\lambda_1=8$ 的指標為 $2$ ， $\lambda_2=0$ 的指標也為 $2$ 。接著分別就各特徵值計算矩陣秩差額：

$\lambda_1=8$ ：

$\begin{aligned} d_1(8)&=r_0(8)-r_1(8)=5-4=1\\ d_2(8)&=r_1(8)-r_2(8)=4-3=1\\ d_3(8)&=r_2(8)-r_3(8)=3-3=0\end{aligned}$

$\lambda_2=0$ ：

$\begin{aligned} d_1(0)&=r_0(0)-r_1(0)=5-3=2\\ d_2(0)&=r_1(0)-r_2(0)=3-2=1\\ d_3(0)&=r_2(0)-r_3(0)=2-2=0\end{aligned}$

最後算出所有特徵值所含的各尺寸基本 Jordan 分塊數：

$\lambda_1=8$ ：

$\begin{aligned} b_1(8)&=d_1(8)-d_2(8)=1-1=0\\ b_2(8)&=d_2(8)-d_3(8)=1-0=1\end{aligned}$

$\lambda_2=0$ ：

$\begin{aligned} b_1(0)&=d_1(0)-d_2(0)=2-1=1\\ b_2(0)&=d_2(0)-d_3(0)=1-0=1\end{aligned}$

結論：對應 $\lambda_1=8$ 僅存在 $1$ 個 $2\times 2$ 基本分塊， $\lambda_2=0$ 有 $1$ 個 $1\times 1$ 基本分塊和 $1$ 個 $2\times 2$ 基本分塊，所以超級 Jordan 分塊分別是

$J(8)=\begin{bmatrix} 8&1\\ 0&8 \end{bmatrix},~ J(0)=\begin{bmatrix} 0&1\\ 0&0 \end{bmatrix}\oplus\begin{bmatrix} 0 \end{bmatrix}=\begin{bmatrix} 0&1&0\\ 0&0&0\\ 0&0&0 \end{bmatrix}$

Jordan 矩陣 $J$ 即為

$J=\begin{bmatrix} J(8)&0\\ 0&J(0) \end{bmatrix}=\begin{bmatrix} 8&1&\vline&0&0&0\\ 0&8&\vline &0&0&0\\\hline 0&0&\vline &0&1&0\\ 0&0&\vline &0&0&0\\ 0&0&\vline&0&0&0 \end{bmatrix}$

一旦得到了 Jordan 矩陣 $J$ ，我們便可利用它來推算相似變換矩陣 $M$ 。暫時只考慮對應特徵值 $\lambda$ 的一個 $m\times m$ 階基本分塊 $J_{\ast}(\lambda)$ ，主要關係式 $AM=MJ$ 具有下列形式：

$A\begin{bmatrix} \cdots&\mathbf{x}_1&\cdots&\mathbf{x}_m&\cdots \end{bmatrix}=\begin{bmatrix} \cdots&\mathbf{x}_1&\cdots&\mathbf{x}_m&\cdots \end{bmatrix}\begin{bmatrix} \ddots&~&~\\ ~&J_{\ast}(\lambda)&~\\ ~&~&\ddots \end{bmatrix}$

其中我們令矩陣 $M$ 對應基本分塊 $J_{\ast}(\lambda)$ 的行向量為 $\mathbf{x}_1,\ldots,\mathbf{x}_m$ ，去除其他不相關的部分可得

$A\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_m \end{bmatrix}=\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_m \end{bmatrix}\begin{bmatrix} \lambda&1&~&~\\ ~&\ddots&\ddots&~\\ ~&~&\ddots&1\\ ~&~&~&\lambda \end{bmatrix}$

展開矩陣乘積導出下列 $m$ 個方程式，依序解出 $\mathbf{x}_1,\ldots,\mathbf{x}_m$ ：

$\begin{aligned} A\mathbf{x}_1=\lambda\mathbf{x}_1~~&\Rightarrow~~(A-\lambda I)\mathbf{x}_1=\mathbf{0}\\ A\mathbf{x}_2=\mathbf{x}_1+\lambda\mathbf{x}_2~~&\Rightarrow~~(A-\lambda I)\mathbf{x}_2=\mathbf{x}_1\\ A\mathbf{x}_3=\mathbf{x}_2+\lambda\mathbf{x}_3~~&\Rightarrow~~(A-\lambda I)\mathbf{x}_3=\mathbf{x}_2\\ &\vdots\\ A\mathbf{x}_m=\mathbf{x}_{m-1}+\lambda\mathbf{x}_m~~&\Rightarrow~~(A-\lambda I)\mathbf{x}_m=\mathbf{x}_{m-1}\end{aligned}$

注意 $\mathbf{x}_1$ 就是對應 $\lambda$ 的特徵向量，而 $\mathbf{x}_2,\mathbf{x}_3,\ldots,\mathbf{x}_m$ 則為廣義特徵向量，這些向量滿足 $(A-\lambda I)^p\mathbf{x}_p=\mathbf{0}$ ， $p=1,\ldots,m$ 。

回到我們的例子，寫出

$\begin{aligned} AM&=A\begin{bmatrix} \mathbf{x}_1&\mathbf{x}_2&\mathbf{x}_3&\mathbf{x}_4&\mathbf{x}_5 \end{bmatrix}=MJ=\begin{bmatrix} \mathbf{x}_1&\mathbf{x}_2&\mathbf{x}_3&\mathbf{x}_4&\mathbf{x}_5 \end{bmatrix}\begin{bmatrix} 8&1&0&0&0\\ 0&8&0&0&0\\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{bmatrix}\end{aligned}$

廣義特徵向量的標準算法略為複雜 (見“Jordan 型式大解讀之尋找廣義特徵向量”)，不過小型矩陣則相對容易計算。將上式乘開，爲了解出 $\mathbf{x}_4$ ，選擇 $\mathbf{x}_3\in C(A-0I)\cap N(A-0I)$ ，結果如下：

$\begin{aligned} A\mathbf{x}_1=8\mathbf{x}_1~~&\Rightarrow~~\mathbf{x}_1=(8,0,0,0,0)^T\\ A\mathbf{x}_2=\mathbf{x}_1+8\mathbf{x}_2~~&\Rightarrow~~\mathbf{x}_2=(0,1,0,0,1)^T\\ A\mathbf{x}_3=0\mathbf{x}_3~~&\Rightarrow~~\mathbf{x}_3=(0,8,0,0,0)^T\\ A\mathbf{x}_4=\mathbf{x}_3+0\mathbf{x}_4~~&\Rightarrow~~\mathbf{x}_4=(-1,0,0,1,0)^T\\ A\mathbf{x}_5=0\mathbf{x}_5~~&\Rightarrow~~\mathbf{x}_5=(0,0,1,0,0)^T\end{aligned}$

即得到相似變換矩陣

$M=\left[\!\!\begin{array}{cccrc} 8&0&0&-1&0\\ 0&1&8&0&0\\ 0&0&0&0&1\\ 0&0&0&1&0\\ 0&1&0&0&0 \end{array}\!\!\right]$

最後我們將推演出的 Jordan 形式算法整理於下：

求出 $A$ 的所有相異特徵值 $\lambda_i$ ， $i=1,\ldots,k$ ，如果可能的話直接解出特徵多項式的根。提醒讀者，這是最麻煩的計算步驟。
針對 $A$ 的每個相異特徵值 $\lambda_i$ ，計算 $\mathrm{rank}(A-\lambda_iI)^p$ ， $p=1,2,\ldots$ ，直到矩陣秩不改變為止，分析計算結果可得超級 Jordan 分塊 $J(\lambda_i)$ ，它們的直和即為 Jordan 矩陣 $J$ 。
就 $A$ 的每個相異特徵值 $\lambda_i$ ，根據步驟 (2) 得到的超級 Jordan 分塊 $J(\lambda_i)$ 解出對應各基本 Jordan 分塊的特徵向量和廣義特徵向量，相似變換矩陣 $M$ 即由這些向量組成。

理論上，上述 Jordan 形式算法適用於任意 $n\times n$ 階矩陣 $A$ ，但我們並不建議將此法應用於數值計算，理由是 Jordan 形式在本質上是一個數值不穩定結構。舉例來說， $A=\begin{bmatrix} \epsilon&0\\ 1&0 \end{bmatrix}$ ， $\epsilon\neq 0$ ，則 $A=MJM^{-1}$ ，其中 $M=\begin{bmatrix} 0&\epsilon\\ 1&1 \end{bmatrix}$ ， $J=\begin{bmatrix} 0&0\\ 0&\epsilon \end{bmatrix}$ 。當 $\epsilon\rightarrow 0$ ， $A\rightarrow\begin{bmatrix} 0&0\\ 1&0 \end{bmatrix}=B$ ， $J\rightarrow\begin{bmatrix} 0&0\\ 0&0 \end{bmatrix}$ ，然而零矩陣並非 $B$ 的 Jordan 矩陣， $B$ 的轉置即為其 Jordan 矩陣。Jordan 形式之所以不具數值穩定性的原因在於矩陣秩 $\mathrm{rank}A$ 不為 $A$ 的連續函數，例如， $A=\begin{bmatrix} \epsilon&0\\ 0&1 \end{bmatrix}$ ，當 $\epsilon\neq 0$ ， $\mathrm{rank}A=2$ ，但若 $\epsilon=0$ ，則 $\mathrm{rank}A=1$ 。不連續的矩陣秩可能引發災難，我們看到矩陣 $A$ 各元的極小擾動量便足以造成 Jordan 矩陣 $J$ 的劇烈變動，很不幸，這是 Jordan 形式與生俱來無可逃避的宿命。

縱使就數值應用而言，Jordan 形式沒有任何實用價值，但它還是一個好用的矩陣理論分析利器。如果我們想要證明某類型的矩陣具備一些特殊的性質，可以先從形式較簡單可對角化矩陣著手，之後再繼續延伸至 Jordan 矩陣與其相似矩陣。譬如，證明 $A$ 相似於 $A^T$ 的最便捷方式即是透過兩者擁有相同的 Jordan 形式 (參閱“矩陣與其轉置的相似性”)。

繼續閱讀：

Jordan 型式大解讀之尋找廣義特徵向量

This entry was posted in 線性代數專欄, 典型形式 and tagged Jordan 典型形式, 分塊矩陣, 廣義特徵向量. Bookmark the permalink.

11 Responses to Jordan 形式大解讀 (下)

levinc says:

12/11/2010 at 4:49 am

一個小地方不甚明白:
Jordan 形式之所以不具數值穩定性的原因在於矩陣秩rank(A)不為A的連續函數.

可以請老師再說明清楚一點嗎？謝謝喔

Reply
ccjou says:

12/11/2010 at 9:26 am

我應該這樣說：矩陣 $A$ 的 Jordan form $J$ 未必是 $A$ 各元 $a_{ij}$ 的連續函數，如上面的例子所顯示的那樣。

然後，我應該再說：本文以計算 $\mathrm{rank}(A-\lambda I)^p$ 方式求得 $J$ 矩陣的演算法不具備數值穩定性，因為 $\mathrm{rank}A$ 不是一個連續函數， $\mathrm{rank}(A)$ 可能因為受到微小擾動而產生大改變。

MATLAB 計算 Jordan form 的指令說明如下：
http://www.mathworks.com/help/toolbox/symbolic/jordan.html

J = jordan(A) computes the Jordan canonical (normal) form of a symbolic or numeric matrix A. The Jordan form of a numeric matrix is extremely sensitive to numerical errors. To compute Jordan canonical form of a matrix, represent the elements of the matrix by integers or ratios of small integers, if possible.

Reply
ayl says:

11/20/2014 at 12:12 am

上篇所讲“超级块 $J(0)$ 每增加一次幂损失的矩阵秩，恰好等于阶数大于或等于 p 的基本Jordan 分块总数”不甚了解。此讲中演算得出的 $J-\lambda I$ 每增加一次幂所损失的矩阵秩可以用对应的超级块来计算，但这算出来的值又如何与某个超级快 $J(\lambda_i)-\lambda_i I$ 的具体分块方式有联系呢，毕竟一个是 $J$ 而另一个 $J(\lambda_i)$ ？

Reply
- ccjou says:
  
  11/20/2014 at 8:14 am
  
  我將你的迴響編輯過以正確顯示LaTeX，方法是在 $J(0)$ 的第一個$後面加入latex和一個空格。
  
  Jordan form $J$ 可以表示為超級Jordan 分塊 $J(\lambda_i)$ 的直和，因此解析過程是針對每一個特徵值 $\lambda_i$ ，找出 $J(\lambda_i)$ 的基本分塊結構。而後者可由冪零矩陣 $\text{rank}(J(\lambda_i)-\lambda_iI)^p$ 算得(過程如上文(3)Jordan 分塊所述，有些複雜，你可能要多讀幾遍)，關鍵式：
  
  $\displaystyle \text{rank}(J-\lambda_{i}I)^p=\sum_{j=1}^k\mathrm{rank}(J(\lambda_j)-\lambda_{i}I_{\beta_j})^p$
  
  但 $A-\lambda_iI$ 相似於 $J-\lambda_iI$ ，因此我們可以直接從 $A$ 推導出超級Jordan 分塊 $J(\lambda_i)$ 。
  
  Reply
  - ayl says:
    
    11/20/2014 at 10:09 am
    
    可能我是学习软件工程，而非数学专业，所以有些吃力。又看几遍后，这是我的理解思路，我将整个过程调整了顺序，老师您看看对不对：一，正如上篇所讲，超级块 $J(\lambda_i)$ 结构可由对应的矩阵 $J(\lambda_i)-\lambda_i I$ 相邻幂之间的矩阵秩差值求得。二，通过演算发现 $J(\lambda_i)-\lambda_i I$ 的矩阵秩的差值可由矩阵J的差值表示，而不需要知道具体每个超级块大小，（当然这也是因为我们无法知道J，所以无法知道每个超级块形状，否则直接就可以算超级块的矩阵秩差值）也就是结论 $d_p(\lambda_i)=r_{p-1}(\lambda_i)-r_p(\lambda_i)$ 。三，由于我们不知道矩阵J，然而却可以根据相似，通过原始矩阵A来求得矩阵J的秩。
    
    Reply
  - ayl says:
    
    11/20/2014 at 10:12 am
    
    不好意思，第一次公式没能显示，再写一次。可能我是学习软件工程，而非数学专业，所以有些吃力。又看几遍后，这是我的理解思路，我将整个过程调整了顺序，老师您看看对不对：一，正如上篇所讲，超级块 $J(\lambda_i)$ 结构可由对应的矩阵 $J(\lambda_i)-\lambda_i I$ 相邻幂之间的矩阵秩差值求得。二，通过演算发现 $J(\lambda_i)-\lambda_i I$ 的矩阵秩的差值可由矩阵J的差值表示，而不需要知道具体每个超级块大小，（当然这也是因为我们无法知道J，所以无法知道每个超级块形状，否则直接就可以算超级块的矩阵秩差值）也就是结论 $d_p(\lambda_i)=r_{p-1}(\lambda_i)-r_p(\lambda_i)$ 。三，由于我们不知道矩阵J，然而却可以根据相似，通过原始矩阵A来求得矩阵J的秩。
    
    Reply
    - ccjou says:
      
      11/20/2014 at 10:15 am
      
      總結得很清楚，完全正確。
      
      Reply
  - ayl says:
    
    11/20/2014 at 10:16 am
    
    可能我还是没能弄对，latex公式好像只能显示第一个，其他的不能显示，如您所说在$xxxx$的第一个$后加latex和空格，其他不变。
    
    Reply
    - ccjou says:
      
      11/20/2014 at 10:18 am
      
      你將 \lambda 打成 \lamda 了。
      
      Reply
juangamber says:

09/28/2015 at 1:40 pm

請問一下
有一矩陣A，J為A的jordan form
則有一可逆矩陣P使P^(-1)AP=J
而這個可逆矩陣唯一嗎
謝謝

Reply
- ccjou says:
  
  09/28/2015 at 2:24 pm
  
  如果不考慮Jordan分塊的排序， $J$ 是唯一的，但 $P$ 不是唯一的，表面的例子如 $(2P)^{-1}A(2P)=P^{-1}AP=J$ ，底層的原因比較複雜，見下文例子的步驟三：
  https://ccjou.wordpress.com/2011/02/14/jordan-%E5%BD%A2%E5%BC%8F%E5%A4%A7%E8%A7%A3%E8%AE%80%E4%B9%8B%E5%B0%8B%E6%89%BE%E5%BB%A3%E7%BE%A9%E7%89%B9%E5%BE%B5%E5%90%91%E9%87%8F/
  
  Reply

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