Linear Algebra Note 3

Vector Spaces and Subspaces (2021.10.27~2021.11.3)

\(A_{m \times n},\ rank(A) = r\)

	\(R\) 的型式	r, m, n 的關係	矩陣種類	解的數量
case 1	\(I\)	\(r = m,\ r = n\)	square & invertible	1
case 2	\(\left[\begin{array}{c} I\\ O\\ \end{array}\right]\)	\(r < m,\ r = n\)	tall & full column rank	0 or 1
case 3	\(\left[\begin{array}{c c} I & F\\ \end{array}\right]\)	\(r = m,\ r < n\)	wide & full row rank	\(\infty\)
case 4	\(\left[\begin{array}{c c} I & F\\ O & O\\ \end{array}\right]\)	\(r < m,\ r < n\)	not full rank	0 or \(\infty\)

• case 1

  • Example
    
    \(\left\{\begin{array}{c} x-y=2 \\ 2x+y=7 \\ \end{array}\right.\to A = \left[\begin{array}{c c} 1 & -1 \\ 2 & 1 \\ \end{array}\right] \to R = \left[\begin{array}{c c} 1 & 0 \\ 0 & 1 \\ \end{array}\right] = I\)
  \(A\vec{x} = \vec{b} \to R\vec{x} = \vec{b'} \implies I\vec{x} = \vec{b'} \\ \therefore A^{-1}(A\vec{x}) = A^{-1}\vec{b} \iff \vec{x_p} =A^{-1}\vec{b} = \vec{b'} \to \text{1 solution}\)
  For
  \(\vec{X_n}\) , we solve
  \(A\vec{x} = \vec{0}\) by setting
  \(\vec{b} = \vec{0} \implies I\vec{x_n} = \vec{0}\)
  
  \(\implies \vec{x_n} = \vec{0}\) and
  \(K_n = \{ \vec{0} \} \to \text{1 solution}\)

• case 2

  • Example
    
    \(\left\{\begin{array}{c} x-y=2 \\ 2x+y=7 \\ 2x-2y=4\ (or\ 6) \end{array}\right.\to A = \left[\begin{array}{c c} 1 & -1 \\ 2 & 1 \\ 2 & -2 \\ \end{array}\right] \to R = \left[\begin{array}{c c} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{array}\right] = \left[\begin{array}{c} I \\ O \\ \end{array}\right]\)
  \(A\) is
  \(m \times n\) with
  \(m > n\) , assume
  \(r = n\) to make
  \(A\) have full column rank

  For a tall matrix

  \(A\) with full column rank
  1. All columns are pivot columns
  2. No free variables , i.e. no special solutions
  3. \(\mathbb{K_H} = N(A) = \{ \vec{0} \}\)
  4. If
     \(A\vec{x} = \vec{b}\) has 1 solution, then this is the only solution
  • Example
    
    \(A = \left[\begin{array}{c c} 1 & 1 \\ 1 & 2 \\ -2 & -3 \\ \end{array}\right],\ \vec{b} = \left[\begin{array}{c c} b_1 \\ b_2 \\ b_3 \\ \end{array}\right] \\ \left[\begin{array}{c c|c} 1 & 1 & b_1 \\ 1 & 2 & b_2 \\ -2 & -3 & b_3 \\ \end{array}\right] \to \left[\begin{array}{c c|c} 1 & 1 & b_1 \\ 0 & 1 & b_2-b_1 \\ 0 & -1 & b_3+2b_1 \\ \end{array}\right] \to \left[\begin{array}{c c|c} 1 & 0 & 2b_1-b_2 \\ 0 & 1 & b_2-b_1 \\ 0 & 0 & b_3+b_2+b_1 \\ \end{array}\right]\)
    1. To have a solution, we must have
       \(b_1+b_2+b_3=0\)
    2. Full column rank
       \(\implies\) all pivot variables and no free variables
       \(\implies \mathbb{K_H} = \{ \vec{0} \}\)
    3. \(\vec{x_p} = \left[\begin{array}{c} 2b_1-b_2 \\ b_2-b_1 \\ \end{array}\right] \to\) the only solution

• case 3

  • Example
    
    \(\begin{split}\left\{\begin{array}{c} x-y+z=2 \\ 2x+y+z=7 \\ \end{array}\right.\to A = \left[\begin{array}{c c c} 1 & -1 & 1 \\ 2 & 1 & 1\\ \end{array}\right] &\to \left[\begin{array}{c c} 1 & -1 & 1 \\ 0 & 3 & -1 \\ \end{array}\right] \\ &\to R = \left[\begin{array}{c c} 1 & 0 & {2 \over 3} \\ 0 & 1 & {-1 \over 3} \\ \end{array}\right] = \left[\begin{array}{c c} I & F \\ \end{array}\right]\end{split}\)
  \(A\) is
  \(m \times n\) with
  \(m < n\) , assume
  \(r = m\) to make
  \(A\) have full row rank

  For a wide matrix

  \(A\) with full row rank
  1. \(R\) has no zero rows, all rows have pivots
  2. For every
     \(\vec{b} \in \mathbb{R}^m\),
     \(A\vec{x} = \vec{b}\) has at least 1 solution
  3. \(R\) has free columns, there are free variables
     \(\implies\) infinitely many solutions
  4. the number of free variables =
     \(n-m\) =
     \(n-r\)
     = the number of all unknowns - the number of pivots
     = the number of special solutions in
     \(N(A)\)
  • Example
    
    \(A = \left[\begin{array}{c c c} 1 & 1 & 1 \\ 1 & 2 & -1 \\ \end{array}\right],\ \vec{b} = \left[\begin{array}{c} 3 \\ 4 \\ \end{array}\right] \\ \left[\begin{array}{c c c|c} 1 & 1 & 1 & 3 \\ 1 & 2 & -1 & 4 \\ \end{array}\right] \to \left[\begin{array}{c c c|c} 1 & 0 & 3 & 2 \\ 0 & 1 & -2 & 1 \\ \end{array}\right] \\ \vec{x_p} = \left[\begin{array}{c} 2 \\ 1 \\ 0 \\ \end{array}\right],\ \vec{x_n} = \left[\begin{array}{c} -3 \\ 2 \\ 1 \\ \end{array}\right],\ \vec{x} = \left[\begin{array}{c} 2 \\ 1 \\ 0 \\ \end{array}\right]+x_3\left[\begin{array}{c} -3 \\ 2 \\ 1 \\ \end{array}\right] \\ \mathbb{K_H} = N(A) = \{c\left[\begin{array}{c} -3 \\ 2 \\ 1 \\ \end{array}\right] \mid c \in \mathbb{R}\}\)

• case 4

  • Example
    
    \(\begin{split}\left\{\begin{array}{c} x-y+z=2 \\ 2x+y+z=7 \\ 2x-2y+2z=4\ (or\ 5) \end{array}\right.\to A = \left[\begin{array}{c c c} 1 & -1 & 1 \\ 2 & 1 & 1 \\ 2 & -2 & 2 \\ \end{array}\right] &\to \left[\begin{array}{c c c c} 1 & -1 & 1 \\ 0 & 3 & -1 \\ 0 & 0 & 0 \\ \end{array}\right] \\ &\to R = \left[\begin{array}{c c c c} 1 & 0 & {2 \over 3} \\ 0 & 1 & {-1 \over 3} \\ 0 & 0 & 0 \\ \end{array}\right] = \left[\begin{array}{c c} I & F \\ O & O \\ \end{array}\right]\end{split}\)
  \(A_{m \times n}\) is not full rank,
  \(r<n\) and
  \(r < m\)
  
  \(R = \left[\begin{array}{c c} I & F \\ O & O \\ \end{array}\right]\) has either no solution, or infinitely many solution depending the
  \(\vec{b'}\) corresponding to the zero rows

Independence, Basis, and Dimension

• Define (linear dependence): A set of vectors
  \(\vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_n}\) are linearly dependent if there exists
  \(a_1,\ a_2,\ \cdots,\ a_n \in \mathbb{R}\) such that
  1. \(a_1,\ a_2,\ \cdots,\ a_n\) are not all zeros
  2. \(a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = \vec{0}\)
• Define (linear independence): A set of vectors
  \(\vec{u_1},\ \vec{u_2},\ \cdots,\ \vec{u_n}\) are linearly independent if they are not linearly dependent, i.e.
  \(a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = \vec{0}\) if and only if
  \(a_1=a_2=\cdots=a_n=0\)

linear dependence implies that some

\(\vec{u_1}\) can be expressed as a linear combination of others, e.g.

\(\begin{split}a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = \vec{0} \implies \vec{u_1} &= {1 \over a_1}(-a_2\vec{u_2}-\cdots-a_n\vec{u_n}) \\ &= -{a_2 \over a_1}\vec{u_2}-\cdots-{a_n \over a_1}\vec{u_n}\end{split}\)

• Example
  

  \(\vec{u_1} = \left[\begin{array}{c} 1 \\ 2 \\ 1 \\ \end{array}\right],\ \vec{u_2} = \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ \end{array}\right],\ \vec{u_3} = \left[\begin{array}{c} 3 \\ 5 \\ 3 \\ \end{array}\right]\), check whether
  \(a_1\vec{u_1}+a_2\vec{u_2}+a_3\vec{u_3} = \vec{0}\) has solutions other than
  \(\left[\begin{array}{c} a_1 \\ a_2 \\ a_3 \\ \end{array}\right] = \vec{0}\)
  i.e. to solve
  \(\left[\begin{array}{c c c} \vec{u_1} & \vec{u_2} & \vec{u_3} \\ \end{array}\right] \left[\begin{array}{c} a_1 \\ a_2 \\ a_3 \\ \end{array}\right] = O\ (A\vec{x} = \vec{0})\)
  
  \(\therefore \vec{u_1},\ \vec{u_2},\ \vec{u_3}\) are linearly independent if and only if
  \(N(A) = \{ \vec{0} \}\)
  
  \(\left[\begin{array}{c c c} 1 & 0 & 3 \\ 2 & 1 & 5 \\ 1 & 0 & 3 \\ \end{array}\right] \to \left[\begin{array}{c c c} 1 & 0 & 3 \\ 0 & 1 & -1 \\ 0 & 0 & 0 \\ \end{array}\right] \implies \left.\begin{array}{c} a_1 = -3a_3 \\ a_2 = a_3 \\ \end{array}\right. \\ \begin{split}\implies N(A) &= \{\left[\begin{array}{c} a_1 \\ a_2 \\ a_3 \\ \end{array}\right] \mid a_1 = -3a_3,\ a_2 = a_3,\ a_1,a_2,a_3 \in \mathbb{R}\} \\ &= \{\left[\begin{array}{c} -3a_3 \\ a_3 \\ a_3 \\ \end{array}\right] \mid a_3 \in \mathbb{R}\} \\ &= \{a_3\left[\begin{array}{c} -3 \\ 1 \\ 1 \\ \end{array}\right] \mid a_3 \in \mathbb{R}\}\end{split} \\ \therefore N(A) \not= \{ \vec{0} \}\)
  
  \(\therefore \vec{u_1},\ \vec{u_2},\ \vec{u_3}\) are linearly dependent

• In

  \(\mathbb{R}^m\), any set of
  \(n\) vectors must be linearly dependent if
  \(n>m\)
  Given a matrix
  \(A_{m \times n} = [\vec{u_1}\ \vec{u_2}\ \cdots \ \vec{u_n}]\) containing
  \(n\) column vectors
  \((n > m)\)
  There must be at least
  \((n-m)\) free variables
  
  \(\implies (n-m)\) special solutions
  
  \(\implies dim(N(A)) \ge n-m\ \ i.e.\ N(A) \not= \{ \vec{0} \}\)
  Also, when
  \(A = [\vec{u_1}\ \vec{u_2}\ \cdots \ \vec{u_n}]\) is full column rank, i.e.
  \(n=r \implies\) no free variables
  when
  \(r=n \implies n\) pivot variables
  \(\implies 0\) free variables,
  \(\therefore N(A) = \{ \vec{0} \}\)

• Theorem
  Let

  \(\mathbb{V}\) be a vector space and
  \(\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n}\) be element in
  \(\mathbb{V}\) s.t. they are linearly dependent. Then, for every
  \(\vec{u}_{n+1} \in \mathbb{V}\),
  \(\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n},\ \vec{u}_{n+1}\) are also linearly dependent

  Addition of vectors does not affect dependent, but mught affect independent
  （可以讓線性獨立變線性相依，但沒辦法把線性相依變線性獨立）

• Define: A set of vectors

  \(\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n}\) spans a space
  \(\mathbb{W}\) if their linear combinations fill the entire space
  i.e.
  \(span(\{ \vec{u_1}\ \vec{u_2}\ \cdots\ \vec{u_n} \}) = \mathbb{W}\)
  For
  \(A = [\vec{u_1}\ \vec{u_2}\ \cdots\ \vec{u_n}],\ span(\{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \}) = C(A) = \mathbb{W}\)
  • Example
    
    \(span(\{ \left[\begin{array}{c} 1 \\ 0 \\ \end{array}\right],\ \left[\begin{array}{c} 0 \\ 1 \\ \end{array}\right] \}) = \mathbb{R}^2 \\ span(\{ \left[\begin{array}{c} 1 \\ 0 \\ \end{array}\right],\ \left[\begin{array}{c} 0 \\ 1 \\ \end{array}\right],\ \left[\begin{array}{c} 4 \\ 7 \\ \end{array}\right] \}) = \mathbb{R}^2 \\ \begin{split}span(\{ \left[\begin{array}{c} 1 \\ 1 \\ \end{array}\right],\ \left[\begin{array}{c} -1 \\ -1 \\ \end{array}\right] \}) &= \text{A line in } \mathbb{R}^2 \\ &= \{ c\left[\begin{array}{c} 1 \\ 1 \\ \end{array}\right] \mid c \in \mathbb{R} \} \\ &= \text{A subspace of } \mathbb{R}^2\end{split}\)

• Define (row space): The row space of a matrix

  \(A_{m \times n}\) is the subspace of
  \(\mathbb{R}^n\) spanned by the rows. The row space of
  \(A\) is the column space of
  \(A^T = C(A^T)\)

• Define (Basis): A basis for a vector space

  \(\mathbb{V}\) is a linearly independent subset of
  \(\mathbb{V}\) that spans
  \(\mathbb{V}\)
  • Example
    
    \(\{ \left[\begin{array}{c} 1 \\ 0 \\ \end{array}\right],\ \left[\begin{array}{c} 0 \\ 1 \\ \end{array}\right]\}\) is a basis of
    \(\mathbb{R}^2\)
    
    \(\{ \left[\begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \\ \end{array}\right],\ \left[\begin{array}{c} 0 \\ 1 \\ \vdots \\ 0 \\ \end{array}\right],\ \cdots \ ,\left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 1 \\ \end{array}\right] \}\) is a basis of
    \(\mathbb{R}^n\)
  • Example
    
    \(A = \left[\begin{array}{c c c} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ \end{array}\right]\)
    
    \(A\) is invertible
    
    \(\iff n\) pivots = rank r (full rank)
    
    \(\iff\) no free variables
    
    \(\iff N(A) = \{ \vec{0} \}\)
    
    \(\iff\) linearly indepedent
    Also,
    \(\forall \ \vec{b} \in \mathbb{R}^n,\ \exists \ \vec{x} \in \mathbb{R}^n\ s.t.\ A\vec{x}=\vec{b},\ \vec{x} = A^{-1}\vec{b}\)
    
    \(i.e.\ \vec{b} = x_1\left[\begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array}\right] + x_2\left[\begin{array}{c} 0 \\ 1 \\ 1 \\ \end{array}\right] + x_3\left[\begin{array}{c} 0 \\ 0 \\ 1 \\ \end{array}\right] \\ \therefore span(A) = \mathbb{R}^3\)

    The vectors

    \(\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n}\) are a basis for

    \(\mathbb{R}^n\) exactly when they form an

    \(n \times n\) invertible matrix

    \(\iff\) full rank

    \(\iff\) linearly independent

