Week 9 - Vector Spaces

1. When Systems Don’t Have a Unique Solution

  • To solve Ax=bAx = b, we may face three different situations: Unique Solution, No Solution and Many Solutions.
  • For example (222234432)(χ0χ1χ2)=(034)\left(\begin{array}{c c c} 2 & 2 & -2 \\ -2 & -3 & 4 \\ 4 & 3 & -2\end{array}\right) \left(\begin{array}{c}\chi_0 \\ \chi_1 \\ \chi_2 \end{array}\right) = \left(\begin{array}{c} 0 \\ 3 \\ 4 \end{array}\right)
    • We will end up with (222012000)(031)\left(\begin{array}{c c c} 2 & 2 & -2 \\ 0 & -1 & 2 \\ 0 & 0 & 0\end{array}\right) \left(\begin{array}{c} 0 \\ 3 \\ 1 \end{array}\right)
    • But 010 \ne 1 => No solution
  • For example (222234432)(χ0χ1χ2)=(033)\left(\begin{array}{c c c} 2 & 2 & -2 \\ -2 & -3 & 4 \\ 4 & 3 & -2\end{array}\right) \left(\begin{array}{c}\chi_0 \\ \chi_1 \\ \chi_2 \end{array}\right) = \left(\begin{array}{c} 0 \\ 3 \\ 3 \end{array}\right)
    • (χ0χ1χ2)=(330)+β(121)\left(\begin{array}{c}\chi_0 \\ \chi_1 \\ \chi_2 \end{array}\right) = \left(\begin{array}{c} 3 \\ -3 \\ 0 \end{array}\right) + \beta \left(\begin{array}{c} -1 \\ 2 \\ 1 \end{array}\right)
    • Many solutions

1.1. When we have many solutions

  • Consider Ax=bAx=b and assume that we have
    • One solution to the system Ax=bAx = b, the specific solution we denote by xsx_s so that Axs=bAx_s = b.
    • One solution to the system Ax=0Ax = 0 that we denote by xnx_n so that Axn=0Ax_n = 0.
  • Then
    • A(xs+xn)=Axs+Axn=b+0=bA(x_s + x_n) = Ax_s + Ax_n = b + 0 = b
  • So xs+xnx_s + x_n is also a solution
  • Now A(xs+βxn)=Axs+A(βxn)=Axs+βAxn=b+0=bA(x_s + \beta x_n) = Ax_s + A(\beta x_n) = Ax_s + \beta A x_n = b + 0 = b
  • So A(xs+βxn)A(x_s + \beta x_n) is a solution for every βR\beta \in \mathbb{R}.
  • Recall the example (222234432)(χ0χ1χ2)=(033)\left(\begin{array}{c c c} 2 & 2 & -2 \\ -2 & -3 & 4 \\ 4 & 3 & -2\end{array}\right) \left(\begin{array}{c}\chi_0 \\ \chi_1 \\ \chi_2 \end{array}\right) = \left(\begin{array}{c} 0 \\ 3 \\ 3 \end{array}\right)
    • After two steps of LU factorization, we get χ0+χ2=3χ12χ2=30=0\begin{aligned} \chi_0 + \chi_2 &= 3 \\ \chi_1 - 2\chi_2 &= -3 \\ 0 &= 0 \end{aligned}
    • Set χ2=0\chi_2 = 0, we conclude that a specific solution is given by xs=(χ0χ1χ2)=(330)x_s = \left(\begin{array}{c}\chi_0 \\ \chi_1 \\ \chi_2 \end{array}\right) = \left(\begin{array}{c} 3 \\ -3 \\ 0 \end{array}\right)
  • Now, to calculate xnx_n. If we choose the free variable χ2=0\chi_2 = 0, then it is easy to see that χ0=χ1=0\chi_0 = \chi_1 = 0, and we end up with the trivial solution, x=0x = 0. So, instead choose χ2=1\chi_2 = 1: χ0+1=0χ12(1)=00=0\begin{aligned} \chi_0 + 1 &= 0 \\ \chi_1 - 2(1) &= 0 \\ 0 &= 0 \end{aligned}
  • Ax=0Ax = 0: xn=(121)x_n = \left(\begin{array}{c} -1 \\ 2 \\ 1 \end{array}\right)
  • But if Axn=0Ax_n = 0, then A(βxn)=0A(\beta x_n) = 0. This means that all vectors xs+βxn=(330)+β(121)x_s + \beta x_n = \left(\begin{array}{c} 3 \\ -3 \\ 0 \end{array}\right) + \beta \left(\begin{array}{c} -1 \\ 2 \\ 1 \end{array}\right)

