Linear Algebra筆記10 - 解Ax=0的演算法 (non reduced row echelon form)

Solve x for Ax=0

假設有以下的matrix A (3 equations, 4 unknowns):

要解Ax=b（求出x），我們要利用row reduction。
不過這邊不需要把0寫入成augmented matrix，因為將永遠是0向量。

注意高斯消去法顯而易見並不會改變nullspace（意即所有解的set形成的subspace），這正是消去法的作用。不過高斯消去法會改變column space，詳見後述。

再來要注意column2是column1的倍數，且row3 = row1 + row2

Elimination Process

經過第一個pivot(1,1)消去column 1所有非pivot位置的數目：

結果發現(2,2)和(3,2)都變成零了，這表示column2 和 column1有倍數關係才會變成這樣的結果。

不過這邊有一點奇怪，這不是一個square matrix，所以這算是第一次課堂上用non-square matrix來做高斯消去法，所以我們無法最後得到一個upper triangular matrix，只能說近似一個upper triangular matrix。

最後一步消去用pivot (2,3)：

這其實有個專有名詞，稱為echelon form，形成某種階梯形沿著零的項目：

至此，我們已經把Ax=0 化簡成 Ux= 0，而不改變null space!

注意row 3為零row向量，代表其為上方pivot所在的row的linear combination，所以是一個non-independent row。

Rank of Algorithm

這個elimination過程中使用到的pivot數目就是所謂的rank! 在此例中為2。

Pivot variables and free variables

現在來到此演算法的一個關鍵步驟。
所有包含pivot的column稱為pivot variable，反之則稱為free variable，意味著可以assign任何x solution給free columns當linear combination形成null space的係數(i.e. 解），所以在此例中, column2 column4為free columns：

所以某特定解x = (x1 x2 x3 x4)，其中x2 和 x4可以是任意數，例如(x1 1 x3 0)
有了任意設定的x2 x4，我們可以解此Ux=0，藉由back substitution帶入x2=1 和 x4=0:

我們可以得到一組特定解：

所以我們可以確定nullspace至少有包含這條線：任意實數c* vector x。
但這肯定不是整個nullspace，為什麼？因為我們可以任選x2=a, x4=b。

假設我們選x2 = 0, x4=1，可以得出另一個解：

Rank, Pivot Variables, Free Variables的關係

我們已經可以確定rank = pivot variables的數量了，因為這就是rank的定義。
知道了rank，我們也可以知道free variables的數量 = n - rank，如果A為 mxn matrix

事實上rank代表了真正independent equation的數量，在此例中為2，因為第三個equation是row1 + row2，不是independent的。

Generate Nullspace

有了兩個特定解的向量：

我們能產生整個nullspace嗎？

可以，事實上這兩者的linear combination就是：

不過x是一個4-d vector，換句話說nullspace要是 R^4 的subspace。