Gilbert Strang 經典線代課程心得

來自MIT的經典線代課程－－Gilbert Strang

第四課：逆反矩陣運算推廣、消元矩陣乘法、L U 分解與置換矩陣( Inverse of AB & A^T 、Product of elimination matrices 、 LU decomposition and Permutation matrix)

上一次課程，我們對於「逆反矩陣」這一個數學名詞進行多方面的討論，試著將「 A 」與「 A^－1」之間的關係與功能性整理清楚，此次課程我們會通過「 AB 」與「 A^T 」的「逆反矩陣」，討論「逆反矩陣」在乘法運算上有沒有值得我們關注的運算性質 ( 顯而易見是有的 )

從結論說起，若有兩個大小相同的「可逆矩陣」 A , B ，則

( AB )^－1＝ B^－1A^－1
( A^T)^－1＝ ( A^－1 )^T

上一堂課提到了相當多「逆反矩陣」運算性質與其背後的原因，其中有個一再提及的核心概念為

「「逆反矩陣」是由「消元矩陣」構成的最終指令」

通過此視角，我們可以將「逆反矩陣」視為一種特殊的「消元矩陣」

「消元矩陣」的目的是將矩陣轉換為 REF，「逆反矩陣」的目的是將矩陣轉換為 I

或是說「逆反矩陣」的指令便是將「可逆矩陣」提供的所有指令抵消，使「逆反矩陣」與「可逆矩陣」結合後得出指令變成「維持不變」的「單位矩陣」

在重溫「逆反矩陣」與「可逆矩陣」之間的關係後，以相同的邏輯看到「 AB 」的「逆反矩陣」

( AB )^－1＝ B^－1A^－1

若是將參與乘法的矩陣視為指令，應該能夠比較好的理解為何需要將順序反過來了，矩陣乘法運算是有序的，並不能像實數運算一樣隨意更改前後順序，因此當我們要用「逆反矩陣」抵銷指令時，就需要按照原始指令一一抵銷

或許能將 AB 視為穿鞋子的動作指令，穿上鞋子 ( B ) 前，需要先上穿襪子 ( A ) ，而脫掉鞋子時需要先脫鞋子 ( B^－1) 再脫襪子 ( A^－1)」，總不能要求「先脫襪子 ( A^－1) 再脫鞋子 ( B^－1) 」，那是有點過分了

當我們將其中的邏輯釐清後，便能利用下式的推論證明我們想的在運算上也能成立

( AB )( B^－1A^－1 ) ＝ A ( B B^－1) A^－1 ＝ A I A^－1 ＝ A A^－1＝ I

( B^－1A^－1 )( AB ) ＝ B^－1 ( A A^－1) B ) ＝ B^－1 I B ＝ B^－1B＝ I

從此例延伸，當我們需要通過「逆反矩陣」將「可逆矩陣」轉換為「單位矩陣」時，以文字敘述為

「順序排放可逆矩陣乘積的逆反矩陣」等於「逆序排放可逆矩陣的逆反矩陣乘積」

即設 C _i＝ ( A _i)^－1，則

( A₁A₂．．．A_n)^－1 ＝ ( C_nC_n－1．．．C₁)

至此「可逆矩陣乘積」的「逆反矩陣」便完成討論了

接下來要通過討論「轉置矩陣 ( Transpose of a matrix)，A^T」的「逆反矩陣」，進一步說明有關「逆反矩陣」與「轉置矩陣」的相關性

在此之前，我想我們需要先了解何謂「轉置矩陣」，從字面意義上看，所謂的「轉置」便是將「矩陣行列進行交換」，數學定義為

[A^T ]_ij＝ [ A ]_ji

關於「轉置矩陣」特有的運算性質是下一個課程的主題，這堂課僅須了解何謂「轉置」就可以了，並不會過多提及與「轉置矩陣」相關的運算性質

此處的重點在於－－「逆反」與「轉置」這兩個指令的相關性，也就是

( A^T)^－1＝ ( A^－1 )^T

換句話說

對可逆方陣而言「逆反 ( Inversing ) 」與「轉置 ( Transposing ) 」具有交換性

教授在課堂上提到

學習「消元」的目的是「正確的認識矩陣」