Some terminology

  • row-echelon form:
    • The boxed values are known as the pivots.
    • In each row to the left of the vertical bar, the left-most nonzero element is the pivot for that row.
    • Notice that the pivots in later rows appear to the right of the pivots in earlier rows.
  • reduced row-echelon form:

1.2. Summary

  • Whether a linear system of equations Ax=bAx = b has a unique solution, no solution, or multiple solutions can be determined by writing the system as an appended system (Ab)\left(A | b\right) and transforming this appended system to row echelon form, swapping rows if necessary.

2. Review of Sets

  • A set is a collection of distinct objects.
  • The objects are the elements of the set.
  • xSx \in S: (object) x is an element of set SS. an element of S.
  • If S contains object x, y and z: {x,y,z}\{x, y, z\}
    • Order doesn't matter.
  • The size of a set denoted by S|S|.
  • (ST)(xSxT)(S \subset T) \iff (x \in S \Rightarrow x \in T)

2.1. Examples

  • {1,2,3}\{1, 2, 3\}
  • {1,2,3}=3|\{1, 2, 3\}| = 3
  • The collection of all integers denoted by Z\mathbb{Z} => {,2,1,0,1,2,}\{\ldots, -2, -1, 0, 1, 2, \ldots\}. Z=|\mathbb{Z}| = \infty
  • The collection of all real numbers denoted by R\mathbb{R}. R=|\mathbb{R}| = \infty
  • The set of all vectors of size nn whose components are real valued is denoted by Rn\mathbb{R}^n.

2.2. Operations with Sets

  • Union of two set
    • Notation: STS \cup T
    • Formal definition: ST={xxSxT}S \cup T = \{ x | x \in S \vee x \in T\}
  • Interaction of two sets
    • Notation: STS \cap T
    • Formal definition: ST={xxSxT}S \cap T = \{ x | x \in S \land x \in T\}
  • Complement of two sets
    • Notation: T\ST \backslash S
    • Formal definition: T\S={xxSxT}T \backslash S = \{ x | x \notin S \land x \in T\}

3. Vector Spaces

3.1. Definition

  • a vector space is a subset, SS, of Rn\mathbb{R}^n with the following properties:
  • 0S0 \in S (the zero vector of size n is in the set S); and
  • If v,wSv, w \in S then (v+w)S(v+w) \in S; and
  • If αR\alpha \in \mathbb{R} and vSv \in S then αvS\alpha v \in S.

  • Example: The set Rn\mathbb{R}^n is a vector space:

    • 0Rn0 \in \mathbb{R}^n
    • If v,wRnv, w \in \mathbb{R}^n then (v+w)Rn(v+w) \in \mathbb{R}^n; and
    • If αR\alpha \in \mathbb{R} and vRnv \in \mathbb{R}^n then αvRn\alpha v \in \mathbb{R}^n.

3.2. Subspaces

  • Subspaces of Rn\mathbb{R}^n are the subsets of Rn\mathbb{R}^n, and also vector spaces.
  • Examples:
    • The set SRnS \subset \mathbb{R}^n described by {χaχR}\{\chi a | \chi \in \mathbb{R}\}, where aRna \in \mathbb{R}^n, is a subspace of Rn\mathbb{R}^n.
      • 0S0 \in S: (pick χ=0\chi = 0).
      • If u,wSu, w \in S then (u+w)S(u + w) \in S: Pick u,wSu, w \in S. Then for some scalars υ\upsilon and some scalars ω\omega, vector v=υav = \upsilon a and vector w=ωaw = \omega a. Then v+w=υa+ωa=(υ+ω)av+w = \upsilon a+ \omega a= (\upsilon + \omega)a, which is also in S.
      • If αR\alpha \in \mathbb{R} and vSv \in S then αvS\alpha v \in S: Pick αR\alpha \in \mathbb{R} and vSv \in S. Then for some υ\upsilon, v=υav = \upsilon a. But αv=α(υa)=(αυ)a\alpha v = \alpha (\upsilon a) = (\alpha \upsilon) a. which is also in S.

