MA1513
Linear Algebra with
Differential Equations
LECTURE 3
Log in to [Link]/vtpoll using your NUS ID
MA1513 LECTURE 3 1
Topics for week 3
Chapter 2: Vector Spaces
2.3 Subspaces
2.4 Linear independence
2.5 Basis and Dimension
2.6 Coordinate vectors
2.7 Projection and Linear approximation
MA1513 LECTURE 3 2
Color Mixing (An analogy)
Three primary colors: Red, Green, Blue (RGB)
Different color shade combination gives “all” colors
e.g. 20% Red + 45% Green + 30% Blue
this specific linear combination of RGB will produce a particular color
The three primary colors span the entire color space:
span{Red, Green, Blue, Yellow} = Color space
- span{Red, Green, Blue} = Color space
{Red, Green, Blue}
None of the three primary colors are redundant: forms a basis for
Red, Green, Blue, Yellow is not linearly independent the color space
- {Red, Green, Blue} is linearly independent
MA1513 LECTURE 3 3
Overview
All the linear combinations
R3 c1u1 + c2u2 + c3u3
span
{u1, u2, u3} span{u1, u2, u3} We say: span{u1, u2, u3}
assume: coplanar is a subspace of R3
{u1, u2, u3} is a building
block of span{u1, u2, u3}
{u1, u2, u3} is not a basis
for span{u1, u2, u3}
MA1513 LECTURE 3 4
Overview
All the linear combinations
R3 c1u1 + c2u2
span
{u1, u2} span{u1, u2} We say: span{u1, u2}
is a subspace of R3
{u1, u2} is a basis
for span{u1, u2}
We say the dimension
of span{u1, u2} is 2
MA1513 LECTURE 3 5
Overview
span{u1, u2, u3} span{u1, u2}
All the linear combinations All the linear combinations
c1u1 + c2u2 + c3u3 c1u1 + c2u2
There is a redundant vector There is no redundant
among {u1, u2, u3} vector among {u1, u2}
{u1, u2, u3} is a linearly dependent set {u1, u2} is a linearly independent set
MA1513 LECTURE 3 6
Overview
All the linear combinations
R3 span c1u1 + c2u2 + c4u4
{u1, u2, u4} span{u1, u2, u4} = R3
span{u1, u2, u4}
assume: non-coplanar
span{u1, u2, u4} is
again a subspace of R3
{u1, u2, u4} is a linearly
independent set
{u1, u2, u4} is a basis for We say the dimension
span{u1, u2, u4} of span{u1, u2, u4} is 3
{u1, u2, u4} is a basis for R3
MA1513 LECTURE 3 7
Extending to Rn
Rn • Start with a set S of n-vectors {u1, u2, …, uk} in Rn
• span(S) is a subspace of Rn
span(S)
• {u1, u2, …, uk} is a building block of span(S)
c1u1 + c2u2 + ··· + ckuk
• If {u1, u2, …, uk} is linearly independent, it is a basis
for span(S) and the dimension of span(S) is k.
S
u1
u2
…
uk
MA1513 LECTURE 3 8
In general, number of
dim(solution space) = free parameters
in the general solution
Solution Space of Ax = 0
2v + 2w − x + z = 0
homogeneous − v − w + 2 x − 3y
+ z = 0
system
x + y + z = 0
Gaussian
v + w − 2 x − z = 0
Elimination
v − s − t
general w s
solution x =
y − t
separate 0
parameters z t
− 1 − 1
general 1 0
linear combination
= s 0 + t − 1
0 0 basis for solution space = {u1, u2}
of vectors
extract the 0 1
dim(solution space) = 2
vectors u1 u2
the vectors obtained linear span span{u1, u2} = solution space of Ax = 0
is always linearly of the vectors subspace of R5
independent
MA1513 LECTURE 3 9
All subspaces of Rn satisfy closure properties
Solution set of linear system Rn
Solutions of
Ax = b
Ax = b linear system with n variables
system is homogeneous system is non-homogeneous
Ax = 0 Ax = b
The set of solutions is The set of solutions is
a “span”, and hence a not a “span”, and hence
subspace of Rn not a subspace of Rn
We call it a solution space We don’t call it a solution space
Satisfies closure properties Does not satisfy closure properties
If u, v are solutions of Ax = 0, If u, v are solutions of Ax = b,
• u + v also a solution • u + v not a solution
• cu also a solution • cu not a solution
MA1513 LECTURE 3 10
Linearly independent set: No redundant vectors in the set
Linearly dependent set: redundant vectors in the set
Example 1 (Linear independence)
Are these sets of vectors in R3 linearly independent?
{ (1, 1, 1), (0, 1, 1), (0, 0, 1) }
{ (1, 1, 1), (0, 1, 0), (1, 0, 1) }
{ (1, 1, 1), (-1, -1, -1) }
{ (1, 1, 1), (1, 1, -1) }
{ (1, 1, 1), (0, 1, 1), (0, 0, 1), (1, 0, 1) }
MA1513 LECTURE 3 11
Example 1 (cont.)
{ (1, 1, 1), (0, 1, 1), (0, 0, 1) }
Standard method: a(1, 1, 1) + b(0, 1, 1) + c(0, 0, 1) = (0, 0, 0)
1 0 0 1 0 00
G.E REF
Alternative method: 1 1 0 =1 1 1 00
only trivial solution lin indep
1 1 1 1 1 10
{ (1, 1, 1), (0, 1, 0), (1, 0, 1) }
Standard method: a(1, 1, 1) + b(0, 1, 0) + c(1, 0, 1) = (0, 0, 0)
1 0 1 1 0 10
G.E REF
Alternative method: 1 1 0 =0 1 1 00
non-trivial solution lin dep
1 0 1 1 0 10
MA1513 LECTURE 3 12
Example 1 (cont.)
{ (1, 1, 1), (-1, -1, -1) } the set has only two vectors
Standard method
Short-cut method scalar multiples of each other linearly dependent
{ (1, 1, 1), (1, 1, -1) } the set has only two vectors
Standard method
Short-cut method not scalar multiples of each other linearly independent
{ (1, 1, 1), (0, 1, 1), (0, 0, 1), (1, 0, 1) } the set has more than 3 vectors in R3
Standard method
Short-cut method more than 3 vectors in R3 linearly dependent
MA1513 LECTURE 3 13
Testing Linear dependency { v1, v2, …, vn }
Standard Method:
• Form the equation c1v1 + c2v2 + … + cnvn = 0.
Check whether the homogeneous system has non-trivial solutions for
c1 , c2 , … cn .
Alternative Methods: (only work under certain circumstances) If Yes,
then linearly dependent
• Use the column vectors v1, v2, …, vn to form a matrix A.
If No,
If A is a square matrix, check whether det(A) = 0. then linearly independent
• If there are only two vectors v1, v2 in the set,
check that v1, v2 are scalar multiple of each other.
• If v1, v2, …, vn ∈ Rm and n > m,
If n < m, no conclusion
then the set is linearly dependent.
MA1513 LECTURE 3 14
Example 1 revisited (Basis)
Which of the sets of vectors is/are bases for R3?
{ (1, 1, 1), (0, 1, 1), (0, 0, 1) }
{ (1, 1, 1), (0, 1, 0), (1, 0, 1) }
{ (1, 1, 1), (-1, -1, -1) }
{ (1, 1, 1), (1, 1, -1) }
{ (1, 1, 1), (0, 1, 1), (0, 0, 1), (1, 0, 1) }
Any set of n linearly independent vectors is a basis for Rn
MA1513 LECTURE 3 15
Announcement
• Online quiz
o Quiz 1: view the correct answers (from Canvas > Quizzes)
o Quiz 2: closing on Sunday night.
Note: If you start a new attempt for a quiz
o Quiz 3: opened
without completing, it will be counted as
your last attempt.
• Grades in Canvas
o Lecture quiz scores (Lecture Quiz 2)
o Group discussion (Tutorial) scores (GD 1)
o Online quiz scores (Quiz 1)
o Practice scores (Practice 1, when it is ready)
MA1513 LECTURE 3 18
G.E. preserves
linear dependency of the columns
Example 2 (Basis for linear span)
need to remove the redundant
V = span{ u1, u2, …, uk } vectors among u1, u2, …, uk
span{(1,2,2,1), (3,6,6,3), (4,9,9,5), (-2,-1,-1,1), (5,8,9,4)}
Form a matrix using u1, u2, …, uk as its columns
1 3 4 −2 5 1 3 4 −2 5
2 6 9 −1 8 G.E 0 0 1 3 −2 REF
2 6 9 −1 9 0 0 0 0 1
1 3 5 1 4 0 0 0 0 0
take columns corresponding pivot columns are linearly independent
to pivot columns of REF non-pivot columns are redundant
Basis for the linear span:
{(1,2,2,1), (3,6,6,3) , (4,9,9,5), (-2,-1,-1,1) , (5,8,9,4)}
MA1513 LECTURE 3 19
Subspace in MA1513
• Rn
• span{v1, v2, …, vk} where v1, v2, …, vk are vectors in Rn subspace of Rn
• Solution space of a homogeneous system Ax = 0 with n variables subspace of Rn
• Row space of an m x n matrix A subspace of Rn
• Column space of an m x n matrix A subspace of Rm
• Nullspace of an m x n matrix A subspace of Rn
• Eigenspace of an n x n matrix A (Chapter 3) subspace of Rn
MA1513 LECTURE 3 21
Row Space and Column Space of A
1 2 2 1 r1
3 6 6 3 r2
4 9 9 5 r3
A=
− 2 − 1 − 1 1 r4
5 8 9 4 r5
4
2 7 3 r6
c1 c2 c3 c4
row space of A = span{r1 , r2 , r3 , r4 , r5 , r6 } subspace of R4
column space of A = span{c1 , c2 , c3 , c4 } subspace of R6
MA1513 LECTURE 3 22
All the vectors v in Rn
Nullspace of A that are “nullified” by A,
i.e. Av = 0.
1 2 2 1
This is same as the solutions of Ax = 0
3 6 6 3
4 9 9 5 Nullspace of A = solution space of Ax = 0
A=
− 2 − 1 − 1 1 So it is a subspace of Rn
5 8 9 4
4
2 7 3
Form the homogeneous system Ax = 0
and solve (using G.E.) as before.
MA1513 LECTURE 3 23
G.E. preserves
linear dependency of the columns
Basis for Column Space
pivot columns
1 2 2 1 1 2 2 1
3 6 6 3 0 1 1 1
4 9 9 5 Gaussian 0 0 1 1
A= →
− 2 − 1 − 1 1 Elimination 0 0 0 0
5 8 9 4 0 0 0 0
0 0 0 0
4
2 7 3
c1 c2 c3 c4 REF
column space of A = span{c1 , c2 , c3 , c4 }
Basis for column space of A = columns in A corresp to pivot columns of REF
={c1 , c2 , c3 }
Dimension of column space = # pivot columns of REF = rank(A) = 3
MA1513 LECTURE 3 24
G.E. does not preserve linear dependency of the rows
G.E. preserves the row spaces
Basis for Row Space dim(row space) = dim(column space)
1 2 2 1 r1 1 2 2 1 v1
3 6 6 3 r2 0 1 1 1 v2
4 9 9 5 r3 Gaussian 0 0 1 1 v3
A= →
− 2 − 1 − 1 1 r4 Elimination 0 0 0 0
5 8 9 4 r5 0 0 0 0
0 0 0 0
4
2 7 3 r6
REF
row space of A = span{r1 , r2 , r3 , r4 , r5 , r6 } = row space of REF = span{v1 , v2 , v3}
Basis for row space of A = non-zero rows in REF ={v1 , v2 , v3 }
Dimension of row space = # nonzero rows of REF = rank(A) = 3
MA1513 LECTURE 3 25
Dimension Theorem of Matrix
rank(A) + nullity(A) = # columns of A
Basis for Nullspace
Nullspace of Solution space of
matrix A system Ax = 0
Basis for nullspace Basis for solution space
Dimension of nullspace Dimension of solution space
Nullity of A # parameters in general solution
# non-pivot columns of REF
MA1513 LECTURE 3 26
Least Squares Solutions
When a linear system Ax = b is inconsistent
A least squares solution x0 of Ax = b :
• x0 is the best approximation to a solution of Ax = b
Ax0 ≈ b ||Ax0 - b||
closest smallest
How to find the least squares solution x0 of Ax = b?
Multiply AT on both sides of Ax = b
Solve the new system ATAx = ATb
MA1513 LECTURE 3 28
Example 3 (Least Squares)
2x + y = 20 2 1 20 2 6 20 30 40
6x + y = 18 6 1 x 18 1 1 1 1 1
2940 98 x0 608
20x + y = 10 20 1 y = 10 98 5 y0 =
56
30x + y = 6 30 1 6 AT
40x + y = 2 40 1 2 ATA ATb
A b
Find least squares solution x0 for Ax = b x0 is the actual solution of ATAx = ATb
x0 2940 98
−1
608 −206/637
What if ATA is singular? x0 = y = =
0 98 5 56 268/13
Solve the new system using GE
(ATA)-1
2940 98 608
98 5 56
MA1513 LECTURE 3 29
If x0 is the least squares solution of Ax = b,
Ax0 = projection of b onto column space of A Rn
b
U p
Projection on Subspaces u1 u 2 … u k
Given a subspace U of Rn and a vector b not in U
Find a vector p in U “nearest” to b How to find this projection of b?
This vector p is called
the projection of b onto a subspace U
Find any basis {u1, … , uk} for U span{u1, … , uk} = U
Form matrix A using u1, … , uk as column vectors span{u1, … , uk}
= column space of A
Consider the linear system Ax = b
Solve the system ATAx = ATb, say x0 least squares solution of Ax = b
projection p = Ax0
MA1513 LECTURE 3 30
If x0 is the least squares solution of Ax = b, (1,-1,1)
Ax0 = projection of b onto column space of A U x+y+z=0
Example 4 (Projection)
Find the projection of (1,-1,1) onto the plane U: x + y + z = 0 in R3
U = span{ 2 non-parallel vectors on the plane } = span{ (1,-1,0), (1,0,-1) }
1 1 1
Form matrix A = −1 0 and column vector b = −1
0 −1 1
Find the least squares solution of Ax = b
2 1 x = 2 x 4/3
Solve A Ax = A b
T T =
1 2 y 0 y −2/3
1 1 2/3
Projection of (1, -1, 1) on U: 4/3
−1 0 = −4/3
−2/3
0 −1 2/3
MA1513 LECTURE 3 31