Linear Algebra筆記2 - Elimination

高斯消去法

某個system of equations如下：

寫成matrix form:

筐起來的數字稱為first pivot，意即不改變的固定樁，用這個pivot的倍數來消去與它同一column的第二個數，意即3。

這是一個recursive process，我們利用上面的結果，繼續找第二個和第三個pivots，以求消除另外兩個未知數：

(error: 右邊中間row應該還是 0 2 -1)


可以看到右邊的matrix是一個所謂的“upper triangle”，也就是對角線左下方全為零，這就是emlimination要達到目的，因為這樣就可以solve X Y Z。


當然等式右邊，也就是Ax=b的b，也應該要放入matrix計算，稱為augmented matrix，上面的消去法只有對A作用，以下才是完整的消去法過程：

複習：Vector-Matrix Multiplication

如果一個matrix ＊ column vector，一個快速的算法就是將之視為matrix中每一個column vector的combination （右乘一個column vector):

另一種形式是 row vector * matrix，則快速算法為將之視為matrix中每一個row vector的combination（左乘一個row vector):

消去法的矩陣形式

以上的複習是為了matrix elimination的快速算法，我們原來題目中的matrix A可以寫成:

由於我們是做row elimination，但這其實相當於做row的combination！
第一次的elimination(利用pivot 1)相當於找出某個matrix，使得以下成立：

在複習中，我們知道row * matrix 相當於row combination of matrix rows，所以很明顯的左邊未知的matrix的第一個row要是以下的combination，以便能夠形成等號右邊的第一個row:

a*[1 2 1] + b*[3 8 1] + c*[0 4 1] = [1 2 1]
很明顯[a b c] = [1 0 0]

同理未知matrix的第三個row因為要讓等號右邊的第三個row和A的第三個row相等，所以等於A的row1 row2的combination係數要零： [0 0 1]

中間row，因為pivot 1是左上角的1，為了要消掉pivot 1，當然就是-3份row1 + 1份row2 + 0份row3 : [-3 1 0]

所以消去法的第一pivot為以下matrix 相乘：

這也就是我們之前學的乘法矩陣公式的由來，例如等式右邊(2,3) = -2所屬的row，其實是:

-3*[1 2 1] + 1*[3 8 1] + 0*[0 4 1]的combination。

所以(2,3)這個entry相當於[-3 1 0] DOTPRODUCT [1 1 1]^t

我們稱左邊這個matrix為E21，因為是要消去(2,1)這個位置：

同理，第二個pivot的消去，可以寫成E32 * A:

整個消去過程就是以下的matrix multiplication：

U就是最後形成的upper triangle matrix。

 根據associative law重寫上式：

(E32*E21) * A = U

Permutation Matrix

其中一種調換row的permutation matrix，左乘一個row operation matrix:

[0 1
1 0]  就是permutation matrix。

如果要達成以下左matrix變成右matrix:

看起來應該要右乘一個column operation matrix:
[0 1
1  0]

E32*E21怎麼算？Inverse Matrix

當然可以直接算，按照矩陣乘法公式，不過我們不想要這樣算，累！

先想以下情況，一個identity matrix，經過某個matrix 乘積後，變成另一個matrix A，反過來說，A要怎麼還原成identity matrix?

A的第二個row為[-3 1 0]，而且A是identity matrix被重組過後的結果。
根據上面的經驗，它的意義是-3*[1 0 0] + 1*[0 1 0] + 0*[0 0 1]，
所以是identity matrix被左乘以一個row vector[-3 1 0]造成的，

我們要還原回去[0 1 0]的話，就要把-3*[1 0 0]抵銷掉，其餘兩個component不變，inverse matrix row 2 = [3 1 0]

inverse matrix row1 and row3明顯不變，因為A的row1 和 row 3並沒有被重組過。

給個notation就是E^-1