Linear Algebra I

Vector Spaces

Year 1 · Semester IILast updated

April 23 Lecture. Links to the board and the recording.

Examples of Vector Spaces

Vectors in Rn\R^n are objects on which we define operations of addition (to each other) and multiplication by a scalar.
Other “objects” on which we can define the same operations:

  • Matrices: [abcdef]\begin{bmatrix}a&b&c\\d&e&f\end{bmatrix}
    • Denoted as Mm×nM_{m\times n} with an order of mm rows by nn columns
    • Addition between 2 matrices works by adding corresponding entries into the resulting matrix. You can only add matrices of the same order
      • [abcdef]+[ghijkl]=[a+gb+hc+id+je+kf+l]\begin{bmatrix}a&b&c\\d&e&f\end{bmatrix} + \begin{bmatrix}g&h&i\\ j&k&l\end{bmatrix} = \begin{bmatrix}a+g&b+h&c+i\\d+j&e+k&f+l\end{bmatrix}
    • Multiplication works by multiplying each term by the scalar
      • n⋅[abcdef]=[a⋅nb⋅nc⋅nd⋅ne⋅nf⋅n]n\cdot\begin{bmatrix}a&b&c\\d&e&f\end{bmatrix}=\begin{bmatrix}a\cdot n&b\cdot n&c\cdot n\\d\cdot n&e\cdot n&f\cdot n\end{bmatrix}
  • Polynomials: anxn+an−1xn−1+an−2xn−2+⋯+a1x+a2a_{n}x^{n}+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\dots+a_1x+a_2 (“formal sum” of powers of variable xx, each with a coefficient)
    • Degree of polynomial is the highest power of xx
    • Addition and scalar multiplication works as expected
  • Functions:
    • Let f(x)=sin⁡xf(x)=\sin x and let g(x)=4exg(x)=4e^x.
    • Addition (f+g)(x)=sin⁡x+4ex(f+g)(x)=\sin x+4e^x
    • Multiplication (c⋅f)(x)=c⋅f(x)=c⋅sin⁡x(c\cdot f)(x)=c\cdot f(x) = c\cdot \sin x

All of these are examples of abstract vector spaces.

Definition of Vector Space

A set VV is called a vector space (and its elements are called vectors) if we can define on VV operations of addition (⊕\oplus) and scalar multiplication (⊙\odot) satisfying the following ten axioms:

Vector Space Axioms
10 All Important Axioms of Vector Spaces
  1. Addition ⊕\oplus is commutative
  • i.e. for u⃗,v⃗∈V:u⃗⊕v⃗=v⃗⊕u⃗\vec u,\vec v\in V:\vec u\oplus\vec v=\vec v\oplus\vec u
  1. Addition ⊕\oplus is associative
  • i.e. for u⃗,v⃗,w⃗∈V:(u⃗⊕v⃗)⊕w⃗=u⃗⊕(v⃗⊕w⃗)\vec u,\vec v,\vec w\in V:(\vec u\oplus\vec v)\oplus\vec w=\vec u\oplus(\vec v\oplus\vec w)
  1. VV is closed under addition
  • If u⃗,v⃗∈V then u⃗⊕v⃗∈V\vec u,\vec v\in V\text{ then }\vec u\oplus\vec v\in V
  1. There exists in VV a zero vector denoted 0⃗\vec{0} such that ∀v⃗∈V:v⃗+0⃗=v⃗\forall\vec v\in V: \vec v + \vec0=\vec v
  2. ∀v⃗∈V  ∃v⃗′ such that v⃗⊕v⃗′=0⃗\forall\vec v\in V\;\exists\vec v^\prime\text{ such that } \vec v\oplus\vec v^\prime=\vec0
  • e.g. in R2\R^2, if v⃗=(5,−3)\vec v=(5, -3) then v⃗′=(−5,3)\vec v^\prime=(-5,3)
  1. V is closed under scalar mult.
  • i.e., if v⃗∈V,c∈R\vec v \in V,c\in\R then c⊙v⃗∈Vc\odot\vec v\in V
  1. For all v⃗∈V\vec v\in V and c1,c2∈Rc_1,c_2\in\R we have: (c1⋅c2)⊙v⃗=c1⊙(c2⊙v⃗)(c_1\cdot c_2)\odot\vec v=c_1\odot(c_2\odot\vec v)
  2. ∀v⃗∈V:  1⊙v⃗=v⃗\forall \vec v\in V:\;1\odot\vec v=\vec v
  3. Distributive Law 1:
  • For any v⃗,u⃗∈V,c∈R:  c⊙(v⃗⊕u⃗)=(c⊙v⃗)⊕(c⊙u⃗)\vec v,\vec u\in V,c\in\R:\; c\odot(\vec v\oplus\vec u)=(c\odot\vec v)\oplus(c\odot\vec u)
  1. Distributive Law 2:
  • For any v⃗∈V,c1,c2∈R:  (c1+c2)⊙v⃗=(c1⊙v⃗)⊕(c2⊙v⃗)\vec v\in V,c_1,c_2\in\R:\; (c_1+c_2)\odot\vec v=(c_1\odot\vec v)\oplus(c_2\odot\vec v)