而「消元」這條路的終點便是「最基礎的矩陣分解 ( Factorization of matrix ) 」，即

「 L U 分解 ( LU decomposition ) 」

現在假定一個「體質良好」的矩陣 A ，所謂的「體質良好矩陣」須滿足以下條件

矩陣的 REF 恰好是「上三角矩陣」
無須進行列交換 ( Row exchange )

則 A 可以被分解為 L U，即

A ＝ L U

雖然我們還沒揭曉 L 是如何出現的，但 L 是由什麼矩陣轉換的，關於這個問題各位心中應該是要有個底的，為了更好的說明 L 是怎麼出現的，此處會用範例進行說明，假定 A 是一個「體質良好」的二乘二矩陣

A ＝ [ 2 , 1；8 , 7]

對 A 使用消元矩陣

E_21 ＝ [ 1 , 0；－4 , 1 ]

使得 A 成為 REF

此時在等號的兩側同乘 E₂₁的「逆反矩陣」可以得到

( E₂₁^－1) E₂₁A ＝ ( E₂₁^－1) U　→　A ＝ ( E₂₁^－1) U

此時的「 E₂₁^－1 」便是「 L U 分解」中的「下三角矩陣 ( Lower triangular matrix , L ) 」，如下圖

值得注意的是，在「 L U 分解」中的「下三角矩陣」主元必為一，因此我們也會將其稱為「單位下三角矩陣 ( Unit lower triangular matrix ) 」，以此方式呈現有幾個優點

數學上的唯一性 ( Uniqueness )
數值計算的效率 ( Efficiency )
應用上的簡化 ( Simplification )

首先是唯一性，如果不將主元限制為一，則我們會有無限多種方式表示一個矩陣的「 L U 分解」，無論是分析上或是老師在訂正答案上，這樣的雜訊 ( 不穩定性 ) 都是不需要的

再來是效率， L 本身便是「消元矩陣」的集大成者，內部所存儲的元是進行「列運算消元」時使用的「消元數 ( 乘數 ) 紀錄」，甚至能說「 L U 分解」的過程中，L 存在目的便是協助我們紀錄「消元過程」的一種數學結構，如果主元上的元不再是一，意味著我們還原紀錄時還需要先「加工」這個矩陣才能使用，自找麻煩

最後是簡化，我們執行「 L U 分解」的目的是為了更好的處理線性方程組的解，相信各位讀者也有解二元一次方程組的經驗，我們總是期待著未知數的係數不是一便是零對吧，因為這樣我們算起來會「很輕鬆」，同樣的道理也能用在此處，主元皆為一的前提下，還原成線性方程組時就可以少掉最後一步的「同除係數」了，積少成多，相當有感

如果「單位下三角矩陣」有著那麼多「下三角矩陣」的優點，那麼...

能不能將「單位上三角矩陣」引入並取代「上三角矩陣」？

嘿！數學上還真的有這種分解法！當我們需要進行性質分析時，總是希望變數越少越好，看著 U 的對角線上那些臃腫不堪的主元，看了頭就痛

因此「瘦身計畫」的執行勢在必行，那我們應該如何解決這個問題呢？

只要在「 L U 分解」裡加入「對角矩陣 ( Diagonal matrix , D ) 」就可以了

「對角矩陣」可以用來表示「 L U 分解」中的 U 主元 ( 如下 )

通過「對角矩陣」使得原先的「上 / 下三角矩陣」成為「單位上 / 下三角矩陣」，這種分解方式被稱為「 LDU 分解 ( LDU Decomposition ) 」

「 LDU 分解」的優點便是「能精準針對矩陣的性質」進行討論，但是「 LDU 分解」不適合用來解方程式，因為在於分離主元對於解方程式沒有實質上的幫助，「 LDU 分解」主要功能是解析矩陣性質而非求解，而「 LU 分解」可以配合高斯消元法有效的解方城組，這便是「 LDU 分解」與「 LU 分解」最大不同的地方

相信讀者對於「 LDU 分解」與「 LU 分解」已經有著足夠多的理解了，但我們依然很難從例子中看出為何要特別把「消元矩陣」寫成「 L 」，所以我們下一個需要了解的問題是