• Theorem
  Let

  \(\mathbb{V}\) be a vector space and
  \(\vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \in \mathbb{V}\) be a subset of
  \(\mathbb{V}\)
  Then
  \(\{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \} = \mathbb{S}\) is a basis for
  \(\mathbb{V}\) if and only if each
  \(\vec{v} \in \mathbb{V}\) can be uniquely expressed as a linear combination of vector of
  \(\mathbb{S} = \{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \}\), i.e.
  \(\vec{v} = a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n}\) for unique
  \(a_1,\ a_2,\cdots,\ a_n \in \mathbb{R}\)
  • Proof
    Let
    \(\mathbb{S}\) be a basis for
    \(\mathbb{V}\)
    If
    \(\vec{v} \in \mathbb{V}\), then
    \(\vec{v} \in \mathbb{V} = span(\mathbb{S})\)
    
    \(\therefore \vec{v}\) is a linear combination of vectors in
    \(\mathbb{S}\)
    Suppose this NOT unique
    i.e.
    \(\vec{v} = a_1\vec{u_1}+a_2\vec{u_2}+\cdots+a_n\vec{u_n} = b_1\vec{u_1}+b_2\vec{u_2}+\cdots+b_n\vec{u_n}\)
    Then
    \((a_1-b_1)\vec{u_1}+(a_2-b_2)\vec{u_2}+\cdots+(a_n-b_n)\vec{u_n} = \vec{O}\ ...①\)
    Since
    \(\mathbb{S}\) is linearly independent (basis)
    ① possible only when
    \(a_1-b_1=0,\ a_2-b_2=0,\ \cdots\ ,a_n-b_n=0\)
    
    \(\iff a_1=b_1,\ a_2=b_2,\ \cdots\ ,a_n=b_n\)
    
    \(\therefore \vec{v}\) is a unique linear combination of
    \(\mathbb{S} = \{ \vec{u_1},\ \vec{u_2},\cdots,\ \vec{u_n} \}\)