Common Vector Spaces:

  • Rn\R^n
  • Mm×n(R)M_{m\times n}(\R) = all matrices of order m×nm\times n (m,n∈N)(m,n\in\N) with entries in R\R
  • Rn[x]\R_n\left[x\right] = set of all polynomials in variable xx with real coefficients and of degree ≤n\le n.
    • Note: Not degree = nn, because that wouldn’t be a vector space

But why are we doing this?

We can prove properties and define concepts just based on the axioms, and these properties/concepts will automatically apply ot all the examples of vector spaces.

Properties of Vector Spaces

  • c⊙0⃗=0⃗c\odot\vec0=\vec0
  • 0⊙v⃗=0⃗0\odot\vec v=\vec0
  • −1⊙v⃗=v⃗′-1\odot\vec v=\vec v^\prime

April 27 Tirgul. Links to the board and the recording.

Subspaces

Definition: Let V be a vector space. A subset U⊆VU\subseteq V is a subspace of VV (denoted U≤VU \le V) if UU is itself a vector space under same operations ⊕,⊙\oplus,\odot as defined in VV.
Examples of subspaces of R2\R^2:
U1=xU_1=x-axis
U2=yU_2=y-axis
U3=xyU_3=xy line
“Trivial” subspaces of R2\R^2:

  1. (0,0){(0,0)}
  2. All of R2\R^2
What axioms need to be checked to determine if U⊆VU\subseteq V is a subspace?
  1. U≠∅U\not=\emptyset
  2. UU is closed under ⊕\oplus
  3. UU is closed under ⊙\odot
What are subspaces of R2\R^2?
  1. {(0,0)}\{(0,0)\}
  2. All of R2\R^2
  3. Any line through the origin (y=kxy=kx or yy-axis)
    • Closure under addition:
      • (x1,kx1)+(x2,kx2)=(x1+x2,kx1+kx2)=(x1+x2,k(x1+x2))∈ line y=kx\begin{aligned}(x_1,kx_1)+(x_2,kx_2)&=(x_1+x_2,kx_1+kx_2)\\&=(x_1+x_2, k(x_1+x_2))\\&\in\text{ line }y=kx\end{aligned}
      • (0,y1)+(0,y2)=(0,y1+y2)∈y(0,y_1)+(0,y_2)=(0,y_1+y_2) \in y-axis
    • Closure under scalar multiplication:
      • c⋅(x,kx)=(cx,ckx)=(cx,k(cx))∈ line y=xk\begin{aligned}c\cdot(x, kx)&=\\(cx,ckx)&=\\(cx, k(cx))&\in\text{ line }y=xk\end{aligned}
      • c⋅(0,y)=(0,cy)∈yc\cdot(0, y)=(0,cy)\in y-axis
What are subspaces of R3\R^3?
  1. {(0,0,0)}\{(0,0,0)\}
  2. Any line through origin
  3. Any plane going through origin
  4. All of R3\R^3