為何可以用「 E 」表示的矩陣，要特別改成「 L 」呢？

難道只是因為階梯狀比較好看嗎？當然不是！

想要進一步的了解其中的不同需要觀察一個相對複雜的結構，所以下一步我們會用「 LU 分解」一個「體質良好」的三階矩陣 A，以觀察 E A ＝ U 與 A ＝ L U 的差別

只要是「體質良好」的三階矩陣 A ，就能使用「消元矩陣」將 A 、 U 兩者連結 ( 如下 )

E₃₂E₁₃E₁₂A ＝ U

通過「消元逆反矩陣」的參與，我們能將上式改寫為

A ＝ ( E₁₂^－1) ( E₁₃^－1) ( E₃₂^－1) U

此時

L ＝ ( E₁₂^－1) ( E₁₃^－1) ( E₃₂^－1)

所以這解決了任何疑問？當然沒有

至於「為何不用 E 而是用 L 連接 A U 兩個矩陣」，這個問題的答案我有偷偷的藏在前面的文章中，重點在於 L 能以「紀錄消元數」的結構存在於分解式中，但是 E 卻做不到這一點

如果你還是不了解，那是正常的，畢竟我還沒說開始舉例，現在我們假定參與消元的「消元矩陣」分別如下

[1,0,0；2,1,0；0,0,1] [1,0,0；0,1,0；0,0,1] [1,0,0；0,1,0；0,－5,1]

此時的 E 可被定義為

有注意到吧？在代表著「消元矩陣」的 E 多了個討人厭的十，十之所以會出現的原因在於「 E₃₂ 」給出的指令為

「將第二列向量乘上負五，再加上第三列向量」

最初建構「消元矩陣」時，我們希望看到的列向量運算是

－5 ( 0 , 1 , 0 ) ＋ ( 0 , 0 , 1 ) ＝ ( 0 , －5 , 1 )

實際上得到的卻是

－5 ( －2 , 1 , 0 ) ＋ ( 0 , 0 , 1 ) ＝ ( －10 , －5 , 1 )

其中的原因便是「 E₂₁ 」的存在使得第一列向量進入第二列向量並參與其中，進而使得 E 失去了原始消元數的資訊

但在逆向運算中， L 如同下式展示的一般，巧妙的迴避了這個問題

這時應該會有另一個問題縈繞在我們的心頭

「這是偶然，還是必然」

畢竟我們從頭到尾給出的性質都是由教授提出的範例進行說明，而靠單一特例是很難說服一個數學家的，所以下一步需要思考的問題是

將 A 推廣至 n 階方陣後，L 是否能夠繼續維持這樣美好的性質

從結論來說，答案必須是肯定的，不然就沒必要搞個「 LU 分解」了

這個問題的重點在於「原因」，若是要探討原因，則需要回歸到最初對於矩陣乘法的理解中也就是

「將矩陣乘法運算視為一組線性組合建構指令」

其中的核心在於矩陣乘法運算並不具備交換律，也就是說誰先誰後會直接影響運算結果

此處我們暫且不論兩個矩陣在非主元位置上的數值差異，建構 E 、 L 之間的最大差異在於乘法運算順序

以「消元逆反矩陣」建構 L 時，給出的列運算指令是由下至上、由右至左進行
以「消元矩陣」建構 E 時，給出的列運算指令是由上至下、由左至右進行

最初建構「消元矩陣」時，策略便是「消元數僅由同行主元構成」這一個規則

建構 E 時，由於順序問題，導致較早執行的指令會改變「消元數僅由同行主元構成」這一規則，從三階方陣的例子中，可以清晰地看到通過因為「 E₂₁」的關係，使得「第一列向量 ( Row₁ ) 」參與了後來的「 E₃₂」的消元指令中

建構 L 時，由於順序問題，較早執行的指令並不會改變「消元數僅由同行主元構成」這一規則，從三階方陣的例子中，我們可以了解到「 E₃₂^－1」的指令中，只有 a₂₂ 會影響消元數，而在「 E₃₁^－1」與「 E₂₁^－1」的指令中，只有 a₁₁會影響消元數，兩者在運算位置上不會有任何「重疊」以參與後續運算，換句話說，只要把所有消元數放在其原本位置上，便能建構出 L

