Gilbert Strang 經典線代課程心得－4

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

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

我們這次的課程是從討論可逆矩陣進行運算時擁有的性質開始，已知現有兩個大小相同的可逆矩陣 A , B，我們想知道 AB 的逆反矩陣與 A^－1 & B^－1 之間的關係

( AB )( ？ ) ＝ ( ？ )( AB ) ＝ I

還記得上一堂課我們得出了很多理解逆反矩陣的方式，其中有一個很重要的理解是－－「消元矩陣是初等矩陣 E 的一員」，所以我們可以將其視為一種特殊的消元矩陣，而我們對消元矩陣的理解應該是一種「列交換指令」，而逆反矩陣的指令便是將可逆矩陣的資訊徹底抹消，使其成為最簡單的單位矩陣

需要特別留意「消元矩陣是有序的」，以穿脫鞋子來舉例，當我們按照順序先穿襪子 ( A ) 再穿鞋子 ( B ) 時，脫掉鞋襪需要做的事情是「先脫鞋子 ( B^－1 ) 再脫襪子 ( A^－1 )」，而不能「先脫襪子 ( A^－1 ) 再脫鞋子 ( B^－1 )」，因此當我們要通過一個逆反矩陣將一個可逆矩陣轉換為單位矩陣時，所以理論上「可逆矩陣乘積的逆反矩陣」寫為「逆序排放可逆矩陣的反矩陣乘積」

若 C _i ＝ ( A _i )^－1 ，則 ( A₁ A₂ ．．． A_n )^－1 ＝ ( C_n C_n－1 ．．． C₁ )

回到這個例子中，在找尋 ( ？ ) 時，我們便可測試上述猜測是否正確，因為我們需要找的是逆反矩陣，因此會需要確認左/右逆反矩陣相等，以下推導便是利用逆反矩陣的性質與乘法結合律進行

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

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

由上式可知，通過鞋襪的猜想是正確的，至此我們已經知道如何處理可逆矩陣乘積的逆反矩陣了，現在我們來看看「 轉置矩陣 ( Transpose of a matrix)，A^T」的逆反矩陣，這邊出現了一個新的矩陣，所謂的「 轉置 」便是將「矩陣行列翻轉」的動作，具體定義為

[A^T ]_ij ＝ _​[ A ]_ji

不過關於轉置矩陣特有的運算性質是下一個課程的主題，此處沒有提到太多性質就不再贅述(內容會太多)，待看完下一章節後再回頭看可以更好的吸收此處內容

就結論而言「 A^T 的逆反矩陣」就是「 A^－1 的轉置矩陣」，這邊要留意到事情是

「對單個可逆方陣而言，逆反(inversing)以及轉置(transposing)是可顛倒的」

教授在此處提到，我們在「消元」這個主題上的路已經快要告一段落了，之所以花了那麼多時間學習消元，是為了更清晰的了解矩陣運算的本質，而「 L U 分解」便是最基礎的矩陣分解( factorization of matrix )

現在我們建構一個體質良好的矩陣 A ，這個矩陣主元不為零且無須進行列交換(Row exchange)，經過消元得到 U ，此時假設一個矩陣 L 使得 A U 得以連結，並記做

A ＝ L U

一樣利用範例進行說明，給定一個二乘二的矩陣

A ＝ [ 2 , 1；8 , 7]

使用消元矩陣

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

使得

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

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

即

此時的 E₂₁^－1 便是 L U 分解中的［下三角矩陣(Lower triangular matrix , L )］，這時 L 中的主元皆為一，因此在 L U 分解裡，我們有時會加入「對角矩陣( Diagonal matrix , D )」使得 L、U 的主元皆成為一，將 A 被分解「下三角矩陣、對角矩陣、上三角矩陣」乘積的分解法被稱為「LDU 分解(LDU Decomposition)」

以上便是 L U 分解的實際例子，其簡單的解構很好的幫助我們理解分解過程中的各個矩陣的功能，不過我們很難從這個例子中看出為何要特別把「E₂₁^－1」寫成「 L 」，只是因為階梯狀比較好看嗎？當然不是！想要進一步的了解其不同，我們需要觀察一個相對複雜的結構，因此接下來會說明，當A 成為一個不用進行列交換的三乘三矩陣時，其 L U 分解過程為何

理論上說，通過消元矩陣將 A 變成 U 的過程可以寫作

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

將其改寫為分解式後可得

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

此時的

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

阿...這不是沒變嗎？NONONO，我們想了解為何不要用消元矩陣乘積而是逆反消元矩陣乘積(寫作 L )的原因很簡單， L 可以更清楚的知道消元數在過程中扮演的角色，一樣通過假設，此時