The Column Space

  • Definition: Let ARm×nA \in \mathbb{R}^{m \times n}. Then the column space of A equals the set {AxxRn}\{Ax | x \in \mathbb{R}^n\}. It is denoted by C(A)\mathcal{C}(A). Ax=(a0a1an1)(χ0χ1χn1)=χ0a0+χ1a1++χn1an1Ax = \left(\begin{array}{c|c|c|c} a_0 & a_1 & \cdots & a_{n-1}\end{array}\right) \left(\begin{array}{c} \chi_0 \\ \chi_1 \\ \vdots \\ \chi_{n-1}\end{array}\right) = \chi_0 a_0 + \chi_1 a_1 + \cdots + \chi_{n-1} a_{n-1}
    • Thus C(A)\mathcal{C}(A) equals the set of all linear combinations of the columns of matrix A.
  • Theorem: The column space of ARm×nA \in \mathbb{R}^{m \times n} is a subspace of Rm\mathbb{R}^m
  • Theorem: Let ARm×n,xRnA \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, and bRmb \in \mathbb{R}^m. Then Ax=bAx = b has a solution if and only if bC(A)b \in \mathcal{C}(A).

The Null Space

  • Definition: Let ARm×nA \in \mathbb{R}^{m \times n}. The set of all vectors xRnx \in \mathbb{R}^n that have the property that Ax=0Ax = 0 is called the null space of A.
    • Frankly speaking, all of the possible vector x that satisfy Ax=0Ax = 0.
      • So xx should be perpendicular to AA.
  • Notation: N(A)={xAx=0}\mathcal{N}(A) = \{x|Ax = 0\}
  • Theorem: Let ARm×nA \in \mathbb{R}^{m \times n}. The null space of A,N(A)A, \mathcal{N}(A), is a subspace.
  • Example:
    • A=[111112344321]A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{bmatrix}
    • rref (A)=[101201230000]\text{rref }(A) = \begin{bmatrix} 1 & 0 & -1 & -2 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix}
      • rref: reduced row-echelon form.
    • => χ0χ22χ3=0,χ1+2χ2+3χ3=0\chi_0 - \chi_2 - 2\chi_3 = 0, \chi_1 + 2 \chi_2 + 3 \chi_3 = 0
    • => [χ0χ1χ2χ3]=χ2[1210]+χ3[2301]\begin{bmatrix} \chi_0 \\ \chi_1 \\ \chi_2 \\ \chi_3 \end{bmatrix} = \chi_2 \begin{bmatrix} 1 \\ -2 \\ 1 \\ 0 \end{bmatrix} + \chi_3\begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix}
    • We defined: χ2R,χ3R\chi_2 \in \mathbb{R}, \chi_3 \in \mathbb{R}
    • So, N(A)=Span ([1210],[2301])\mathcal{N}(A) = \text{Span }\left( \begin{bmatrix} 1 \\ -2 \\ 1 \\ 0 \end{bmatrix},\begin{bmatrix} 2 \\ -3 \\ 0 \\ 1 \end{bmatrix}\right)
    • N(A)=N(rref (A))\mathcal{N}(A) = \mathcal{N}(\text{rref }(A))