「 IF NO ROW EXCHANGE , The multipliers(elimination step) go directly into L 」

以上論述便是為了說明

為何比起「 E A ＝ U 」，我們更想知道「 A ＝ L U 」

這個問題埋了快兩節課，不得不說還真是一段漫長的旅程，恭喜各位撐過來了～

不過最重要的「使用說明書」教授並沒有提到，我猜想課程內容還是以概念 / 理解為主，所以我寫了簡單的「使用教學」，避免讀者辛苦的搞了半天，弄懂了原理卻不知道該怎麼使用，流程如下

A x ＝ b
對 A 進行 LU 分解 → L U x ＝ b
將 U x 定義為 y → L y ＝ b
轉換為線性方程組 → 由 y_n 依序解出 y₁
將 U x ＝ y 轉換為線性方程組
解得 x → 由 x₁ 依序解出 x_n

「 L U 分解」即是通過「上 / 下三角矩陣」進行乘法運算時，有著將變數一一獨立的性質進行方程式變數的拆解

但是這與直接解線性方程組有差嗎？

這個問題理應沒有標準答案，所以我只在這邊提出我的個人觀點以供各位讀者參考

總體來看，這種分解法雖然能更好的計算出數值，但需要花費的時間也比較多，比起公式，我更希望讀者以 SOP 的概念去理解此「 L U 分解」

在這個解方中，步驟明確、指令清晰且應對能力強，最重要的是可以寫成程式讓電腦跑，只是它的泛用性不適用於人工計算而已，這與中學時期學習到的「二次多項式方程式公式解」很像，有些利用十字交乘法、配方法就能解出來的問題，使用公式解去處理，難免讓人有些「殺雞焉用牛刀」之感，不僅速度慢還加大了計算量，可是隨著學到複雜性更高的數學時，陪伴在我們身旁的方式只剩下公式解了，這就是依建於其泛用性

說了這麼多，是希望各位讀者在學習的過程中，不過不要覺得沒效率的東西沒有必要學習，理論與實踐往往是相互掛鉤的，理論要能實踐才能有價值，實踐才能找出理論不足之處，通過學習「 L U 分解」，我們學到了很多初等矩陣的性質 / 應用方式，並且這東西能廣泛應用於問題，雖然我大概不會用到，但是對我而言，這樣就足夠了^^

在結束了我們漫長的消元之旅後，教授提了一個看似與線性代數無關的問題：

「對於一個 n 乘 n 的矩陣，我們理論上最多需要進行幾次消元運算？」

首先定義運算次數應當如何計算

只要元與元間進行一次「乘＋加」，便算作一次

也就是說，當我們將第一列向量加到第二列向量時，此時便進行了 n 次運算，完成第一行消元需進行 n－1 次，才能將第一行的向量改為

( Pivot , 0 , 0 , ... , 0 )^T

一一消元後，將運算總量以函數 F ( n ) 表示，則

F ( n ) ＝ n ( n － 1 ) ＋ ( n － 1 ) ( n － 2 ) ＋ ... ＋ ( 2 ) ( 1 ) ＝ ( 2 / 3 ) ( ( n － 1 )3 － ( n － 1 ) )

是不是看不出這個算是究竟告訴了我們什麼，那就對了，我也看不出來，因為教授使用了更粗糙的估算使 F ( n ) 變為

n²＋ ( n － 1 )²＋．．．＋１²＝ n³/ 3

以這種「雖有誤差，但能更好表達中心思想」的寫法列出其實挺有趣的

「正確的估算」其實是一件難事，因為估算者很難知曉哪些數值是雜訊，哪些數值是不可忽視的數值，所以對於這樣的說明方式我大概能理解，但還是會覺得這樣誤差真的挺大

我想這也是數學有趣的地方，相同的數值有著不同解釋，俗話說得好「有一千的人就有一千個哈姆雷特」，與文學不同不同的是

數學上縱使有再多的觀點，數值永遠都是那樣乾淨簡潔俐落且不容置疑

話說回 A x ＝ b ，在相同的條件下對 b 進行同步運算後，最終的結果 b 應該會經歷約 n²次運算，我猜想是書中有提到一些性質但教授上課沒提到，所以下面我會以個人學經歷來說說引入這段課程的原因 ( 個人意見僅供參考 )