[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₃₂ 給出的指令為「將第二列向量乘上負五，再加上第三列向量」，但是新的列向量是( －2 , 1 , 0 )而不是( 0 , 1 , 0 )，是因為E₂₁的指令使得第一列向量參與其中，隨著倍數放大得到了這個數值

但是如果我們逆向運算呢？

哈！堪稱完美，我們可以清晰地看出消元數且不會多出來的數值，這兩者間的差異只差在順逆，因為順序原因，當我們以逆反矩陣寫出時，我們的指令會是由下往上、由右往左進行運算，我們消元時，消元矩陣的值都是且只是由同行主元構成，並無其他元參與其中

順推，則前面的指令會改變「數值由同行主元構成」這一個規則，從 E 的例子中，我們可以清晰地看到通過 E₂₁ 使得第一列向量參與了後來的 E₃₂

逆推，則指令又會回歸「數值由同行主元構成」這一個規則，從 L 的例子中，我們可以了解到 E₃₂ 是由 a₂₂ 構成的，而 E₃₁、E₂₁ 都是由 a₁₁ 構成的，期間不會有任何機會改變參與後續運算的列向量，在這個過程中，我們可以就消元數，直接建構出 L 這個矩陣

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

以上就是為何我們比起「 E A ＝ U 」，我們更想知道「 A ＝ L U 」的原因了(這個問題埋了快兩節課，真棒)，要怎麼使用這個分解法教授並沒有提到 ( 上課主要是提及概念 )，這邊做一個簡單的補充使用方式，避免搞了老半天不知道為什麼要繞這麼大圈

A x ＝ b → L ( U x ) ＝ b → L y ＝ b → 解得 y → U x ＝ y → 解得 x

其實所謂的 L U 分解便是協助我們拆解矩陣的一個方式，通過上下三角矩陣的性質，我們能更好的求出 x y ，這與直接解線性方程組有差嗎？這問題倒是挺難回答的

(以下為個人觀點) 總體來看，這種分解法雖然能更好的計算出數值，但需要花費的時間也比較多，比起公式，我更希望讀者以 SOP 的概念去理解此法，在這個解方中，步驟明確、指令清晰且應對能力強，最重要的是可以寫成程式讓電腦跑，只是它的泛用性不適用於人工計算而已，這與中學時期學習到的「二次多項式方程式公式解」很像，有些利用十字交乘法、配方法就能解出來的問題，使用公式解去處理，難免讓人有些「殺雞焉用牛刀」之感，不僅速度慢還加大了計算量，可是隨著學到複雜性更高的數學時，陪伴在我們身旁的方式只剩下公式解了，這就是依建於其泛用性

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

在結束了我們漫長的消元之旅後，教授提了一個問題：

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

我們將元與元間進行一次『乘＋加』運算算作一次，在討論這個問題前，不訪先從 n 乘 n 的方陣開始會比較輕鬆，當我們將第一列向量加到第二列向量中，此時便進行了 n 次運算，完成第一行消元需進行 n－1 次，將其總量以函數 F ( n )表示，則

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

是不是看不出什麼，對，我也看不出來，這邊教授用了很粗糙的估算使其變為

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

有一說一，中間真的加了不少料 = = 但不妨礙理解，人家是MIT教授，這也沒啥好爭的，畢竟不是重點，能理解概念就行了，所以說回 A x ＝ b ，現在需要對 b 進行同步運算，則此時的 b 應該會運算大約 n² 次，這一樣是估算值，應該是書中有提到一些性質但教授沒提到(我猜的)，或是我有看不懂的地方，不然突然算計算次數也是挺妙的轉折，我猜這與時間複雜度(O)可能有關，但事是這麼個事，教授也沒說要幹啥，那就先這樣吧，至此消元結束(灑花)

接著我們說說「置換矩陣( 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 ) 」結構，這很有趣(你問我有趣在哪我也不知道)，這代表我們能在線性代數上找到一些代數結構並引入其他方式進行分析

還不只這樣，你有沒有注意到上方列出的六種可能裡，個別置換矩陣的轉置矩陣便是其逆反矩陣，也就是

P^T＝P^－1

這是巧合嗎？我可不這麼認為，有沒有方式說明這個性質呢？問題的答案就藏在左右置換矩陣中，這邊就先不暴雷了，好好想想原因吧！快樂的時光總是過得特別快，這次的筆記心得到這邊便結束了，下一個課程會細說轉置矩陣、置換矩陣與向量空間(vector space)，感謝你們的閱讀，期待我們的下次碰面