How to find a basis of

\(C(A)\)

• Example
  

  \(A = \left[\begin{array}{c c c} 1 & 1 & 1 \\ 1 & 2 & 1 \\ \end{array}\right] \to R = \left[\begin{array}{c c c} \color{red}{1} & 0 & 3 \\ 0 & \color{red}{1} & -2 \\ \end{array}\right]\)
  free columns are linear combinations of pivot columns
  otherwise, they must be able to create new pivot and become pivot columns themselves
  since row operations will NOT affect this structure, the pivot columns of
  \(A\) will be a basis for
  \(C(A)\)

  Although

  \(N(A) = N(R),\ C(A) \not= C(R)\) in general
  But we can use the columns of

  \(A\) that correspond to pivot columns of

  \(R\) as a basis

• Theorem
  Every basis for a same vector space must have the same number of vectors
  i.e. for

  \(\vec{v_1},\ \vec{v_2},\cdots,\ \vec{v_m}\) and
  \(\vec{w_1},\ \vec{w_2},\cdots,\ \vec{w_n}\), both bases for
  \(\mathbb{V}\),
  
  \(m = n =\) dimension of the vector space
  \(\mathbb{V}\)
  • Proof
    (Assume
    \(n>m\)) Since
    \(\vec{v_1},\ \vec{v_2},\cdots,\ \vec{v_m}\) is a basis for
    \(\mathbb{V}\), every element in
    \(\mathbb{V}\) can be expressed as a linear combination of
    \(\vec{v_1},\ \vec{v_2},\cdots,\ \vec{v_m}\)
    Particularly, let
    
    \(\left.\begin{array}{c} \vec{w}_1 = a_{11}\vec{v_1}+a_{21}\vec{v_2}+\cdots+a_{m1}\vec{v_m} \\ \vec{w}_2 = a_{12}\vec{v_1}+a_{22}\vec{v_2}+\cdots+a_{m2}\vec{v_m} \\ \vdots \\ \vec{w}_n = a_{1n}\vec{v_1}+a_{2n}\vec{v_2}+\cdots+a_{mn}\vec{v_m} \\ \end{array}\right.\)
    
    \(\iff \left[\begin{array}{c c c c} \vec{w}_1 & \vec{w}_2 & \cdots & \vec{w}_n \\ \end{array}\right] = \left[\begin{array}{c c c c} \vec{v}_1 & \vec{v}_2 & \cdots & \vec{v}_n \\ \end{array}\right] \left[\begin{array}{c c c c} \vec{a}_{11} & \vec{a}_{12} & \cdots & \vec{a}_{1n} \\ \vec{a}_{21} & \vec{a}_{22} & \cdots & \vec{a}_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \vec{a}_{m1} & \vec{a}_{m2} & \cdots & \vec{a}_{mn} \\ \end{array}\right]\)
    
    \(A\) is a
    \(m \times n\) (wide) matrix
    \(\implies N(A) \not= \{ \vec{0} \}\)
    
    \(\therefore \exists\) nonzero
    \(\vec{x} \in \mathbb{R}^n\) s.t.
    \(A\vec{x} = \vec{0} \implies VA\vec{x} = \vec{0} \implies W\vec{x} = \vec{0}\)
    
    \(\therefore N(W) \not= \{ \vec{0} \}\) violating the fact that
    \(\vec{w_1},\ \vec{w_2},\cdots,\ \vec{w_n}\) is a basis (vectors in a basis must be linearly independent)
    similarly, we can prove that
    \(n<m\) is impossible either,
    \(\therefore n=m\)

  we have learned

  \(dim(N(A)) =\) the number of free variables = the number of special solutions
  Check that these special solutions form a basis for

  \(N(A)\)
  i.e.

  \(N(A) = span\{special\ solutions\}\) where special solutions are linearly independent