April 30 Lecture. Links to the board and the recording.
[Incomplete] Coming soon to a PDF near you…

Checking if a subset is a subspace

U⊆VU\subseteq V is a subspace of V (U≤VU\le V) iff

  1. U≠∅U\not=\emptyset
  2. UU is closed under addition
  3. UU is closed under scalar multiplication
    See the board for examples, I can’t be bothered to type them all out.
Intersection and Union of Subspaces

Suppose U1,U2≤VU_1,U_2\le V.
U1∩U2≤VU_1\cap U_2\le V is always true
U1∪U2≤VU_1\cup U_2\le V is true ONLY if U1⊆U2U_1\subseteq U_2 or U2⊆U1U_2\subseteq U_1.


May 4 Tirgul. Links to the board and the recording.

Linear Combination

Definition:
Given a finite set S={v⃗1,…,v⃗k}S=\{\vec v_1,\dots,\vec v_k\} in any vector space V, a linear combination of SS is any vector of form u⃗=c1v⃗1+⋯+ckv⃗k\vec u=c_1\vec v_1+\dots+c_k\vec v_k.

Span

Definition:
The span of a finite set of vectors S={v⃗1,…,v⃗k}S=\{\vec v_1,\dots,\vec v_k\} is the set of all linear combinations of SS.
For any finite set S⊆VS\subseteq V, Span S≤V\text{Span }S\le V.
In fact, Span S\text{Span }S is the smallest subspace of V containing every vector of SS.


May 7 Lecture. Links to the board and the recording.

Linear Independence

Definition:
A (finite, non-empty) set S⊆VS\subseteq V is linearly independent if no vector in SS is a Linear Combination of other vectors in SS.
Elaborated Definition:
A (finite, non-empty) set S⊆VS\subseteq V is linearly independent if the following is true:
If c1v⃗1+⋯+ckv⃗k=0⃗c_1\vec v_1+\dots +c_k\vec v_k=\vec 0 then c1=⋯=ck=0c_1=\dots=c_k=0.
Example:
S={(1,2,3,),(0,−1,4)}S=\{(1, 2, 3,), (0,-1,4)\}
Suppose: c1⋅(1,2,3)+c2⋅(0,−1,4)=(0,0,0)c_1\cdot(1,2,3)+c_2\cdot(0,-1,4)=(0,0,0)
That means that:

c1⋅1+c2⋅0=0c1⋅2+c2⋅−1=0c1⋅3+c2⋅4=0\begin{aligned} c_1\cdot1&+c_2\cdot0&=0\\ c_1\cdot2&+c_2\cdot-1&=0\\ c_1\cdot3&+c_2\cdot4&=0 \end{aligned}

Solving for c1,c2,c3c_1, c_2, c_3, we will see that they all equal zero.
This is proof of linear independence.
Example:
S={(1,2,3),(−4,−8,−12)}S=\{(1, 2, 3), (-4,-8,-12)\}
Suppose: c1⋅(1,2,3)+c2⋅(−4,−8,−12)=(0,0,0)c_1\cdot(1,2,3)+c_2\cdot(-4,-8,-12)=(0,0,0)
Extracting equations for c_1, c_2, c_3 will yield the following:
c1−4c2=02c1−8c2=03c1−12c2=0\begin{aligned}&c_1-4c_2&=0\\2&c_1-8c_2&=0\\3&c_1-12c_2&=0\end{aligned}
The second and third equations are both multiples of the first equation, so we can ignore them. we are left with c1=4c2c_1=4c_2, which has an infinite number of solutions. This means that SS is linearly dependent.
In other words, SS is linearly independent if the only linear combination of SS equal to 0⃗\vec 0 is the trivial linear combination (i.e., all scalars are 0).
By this definition, S=0⃗S=\vec 0 is not independent, because if c⋅(0,0,0)=(0,0,0)c\cdot(0, 0, 0)=(0, 0, 0), then cc need not be 00, can be any scalar.
Any other set of one vector is independent.

