運用等價問題來解題

本文的閱讀等級:高級

解題的最初過程多半會經過以下步驟:收集資訊,探索並深入了解,藉由猜測和分析找出關聯或模式。不過如果計算過於複雜或者問題本身沒有透露一些可供啟發的訊息,那該怎麼辦呢?本文介紹一個有效的解題方法──將問題改寫為另一個形式較簡單的等價問題。然而,改寫問題並不存在一套標準作法,通常需要仰賴個人的想像力與洞察力;縱使如此,透過適當練習仍可增進改寫問題的能力。一個問題常存在多種解法,並且各自有不同的探索途徑,所以我們要避免注意力過份狹窄。反過來說,天下沒有「一招半式闖江湖」這回事,死抱不放過去熟知的算法與技巧是也有害的,故應盡量保持彈性,見機行事見招拆招。下面我以一個計算問題為例說明運用等價問題來解題的實現過程。

 
T 為定義於 \mathbb{C}^4 的線性變換,若

T\begin{bmatrix}    0\\    1\\    1\\    1    \end{bmatrix}=\begin{bmatrix}    0\\    1\\    1\\    1    \end{bmatrix},~ T\begin{bmatrix}    1\\    0\\    1\\    1    \end{bmatrix}=\begin{bmatrix}    -2\\    -6\\    -6\\    -4    \end{bmatrix},~ T\begin{bmatrix}    1\\    1\\    0\\    1    \end{bmatrix}=\begin{bmatrix}    -0\\    -6\\    -6\\    -3    \end{bmatrix},~ T\begin{bmatrix}    1\\    1\\    1\\    0    \end{bmatrix}=\begin{bmatrix}    1\\    3\\    3\\    2    \end{bmatrix}

T 的 Jordan 形式(取自台大數研所2010年入學試題)。

 
先以 4\times 4 階矩陣 A 表示線性變換 T,合併以上方程式即得 AB=C,其中

B=\begin{bmatrix}    0&1&1&1\\    1&0&1&1\\    1&1&0&1\\    1&1&1&0    \end{bmatrix}.~ C=\left[\!\!\begin{array}{crrc}    0&-2&0&1\\    1&-6&-6&3\\    1&-6&-6&3\\    1&-4&-3&2    \end{array}\!\!\right]

我們的問題是計算 A 的 Jordan 形式。這個問題看似平淡無奇,只要算出 A=CB^{-1},再將 A 套入 Jordan 形式的標準演算法即可(參閱“Jordan 形式大解讀(下)”)。不過眼前還有另一個選項,令 D=B^{-1}AB=B^{-1}CD 相似於 A,相似矩陣有相同的 Jordan 形式,故 A 的 Jordan 形式即為 D 的 Jordan 形式。那麼應該選擇 A=CB^{-1}D=B^{-1}C 呢?我們當然希望挑選數值較為簡單或包含許多零元的矩陣。要回答此問題,勢必先求出 B^{-1}

 
在一般情況下,吾人通常使用高斯—約當法來解 B^{-1},不過由於 B 具有特殊型態,我們將它改寫為

B=\begin{bmatrix}    1&1&1&1\\    1&1&1&1\\    1&1&1&1\\    1&1&1&1    \end{bmatrix}-\begin{bmatrix}    1&0&0&0\\    0&1&0&0\\    0&0&1&0\\    0&0&0&1    \end{bmatrix}=-(I-\mathbf{e}\mathbf{e}^T)

其中 \mathbf{e} 的每個元都為 1。注意 I-\mathbf{e}\mathbf{e}^T 為基本矩陣(見“特殊矩陣(10):基本矩陣”),其逆矩陣也是基本矩陣,故設

B^{-1}=-(I+k\mathbf{e}\mathbf{e}^T)

直接計算

\begin{aligned}  BB^{-1}&=(I-\mathbf{e}\mathbf{e}^T)(I+k\mathbf{e}\mathbf{e}^T)\\  &=I-\mathbf{e}\mathbf{e}^T+k\mathbf{e}\mathbf{e}^T-k\mathbf{e}(\mathbf{e}^T\mathbf{e})\mathbf{e}^T\\    &=I-(1+3k)\mathbf{e}\mathbf{e}^T=I\end{aligned}

解出 k=-\frac{1}{3},即得

\displaystyle  B^{-1}=-(I-\frac{1}{3}\mathbf{e}\mathbf{e}^T)=\frac{1}{3}\left[\!\!\begin{array}{rrrr}    -2&1&1&1\\    1&-2&1&1\\    1&1&-2&1\\    1&1&1&-2    \end{array}\!\!\right]

 
仔細觀察 C 矩陣,不難發現除了第 3 行之外,第 1 列與第 4 列之和剛好等於第 2 列及第 3 列,這暗示我們在 C 左乘 B^{-1} 可產生許多零元,因此應當選擇 D,計算得到

D=B^{-1}C=\left[\!\!\begin{array}{crrc}  1&-4&-5&2\\  0&0&1&0\\  0&0&1&0\\  0&-2&-2&1  \end{array}\!\!\right]

為了與 D 相互參照,我們將 A 矩陣也列出:

A=CB^{-1}=\displaystyle\frac{1}{3}\left[\!\!\begin{array}{rrrr}    -1&5&-1&-4\\    -11&10&10&-17\\    -11&10&10&-17\\    -7&8&5&-10    \end{array}\!\!\right]

事實證明挑選 D 是明智的決定。

 
接下來的工作是求 D 的 Jordan 形式。第一步要找出 4\times 4 階矩陣 D 的特徵值,表面上,這又是一個單調冗長的機械化程序。標準的制式方法是直接計算行列式 p_D(t)=\mathrm{det}(D-tI),但我們發現 D 的第 2 列與第 3 列完全相同,也就是說,D 是不可逆的。不可逆矩陣的特徵多項式計算工作可以加以簡化(詳見“不可逆矩陣的特徵多項式”),先將 D 的線性獨立列挑出並組成下列矩陣:

V=\left[\!\!\begin{array}{crrc}    1&-4&-5&2\\    0&0&1&0\\    0&-2&-2&1\\    0&0&0&0    \end{array}\!\!\right]

矩陣 D 的每一列都可表示成 V 矩陣獨立列向量的線性組合,故得

D=\left[\!\!\begin{array}{crrc}    1&-4&-5&2\\    0&0&1&0\\    0&0&1&0\\    0&-2&-2&1    \end{array}\!\!\right]=\begin{bmatrix}    1&0&0&0\\    0&1&0&0\\    0&1&0&0\\    0&0&1&0    \end{bmatrix}\left[\!\!\begin{array}{crrc}    1&-4&-5&2\\    0&0&1&0\\    0&-2&-2&1\\    0&0&0&0    \end{array}\!\!\right]=UV

矩陣乘積 UVVU 雖然未必相似,但它們卻有相同的特徵多項式,於是我們轉而計算型態更簡單的 VU,得到下面的分塊對角矩陣:

VU=\left[\!\!\begin{array}{crcc}    1&-9&2&0\\    0&1&0&0\\    0&-4&1&0\\    0&0&0&0    \end{array}\!\!\right]

很容易看出 p_D(t)=p_{VU}(t)=t(t-1)^3。方陣 D 有特徵值 \lambda_1=0,代數重數為 1,對應一 1\times 1 階 Jordan 分塊 J(0)。至於特徵值 \lambda_2=1,其代數重數為 3,解出特徵空間 N(D-I) 僅有一特徵向量 \begin{bmatrix}    1\\    0\\    0\\    0    \end{bmatrix},故幾何重數為 \mathrm{dim}N(D-I)=1,這指出 \lambda_2=1 對應一 3\times 3 階 Jordan 分塊 J(1)。所以,矩陣 D 的 Jordan 形式 (即線性變換 T 的 Jordan 形式) 為

J=J(1)\oplus J(0)=\begin{bmatrix}    1&1&0&0\\    0&1&1&0\\    0&0&1&0\\    0&0&0&0    \end{bmatrix}

 
回顧整個解題過程,總共出現了三種改寫方式與等價問題:

(1) 將 B=\begin{bmatrix}    0&1&1&1\\    1&0&1&1\\    1&1&0&1\\    1&1&1&0    \end{bmatrix} 改寫為基本矩陣 -I+\mathbf{e}\mathbf{e}^T 以便迅速導出逆矩陣 B^{-1}

(2) 將原本求 A 的 Jordan 形式改成求相似矩陣 D=B^{-1}AB 的 Jordan 形式,因為 D 矩陣包含許多零元。

(3) 計算不可逆矩陣 D=UV 的特徵多項式改為 VU 的特徵多項式,理由是 VU 具有簡約的分塊主對角形式。

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

8 Responses to 運用等價問題來解題

  1. levinc 說道:

    話說回來,要能見招拆招…本身會的招也要夠多才行阿(默…)

  2. miohwsiemit 說道:

    老師不好意思,之前我PO的問題不見了~
    我在PO一次請教老師@@~
    想請問老師:
    關於您提到用矩陣D代替矩陣A求Jordan form的過程
    為什麼會選擇矩陣D,我不太明白(怎麼在左乘或右乘中看出矩陣D的"0元"比較多?)
    (還有矩陣C的第一列與第四列的和好像不等於第2列及第4列耶…)

    謝謝

  3. ccjou 說道:

    最近我們網站出了些問題,有些資料因此遺失。

    確實矩陣C的第一列與第四列的和不等於第2列及第4列,應該加上一句"除了第三行之外"。若仔細觀察 B^{-1}即可提早發現 D 會有很多零元。如果還是看不出來,那只好試著計算一下了。

  4. matrix67 說道:

    您好,我是大陸的讀者,關於這道題目我有些不明白。您令A=CB^(-1),但是這樣子得到的矩陣就是線性變換T在兩組不同基底下的矩陣,我感覺這樣子得到的矩陣之間並不相似,這樣子來做會正確嗎?

  5. matrix67 說道:

    似乎我和您對於這道題的理解不同,我覺得[0;1;1;1],[1;0;1;1],[1;1;0;1],[1;1;1;0]是C^4空間的一組基底,T[0;1;1;1]=[0;1;1;1]的意思是T[0;1;1;1]=[1;0;1;1]+[1;1;0;1]+[1;1;1;0];我覺得這道題目應該要說清楚基底是什麽吧,不然怎麼知道座標是對哪組基來說的

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s