• Example

  1. \(\mathbb{M}_a \triangleq \{ \text{All } 2 \times 2 \text{ real matrices} \} \to dim(\mathbb{M}_a) = 4\)
     one basis is
     \(\{ \left[\begin{array}{c c} 1 & 0 \\ 0 & 0 \\ \end{array}\right], \left[\begin{array}{c c} 0 & 1 \\ 0 & 0 \\ \end{array}\right], \left[\begin{array}{c c} 0 & 0 \\ 1 & 0 \\ \end{array}\right], \left[\begin{array}{c c} 0 & 0 \\ 0 & 1 \\ \end{array}\right]\}\)
  2. \(\mathbb{M}_b \triangleq \{ \text{All } n \times n \text{ real matrices} \} \to dim(\mathbb{M}_b) = n^2\)
  3. \(\mathbb{M}_c \triangleq \{ \text{All } n \times n \text{ upper triangular matrices} \} \to dim(\mathbb{M}_c) = {n(n+1) \over 2}\)

Dimension of the Four Fundamental Subspaces

\(A_{m \times n},\ rank(A)=r,\ R=EA,\ R \le m\)

Subspace	Dimension	\(\in\)
\(C(A)\)	\(r\)	\(\mathbb{R}^m\)
\(C(A^T)\)	\(r\)	\(\mathbb{R}^n\)
\(N(A)\)	\(n-r\)	\(\mathbb{R}^n\)
\(N(A^T)\)	\(n-r\)	\(\mathbb{R}^m\)

