分塊矩陣的解題案例──逆矩陣與矩陣乘積的特徵值

本文的閱讀等級:中級

數學解題像是一門具歸納性質的實驗科學活動,學者不僅試圖了解各種解答,還希望能明白這些解答背後的動機和過程。美國數學家波利亞 (George Polya) 在其名著“How to Solve it” (中譯《怎樣解題》,天下文化出版,2006) 主張數學解題過程可分為四個階段。第一、了解問題:要知道未知數是什麼?已知數是什麼?條件是什麼?第二、擬定計畫:找出已知數和未知數之間的關係。如果這個關係不是很明確,可以嘗試考慮類似的問題。最後,我們應該能想出解題的計畫。第三、執行計畫:將解題計畫付諸實現,仔細檢查每一個步驟。第四、驗算與回顧:驗算所得的解答,檢驗每個論證步驟是否正確。波利亞並以「啟發法」(heuristic,或稱助探法) 為基礎,舉出一連串提示問題引領讀者朝著解答方向前進。本文就以矩陣分析常使用的分塊矩陣為例,跟隨波利亞的腳步,學習透過有效的提問來激發想法,從而構思解題計畫,跨越障礙直達問題核心。

 
案例一:設 Am\times m 階,Bm\times nCn\times m 階,Dn\times n 階,求分塊方陣 \begin{bmatrix}    A&B\\    C&D    \end{bmatrix} 的逆矩陣以及存在條件。

 
首先選擇使用合適的記號或符號,我們能否把條件的各個部份分開並寫下來?設待求的逆矩陣為 \begin{bmatrix}    W&X\\    Y&Z    \end{bmatrix},逆矩陣的定義直接給出解的條件:

\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}\begin{bmatrix}    W&X\\    Y&Z    \end{bmatrix}=\begin{bmatrix}    I_m&0\\    0&I_n    \end{bmatrix}

乘開上式得到下列四個條件式:

\begin{aligned}  AW+BY&=I_m\\    AX+BZ&=0\\    CW+DY&=0\\    CX+DZ&=I_n\end{aligned}

由已知分塊的尺寸推論 Wm\times m 階,Xm\times n 階,Yn\times m 階,Zn\times n 階,也就是說,上面三個矩陣所含的對應元分塊有相同的尺寸,例如 AWI_m 皆為 m\times m 方陣。我們要特別強調限制各對應元分塊尺寸的重要性,這將能夠有效地約束簡化分塊矩陣乘法的設計。

 
因為上面每個式子都包含兩個未知分塊,讀者熟悉的迭代消去法在此很難發揮作用。如果不能立刻解決眼前的問題,可以試著考慮一些相關但比較容易解決的問題或比較特殊的問題。例如,分塊上三角矩陣,亦即 C=0,有較簡約的條件方程式:

\begin{aligned}  AW+BY&=I_m\\    AX+BZ&=0\\    DY&=0\\    DZ&=I_n\end{aligned}

採用反向迭代,依序分別解出 Z=D^{-1}Y=D^{-1}0=0X=-A^{-1}BC^{-1}W=A^{-1}。分塊三角矩陣的逆矩陣存在條件是主對角分塊 AD 必須是可逆的,逆矩陣公式為

\begin{bmatrix}    A&B\\    0&D    \end{bmatrix}^{-1}=\begin{bmatrix}    A^{-1}&-A^{-1}BD^{-1}\\    0&D^{-1}    \end{bmatrix}

 
與一般矩陣相同,分塊上 (下) 三角矩陣的逆矩陣也是分塊上 (下) 三角矩陣。看一些特殊情況,如基本矩陣其主對角分塊為單位矩陣,立刻得到

\begin{aligned}\begin{bmatrix}    I_m&B\\    0&I_n    \end{bmatrix}^{-1}&=\begin{bmatrix}    I_m&-B\\    0&I_n    \end{bmatrix}\\  \begin{bmatrix}    I_m&0\\    C&I_n    \end{bmatrix}^{-1}&=\begin{bmatrix}    I_m&0\\    -C&I_n    \end{bmatrix}\end{aligned}

我們能運用上面的結果解出答案嗎?應該引入什麼中間步驟或輔助元素才能讓分塊三角形逆矩陣派上用場?將 2\times 2 階分塊矩陣分解為分塊三角矩陣的乘積是最明顯不過的想法。運用基本矩陣乘法實現消去法的化簡過程,不難設計出下面的矩陣乘法運算:

\begin{bmatrix}    I_m&0\\    -CA^{-1}&I_n    \end{bmatrix}\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}=\begin{bmatrix}    A&B\\    0&D-CA^{-1}B    \end{bmatrix}

上式的成立條件是 A^{-1} 存在。若要繼續化簡至分塊對角矩陣,可將上式右乘另一個基本矩陣,如下:

\begin{bmatrix}    I_m&0\\    -CA^{-1}&I_n    \end{bmatrix}\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}\begin{bmatrix}    I_m&-A^{-1}B\\    0&I_n    \end{bmatrix}=\begin{bmatrix}    A&0\\    0&D-CA^{-1}B    \end{bmatrix}

再將等號兩邊左右乘以基本矩陣的逆矩陣就得到 LDU 分解式:

\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}=\begin{bmatrix}    I_m&0\\    CA^{-1}&I_n    \end{bmatrix}\begin{bmatrix}    A&0\\    0&D-CA^{-1}B    \end{bmatrix}\begin{bmatrix}    I_m&A^{-1}B\\    0&I_n    \end{bmatrix}

S_A=D-CA^{-1}B,此式稱為 A 的 Schur 互補 (complement)。如果 S_A 是可逆的,就有

\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}^{-1}=\begin{bmatrix}    I_m&-A^{-1}B\\    0&I_n    \end{bmatrix}\begin{bmatrix}    A^{-1}&0\\    0&S_A^{-1}    \end{bmatrix}\begin{bmatrix}    I_m&0\\    -CA^{-1}&I_n    \end{bmatrix}

乘開上式就導出一個形式複雜的分塊逆矩陣公式:

\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}^{-1}=\begin{bmatrix}    A^{-1}+A^{-1}BS_A^{-1}CA^{-1}&-A^{-1}BS_A^{-1}\\    -S_A^{-1}CA^{-1}&S_A^{-1}    \end{bmatrix}

 
能否用不同的方式得出答案?上述解題程序的另一個實現是將分塊矩陣化簡為 UDL 分解。請讀者自行驗證

\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}=\begin{bmatrix}    I_m&BD^{-1}\\    0&I_n    \end{bmatrix}\begin{bmatrix}    S_D&0\\    0&D    \end{bmatrix}\begin{bmatrix}    I_m&0\\    D^{-1}C&I_n    \end{bmatrix}

其中 S_D=A-BD^{-1}CD 的 Schur 互補。當 DS_D 可逆時,計算得到另一個合法的逆矩陣公式:

\begin{bmatrix}    A&B\\    C&D    \end{bmatrix}^{-1}=\begin{bmatrix}    S_D^{-1}&-S_D^{-1}BD^{-1}\\    -D^{-1}CS_D^{-1}&D^{-1}+D^{-1}CS_D^{-1}BD^{-1}    \end{bmatrix}

最後要問是否可將這個結果應用到別的問題上?令上面兩個公式的 (1,1) 元相等,便導出矩陣和的逆矩陣公式 (見“兩矩陣和的逆矩陣”):

(A-BD^{-1}C)^{-1}= A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}

這是一個典型的「殊途同歸」的應用表現。

 
案例二:設 Am\times n 階,Bn\times m 階,證明 ABBA 有相同的非零特徵值集合 (參閱“AB 和 BA 有何關係?”)。

 
挑出問題中隱藏的線索,從關鍵字詞是否能聯想什麼有用的定理?我們知道兩相似矩陣有相同的特徵值。先回顧建立相似矩陣關係的矩陣乘法,設 MXYZ 為同階方陣,且 M 是可逆的,若 MX=YXM=Z,則 Y 相似於 Z,因為 Y=MX=MZM^{-1}

 
應用分塊矩陣解題除了掌握矩陣代數技巧還要知道命題的關鍵性質,分塊矩陣乘法的設計通常由問題情境所引導。我們已經考慮了與問題相關的所有必要觀念或性質嗎?關鍵性質是分塊三角矩陣的特徵值由主對角分塊特徵值所構成 (見“分塊矩陣特徵值的計算方法”),如欲利用此性質,應該如何轉換問題才好?矩陣 ABm\times m 階,BAn\times n 階,如果能夠證明 Y=\begin{bmatrix}    AB&0\\    \ast&0    \end{bmatrix} 相似於 Z=\begin{bmatrix}    0&0\\    \ast&BA    \end{bmatrix} 等於就證得原命題。矩陣 YZ 中的分塊 \astm\times n 階,因此 B 的倍數即為當然選擇。

 
一旦有了使用相似矩陣解題的想法,下一個步驟要建立 YZ 的相似關係。實際作法是把分塊 AB 分別納入 MX 的正確位置,使得 YZ 各自包含 ABBA。讀者能否一眼就看出符合命題的分塊矩陣?萬一不行,就從有最簡約形式的分塊矩陣下手。自然地,我們可令 M=\begin{bmatrix}    I_m&A\\    0&I_n    \end{bmatrix}X=\begin{bmatrix}    0&0\\    B&0    \end{bmatrix},計算 MXXM

