Matrix vector products
我們接下來可以將 matrix 和 vector 結合運算,我們表達 matrix size 為 m × n 時為
A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋱ a m 1 a m n ] \mathbf{A} = \begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & &\ddots\\
a_{m1} & & & a_{mn}
\end{bmatrix} A = a 11 a 21 ⋮ a m 1 a 12 a 22 ⋯ ⋯ ⋱ a 1 n a 2 n a mn 而可以跟他相乘的 vector 的 components 必須要等於 matrix 的 column size
例如: m × y matrix 只能跟 y × n 的 vector 相乘,並且會變成 m × n 的 matrix
[ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋱ a m 1 a m n ] ⋅ [ x 1 x 2 ⋮ x n ] = A x ⃗ = [ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n ] = b = [ b 1 b 2 ⋮ b n ] \begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & &\ddots\\
a_{m1} & & & a_{mn}
\end{bmatrix}
\cdot
\begin{bmatrix}
x_{1} \\x_{2}\\\vdots\\x_{n}
\end{bmatrix}
= \mathbf{A}\vec{x}
= \begin{bmatrix}
a_{11}x_1 + a_{12}x_2+\cdots+a_{1n}x_n\\
a_{21}x_1 + a_{22}x_2+\cdots+a_{2n}x_n\\
\vdots\\
a_{m1}x_1 + a_{m2}x_2+\cdots+a_{mn}x_n\\
\end{bmatrix}=b=
\begin{bmatrix}
b_{1} \\b_{2}\\\vdots\\b_{n}
\end{bmatrix} a 11 a 21 ⋮ a m 1 a 12 a 22 ⋯ ⋯ ⋱ a 1 n a 2 n a mn ⋅ x 1 x 2 ⋮ x n = A x = a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a mn x n = b = b 1 b 2 ⋮ b n 舉個例子
A x ⃗ = [ − 3 0 3 2 1 7 − 1 9 ] [ 2 − 3 4 − 1 ] = [ − 6 + 0 + 12 − 2 2 − 21 − 4 − 9 ] = [ 4 − 32 ] \mathbf{A}\vec{x} =
\begin{bmatrix} -3 & 0 & 3 & 2 \\1 &7 & -1& 9
\end{bmatrix}
\begin{bmatrix} 2 \\-3\\4\\-1
\end{bmatrix}=
\begin{bmatrix} -6+0+12-2 \\ 2-21-4-9
\end{bmatrix} =\begin{bmatrix} 4\\-32
\end{bmatrix} A x = [ − 3 1 0 7 3 − 1 2 9 ] 2 − 3 4 − 1 = [ − 6 + 0 + 12 − 2 2 − 21 − 4 − 9 ] = [ 4 − 32 ] 我們可以把 matrix A 的兩列視為兩個 row vector ,也就是 column vector 的 Transpose
並且把矩陣相乘的結果表示為 Dot Product
a 1 ⃗ = [ − 3 0 3 2 ] , a 2 ⃗ = [ 1 7 − 1 9 ] , A x ⃗ = [ a 1 T ⃗ a 2 T ⃗ ] x ⃗ = [ a 1 ⃗ ⋅ x ⃗ a 2 ⃗ ⋅ x ⃗ ] \vec{a_1} = \begin{bmatrix} -3\\0\\3\\2\end{bmatrix},
\vec{a_2} = \begin{bmatrix} 1\\7\\-1\\9\end{bmatrix},
\mathbf{A}\vec{x} = \begin{bmatrix} \vec{a_1^T} \\\vec{a_2^T} \end{bmatrix}\vec{x}
= \begin{bmatrix} \vec{a_1}\cdot\vec{x}\\ \vec{a_2}\cdot\vec{x} \end{bmatrix} a 1 = − 3 0 3 2 , a 2 = 1 7 − 1 9 , A x = [ a 1 T a 2 T ] x = [ a 1 ⋅ x a 2 ⋅ x ] 我們也可以把矩陣視為一個一個的 column vector
A x ⃗ = [ − 3 0 3 2 1 7 − 1 9 ] [ x 1 x 2 x 3 x 4 ] \mathbf{A}\vec{x} =
\begin{bmatrix} \color{red}-3 & \color{blue}0 & \color{green}3 & \color{orange}2
\\\color{red}1 &\color{blue}7 & \color{green}-1& \color{orange}9
\end{bmatrix}
\begin{bmatrix} x_1 \\x_2\\x_3\\x_4
\end{bmatrix} A x = [ − 3 1 0 7 3 − 1 2 9 ] x 1 x 2 x 3 x 4 把矩陣相乘的結果表示為每個 vector 和 xi 的乘積相加的 linear combination
A x ⃗ = [ v 1 ⃗ v 2 ⃗ v 3 ⃗ v 4 ⃗ ] [ x 1 x 2 x 3 x 4 ] = x 1 v 1 ⃗ + x 2 v 2 ⃗ + x 3 v 4 ⃗ + x 4 v 4 ⃗ \mathbf{A}\vec{x} = \begin{bmatrix}\color{red}\vec{v_1} & \color{blue}\vec{v_2} & \color{green}\vec{v_3} & \color{orange}\vec{v_4}\end{bmatrix} \begin{bmatrix} x_1 \\x_2\\x_3\\x_4
\end{bmatrix} = x_1\vec{v_1} + x_2\vec{v_2} +x_3\vec{v_4} +x_4\vec{v_4} A x = [ v 1 v 2 v 3 v 4 ] x 1 x 2 x 3 x 4 = x 1 v 1 + x 2 v 2 + x 3 v 4 + x 4 v 4 Null space of a matrix
假設有一個 matrix A: m × n,和 vector x 相乘皆為零向量,我們稱之為 homogeneous equation
A : m × n A x ⃗ = 0 \begin{aligned}
&\mathbf{A}: m\times n \\
&\mathbf{A}\vec{x} = \mathbf{0}\\
\end{aligned} A : m × n A x = 0 現在我們想知道所有能夠符合這個 equation 的 x 集合,能不能構成一個 valid 的 subspace ?
N = { x ⃗ ∈ R n ∣ A x ⃗ = 0 } \mathbf{N} = \begin{Bmatrix} \vec{x} \in \mathbb{R}^n \mid \mathbf{A}\vec{x} = \mathbf{0}\end{Bmatrix} N = { x ∈ R n ∣ A x = 0 } 答案是可以的,他符合 subspace 的三項條件
x 符合加法封閉 (closure under addition)
x 符合乘法封閉 (closure under scalar multiplication)
1. A 0 = 0 , 0 ∈ N 2. v 1 , v 2 ∈ N , A v 1 = 0 , A v 2 = 0 A ( v 1 + v 2 ) = A v 1 + A v 2 = 0 + 0 = 0 3. v 1 ∈ N , c ∈ R A ( c v 1 ) = c ( A v 1 ) = c 0 = 0 \begin{aligned}
1. \,\,\, &\mathbf{A}\mathbf{0}=\mathbf{0}, \mathbf{0} \in N\\\\
2. \,\,\, &v_1, v_2 \in N, \,\mathbf{A}v_1 = \mathbf{0},\, \mathbf{A}v_2 = \mathbf{0} \\ & \mathbf{A}(v_1+v_2) = \mathbf{A}v_1+\mathbf{A}v_2 = \mathbf{0 + 0 = 0}\\\\
3. \,\,\, &v_1 \in N, c \in \mathbb{R}\\
&\mathbf{A}(cv_1) = c(\mathbf{A}v_1) = c\mathbf{0}= \mathbf{0}
\end{aligned} 1. 2. 3. A0 = 0 , 0 ∈ N v 1 , v 2 ∈ N , A v 1 = 0 , A v 2 = 0 A ( v 1 + v 2 ) = A v 1 + A v 2 = 0 + 0 = 0 v 1 ∈ N , c ∈ R A ( c v 1 ) = c ( A v 1 ) = c 0 = 0 我們稱這個 subspace N 為 A 的 NullSpace
N = N ( A ) = Nullspace of A \mathbf{N} = N(\mathbf{A}) = \text{Nullspace of } \mathbf{A} N = N ( A ) = Nullspace of A Calculating the null space of a matrix
我們來試著計算隨便一個 matrix A 他的 nullspace 為何
A = [ 1 1 1 1 1 2 3 4 4 3 2 1 ] [ x 1 x 2 x 3 x 4 ] = [ 0 0 0 ] \mathbf{A} = \begin{bmatrix} 1&1&1&1 \\ 1&2&3&4 \\ 4&3&2&1\end{bmatrix}
\begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix} =
\begin{bmatrix} 0\\0\\0\end{bmatrix} A = 1 1 4 1 2 3 1 3 2 1 4 1 x 1 x 2 x 3 x 4 = 0 0 0 也就是解決 equation
x 1 + x 2 + x 3 + x 4 = 0 x 1 + 2 x 2 + 3 x 3 + 4 x 4 = 0 4 x 1 + 3 x 2 + 2 x 3 + x 4 = 0 \begin{aligned}
x_1+x_2+x_3+x_4&=0\\
x_1+2x_2+3x_3+4x_4&=0\\
4x_1+3x_2+2x_3+x_4&=0
\end{aligned} x 1 + x 2 + x 3 + x 4 x 1 + 2 x 2 + 3 x 3 + 4 x 4 4 x 1 + 3 x 2 + 2 x 3 + x 4 = 0 = 0 = 0 可以利用 Reduced row echelon form 來解
[ 1 1 1 1 0 1 2 3 4 0 4 3 2 1 0 ] ⇒ [ 1 1 1 1 0 0 1 2 3 0 0 1 2 3 0 ] ⇒ [ 1 0 − 1 − 2 0 0 1 2 3 0 0 0 0 0 0 ] \begin{bmatrix}\begin{array}{cccc|c} 1&1&1&1&0 \\ 1&2&3&4&0 \\ 4&3&2&1&0\end{array}\end{bmatrix}
\Rightarrow
\begin{bmatrix}\begin{array}{cccc|c} 1&1&1&1&0 \\ 0&1&2&3&0 \\ 0&1&2&3&0\end{array}\end{bmatrix}
\Rightarrow
\begin{bmatrix}\begin{array}{cccc|c} 1&0&-1&-2&0 \\ 0&1&2&3&0 \\ 0&0&0&0&0\end{array}\end{bmatrix} 1 1 4 1 2 3 1 3 2 1 4 1 0 0 0 ⇒ 1 0 0 1 1 1 1 2 2 1 3 3 0 0 0 ⇒ 1 0 0 0 1 0 − 1 2 0 − 2 3 0 0 0 0 再轉回 equation
x 1 − x 3 − 2 x 4 = 0 ⇒ x 1 = x 3 + 2 x 4 x 2 + 2 x 3 + 3 x 4 = 0 ⇒ x 2 = − 2 x 3 − 3 x 4 \begin{aligned}
x_1 -x_3-2x_4&=0 \Rightarrow \color{red}{x_1=x_3+2x_4}\\
x_2+2x_3+3x_4&=0 \Rightarrow \color{red}{x_2=-2x_3-3x_4}
\end{aligned} x 1 − x 3 − 2 x 4 x 2 + 2 x 3 + 3 x 4 = 0 ⇒ x 1 = x 3 + 2 x 4 = 0 ⇒ x 2 = − 2 x 3 − 3 x 4 最後得出一個 linear combination,其中 x3 和 x4 可以為任何實數,來拖移兩個向量在 R4 nullspace 移動
[ x 1 x 2 x 3 x 4 ] = x 3 [ 1 − 2 1 0 ] + x 4 [ 2 − 3 0 1 ] \begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix}=
x_3\begin{bmatrix} 1\\-2\\1\\0 \end{bmatrix}+
x_4\begin{bmatrix} 2\\-3\\0\\1 \end{bmatrix} x 1 x 2 x 3 x 4 = x 3 1 − 2 1 0 + x 4 2 − 3 0 1 也就是這個 nullspace 是由這兩個向量來 span 而成的
其實也可以發現,要求得 N(A) 跟求得 N(rref(A)) 的 nullspace 是一樣的
N ( A ) = s p a n ( [ 1 − 2 1 0 ] , [ 2 − 3 0 1 ] ) = N ( r r e f ( A ) ) N(\mathbf{A}) = span\left(\begin{bmatrix}1\\-2\\1\\0\end{bmatrix}, \begin{bmatrix}2\\-3\\0\\1\end{bmatrix}\right)= N(rref(\mathbf{A})) N ( A ) = s p an 1 − 2 1 0 , 2 − 3 0 1 = N ( rre f ( A )) Null space's relation to linear independence
當 matrix A 為 m × n 時,其 nullspace 一定為 n 個 components 的 vector
N ( A ) = { x ⃗ ∈ R n ∣ A x ⃗ = 0 ⃗ } N(\mathbf{A}) = \begin{Bmatrix} \vec{x} \in \mathbb{R}^n \mid \mathbf{A}\vec{x}=\vec{0}\end{Bmatrix} N ( A ) = { x ∈ R n ∣ A x = 0 } 得出來的 0 矩陣會有 m 個 components
A m × n = [ v 1 ⃗ v 2 ⃗ ⋯ v n ⃗ ] [ x 1 x 2 ⋮ x n ] = [ 0 1 0 2 ⋮ 0 m ] \mathbf{A}_{m \times n} = \begin{bmatrix} \vec{v_1} & \vec{v_2} & \cdots & \vec{v_n} \end{bmatrix}\begin{bmatrix} x_1\\x_2\\\vdots \\ x_n \end{bmatrix} = \begin{bmatrix} 0_1\\0_2\\\vdots \\ 0_m \end{bmatrix} A m × n = [ v 1 v 2 ⋯ v n ] x 1 x 2 ⋮ x n = 0 1 0 2 ⋮ 0 m 我們將上面的運算拆出來變成 linear combination 的形式
x 1 v 1 ⃗ + x 2 v 2 ⃗ + ⋯ + x n v n ⃗ = 0 ⃗ x_1\vec{v_1} + x_2\vec{v_2} + \cdots + x_n\vec{v_n} = \vec{0} x 1 v 1 + x 2 v 2 + ⋯ + x n v n = 0 這時我們思考,若 v1 到 vn 要 linear independence ,那 x1 到 xn 必須都為 0
若 x1 到 xn 都為 0,代表這個 linear combination 只有唯一解
也就是說,A 的 nullspace 在 v1 到 vn 皆為 linear independence 下只有 0 矩陣而已
v 1 , v 2 , ⋯ , v n L.I ⟺ x 1 , x 2 , ⋯ , x n = 0 ⟺ N ( A ) = { 0 ⃗ } v_1,v_2,\cdots,v_n \text{ L.I} \iff x_1, x_2,\cdots,x_n =0 \iff N(\mathbf{A}) = \begin{Bmatrix} \vec{0} \end{Bmatrix} v 1 , v 2 , ⋯ , v n L.I ⟺ x 1 , x 2 , ⋯ , x n = 0 ⟺ N ( A ) = { 0 } Column space of a matrix
我們已經知道 m × n 代表 Matrix A 有 n 個 column vector,每個都在 Rm 空間
A m × n = [ v 1 ⃗ v 2 ⃗ ⋯ v n ⃗ ] , v 1 ⃗ , v 2 ⃗ , ⋯ , v n ⃗ ∈ R m \mathbf{A}_{m \times n} = \begin{bmatrix} \vec{v_1} & \vec{v_2} & \cdots & \vec{v_n} \end{bmatrix}
, \vec{v_1}, \vec{v_2},\cdots, \vec{v_n}\in \mathbb{R}^m A m × n = [ v 1 v 2 ⋯ v n ] , v 1 , v 2 , ⋯ , v n ∈ R m 而 Column space 指的就是由這 n 個 column vector 所 span 的空間
C ( A ) = s p a n ( v 1 ⃗ , v 2 ⃗ , ⋯ , v n ⃗ ) C(\mathbf{A}) = span\left( \vec{v_1}, \vec{v_2},\cdots, \vec{v_n} \right) C ( A ) = s p an ( v 1 , v 2 , ⋯ , v n ) 我們也知道 span 出來的空間符合 subspace 的三大條件
a ⃗ ∈ C ( A ) a ⃗ = c 1 v 1 ⃗ + c 2 v 2 ⃗ + ⋯ + c n v n ⃗ 1. a ⃗ contains zero vector 2. s a ⃗ = s c 1 v 1 ⃗ + s c 2 v 2 ⃗ + ⋯ + s c n v n ⃗ , s a ⃗ ∈ C ( A ) 3. b ⃗ = b 1 v 1 ⃗ + b 2 v 2 ⃗ + ⋯ + b n v n ⃗ , b ⃗ ∈ C ( A ) a ⃗ + b ⃗ = ( c 1 + b 1 ) v 1 ⃗ + ( c 2 + b 2 ) v 2 ⃗ + ⋯ + ( c n + b n ) v n ⃗ ∈ C ( A ) \begin{aligned}
\vec{a} &\in C(\mathbf{A})\\
\vec{a} &= c_1\vec{v_1} + c_2\vec{v_2} + \cdots + c_n\vec{v_n}\\\\
1.\,\, &\vec{a} \text{ contains zero vector}\\
2.\,\, &s\vec{a} = sc_1\vec{v_1} + sc_2\vec{v_2} + \cdots + sc_n\vec{v_n},\,\, s\vec{a} \in C(\mathbf{A})\\
3.\,\, &\vec{b} = b_1\vec{v_1} + b_2\vec{v_2} + \cdots + b_n\vec{v_n},\,\, \vec{b} \in C(\mathbf{A})\\
&\vec{a}+\vec{b} = (c_1+b_1)\vec{v_1} + (c_2+b_2)\vec{v_2} + \cdots + (c_n+b_n)\vec{v_n} \in C(\mathbf{A})
\end{aligned} a a 1. 2. 3. ∈ C ( A ) = c 1 v 1 + c 2 v 2 + ⋯ + c n v n a contains zero vector s a = s c 1 v 1 + s c 2 v 2 + ⋯ + s c n v n , s a ∈ C ( A ) b = b 1 v 1 + b 2 v 2 + ⋯ + b n v n , b ∈ C ( A ) a + b = ( c 1 + b 1 ) v 1 + ( c 2 + b 2 ) v 2 + ⋯ + ( c n + b n ) v n ∈ C ( A ) 我們可以用下面 Set 的方式來思考 Column space
Column space 就是 matrix A 和任何可以與他相乘的 vector x 所生成的所有向量集合
vector x 必須要為 n 個 components 這樣才可以相乘
{ A x ⃗ ∣ x ⃗ ∈ R n } ∣ A x ⃗ = x 1 v 1 ⃗ + x 2 v 2 ⃗ + ⋯ + x n v n ⃗ \begin{Bmatrix}\mathbf{A}\vec{x}\mid\vec{x}\in\mathbb{R}^n \end{Bmatrix} \mid
\mathbf{A}\vec{x}= x_1\vec{v_1} + x_2\vec{v_2} + \cdots + x_n\vec{v_n} { A x ∣ x ∈ R n } ∣ A x = x 1 v 1 + x 2 v 2 + ⋯ + x n v n 可以表示成
{ x 1 v 1 ⃗ + x 2 v 2 ⃗ + ⋯ + x n ∣ x 1 , x 2 , ⋯ , x n ∈ R } = s p a n ( v 1 ⃗ , v 2 ⃗ , ⋯ , v n ⃗ ) = C ( A ) \begin{Bmatrix}x_1\vec{v_1} + x_2\vec{v_2} + \cdots + x_n \mid x_1,x_2,\cdots,x_n \in\mathbb{R} \end{Bmatrix}
= span\left( \vec{v_1}, \vec{v_2},\cdots, \vec{v_n} \right)
= C(\mathbf{A}) { x 1 v 1 + x 2 v 2 + ⋯ + x n ∣ x 1 , x 2 , ⋯ , x n ∈ R } = s p an ( v 1 , v 2 , ⋯ , v n ) = C ( A ) 舉個例子,若向量 b1 不在 A 的 column space 裡,那 Ax = b1 是永遠不會有解的
相反,若向量 b2 他存在於 A 的 column space 裡,那 Ax = b2 將至少會有一個解
b 1 ⃗ ∉ C ( A ) ∣ A x ⃗ = b 1 ⃗ has no solution b 2 ⃗ ∈ C ( A ) ∣ A x ⃗ = b 2 ⃗ has a least one solution \begin{aligned}
\vec{b_1} \notin C(\mathbf{A}) &\mid \mathbf{A}\vec{x} = \vec{b_1} \text{ has no solution}\\
\vec{b_2} \in C(\mathbf{A}) &\mid \mathbf{A}\vec{x} = \vec{b_2} \text{ has a least one solution}\\
\end{aligned} b 1 ∈ / C ( A ) b 2 ∈ C ( A ) ∣ A x = b 1 has no solution ∣ A x = b 2 has a least one solution Null space and column space basis
現在要找出下面 matrix A 的 column space 和 null space
A = [ 1 1 1 1 2 1 4 3 3 4 1 2 ] \mathbf{A}= \begin{bmatrix} 1&1&1&1\\2&1&4&3\\ 3&4&1&2\end{bmatrix} A = 1 2 3 1 1 4 1 4 1 1 3 2 我們可以非常輕鬆求得他的 column space 等於每個 column vector span 而成的空間
但他是否為這個空間的 basis 呢 ? (要為 basis 必須要 linear independence)
C ( A ) = s p a n ( [ 1 2 3 ] , [ 1 1 4 ] , [ 1 4 1 ] , [ 1 3 2 ] ) C(\mathbf{A}) = span\left(
\begin{bmatrix}1\\2\\3\end{bmatrix},
\begin{bmatrix}1\\1\\4\end{bmatrix},
\begin{bmatrix}1\\4\\1\end{bmatrix},
\begin{bmatrix}1\\3\\2\end{bmatrix} \right) C ( A ) = s p an 1 2 3 , 1 1 4 , 1 4 1 , 1 3 2 要知道 matrix A 有沒有 linear independence 只要看 null space 是否只有包含 0 向量即可
x 1 v 1 ⃗ + x 2 v 2 ⃗ + ⋯ + x n v n ⃗ = 0 ∣ x 1 , x 2 , ⋯ , x n = 0 ⟺ A is L.I. A x ⃗ = 0 , x ⃗ = { 0 ⃗ } x_1\vec{v_1}+ x_2\vec{v_2} + \cdots + x_n\vec{v_n} = 0 \mid x_1,x_2,\cdots,x_n = 0 \iff \mathbf{A} \text{ is L.I.}\\
A\vec{x}=0, \vec{x} = \begin{Bmatrix}\vec{0} \end{Bmatrix} x 1 v 1 + x 2 v 2 + ⋯ + x n v n = 0 ∣ x 1 , x 2 , ⋯ , x n = 0 ⟺ A is L.I. A x = 0 , x = { 0 } 要求 A 的 null space 等於求 rref(A) 的 null space
r r e f ( A ) = [ 1 0 3 2 0 1 − 2 − 1 0 0 0 0 ] [ x 1 x 2 x 3 x 4 ] = [ 0 0 0 ] rref(\mathbf{A})= \begin{bmatrix} 1&0&3&2\\0&1&-2&-1\\ 0&0&0&0\end{bmatrix}
\begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix} =
\begin{bmatrix} 0\\0\\0\end{bmatrix} rre f ( A ) = 1 0 0 0 1 0 3 − 2 0 2 − 1 0 x 1 x 2 x 3 x 4 = 0 0 0 將矩陣列回 equation
x 1 + 3 x 3 + 2 x 4 = 0 ⇒ x 1 = − 3 x 3 − 2 x 4 x 2 − 2 x 3 − x 4 = 0 ⇒ x 2 = 2 x 3 + x 4 x_1+3x_3+2x_4=0 \Rightarrow \color{red}{x_1=-3x_3-2x_4}\\
x_2-2x_3-x_4=0 \Rightarrow \color{red}{x_2 = 2x_3+x_4}\\ x 1 + 3 x 3 + 2 x 4 = 0 ⇒ x 1 = − 3 x 3 − 2 x 4 x 2 − 2 x 3 − x 4 = 0 ⇒ x 2 = 2 x 3 + x 4 並且利用 free variables 來表示 null space 空間
[ x 1 x 2 x 3 x 4 ] = x 3 [ − 3 2 1 0 ] + x 4 [ − 2 1 0 1 ] \begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix} =
x_3\begin{bmatrix} -3\\2\\1\\0\end{bmatrix} +
x_4\begin{bmatrix} -2\\1\\0\\1\end{bmatrix} x 1 x 2 x 3 x 4 = x 3 − 3 2 1 0 + x 4 − 2 1 0 1 至此,我們可以得到 null space 為下,而且並不是只含有 0 向量
N ( A ) = N ( r r e f ( A ) ) = s p a n ( [ − 3 2 1 0 ] , [ − 2 1 0 1 ] ) N(\mathbf{A}) = N(rref(\mathbf{A}))=span\left(\begin{bmatrix} -3\\2\\1\\0\end{bmatrix},\begin{bmatrix} -2\\1\\0\\1\end{bmatrix}\right) N ( A ) = N ( rre f ( A )) = s p an − 3 2 1 0 , − 2 1 0 1 所以 A 不為 linear independence,也就是剛剛的 column space 不為 basis
要得到 basis 我們要從剛剛的 column space 刪除多餘的 vectors
x 1 = − 3 x 3 − 2 x 4 x 2 = 2 x 3 + x 4 \begin{aligned}
x_1 &= -3x_3-2x_4\\
x_2 &= 2x_3+x_4
\end{aligned} x 1 x 2 = − 3 x 3 − 2 x 4 = 2 x 3 + x 4 透過剛剛求得的 equation,我們知道 x1 和 x2 都可以由 x3 和 x4 組成,所以 x3 和 x4 是多餘的
basis of C ( A ) = s p a n ( x 1 ⃗ , x 2 ⃗ ) = s p a n ( [ 1 2 3 ] , [ 1 1 4 ] ) \text{basis of } C(\mathbf{A}) = span\left(\vec{x_1},\vec{x_2} \right) = span\left(
\begin{bmatrix}1\\2\\3\end{bmatrix},
\begin{bmatrix}1\\1\\4\end{bmatrix}\right) basis of C ( A ) = s p an ( x 1 , x 2 ) = s p an 1 2 3 , 1 1 4 Visualizing a column space as a plane in R3
從上面的例子我們知道兩個 R3 vector 所 span 出來的為三維空間 中的一個平面
那我們要怎麼找出平面呢 ?
方法一
先找到 normal vector (可以由 (1, 2, 3) 和 (1, 1, 4) 的 Cross product 求得!)
再從任一點向量 (x, y, z) 和 (1, 2, 3) 或 (1, 1, 4) 相減得到一條 躺在該平面上的向量
最後因為該向量跟 normval vector 會垂直,所以 dot product 為 0
n ⃗ ⋅ ( x ⃗ − [ 1 2 3 ] ) = 0 ⃗ \vec{n} \cdot (\vec{x} - \begin{bmatrix}1\\2\\3\end{bmatrix}) = \vec{0} n ⋅ ( x − 1 2 3 ) = 0 來找 normal vector n
n ⃗ = [ 1 2 3 ] × [ 1 1 4 ] = [ 8 − 3 − ( 4 − 3 ) 1 − 2 ] = [ 5 − 1 − 1 ] \vec{n} =
\begin{bmatrix}1\\2\\3\end{bmatrix}\times
\begin{bmatrix}1\\1\\4\end{bmatrix} =
\begin{bmatrix}8-3\\-(4-3)\\1-2\end{bmatrix} =
\begin{bmatrix}5\\-1\\-1\end{bmatrix} n = 1 2 3 × 1 1 4 = 8 − 3 − ( 4 − 3 ) 1 − 2 = 5 − 1 − 1 接著代回上面式子
[ 5 − 1 − 1 ] ⋅ [ x − 1 y − 2 z − 3 ] = 0 \begin{bmatrix}5\\-1\\-1\end{bmatrix} \cdot
\begin{bmatrix}x-1\\y-2\\z-3\end{bmatrix}=0 5 − 1 − 1 ⋅ x − 1 y − 2 z − 3 = 0 即可得到平面方程式
5 ( x − 1 ) − 1 ( y − 2 ) − 1 ( z − 3 ) = 0 ⇒ 5 x − 5 − y + 2 − z + 3 = 0 ⇒ 5 x − y − z = 0 ∈ C ( A ) \begin{aligned}
&5(x-1)-1(y-2)-1(z-3)=0\\
\Rightarrow\,\,&5x-5-y+2-z+3=0\\
\Rightarrow\,\,&5x-y-z=0 \in C(\mathbf{A})
\end{aligned} ⇒ ⇒ 5 ( x − 1 ) − 1 ( y − 2 ) − 1 ( z − 3 ) = 0 5 x − 5 − y + 2 − z + 3 = 0 5 x − y − z = 0 ∈ C ( A ) 方法二
我們知道,Column space 裡的任何一個解 (vector b) 都應該在該平面上
C ( A ) = { A x ⃗ ∣ x ⃗ ∈ R n } = { b ⃗ ∣ A x ⃗ = b ⃗ AND x ⃗ ∈ R n } C(\mathbf{A}) =
\begin{Bmatrix} \mathbf{A}\vec{x}\mid\ \vec{x}\in \mathbb{R}^n \end{Bmatrix}=
\begin{Bmatrix} \vec{b}\mid\ \mathbf{A}\vec{x} = \vec{b} \text{ AND } \vec{x} \in \mathbb{R}^n \end{Bmatrix} C ( A ) = { A x ∣ x ∈ R n } = { b ∣ A x = b AND x ∈ R n } 我們又知道,要解決 Ax=b 可以轉換為 [A|b] 的矩陣來求 reduced row echelon form
b ⃗ = [ x y z ] , A x ⃗ = b ⃗ ⇒ [ 1 1 1 1 x 2 1 4 3 y 3 4 1 2 z ] → [ 1 1 1 1 x 0 1 − 2 − 1 2 x − y 0 0 0 0 5 x − y − z ] \vec{b} = \begin{bmatrix} x\\y\\z\end{bmatrix},
\mathbf{A}\vec{x}=\vec{b} \Rightarrow
\begin{bmatrix} \begin{array}{cccc|c} 1&1&1&1&x\\2&1&4&3&y\\3&4&1&2&z \end{array} \end{bmatrix} \rightarrow
\begin{bmatrix} \begin{array}{cccc|c} 1&1&1&1&x\\0&1&-2&-1&2x-y\\0&0&0&0&5x-y-z \end{array} \end{bmatrix} b = x y z , A x = b ⇒ 1 2 3 1 1 4 1 4 1 1 3 2 x y z → 1 0 0 1 1 0 1 − 2 0 1 − 1 0 x 2 x − y 5 x − y − z 要滿足 Ax=b 的 b 為 valid vector,那最後一行的 5x - y - z 必須要等於 0 才行,所以我們得到
5 x − y − z = 0 ∈ C ( A ) 5x-y-z = 0 \in C(\mathbf{A}) 5 x − y − z = 0 ∈ C ( A ) Any subspace basis has same number of elements
下面用矛盾證明 subspace 的 basis 所含的 elements 數量皆相同
A = { a 1 , a 2 , ⋯ , a n } is basis of V B = { b 1 , b 2 , ⋯ , b m } spans V ∣ m < n \begin{aligned}
\mathbf{A} &= \begin{Bmatrix} a_1,a_2,\cdots,a_n\end{Bmatrix} \text{ is basis of } \mathbf{V}\\
\mathbf{B} &= \begin{Bmatrix} b_1,b_2,\cdots,b_m\end{Bmatrix} \text{ spans } \mathbf{V} \mid m<n\\
\end{aligned} A B = { a 1 , a 2 , ⋯ , a n } is basis of V = { b 1 , b 2 , ⋯ , b m } spans V ∣ m < n 若把 a1, a2 依序帶入 B set 中取代 b1, b2 ,表面上可以維持 B spans V
而且取代時不可以把原本在 A set 的元素取代掉,因為 A set 的元素之間是 linear independence 的
B 1 = { a 1 , b 2 , b 3 , ⋯ , b m } spans V B 2 = { a 1 , a 2 , b 3 , ⋯ , b m } spans V ⋮ B m = { a 1 , a 2 , a 3 , ⋯ , a m } spans V \begin{aligned}
&\mathbf{B_1} = \begin{Bmatrix} a_1, b_2,b_3, \cdots, b_m\end{Bmatrix} \text{ spans }\mathbf{V}\\
&\mathbf{B_2} = \begin{Bmatrix} a_1, a_2,b_3, \cdots, b_m\end{Bmatrix} \text{ spans }\mathbf{V}\\
&\vdots\\
&\mathbf{B_m} = \begin{Bmatrix} a_1, a_2,a_3, \cdots, a_m\end{Bmatrix} \text{ spans }\mathbf{V}\\
\end{aligned} B 1 = { a 1 , b 2 , b 3 , ⋯ , b m } spans V B 2 = { a 1 , a 2 , b 3 , ⋯ , b m } spans V ⋮ B m = { a 1 , a 2 , a 3 , ⋯ , a m } spans V 但是我們知道 m < n , A 又可以表示成 Bm 的延伸
A = { a 1 , a 2 , ⋯ , a m , ⋯ a n } is basis of V \mathbf{A} = \begin{Bmatrix} \color{red}{a_1,a_2,\cdots,a_m}\color{black},\cdots a_n\end{Bmatrix} \text{ is basis of } \mathbf{V} A = { a 1 , a 2 , ⋯ , a m , ⋯ a n } is basis of V 我們知道 A 已經確定是 span V 的最小組合了,但卻又能用 m 個 a 元素來 span V,產生矛盾
因此,不可能有比 basis 更少的元素組合可以 span subspace
而且,basis 也不能有多餘的元素出現在裡面
綜合在一起,同一個 subspace 底下的任何 basis 都擁有一個數量的 elements
我們又將這些 basis 共同擁有的元素數量,稱作 dimension
D i m ( A ) = n Dim(\mathbf{A}) = n D im ( A ) = n Dimension of the null space or nullity
假設我們要找出 matrix B 的 nullspace
B = [ 1 1 2 3 2 1 1 3 1 4 ] \mathbf{B} = \begin{bmatrix}1&1&2&3&2\\1&1&3&1&4\end{bmatrix} B = [ 1 1 1 1 2 3 3 1 2 4 ] 我們知道只要將 B 轉為 reduced row echelon form
r r e f ( B ) = [ 1 1 0 7 − 2 0 0 1 − 2 2 ] [ x 1 x 2 x 3 x 4 x 5 ] = [ 0 0 ] rref(\mathbf{B})= \begin{bmatrix}1&1&0&7&-2\\0&0&1&-2&2\end{bmatrix}
\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix} =
\begin{bmatrix}0\\0\end{bmatrix} rre f ( B ) = [ 1 0 1 0 0 1 7 − 2 − 2 2 ] x 1 x 2 x 3 x 4 x 5 = [ 0 0 ] 再利用 equation 就可以找出 span null space 的向量集
x 1 + x 2 + 7 x 4 − 2 x 5 = 0 ⇒ x 1 = − x 2 − 7 x 4 + 2 x 5 x 3 − 2 x 4 + 2 x 5 = 0 ⇒ x 3 = 2 x 4 − 2 x 5 [ x 1 x 2 x 3 x 4 x 5 ] = x 2 [ − 1 1 0 0 0 ] + x 4 [ − 7 0 2 1 0 ] + x 5 [ 2 0 − 2 0 1 ] x_1+x_2+7x_4-2x_5=0 \Rightarrow \color{red}{x_1=-x_2-7x_4+2x_5}\\
x_3-2x_4+2x_5=0 \Rightarrow \color{red}{x_3=2x_4-2x_5}\\
\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix} =
x_2\begin{bmatrix} -1\\1\\0\\0\\0\end{bmatrix}+
x_4\begin{bmatrix} -7\\0\\2\\1\\0\end{bmatrix}+
x_5\begin{bmatrix} 2\\0\\-2\\0\\1\end{bmatrix} x 1 + x 2 + 7 x 4 − 2 x 5 = 0 ⇒ x 1 = − x 2 − 7 x 4 + 2 x 5 x 3 − 2 x 4 + 2 x 5 = 0 ⇒ x 3 = 2 x 4 − 2 x 5 x 1 x 2 x 3 x 4 x 5 = x 2 − 1 1 0 0 0 + x 4 − 7 0 2 1 0 + x 5 2 0 − 2 0 1 所以 N(B) =
N ( B ) = N ( r r e f ( B ) ) = s p a n ( [ − 1 1 0 0 0 ] , [ − 7 0 2 1 0 ] , [ 2 0 − 2 0 1 ] ) = s p a n ( v 1 ⃗ , v 2 ⃗ , v 3 ⃗ ) N(\mathbf{B}) = N(rref(\mathbf{B})) = span\left(
\begin{bmatrix}-1\\1\\0\\0\\0\end{bmatrix},
\begin{bmatrix}-7\\0\\2\\1\\0\end{bmatrix},
\begin{bmatrix}2\\0\\-2\\0\\1\end{bmatrix}
\right) = span(\vec{v_1},\vec{v_2},\vec{v_3}) N ( B ) = N ( rre f ( B )) = s p an − 1 1 0 0 0 , − 7 0 2 1 0 , 2 0 − 2 0 1 = s p an ( v 1 , v 2 , v 3 ) 而且這三個向量 linear independent,所以為 N(B) 的 basis
然後因為找到 basis 了,所以 N(B) 的 dimension 為 3,又可以稱作 nullity = 3
🤷♂️ Nullity = reduced row echelon form 的 non-pivot column 數量
Dimension of the column space or rank
我們可以將 matrix A 的 column 分為五等份,而 column space 即為這五個 column 所 span 而成
A = [ 1 0 − 1 0 4 2 1 0 0 9 − 1 2 5 1 − 5 1 − 1 − 3 − 2 9 ] , C ( A ) = s p a n ( [ − 1 2 − 1 1 ] , [ 0 1 2 − 1 ] , [ − 1 0 5 − 3 ] , [ 0 0 1 − 2 ] , [ 4 9 − 5 9 ] ) \mathbf{A} = \begin{bmatrix}1&0&-1&0&4\\2&1&0&0&9\\-1&2&5&1&-5\\1&-1&-3&-2&9\end{bmatrix},
C(\mathbf{A}) = span\left(
\begin{bmatrix}-1\\2\\-1\\1\end{bmatrix},
\begin{bmatrix}0\\1\\2\\-1\end{bmatrix},
\begin{bmatrix}-1\\0\\5\\-3\end{bmatrix},
\begin{bmatrix}0\\0\\1\\-2\end{bmatrix},
\begin{bmatrix}4\\9\\-5\\9\end{bmatrix}
\right) A = 1 2 − 1 1 0 1 2 − 1 − 1 0 5 − 3 0 0 1 − 2 4 9 − 5 9 , C ( A ) = s p an − 1 2 − 1 1 , 0 1 2 − 1 , − 1 0 5 − 3 , 0 0 1 − 2 , 4 9 − 5 9 但我們並不知道他們五個是否 linear independent,即是否為 basis of column space
這邊提供一個方法找出 column space 的 basis 並且得知他的 dimension 也就是 rank
先將 A 化簡為 reduced row echelon form
這些 column 對應回 A ,即是 C(A) 的 basis
r r e f ( A ) = [ 1 0 − 1 0 4 0 1 2 0 1 0 0 0 1 − 3 0 0 0 0 0 ] rref(\mathbf{A}) = \begin{bmatrix}
\color{red}1&\color{blue}0&-1&\color{green}0&4\\
\color{red}0&\color{blue}1&2&\color{green}0&1\\
\color{red}0&\color{blue}0&0&\color{green}1&-3\\
\color{red}0&\color{blue}0&0&\color{green}0&0\end{bmatrix} rre f ( A ) = 1 0 0 0 0 1 0 0 − 1 2 0 0 0 0 1 0 4 1 − 3 0 因為 1, 2, 4 行為 pivot column ,所以對應回 A 的 1, 2, 4 行即為 C(A) 的 basis
C ( A ) = s p a n ( [ − 1 2 − 1 2 ] , [ 0 1 2 − 1 ] , [ 0 0 1 − 2 ] ) C(\mathbf{A})= span\left(
\begin{bmatrix}-1\\2\\-1\\2\end{bmatrix},
\begin{bmatrix}0\\1\\2\\-1\end{bmatrix},
\begin{bmatrix}0\\0\\1\\-2\end{bmatrix}
\right) C ( A ) = s p an − 1 2 − 1 2 , 0 1 2 − 1 , 0 0 1 − 2 🤷♂️ Dimension = reduced row echelon form 的 pivot column 數量
以下解釋了為何 rref(A) 的 pivot column 會等於 C(A) 的 basis
Showing relation between basis cols and pivot cols
Showing that the candidate basis does span C(A)