• Example
  
  \(\begin{split}A_{3 \times 5} = \left[\begin{array}{c c c c c} 1 & 3 & 5 & 0 & 7 \\ 0 & 0 & 0 & 1 & 2 \\ 1 & 3 & 5 & 1 & 9 \\ \end{array}\right] \to R &= \left[\begin{array}{c c c c c} 1 & 3 & 5 & 0 & 7 \\ 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array}\right] \\ &= E_{32}E_{31}A &= \left[\begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \\ \end{array}\right]\left[\begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{array}\right]A \\ &= EA &= \left[\begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & -1 & 1 \\ \end{array}\right]A\end{split}\)
  1. Find a basis for
     \(C(A)\)
     
     \(\begin{split}C(A) \not= C(R),\ dim(C(A)) &= dim(C(R)) \\ &= dim(span\{ \left[\begin{array}{c} 1 \\ 0 \\ 0 \\ \end{array}\right], \left[\begin{array}{c} 3 \\ 0 \\ 0 \\ \end{array}\right], \left[\begin{array}{c} 5 \\ 0 \\ 0 \\ \end{array}\right], \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ \end{array}\right], \left[\begin{array}{c} 7 \\ 2 \\ 0 \\ \end{array}\right]\}) \\ &= dim(span\{ \left[\begin{array}{c} 1 \\ 0 \\ 0 \\ \end{array}\right], \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ \end{array}\right] \}) = 2 = rank(A)\end{split}\)
     A basis for
     \(C(A) = \{ \left[\begin{array}{c} 1 \\ 0 \\ 1 \\ \end{array}\right], \left[\begin{array}{c} 0 \\ 1 \\ 1 \\ \end{array}\right] \}\) (pivot columns in
     \(A\))
  2. Find a basis for
     \(C(A^T)\)
     
     \(\begin{split}dim(C(A^T)) &= \text{pivot columns in } A^T \\ &= \text{pivot rows in } A \\ &= dim(span\{ \left[\begin{array}{c} 1 \\ 3 \\ 5 \\ 0 \\ 7 \\ \end{array}\right], \left[\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \\ 2 \\ \end{array}\right] \}) = 2\end{split}\)
  3. Find a basis for
     \(N(A)\)
     
     \(\begin{split}N(A) = N(R) \to dim(N(A)) &= dim(N(R)) \\ &= \text{the number of special solutions} \\ &= \text{the number of free variables} = n-r\end{split}\)
  4. Find a basis for
     \(N(A^T)\)
     
     \(dim(N(A^T)) = m-r\)