\begin{aligned}  \begin{bmatrix}    I_m&A\\    0&I_n    \end{bmatrix}\begin{bmatrix}    0&0\\    B&0    \end{bmatrix}&=\begin{bmatrix}    AB&0\\    B&0    \end{bmatrix}\\    \begin{bmatrix}    0&0\\    B&0    \end{bmatrix}\begin{bmatrix}    I_m&A\\    0&I_n    \end{bmatrix}&=\begin{bmatrix}    0&0\\    B&BA    \end{bmatrix}\end{aligned}

得知 \begin{bmatrix}    AB&0\\    B&0    \end{bmatrix} 相似於 \begin{bmatrix}    0&0\\    B&BA    \end{bmatrix},故 ABBA 有相同的非零特徵值集合。

 
另一條思路是從特徵值的定義出發。如何讓問題的起點與終點彼此更接近一些?只需要證明 ABBA 的特徵多項式有相同非零根即可,也就是特徵多項式滿足

\lambda^n\mathrm{det}(\lambda I_m-AB)=\lambda^m\mathrm{det}(\lambda I_n-BA)

原因是當 \lambda\neq 0 時,若 \mathrm{det}(\lambda I_m-AB)=0,則 \mathrm{det}(\lambda I_n-BA)=0,反之亦然。但要怎麼導出相同的特徵多項式呢?我們想起分塊三角矩陣的行列式性質,將特徵多項式還原為分塊矩陣的行列式,如下:

\begin{aligned}  \begin{vmatrix}    \lambda I_m-AB&0\\    kB&\lambda I_n    \end{vmatrix}&=\lambda^n\det(\lambda I_m-AB)\\    \begin{vmatrix}    \lambda I_m&kA\\    0&\lambda I_n-BA    \end{vmatrix}&=\lambda^m\det(\lambda I_n-BA)\end{aligned}

其中 k 為任意數。接著,設法利用矩陣乘法運算製造出上面的分塊三角矩陣。先把 I_mI_nAB 置入唯一決定位置,\begin{bmatrix}    I_m&A\\    B&I_n    \end{bmatrix},再令基本矩陣與此矩陣相乘,如有必要再改變乘數。中間過程類似填字遊戲,下面是經過數次嘗試錯誤後得到的結果:

\begin{aligned}  \begin{bmatrix}    I_m&-A\\    0&\lambda I_n    \end{bmatrix}\begin{bmatrix}    \lambda I_m&A\\    B&I_n    \end{bmatrix}&=\begin{bmatrix}    \lambda I_m-AB&0\\    \lambda B&\lambda I_n    \end{bmatrix}\\    \begin{bmatrix}    I_m&0\\    -B&\lambda I_n    \end{bmatrix}\begin{bmatrix}    \lambda I_m&A\\    B&I_n    \end{bmatrix}&=\begin{bmatrix}    \lambda I_m&A\\    0&\lambda I_n-BA    \end{bmatrix}\end{aligned}

計算上二式等號兩邊的行列式,根據矩陣乘積的行列式可乘公式可推得

\begin{vmatrix}    \lambda I_m-AB&0\\    \lambda B&\lambda I_n    \end{vmatrix}=\begin{vmatrix}    \lambda I_m&A\\    0&\lambda I_n-BA    \end{vmatrix}

 
上述這兩個方法的解題瓶頸終究都在分塊矩陣乘法的設計上;我們可能功虧一簣,試了半天仍然湊不出適當合用的分塊矩陣。不可否認地,所有的解題活動都存在風險,都有若干運氣的成分,但正因為解題活動的不確定性也才帶來更多的樂趣和喜悅。最後,我抄錄《怎樣解題》第一版的一段中譯序文供讀者參考[1]。波利亞的這篇序文寫於1944年,今日重讀依然讓我們感到新意盎然。

大發現解決大問題,然而,並不是只有大發現才有存在的價值;每一個問題的解答,都需要有某個「發現」才行。你所面臨的也許只是個小問題,但是如果它能引起你的好奇心,引發你的創造力,而且,如果你是用自己的方法來解決這個問題的,那麼,你一樣會經歷到發現過程中的緊張情緒,以及享受到最後那份「勝利」的喜悅與興奮。這一類的經驗,也許會讓年輕人培養出智性上的品味,甚至烙印在心裡,成為陪伴終生的一種性格。

因此,數學老師也就掌握了大好良機。如果他(她)在教學過程中總是讓學生不斷做些機械性的計算,那無異於扼殺了學生的興趣,阻礙了學生的智能發展,同時浪費了大好良機。但是,如果他(她)能夠掌握良機,刺激學生的好奇心,能夠因材「出題」,刺激學生思考,協助他們解決問題,如此一來,也許就能夠讓學生培養出獨立思考的愛好,也學會獨立思考的方法。