計算「計算次數」真的是挺妙的轉折，我猜這與此演算法的「時間複雜度 ( O ( n³ ) ) 」有關，目的則是引入「高斯消元法」的計算成本這一概念，當矩陣維度增加時，計算量會以何種方式進行增加

這個問題也是讓講究效率的數學家相當感興趣的問題，不過這樣的問題大多會被放在「數值分析」這一主題下，在此就不多說明，畢竟教授也沒說提到這個的目的為何，就先這樣吧

下一個我們需要認識的老朋友是前面課程中提到過的

「置換矩陣 ( Permutation matrix , P ) 」

嚴格來說「置換矩陣」是下堂課的內容，這段內容是一如既往地「提前預告」，也算是補足「消元法」的最後一塊拼圖

我們先複習一下何謂「置換矩陣」，前面的課程有提到過，「置換矩陣」的功能很簡單，即「交換行列」，是一種「初等矩陣」

有意思的地方在於隨著「置換矩陣」的位置不同，給出交換指令也會隨之改變

要進行「行置換」，需使用「右置換矩陣」 A×P
要進行「列置換」，需使用「左置換矩陣」 P×A

接著說明「置換矩陣」的運算性質，為方便說明，以下統一進行的是列置換

假定現在我們要對一個三階方陣進行置換，則能寫出一共 6 種置換矩陣，分別是

請問這六種可能性只能一個一個找嗎？

當然不是，若以組合數學的概念理解的話，便能進行說明與推廣，以三階方陣進行「列置換」為例，能選用的指令為三，分別是

元矩陣第一列的 [ 1 , 0 , 0 ]
元矩陣第二列的 [ 0 , 1 , 0 ]
元矩陣第三列的 [ 0 , 0 , 1 ]

重新選擇列向量時，第一列可以選擇以上三列的其中一列，故有三種選擇，第二列剩兩種選擇，第三列只剩一種選擇，故可能性為

3 × 2 × 1 ＝ 3！

現在嘗試將此規則推廣至 n 階方陣，同樣考慮 n 階方陣有 n 個不同的列向量，第一列有 n 種選擇，第二列則是 ( n－1 ) 種選擇，．．．，第 n 列只剩 1 種選擇，故所有可能性應為

n × (n－1) × ．．． × 1 ＝ n！

而同階的「置換矩陣」之間還有一些有趣的運算性質

「置換矩陣」乘上「置換矩陣」必然是「置換矩陣」( 乘法封閉性 )
「置換矩陣」的「逆反矩陣」必然「置換矩陣」( 乘法反元素 )
「單位矩陣」是一種「置換矩陣」( 乘法單位元素 )

再考慮到矩陣乘法運算擁有的「結合律」，結合以上條件，我們能夠發現這是「代數學」上的「群 ( Group ) 」結構，意味著由「同階置換矩陣」形成的集合會形成一個「非交換群 ( Non － Abelian Group ) 」，這可是一個有趣的發現

什麼？你問哪裡有趣，我也不知道，可能數學家特別喜歡巧合吧，畢竟巧合象徵著不同領域的內容勾搭上了，意味著我們或許能在「線性代數」上找到一些「代數學結構」並引入「代數學理論」方式進行分析，進而將理論進一步完善，就像玩遊戲就要「全要素蒐集」是一樣的道理

嗯？你說這種要素也太小眾了，我完全認同，我的教授當年上課時很開心地掛跨領域談天說地時，台下的我也是「這個人在嗨什麼」的心情，時過境遷阿，終於輪到我自嗨了

有些讀者應該注意到了，在上方列出的六種可能裡，個別「置換矩陣」的「轉置矩陣」便是其「逆反矩陣」，以算式列出便是

P^T＝P^－1

這是巧合嗎？我可不這麼認為，有沒有方式說明這個性質呢？答案就藏在「左右置換矩陣」中，好好想想原因吧！

快樂的時光總是過得特別快，這次的筆記心得到這邊便結束了，下一個課程會細說「轉置矩陣」、「置換矩陣」與「向量空間 ( Vector space ) 」，感謝你的閱讀，期待我們的下次碰面，88