Orthogonality (2021.11.3~2021.11.5)

• Define(Inner Product)
  Let

  \(\vec{v},\ \vec{w} \in \mathbb{R}^n,\ \vec{v} =\left[\begin{array}{c} v_1 \\ v_2 \\ \vdots \\ v_n \\ \end{array}\right],\ \vec{w} =\left[\begin{array}{c} w_1 \\ w_2 \\ \vdots \\ w_n \\ \end{array}\right]\), the inner product of
  \(\vec{v}\) and
  \(\vec{w}\) is defined as
  
  \(<\vec{v},\ \vec{w}> = \vec{v}^T\vec{w} = \sum\limits_{i = 0}^n v_iw_i = \sum\limits_{i = 0}^n w_iv_i = \vec{w}^T\vec{v} = <\vec{w},\ \vec{v}>\)

• Define(norm)
  The norm (length) of a vector

  \(\vec{v}\) in
  \(\mathbb{R}^n\) is
  
  \(\begin{Vmatrix} \vec{v} \end{Vmatrix} = \sqrt{<\vec{v},\ \vec{v}>} = \sqrt{\vec{v}^T\vec{v}} = \sqrt{v_1^2+v_2^2+\cdots+v_n^2}\ ,\ \begin{Vmatrix} \vec{v} \end{Vmatrix} = 0 \iff \vec{v} = \vec{0},\ i.e. v_i = 0\)

• Define(Orthogonal): Two vectors

  \(\vec{v}\) and
  \(\vec{w}\) are orthogonal if
  \(\vec{w}^T\vec{v}=0\), denoted by
  \(\vec{v} \perp \vec{w}\)
  • Example
    
    \(\left[\begin{array}{c} 2 \\ 0 \\ \end{array}\right]^T\left[\begin{array}{c} 0 \\ 1 \\ \end{array}\right] = 2 \cdot 0 + 0 \cdot 1 = 0 \implies \left[\begin{array}{c} 2 \\ 0 \\ \end{array}\right] \perp \left[\begin{array}{c} 0 \\ 1 \\ \end{array}\right] \\ \left[\begin{array}{c} 1 \\ 1 \\ \end{array}\right]^T\left[\begin{array}{c} 1 \\ -1 \\ \end{array}\right] = 1 \cdot 1 + 1 \cdot (-1) = 0 \implies \left[\begin{array}{c} 1 \\ 1 \\ \end{array}\right] \perp \left[\begin{array}{c} 1 \\ -1 \\ \end{array}\right]\)

• Theorem
  

  \(\vec{v}\) and
  \(\vec{w}\) are orthogonal if and only if
  \(\begin{Vmatrix} \vec{v}+\vec{w} \end{Vmatrix}^2 = \begin{Vmatrix} \vec{v} \end{Vmatrix}^2 + \begin{Vmatrix} \vec{w} \end{Vmatrix}^2\)
  • Proof
    
    \(\begin{split}\begin{Vmatrix} \vec{v}+\vec{w} \end{Vmatrix}^2 &= (\sqrt{<(\vec{v}+\vec{w}), (\vec{v}+\vec{w})>})^2 \\ &= <(\vec{v}+\vec{w}), (\vec{v}+\vec{w})> \\ &= (\vec{v}+\vec{w})^T(\vec{v}+\vec{w}) \\ &= (\vec{v}^T+\vec{w}^T)(\vec{v}+\vec{w}) \\ &= \vec{v}^T\vec{v} + \vec{v}^T\vec{w} + \vec{w}^T\vec{v} + \vec{w}^T\vec{w} \\ &= \vec{v}^T\vec{v} + 0 + 0 + \vec{w}^T\vec{w} = \begin{Vmatrix} \vec{v} \end{Vmatrix}^2+\begin{Vmatrix} \vec{w} \end{Vmatrix}^2\end{split}\)

• Define(Orthogonal subspaces): Two subspaces

  \(\mathbb{V}\) and
  \(\mathbb{W}\) within a vector space and orthogonal if every
  \(\vec{v} \in \mathbb{V}\) is orthogonal to every vector
  \(\vec{w} \in \mathbb{W}\), i.e.
  \(\forall\ \vec{v} \in \mathbb{V},\ \forall\ \vec{w} \in \mathbb{W},\ \vec{v} \perp \vec{w} \text{ as } \mathbb{V} \perp \mathbb{W}\)