4. Span, Linear Independence, and Bases

  • Definition: Let {v0,v1,,vn1}Rm\{v_0, v_1, \cdots, v_{n-1} \} \subset \mathbb{R}^m. Then the span of these vectors, Span {v0,v1,,vn1}\{v_0, v_1, \cdots, v_{n-1}\}, is said to be the set of all vectors that are a linear combination of the given set of vectors. If V=(v0v1vn1) then Span(v0,v1,,vn1)=C(V).\text{If}\ V = \left(\begin{array}{c|c|c|c} v_0 & v_1 & \cdots & v_{n-1} \end{array}\right)\ \text{then Span}\left(\begin{array}{c c c c} v_0, v_1, \cdots, v_{n-1} \end{array}\right) = \mathcal{C}(V).

    • Linear Combination: Let u,vRmu,v \in \mathbb{R}^m and α,βRα,β \in \mathbb{R}. Then αu+βvαu + βv is said to be a linear combination of vectors uu and vv.
    • Let u,vRmu,v \in \mathbb{R}^m. Span (u,v)=Rm\text{Span }(u, v) = \mathbb{R}^m means we can use the linear combination of vectors u and v to represent all of the vectors Rm\in \mathbb{R}^m.
  • Definition: A spanning set of a subspace S is a set of vectors {v0,v1,,vn1}\{v_0, v_1, \cdots, v_{n-1} \} such that Span({v0,v1,,vn1}\{v_0, v_1, \cdots, v_{n-1} \}) = S.

    • For example: Span {(12),(21)}=R2\text{Span }\{ \left(\begin{array}{c}1 \\ 2\end{array}\right), \left(\begin{array}{c}2 \\ 1\end{array}\right) \} = \mathbb{R}^2
  • Definition: Let {v0,v1,,vn1}Rm\{v_0, v_1, \cdots, v_{n-1} \} \subset \mathbb{R}^m. Then this set of vectors is said to be linearly independent if χ0v0+χ1v1++χn1vn1=0\chi_0 v_0 + \chi_1 v_1 + \cdots + \chi_{n-1} v_{n-1} = 0 implies that χ0=χ1==χn1=0\chi_0 = \chi_1 = \cdots = \chi_{n-1} = 0. A set of vectors that is not linearly independent is said to be linearly dependent.
    • In other words, the only solution for Ax=0Ax = 0 is x=0, where, A={v0,v1,,vn1},xT={χ0,χ1,,χn1} \overrightarrow{x} = \overrightarrow{0}, \text{ where, } A = \{v_0, v_1, \cdots, v_{n-1}\}, x^T = \{\chi_0, \chi_1, \cdots, \chi_{n-1} \}
    • For example: Span {(12),(24)}\text{Span }\{ \left(\begin{array}{c}1 \\ 2\end{array}\right), \left(\begin{array}{c}2 \\ 4\end{array}\right) \} is linearly dependent.
      • Because the set (24)\left(\begin{array}{c}2 \\ 4\end{array}\right) can be represent with 2(12) 2 \left(\begin{array}{c}1 \\ 2\end{array}\right). We can do: 2(12)(24)=02 \left(\begin{array}{c}1 \\ 2\end{array}\right) - \left(\begin{array}{c}2 \\ 4\end{array}\right) = 0 to make the linear combination to be 0. And don't have to make all χn=0\chi_n = 0.
      • In other words, (24)\left(\begin{array}{c}2 \\ 4\end{array}\right) doesn't give us any new dimension, still the same as (12)\left(\begin{array}{c}1 \\ 2\end{array}\right).
      • So Span {(12),(24)}=Span {(12)}\text{Span }\{ \left(\begin{array}{c}1 \\ 2\end{array}\right), \left(\begin{array}{c}2 \\ 4\end{array}\right) \} = \text{Span }\{ \left(\begin{array}{c}1 \\ 2\end{array}\right) \}
      • (12),(21)\left(\begin{array}{c}1 \\ 2\end{array}\right), \left(\begin{array}{c}2 \\ 1\end{array}\right) is linear independent set.
      • Also, we know that two vectors with different directions can span a plane. So if we add any vectors to {(12),(21)}\{ \left(\begin{array}{c}1 \\ 2\end{array}\right), \left(\begin{array}{c}2 \\ 1\end{array}\right) \} , it will be linear dependent set.
  • Theorem: Let the set of vectors {v0,v1,,vn1}Rm\{ v_0, v_1 , \ldots , v_{n-1} \} \subset \mathbb {R}^ m be linearly dependent. Then at least one of these vectors can be written as a linear combination of the others.

    • In other words, the dependent vector aja_j can be written as a linear combination of the other n−1 vectors.
  • Theorem: Let {a0,a1,,an1}Rm\{ a_0, a_1 , \ldots , a_{n-1} \} \subset \mathbb {R}^ m and let A=(a0a1an1) A = \left(\begin{array}{c|c|c|c} a_0 & a_1 & \cdots & a_{n-1}\end{array}\right) . Then the vectors {a0,a1,,an1}\{ a_0, a_1 , \ldots , a_{n-1} \} are linearly independent if and only if N(A)={0}\mathcal{N}(A) = \{0\}.

    • aka χ0=χ1==χn1=0\chi_0 = \chi_1 = \cdots = \chi_{n-1} = 0
  • Definition: A basis for a subspace S of RnR^n is a set of vectors in S that

    1. is linearly independent and
    2. Spans S.

    3. Basis is the minimum set of vectors that spans the subspace.

    4. Let {v1,v2,,vn}= Basis of subspace U \{v_1, v_2, \cdots, v_n\} = \text{ Basis of subspace U }. Then {v1,v2,,vn}\{v_1, v_2, \cdots, v_n\} are linear independent,
    5. And all of the linear combinations of {v1,v2,,vn}\{v_1, v_2, \cdots, v_n\} can get all of the possible components of UU. And each member of U can be uniquely defined by a unique combination of {v1,v2,,vn}\{v_1, v_2, \cdots, v_n\}.
  • Theorem: Let S be a subspace of Rm\mathbb{R}^m and let {v0,v1,,vk1}Rm\{v_0, v_1, \cdots, v_{k-1} \} \subset \mathbb{R}^m and {w0,w1,,wn1}Rm\{w_0, w_1, \cdots, w_{n-1} \} \subset \mathbb{R}^m both be basis for S. Then k=nk = n. In other words, the number of vectors in a basis is unique.
  • Definition: The dimension of a subspace S equals the number of vectors in a basis for that subspace.
    • For example: A=[1123211314]A = \begin{bmatrix}1 & 1 & 2 & 3 & 2 \\ 1 & 1 & 3 & 1 & 4\end{bmatrix}
    • rref (A)=[1123200122]\text{rref }(A) = \begin{bmatrix}1 & 1 & 2 & 3 & 2 \\ 0 & 0 & 1 & -2 & 2\end{bmatrix}
    • => [χ0χ1χ2χ3χ4]=χ1[11000]+χ3[70210]+χ4[20201]\begin{bmatrix} \chi_0 \\ \chi_1 \\ \chi_2 \\ \chi_3 \\ \chi_4 \end{bmatrix} = \chi_1 \begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \chi_3\begin{bmatrix} -7 \\ 0 \\ 2 \\ 1 \\ 0 \end{bmatrix} + \chi_4\begin{bmatrix} 2 \\ 0 \\ -2 \\ 0 \\ 1 \end{bmatrix}
    • set v0=[11000],v1=[70210],v2=[20201]v_0 = \begin{bmatrix} -1 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} , v_1 = \begin{bmatrix} -7 \\ 0 \\ 2 \\ 1 \\ 0 \end{bmatrix}, v_2 = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 0 \\ 1 \end{bmatrix}
    • then {v0,v1,v2}\{v_0, v_1, v_2\} is the basis of N(A)\mathcal{N}(A).
    • N(A)=N(rref(A))=Span (v0,v1,v2)\mathcal{N}(A) = \mathcal{N}(\text{rref}(A)) = \text{Span }(v_0, v_1, v_2).
    • the dimension of null space of A = 3, which also equals to the number of non-pivot columns of rref(A)\text{rref}(A).
    • C(A)=Span((11),(23))\mathcal{C}(A) = \text{Span}(\begin{pmatrix}1 \\ 1\end{pmatrix}, \begin{pmatrix}2 \\ 3\end{pmatrix}).
    • the dimension of A = 2, which also equals to the number of pivot columns of rref(A)\text{rref}(A).
  • Definition: Let ARm×nA \in \mathbb{R}^{m \times n}. The rank of A equals the number of vectors in a basis for the column space of A. Denoted by rank(A)\text{rank}(A).