How to check if a set of vectors is Linearly Independent
Method to tell if S⊆RnS\subseteq\R^n is independent:
  1. Write vectors of SS as columns in a matrix AA
  2. Consider AA as a coefficient matrix of a homogeneous system, and solve
  3. If the solution is unique, SS is independent. If there are infinitely many solutions, SS is dependent. If there are zero solutions, you messed something up.

Example with Rn\R^n:
S1={(1,3,5),(2,4,6),(−1,1,3)}S_1=\{(1,3,5),(2,4,6),(-1,1,3)\}
To check if S1S_1 is independent:
Suppose c1(135)+c2(246)+c3(−113)=(000)c_1\begin{pmatrix}1\\3\\5\end{pmatrix}+c_2\begin{pmatrix}2\\4\\6\end{pmatrix}+c_3\begin{pmatrix}-1\\1\\3\end{pmatrix}=\begin{pmatrix}0\\0\\0\end{pmatrix} (We wish to show: c1=c2=c3=0c_1=c_2=c_3=0)
Extract equations for c1,c2,c3c_1, c_2, c_3:
c1+2c2−c3=03c1−4c2+c3=05c1+6c2+3c3=0\begin{aligned}&c_1+2c_2-c_3&=0\\3&c_1-4c_2+c_3&=0\\5&c_1+6c_2+3c_3&=0\end{aligned}
Solve system using coefficient matrix:
[12−1341563]\begin{bmatrix}1&2&-1\\3&4&1\\5&6&3\end{bmatrix}
There are two possibilities for a homogeneous system:

  • There is a unique solution (0,0,0)(0,0,0), which means c1=c2=c3=0c_1=c_2=c_3=0, which proves SS to be independent.
  • There are infinitely many solutions, which means c1=c2=c3=0c_1=c_2=c_3=0 is not true, which proves SS to be dependent.
    Solving the matrix as such…
[1 2 −1 3 4  1 5 6  3 ]→R3→R3−5R1R2→R2−3R1[12−10−240−48]→R2→−12R2[12−101−20−48]→R3→R3+4R2[1 2 −1 0 1 −2 0 0  0 ]⇒Infinite number of solutions⇒S is linearly dependent\begin{aligned} \begin{bmatrix} 1\ &2\ & -1\\\ 3\ &4\ &\ 1\\\ 5\ &6\ &\ 3\ \end{bmatrix} &\xrightarrow[R_3\rightarrow R_3-5R_1]{R_2\rightarrow R_2-3R_1} \begin{bmatrix} 1 & 2& -1\\ 0 &-2& 4\\ 0 &-4& 8 \end{bmatrix} \xrightarrow{R_2\rightarrow-\frac12R_2}\\ \begin{bmatrix} 1 & 2& -1\\ 0 & 1& -2\\ 0 &-4& 8 \end{bmatrix} &\xrightarrow{R_3\rightarrow R_3+4R_2} \begin{bmatrix} \bf1\ &2\ & -1\\\ 0\ &\bf1\ & -2\\\ 0\ &0\ &\ \bf0\ \end{bmatrix}\\ \Rightarrow&\text {Infinite number of solutions}\\ \Rightarrow&S\text { is linearly dependent} \end{aligned}

Basis and Dimension