• Define(Orthogonal complement): The orthogonal complement of a subspace

  \(\mathbb{V}\) contains every vector that is orthogonal to
  \(\mathbb{V}\). The orthogonal complement of
  \(\mathbb{V}\) is denoted by
  \(\mathbb{V}^{\perp}\)

• Theorem
  

  \(\mathbb{V}^{\perp}\) is a subspace
  • Proof
    1. \(\forall\ \vec{v} \in \mathbb{V},\ \vec{v}^T\vec{0} = \vec{0} \implies \vec{0} \in \mathbb{V}^{\perp}\)
    2. Let
       \(\vec{w}_1\) and
       \(\vec{w}_2 \in \mathbb{V}^{\perp}\)
       
       \(\forall\ \vec{v} \in \mathbb{V},\ \vec{v}^T\vec{w}_1=0,\ \vec{v}^T\vec{w}_2=0 \\ \therefore \vec{v}^T(\vec{w}_1+\vec{w}_2) = \vec{v}^{\perp}\vec{w}_1+\vec{v}^{\perp}\vec{w}_2 = 0 \implies \vec{w}_1+\vec{w}_2 \in \mathbb{V}^{\perp}\)
    3. Let
       \(c \in \mathbb{R}\)
       
       \(\vec{v}^T(c\vec{w}_1) = c\vec{v}^T\vec{w}_1 = 0 \implies c\vec{w_1} \in \mathbb{V}^{\perp}\)

• Theorem
  

  \(C(A^T) \perp N(A)\), moreover,
  \(C(A^T) = N(A)^{\perp}\) and
  \(N(A) = C(A^T)^{\perp}\)
  • Proof
    By definition
    \(N(A)\) contains all
    \(\vec{x} \in \mathbb{R}^n\)
    s.t.
    \(A\vec{x} = \vec{0} = \left[\begin{array}{c} row\ 1 \\ row\ 2 \\ \vdots \\ row\ m \\ \end{array}\right]\vec{x} = \left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 0 \\ \end{array}\right]\) i.e.
    \(\left.\begin{array}{c} [row\ 1]\vec{x} = 0 \\ [row\ 2]\vec{x} = 0 \\ \vdots \\ [row\ m]\vec{x} = 0 \\ \end{array}\right.\)
    
    \(\iff \vec{u} \cdot \vec{x} = 0,\ \vec{u} =\) any linear combination of row vectors
    \(\in C(A^T)\)
    
    \(\iff C(A^T) \perp N(A)\)
    similarly, we can show
    \(C(A) \perp N(A^T)\)

• Theorem
  Let

  \(v_1,\ v_2,\ \cdots,\ v_r\) be a basis for
  \(C(A^T)\) and
  \(w_1,\ w_2,\ \cdots,\ w_{n-r}\) be a basis for
  \(N(A)\)
  \((dim(C(A^T)) = r,\ dim(N(A)) = n-r)\)
  show that
  \(v_1,\ v_2,\ \cdots,\ v_r,\ w_1,\ w_2,\ \cdots,\ w_{n-r}\) form a basis for
  \(\mathbb{R}^n\)
  • Proof
    For
    \(\vec{0} \in \mathbb{R}^n\)
    
    \(\begin{split}\vec{0} &= a_1\vec{v}_1+a_2\vec{v}_2+\cdots+a_r\vec{v}_r+b_1\vec{w}_1+b_2\vec{w}_2+\cdots+b_{n-r}\vec{w}_{n-r} \\ &\implies a_1\vec{v}_1+a_2\vec{v}_2+\cdots+a_r\vec{v}_r = -(b_1\vec{w}_1+b_2\vec{w}_2+\cdots+b_{n-r}\vec{w}_{n-r}) = \vec{y} \\ &\implies \vec{y} \in C(A^T),\ \vec{y} \in N(A) \\ &\implies \vec{y} \in C(A^T) \cap N(A) \\ &\because C(A^T) \perp N(A)\ \therefore \vec{y} = \vec{0}\end{split}\)
    Meanwhile, since
    \(v_1,\ v_2,\ \cdots,\ v_r\) form a basis of
    \(C(A^T)\) and
    \(w_1,\ w_2,\ \cdots,\ w_{n-r}\) form a basis of
    \(N(A)\)
    
    \(\implies v_1,\ v_2,\ \cdots,\ v_r,\ w_1,\ w_2,\ \cdots,\ w_{n-r}\) form a basis of
    \(\mathbb{R}^n\)

Projections

Projection of

\(\vec{b}\) onto

1. Z-axis is
   \(\left[\begin{array}{c} 0 \\ 0 \\ 4 \\ \end{array}\right] = \vec{P}_1 = P_1\vec{b} = \left[\begin{array}{c c c} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ \end{array}\right] \left[\begin{array}{c} 2 \\ 3 \\ 4 \\ \end{array}\right]\)