如果大專院校的學生選修的學科還包括數學的話,可以說他們掌握了一個獨特的機會。然而,學生如果將數學單純視為修滿畢業學分所需的一門學科,只要通過期末測驗就可以立刻把所學拋到腦後、忘得乾乾淨淨的話,那當然可說是坐失良機了。就算學生在數理上頗具天分,機會還是可能從指尖溜走,因為這些天賦異稟的學生也跟其他人一樣,必須花點功夫探索自己的天分,培養自己的興趣。想想看,如果沒嚐過覆盆子派,哪裡會知道自己喜不喜歡呢?

然而,學生最後可能還是會發現,數學問題也許就像填字遊戲一樣好玩,他們還可能發現解數學題時的心智活動,也可以像一場勢均力敵的網球賽一樣讓人嚮往。學生一旦嚐過了數學的愉悅之處,就很難再忘記,而這樣一來,數學就有機會在他們的生命中占有一席之地,成為他們的嗜好、未來從事專業工作時必需的工具、成為他們的專業,或幻化成他們的抱負。

 
參考來源:
[1] 《怎樣解題》,波利亞著,蔡坤憲譯,遠見天下出版,2006。

Advertisements
本篇發表於 特徵分析, 線性代數專欄 並標籤為 , 。將永久鏈結加入書籤。

9 則回應給 分塊矩陣的解題案例──逆矩陣與矩陣乘積的特徵值

  1. levinc 說道:

    好像不用Schur complement 也可以直接得出公式
    直接解 AW+BY=I; CW+DY=0
    可得 Y=-inv(D)CW => AW-B*inv(D)CW =(A-B*inv(D)C)W = I_m
    所以,
    W=inv(A-B*inv(D)C),
    Y=-inv(D)C*inv(A-B*inv(D)C) .

    再解另兩條 AX+BZ=0; CX+DZ=I
    得 Z=inv(D)-inv(D)CX,
    AX+B*inv(D)-B*inv(D)CX = (A-B*inv(D)C)X+B*inv(D) = O
    所以就知道,X=-inv(A-B*inv(D)C)B*inv(D);
    Z=inv(D)+inv(D)C*inv(A-B*inv(D)C)B*inv(D)

    XD

  2. levinc 說道:

    令\lambda \neq 0,

    知道|\lambda I_n -BA| = \lambda^n |In-B(\lambda^{-1}A)|
    然後由|I_m -AB| = |I_n – BA|,
    上式可=\lambda^n |I_m – (\lambda^{-1}A)B| = \lambda^{n-m} |\lambda I_m – AB|,
    移項後可得証 \lambda^m |\lambda I_n-BA| = \lambda^n |\lambda I_m -AB|.

    這不就可避免找那麻煩的三角矩陣嘛XD

     

  3. ccjou 說道:

    謝謝你在第一個迴響提供的做法,直接用矩陣代數亦可解出逆矩陣。

    關於第二個迴響,我不清楚為何證明過程在一開始就引用
    \mathrm{det}(I_m-AB)=\mathrm{det}(I_n-BA)

  4. levinc 說道:

    因為想得到det(I_n-B(lambda^{-1}A))=det(I_m-(lambda^{-1}A)B),
    視(lambda^{-1}A)為一新矩陣即可。

  5. ccjou 說道:

    我的意思是我們是不是應該先證明
    \mathrm{det}(I_m-AB)=\mathrm{det}(I_n-BA)

    這個式子不是這麼明顯。

  6. ccjou 說道:

    喔,我想我還是說清楚好了。上面的公式稱為"Sylvester 行列式定理"
    https://ccjou.wordpress.com/2009/12/04/%E7%9F%A9%E9%99%A3%E5%92%8C%E4%B9%8B%E8%A1%8C%E5%88%97%E5%BC%8F-%E4%B8%8A/
    弔詭的是,此公式的證明似乎仍要仰賴分塊矩陣乘法。

  7. levinc 說道:

    我剛試了幾種証明這公式的手法,雖然不如老師那篇談的那麼複雜,
    但的確也都要用到分塊矩陣的結果。
    例如一個簡單的做法:
    [I_m, A; B, I_n] =
    [I_m-AB, A; O, I_n]*[I_m, O; B, I_n] =
    [I_m, O; B, I_n]*[I_m, A; O, I_n-BA]
    同時取det可得。

    前面回響那個方法好像有點tricky…
    當時只想說是不是能避開不用那麼麻煩找三角矩陣的方法,看來還是需要它 orz

  8. cj 說道:

    老师:“令上面兩個公式的 (1,1) 元相等,便導出矩陣和的逆矩陣公式” 这个部分,须要m=n这个条件的吧?谢谢您的文章。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s