5. Showing that A^T A is invertible

  • Let ARm×kA \in \mathbb{R}^{m \times k}, and {a0,a2,,am1}\{a_0, a_2, \cdots, a_{m-1}\} are linearly independent. Is ATAA^T A invertible?
  • ATARk×kA^T A \in \mathbb{R}^{k \times k}.
  • So, we only need to prove ATAA^T A's columns also linear independent.
    • Because, ATAA^T A is a square matrix, if ATAA^T A's columns are linear independent, the reduced row-echelon form of ATAA^T A will be II.
  • Let vN(ATA)v \in \mathcal{N}(A^T A)
    • then ATAv=0A^T A v = 0 => vTATAv=vT0=0v^T A^T A v = v^T \overrightarrow{0} = 0 => (Av)TAv=0(A v)^T A v = 0
    • which means Av2=0\lVert Av \rVert _2 = 0 => Av=0A v = 0
    • We've assumed AA's columns are linearly independent,
    • so vN(A)={0}v \in \mathcal{N}(A) = \{\overrightarrow{0}\} => v=0v = \overrightarrow{0}
    • So, the only solution of ATAv=0A^T A v = 0 is v=0v = \overrightarrow{0}
  • Then ATAA^T A's columns are linearly independent, which means ATAA^T A is invertible.

6. Refers

7. Words

  • echelon ['eʃəlɔn] n. 梯形;梯次编队;梯阵;阶层 vi. 形成梯队 vt. 排成梯队

results matching ""

    No results matching ""