2. XY-plane is
   \(\left[\begin{array}{c} 2 \\ 3 \\ 0 \\ \end{array}\right] = \vec{P}_2 = P_2\vec{b} = \left[\begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{array}\right] \left[\begin{array}{c} 2 \\ 3 \\ 4 \\ \end{array}\right]\)

\(\vec{P}_1 = \vec{P}_2 = \vec{b},\ P_1 + P_2 = \left[\begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array}\right] = I\)
Z-axis and XY-plane are orthogonal compliments

Projection onto a Subspace

To find a

\(\vec{p} \in\) the subspace that is closest to

\(\vec{b}\) ( minimal error

\((\vec{p},\ \vec{b})\) )
For a given vector

\(\vec{b} \in \mathbb{R}^m\) and a subspace of

\(\mathbb{R}^m\) spanned by basis

\(\vec{a}_1,\ \vec{a}_2,\ \cdots,\ \vec{a}_n\) , the projection of

\(\vec{b}\) onto the subspace,

\(\vec{p}\), is given by

\(P \cdot \vec{b} = \vec{p}\) where

\(P\) is the projection matrix
Let

\(A = [\vec{a}_1\ \vec{a}_2\ \cdots\ \vec{a}_n],\ \vec{p} = \hat{x_1}\vec{a}_1+\hat{x_2}\vec{a}_2+\cdots+\hat{x_n}\vec{a}_n\) where

\(\hat{x_1},\ \hat{x_2},\ \cdots,\ \hat{x_n} \in \mathbb{R} \implies \vec{p} = A\vec{x}\)
Let the error

\(\vec{e} = \vec{b} - \vec{p}\)

\(\because \vec{e} \perp \vec{p},\ \vec{e}^{\perp}\vec{p} = 0\) , i.e.

\(\vec{e}^T\vec{a}_1=0,\ \vec{e}^T\vec{a}_2=0,\ \cdots,\ \vec{e}^T\vec{a}_n=0\)

\(\begin{split}\therefore \vec{e}^TA = (\vec{b}-\vec{p})^TA = \vec{0} \iff \vec{b}^TA &= (\vec{p}+\vec{e})^TA \\ &= \vec{p}^TA + \vec{e}^TA \\ &= \vec{p}^TA + 0 = \vec{p}^TA \\ &= (A\vec{x})^TA = \vec{x}^TA^TA\end{split} \\ \vec{b}^TA = \vec{x}^TA^TA \iff A^TA\vec{x} = A^T\vec{b} \\ \therefore (A^TA)^{-1}(A^TA)\vec{x} = (A^TA)^{-1}A^T\vec{b} \implies \vec{x} = (A^TA)^{-1}A^T\vec{b} \\ \vec{p} = A\vec{x} = A(A^TA)^{-1}A^T\vec{b} = P\vec{b} \implies P = A(A^TA)^{-1}A^T\)

since

\(n < m\),

\(A_{m \times n}\) is a tall matrix with full column rank (

\(\because\) basis)

\(\implies A^TA\) is invertible

For

\(n=1\)

\(\begin{split}\hat{x} = {\vec{a}^T\vec{b} \over \vec{a}^T\vec{a}},\ \vec{p} = \vec{a}{\vec{a}^T\vec{b} \over \vec{a}^T\vec{a}},\ P = {\vec{a}\vec{a}^T \over \vec{a}^T\vec{a}}\end{split}\)

• Theorem
  
  \(A^TA\) is invertible if and only if
  \(A\) has linearly independent columns
  • Proof
    First, show that
    \(A^TA\) has the same null space as
    \(A\)
    i.e.
    \(N(A) \subseteq N(A^TA)\) and
    \(N(A^TA) \subseteq N(A)\)
    
    \(\forall \vec{x} \in N(A),\ A\vec{x} = \vec{0} \\ \implies A^TA\vec{x} = A^T\vec{0} = \vec{0} \\ \implies \vec{x} \in N(A^TA)\ \therefore N(A) \subseteq N(A^TA)...① \\ \forall \vec{x} \in N(A^TA),\ (A^TA)\vec{x} = \vec{0} \\ \implies \vec{x}^T(A^TA)\vec{x} = \vec{x}^T\vec{0} = \vec{0} \\ \vec{x}^T(A^TA)\vec{x} = \begin{Vmatrix} A\vec{x} \end{Vmatrix}^2 = 0\)
    i.e.
    \(A\vec{x}\) is a vector with norm = 0
    
    \(\therefore A\vec{x}=\vec{0},\ \vec{x} \in N(A) \implies N(A^TA) \subseteq N(A)...②\)
    From ① and ②,
    \(N(A) = N(A^TA)\)
    Note that
    \(A\) is
    \(m \times n\) , and
    \(A^TA\) is
    \(n \times n\) , given
    \(rank(A) = r\)
    
    \(\because N(A) = N(A^TA) \\ \implies dim(N(A)) = dim(N(A^TA)) \\ \implies n-r = n-rank(A^TA) \\ \implies rank(A) = r\)
    As
    \(A\) has linearly dependent columns i.e.
    \(rank(A)=n,\ rank(A^TA)=n \implies A^TA\) is invertible