Definition:
A basis of a vector space VV is a linearly independent set SS which spans VV. (i.e. Span(SS) =V=V)
Examples:
In R2\R^2, S1={(1,0),(0,1)}S_1=\{(1,0),(0,1)\}
This set is independent (easy to check)
This set spans R2\R^2: ∀(a,b)∈R2:(a,b)=a(1,0)+b(0,1)\forall (a,b)\in\R^2:(a,b)=a(1,0)+b(0,1)
Therefore, S1S_1 is a basis of R2\R^2
In R2\R^2, S1={(1,1),(−3,5)}S_1=\{(1,1),(-3,5)\}
Independent? Neither is a multiple of the other, so yes.
Spanning? ∀(a,b)∈R2∃?c1,c2∈R∣(a,b)=c1(1,1)+c2(−3,5))\forall (a,b)\in\R^2\stackrel?\exists c_1,c_2\in\R\mid(a,b)=c_1(1,1)+c_2(-3,5))
Yes (We’ll come back to this later.)
Therefore, S2S_2 is a basis of R2\R^2
In R2\R^2, S3={(1,0),(0,1),(2,3)}→S_3=\{(1,0),(0,1), (2,3)\}\rightarrow spans, but isn’t independent
In R2\R^2, S4={(1,3)}→S_4=\{(1,3)\}\rightarrow independent, but doesn’t span
In R2\R^2, S5={(1,−1),(−3,3)}→S_5=\{(1,-1),(-3,3)\}\rightarrow doesn’t span and isn’t independent
Claims:
Proofs omitted. See pp. 12, 13

  1. If B={v⃗1,…v⃗n}B=\{\vec v_1,\dots\vec v_n\} is a basis of VV, then any v⃗∈V\vec v\in V has a unique representation as a linear combination of BB
  2. If S⊆Rn,S={v⃗1,…v⃗n}S\subseteq\R^n, S=\{\vec v_1,\dots\vec v_n\} (i.e., SS is a set of nn vectors in Rn\R^n) then SS spans Rn\R^n iff SS is independent.
    • Hence: it is enough to check one condition (independent or spanning) to determine if SS is a basis

May 11 Tirgul. Links to the board and the recording.

Question 3/b

Prove or disprove 1. The set {(−1,2,1,1),(0,−1,1,1),(0,2,1,1),(1,2,−1,1)}\{(−1,2,1,1), (0, −1,1,1), (0,2,1,1), (1,2, −1,1)\} is linearly independent in R4\R^4

Method:

  1. Write vectors as columns in coefficient matrix
  2. Solve the matrix (Row Echelon Form)
  3. If Row Echelon Form is achieved, that is proof of a unique solution, and therefore Set Independence
  4. Otherwise, there are infinite solutions because the set is not independent.
Question 4/c

Find kk such that the set v⃗1=(−1,2,3,2),v⃗2=(2,2,2,2),v⃗3=(−2,−5,−6,−4),v⃗4=(2,6,𝑘,5){\vec v_1 = (−1,2,3,2), \vec v_2 = (2,2,2,2), \vec v_3 = (−2, −5, −6, −4), \vec v_4 = (2,6,𝑘, 5)} is linearly dependent, or prove that there is no such kk.

Method:

  1. Steps 1 and 2 as above
  2. Find the values for kk that will achieve Row Echelon Form.
  3. If no such value exists, this is proof that there is no kk
  4. If such value exists, this is your answer.
Question 2/a

Express the polynomial −x2+3x+11-x^2 + 3x +11 as a linear combination of the polynomials x2−x+6x^2-x+6, 2x2−3x2x^2-3x, and x−3x-3.

Method:

  1. Assign vectors. In this case,
    u⃗=−x2+3x+11v⃗1=x2−x+6v⃗2=2x2−3xv⃗3=x−3\begin{aligned}\vec u&=-x^2 + 3x +11\\\vec v_1&=x^2-x+6\\\vec v_2&=2x^2-3x\\\vec v_3&=x-3\end{aligned}
  2. We seek c1,c2,c3c_1, c_2, c_3 such that:
    c1(x2−x+6)+c2(2x2−3x)+c3(x−3)=u⃗c_1(x^2-x+6)+c_2(2x^2-3x)+c_3(x-3)=\vec u
  3. Rewrite the equation like so: (c1+2c2)x2+(−c1−3c2+c3)x+(6c1−3c3)=−x2+3x+11\begin{aligned}(c_1+2c_2)x^2&+&(-c_1-3c_2+c_3)x&+&(6c_1-3c_3)&=\\-x^2&+&3x&+&11&\end{aligned}
  4. Solve for c1,c2,c3c_1, c_2, c_3
  5. Write answer as c1(x2−x+6)+c2(2x2−3x)+c3(x−3)c_1(x^2-x+6)+c_2(2x^2-3x)+c_3(x-3)
    Of course, substituting c1,c2,c3c_1, c_2, c_3 with the values from step 4.