URL http://www.mast.queensu.ca/~helena/linalg3.html

3: Vector Spaces, Linear Independence and Spanning sets.

Text book sections 2.1, 2.2, 2.3, 2.4

Note:

Most, but not everything I said in the lecture is written up yet on this page. You can find a copy of the overheads used in the lecture on reserve in Straufer library. Also I will fix the below soon. Let me know if you need help with anything from this lecture.

Topics for this lecture:

Vector space Rⁿ (text 2.1)

---a list of n numbers

Span (text 2.1)

---Where can some vectors get you?

Vector equation. (text 2.1)

---Sum of vectors - Another way of writing a linear system

Ax=b (text 2.2)

---A way of writing a linear system with vectors and matrices

Homogeneous and non homogenous systems (text 2.3)

---Corresponding to lines through the origin, or not through the origin.

Linear independence (text 2.4)

---What's the least information we need?

Introduction

First we are going to go over span and vector equations again, which we started last week. Please see the second half of the notes for the second lecture (I need to add more details to this part)

Another look at a vector space

Spanning and linear independence

Text book 2.1

Motivation

At the end of last lecture, we looked at spanning. We wrote down vector equations. This is just another way to think about the information in a linear system. We will review the idea of spanning.

We previously defined a vector space to be a string of numbers. But we can just say a vector space is a collection of things that can be added together and multiplied by scalars, and behave in the way these strings of numbers behave.

There are lots of problems where if you have two solutions you can add them together to get a third.

Example 1

Eg., for my calorie free diet, one solution is a carrot, another solution is a stick of celery. Then 3 carrots and 2 sticks of celery is another solution. We can represent it by (3,2). The vectors keep track of how we are building up our basic solutions. The basic solutions here are "carrot" and "celery", represented by (1,0), and (0,1).

But there are more possible "basic" solutions, eg, an apple. So we could use three numbers, eg (1,2,3) to mean 1 carrot, 2 sticks of celery, and three apples.

"Carrot", "celery" and "apple" are more basic solutions than the solution "3 carrots and 2 apples". This is because "3 carrots and 2 apples" can be made from some of "carrots" and "apples"; it is in the span. As vectors, we say (3,0,2) is in the span of (1,0,0) and (0,0,1). We also can say (3,0,2) depends on (1,0,0) and (0,0,1).

But "apples" "carrots" and "celery" can not be got from each other. There is no way to get to (0,0,1) from (1,0,0) and (0,1,0). So these vectors are independent.

If I want to know all possible calorie free diets, I need to find all possible "basic" solutions. I want a collection of solutions that will span the whole set of solutions, that is, a collection of solutions that I can use to get to any other solution. When I know what all possible basic solutions are, then I'll know how long to make my list of numbers.

Example 2

QuestionWhat are all the functions f with f(0)=0?

Partial AnswerThink of some examples. sin(0)=0, and x^2 =0 at x=0. What are some more examples? How about

x
cos(x)-1
x^3

If you add up any of these solutions, you get another solution. You can multiply by scalars too.

We can write a table to show what some possibilities are:

functions made from the "basic" functions
f1 f2 f3 f4 f5 f6
Amount of x 1 0 0 1 0 1
Amount of sin(x) 0 1 0 3 0 0
Amount of x² 0 0 1 0 7 -1
Result: x sin(x) x² x+3sin(x) 7x² x-x²

	functions made from the "basic" functions
	f1	f2	f3	f4	f5	f6
Amount of x	1	0	0	1	0	1
Amount of sin(x)	0	1	0	3	0	0
Amount of x²	0	0	1	0	7	-1
Result:	x	sin(x)	x²	x+3sin(x)	7x²	x-x²

We have a vector space here. How many basic solutions do we need? How do we know functions are independent? These are quite difficult questions.

Maybe we could find a few functions like x, x^2, x^3, and give a new interpretation of the vector space R^3. We could say that a vector (2,5,7) means 2x+5x^2+7x^3. We've got a three dimensional vector space of functions. (Recall other interpretations that were allowed, eg (2,5,7)=2 eggs, 5 fish and 7 apples.)

But can you get all functions from these three?

Anyway, the point is, before you assign strings of numbers to your vectors, you don't really know how many numbers you need.

If we have strings of length n, we know we are in an n dimensional vector space. But how did we know that n was the right number to use?

A few more words on each of the above topics

Vector space

Rⁿ is just lists of n numbers, which can represent all kinds of things, eg, R² can be points on a graph, or on a map.

Span

Eg, 2(1,3)+3(1,-1)=(5,3), so (5,3) is in the span of (1,3) and (1,-1). The span of these two vectors is the set of all vectors you can get to from them. In fact, you can get everywhere in R² with (1,3) and (1,-1), so they span R².

we can write the question of whether you can get to (5,3) with (1,3) and (1,-1) like this:

/ 1 \ x / 1 \ y = / 5 \
\ 3 / \ -1 / \ 3 /

This is a vector equation. If you can solve it, then (5,3) is in the span of (1,3) and (1,-1). This is the same as solving:

/ 1 1 | 5 \
\ 3 -1 | 3 /

Ax=b

We introduce a new notation for writing the above:

/ 1 1 \ / x \ = / 5 \
\ 3 -1 / \ y / \ 3 /

Homogeneous and Nonhomogeneous linear systems

A line is a solution of a linear system that has infinitely many solutions. Last lecture we saw how there was a new notation for lines:

instead of

y=bx+c we can write (0,c)+t(1,b)

If c is zero, then the line goes through the origin. Any line is a line through the origin that has been shifted. The line y=bx+c is the line y=bx, raised a distance c. A line through the origin is the span of a single vector. y=bx is the span of the vector (1,b).

A homogenous system is one that corresponds to lines or planes, or higher dimensional things, that are through the origin.

How does this relate to the augmented matrix and the matrix vector equation?

Linear Independence

If u=av+bw, where u, v and w are some vectors, then u depends on v and w. These three vectors correspond to an overdetermined system. On the other hand, if we have a set of vectors, and none can be expressed in terms of the others, then they are independent.

Vector Spaces

You can add vectors to each other, and multiply by a scalar. See last lecture for a reminder. The picture below shows a geometric interpretation of vector addition.

Note that you can write vectors vertically and horizontally, but even if they have the same numbers inside, they are not said to be equal unless they are also the same shape.

vector addition

exercise:

1:Draw the following vectors on an x y graph with arrows.
- u=(1,3)
- v=(2,1)
- -u, 3v, v+0,
- 3u-v, 3u+v, 3u
- 3v, 3v-u, 3v+u
2:Solve the vector equation:

/ 1 \ x + / 2 \ y = / 2 \
\ 3 / \ 1 / \ 3 /

Answer

Answer to part one is here
Answer to part two: You can write this as an augmented matrix to solve it, or you can just solve by inspection.

The above is going to lead us to the idea of span.

Last lecture we saw a new way of writing the equation of a line in terms of vectors. (Please refer back to that.)

Now we see how to write the equation of a plane in terms of vectors. In three dimensional space, we can describe a plane as everywhere you can get by going in two directions starting from some point. eg:

(1,1,1)+t(1,0,0)+r(0,1,0) means start at (1,1,1) and go any amount you like either in the (1,0,0) direction, or the (0,1,0) direction. So, this turns out to be the plane z=1.

In class we saw a demonstration of

the plane x=1
the plane z=2
the point (1,1,1)
the vector (1,1,1)
the lines:
- (0,2,0)+t(1,0,1)
- (0,2,0)+t(1,1,1)
- (0,2,0)+t(0,1,1)
- (0,2,0)+t(0,1,1)
the planes:
- (0,2,0)+t(0,-1,1)+r(1,-1,0)
- (0,2,0)+t(0,0,1)+r(1,-1,0)
the span of (1,1,1)
the span of (1,1,1) and (0,0,1)

Span

If we have some vectors v₁,v₂,v₃,...v_n, the the span is everywhere we can get to by adding multiples of them together (that is, taking linear combinations). So the span is the set of all vectors of the form a₁v₁+a₂v₂+ ...a_n-1v_n-1+a_nv_n

Question:

Is (2,1) in the span of (1,3) and (2,3)?

Is (1,2,3,4) in the span of the following vectors?

(1,1,0,0)
(1,0,1,1)
(-1,1,-1,0)
(0,0,1,1)

As a vector equation, this is the question of whether we can solve the following:

-1

Remember that (1,1,0,0)4=4(1,1,0,0)=(4,4,0,0), and (1,1,0,0)x=x(1,1,0,0)=(x,x,0,0), so the above means that

/ x \ / y \ / -z \ / 0 \ / 1 \
| x | + | 0 | + | z | + | 0 | = | 2 |
| 0 | | y | | -z | | w | | 3 |
\ 0 / \ y / \ 0 / \ w / \ 4 /

Next, rememember how to add vectors, eg (1,2,3)+(3,4,5)=(1+3,2+4,3+5)=(4,6,8). So we get:

/ x + y - z \ / 1 \
| x w | = | 2 |
| y - z + w | | 3 |
\ y + w / \ 4 /

Next, two vectors are equal only if corresponding entries are all equal. Eg (a,b,c)=(1,2,3) means a=1, b=2, c=3. So we get:

x + y - z = 1
x w = 2
y - z + w = 3
y + w = 4

This is a linear system, so to solve it, we write an augemented matrix, and reduce to echelon form:

/ 1 1 -1 0 | 1 \
| 0 0 0 1 | 2 |
| 0 1 -1 1 | 3 |
\ 0 1 0 1 | 4 /

Multiplication of a matrix and a vector: the equation Ax=b

The new notation for the above problem is the following:

/ 1 1 -1 0 \ / x \ / 1 \
| 0 0 0 1 | | y | = | 2 |
| 0 1 -1 1 | | z | | 3 |
\ 0 1 0 1 / \ w / \ 4 /

In this notation, the vector tells you what the entries in each column represent. So this tells you that the first column means "x"s, the second column means "y"s, the third column means "z"s, and the fourth column means "w"s. So when you multiply a matrix by a vector, the number of columns of the matrix is the same as the number of rows of the vector. The vector it's equal to must tell you the result of each row of the matrix, so it has the same number of rows as the number of rows of the matrix.

Compare the above matrix vector equation with the augmented matrix. The main difference is that you can see what the columns represent in the matrix notation. This means it's easier to change what they represent, and change the amounts of x, y, z, w, to get a different result. This is starting to view a linear system as a transformation.

The title of this section of the book is "The equation Ax=b". A is a matrix, and b and x are vectors, ie, strings of numbers, not just single numbers. In the example here,

A = / 1 1 -1 0 \ ,x = / x \ and b = / 1 \
| 0 0 0 1 | | y | | 2 |
| 0 1 -1 1 | | z | | 3 |
\ 0 1 0 1 / \ w / \ 4 /

This is not very good notation in this case, since the x that means the whole vector is definitely not the same as the x inside the vector.

example: mining company

This is example 2.1 27 in the text book.

The following table shows how much copper and silver a mining company can get from it's two mines in one working day.

One day's opperation of: Amount of copper (tonnes) amount of silver(kg)
mine 1 20 550
mine 2 30 500
If we define the vectors v1 and v2 by

One day's opperation of:	Amount of copper (tonnes)	amount of silver(kg)
mine 1	20	550
mine 2	30	500

v1 = / 20 \ , v2 = / 30 \
\ 550 / \ 500 /

So v1 gives the output of mine one in one day, and v2 gives the output of mine two in one day. 3v2=3(30,500)=(90,1500) gives the output of v2 over 3 days.

ProblemHow can we get 150 tonnes of copper and 2825 kg of silver?

This is represented by the vector equation:

/ 20 \ x + / 30 \ = / 150 \
\ 550 / \ 500 / \ 2825 /
To solve, we write the augmented matrix:

/ 20 30 | 150 \
\ 550 500 | 2825 /
and row reduce until you get the answer.

The vector notation is nice, since it makes you think of how the problem is about adding together the stuff from mine one over a certain number of days to the stuff from mine two over a certain number of days.

As a matrix equation, it looks like:

/ 20 30 \ / x \ = / 150 \
\ 550 500 / \ y / \ 2825 /

We can write out other problems, eg, how to get 50 tonnes of copper and 1050kg silver:

/ 20 30 \ / x \ = / 50 \
\ 550 500 / \ y / \ 1050 /

Or we can ask questions like "what do we get if we run mine one for 1 day and mine 2 for 2 days?":

/ 20 30 \ / 1 \ = / c \
\ 550 500 / \ 2 / \ s /

We can easily change what the problem is about by changing the vectors involved.

Questions

Calculate the following, and say what the result means:

/ 20 30 \ / 2 \
\ 550 500 / \ 2 /

/ 20 30 \ / 3 \
\ 550 500 / \ 1 /

/ 20 30 \ / 1 \
\ 550 500 / \ 0 /

How to calculate Ax=b

The following gives the formular for 2 by 2 matrices (2 rows, 2 columns):

/ a b \ / x \ = / ax+by \
\ c d / \ y / \ cx+dy /

The vector (x,y) tells you what the columns of the matrix represent.

we've already talked about how matrix vector multiplication works. See the text book for a precise definition for arbitrary matrices.

Example

/ 1 0 0 1 1 \ / x \ / x+w+t \
| 2 1 0 5 1 | | y | = | 2x+y+5w+t |
| 3 1 0 0 1 | | z | | 3x+y+t |
\ 4 7 1 9 0 / | w | \ 4x+7y+z+9w /
\ t /

So the (x,y,z,w,t) vector means that the rows of the matrix represent x,y,z,w,t. Eg, the first row of the matrix has

1 in the x row
0 in the y row
0 in the z row
1 in the w row
1 in the t row

So it represent x+w+t.

Next we're going to take some specific values for x,y,z,w,t, eg, x=0,y=0,z=1,w=1,t=0. Then in that case, the first row gives x+w+t=0+1+0=1. And the whole matrix gives:

/ 1 0 0 1 1 \ / 0 \ / 1 \
| 2 1 0 5 1 | | 0 | = | 5 |
| 3 1 0 0 1 | | 1 | | 0 |
\ 4 7 1 9 0 / | 1 | \ 10 /
\ 0 /

Multiplying matices and vectors like this is important, so make sure you get enough practice. Make them up and random, and test yourself using MatLab.

Examples:Multiply the following:

/ 1 2 \ / 1 \
| 3 4 | \ 2 /
\ 1 0 /

[ 1 2 3 ] / 1 \
| 3 |
\ 2 /

Note, the following is Not possible:

/ 1 2 3 \ / 1 \
\ 0 4 5 / \ 3 /
This is not possible since the number of columns in the matrix is not the same as the number of rows in the vector, so it's not telling you what all the columns mean.

Homogeneous and Non homogeneous systems.

A solution to Ax=0 will either give only the point (0,0), or (0,0,0) (or more zeros in a higher dimensional space), or else it will give a line, or a plane, or something of large dimension, which goes through the origin.

This kind of linear system is called homogeneous

Any linear system gives a point or a line or a plane, or whatever, which is got from shifting a point, line or plane etc, through the origin.

If we want to solve Ax=b for some matrix A and some vector b, say we have a solution x₁, with

Ax₁=b and a vector x₂ Ax₂=0

Then x₁+x₂ is a solution to Ax=b. So we can get all the solutions by adding a particular one to the solution that comes from a point, line, or plane, (etc) though the origin.

homogenous and nohomogeneous, graph

Dimension of vector spaces

Motivation

How do we really know that the space we live in is three dimensional?

You might say that it's because there are three directions you can move in, (up down), (left, right), and (back, forth). (I'm going to use a nice Escher picture to illustrate this idea.)

Moving in these three directions, we can get anywhere in space.

But is it enough to say there are three directions?

Would North, West, and North East do? Can we get everywhere in space by going in those directions? (To make these into vectors, we really need to say "one unit North, one unit West, etc.)

Why not?

The thing about these three vector is that one of them is linearly dependent on the others. We could say that North East can be defined in terms of North and West; but we could define West in terms of North and North East. So instead of saying one depends on the other, since they are all equally guilty, we say the set of these three vectors is linearly dependent.

Now how come the first three were enough to get everywhere? When this happens, that some vectors can get us everywhere in a vector space, we say that they span the space. The span of a collection of vectors is all the vectors you can get to using them. Eg, the span of North, West, and North East is "the ground", or all points with height zero. They are three vectors, but they only span a two dimensional space.

We will find out how to see when some strings of numbers are linearly independent, and how to see when they span the vector space.

We will look at the geometric interpretation, and at the meaning of linear independence and spanning for linear systems of equations.

We will look at the meaning of linear independence in some detail and see several examples of it's application.

Homework

Before working on the assignment problems, make sure you understand the material.

Read chapter 2 of the study guide
work through the first few exercises of each section, eg, one of each type of the first 10 questions of each section.
For more practice:
- From section 2.1, questions: 4, 14, 28
- From section 2.2, questions: 4, 16, 36
- From section 2.3, questions: 4, 16, 34
- From section 2.4, questions: 6, 16, 36
- From section 2.5, questions: 2, 12, 20
- From section 2.6, questions: 2, 20, 36

Email me if you have any problems with this.

Assignment

This is to be handed in to be marked on Tuesday 20th May.

From section 2.1, questions: 16, 26
From section 2.2, questions: 18, 28
From section 2.3, questions: 18, 28
From section 2.4, questions: 24, 28
From section 2.5, questions: 14, 18
From section 2.6, questions: 24, 28

Solutions

Solutions to the assignment questions are now (from 22nd May) available on reserve from third floor of straufer library.

What will be on the quiz

On Thursday 15th of May there will be a quiz, with a question like the following:

part 1 Is the vector (1,2) in the span of (2,-2) and (-1,2)?

Write the problem as

a linear system
an augmented matrix
a vector equation
an equation of the form Ax=b

Draw a graph showing how (1,2) is in the span of (2,-2) and (-1,2)

Is this solution unique?

part 2 Are (1,2,1), (2,-2,1) and (-1,2,3) linearly independent?

Solution

part 1 Is the vector (1,2) in the span of (2,-2) and (-1,2)?

a linear system:

2 x - y = 1
-2 x + 2y = 2
an augmented matrix:

/ 2 -1 | 1 \
\ -2 2 | 2 /
a vector equation:

/ 2 \ x + / -1 \ y = / 1 \
\ -2 / \ 2 / \ 2 /
an equation of the form Ax=b

/ 2 -1 \ / x \ = / 1 \
\ -2 2 / \ y / \ 2 /

To solve this, row reduce the augmented matrix:

/ 2 -1 | 1 \ / 2 -1 | 1 \ R1+R2 / 2 0 | 4 \ R1/2 / 1 0 | 2 \
\ -2 2 | 2 / R2+R1 \ 0 1 | 3 / \ 0 1 | 3 / \ 0 1 | 3 /
So the solution is x=2, y=3, and

(1,2)=2(2,-2)+3(-1,2)

This is illustrated in the graph below: The solution is unique, since when we reduced to echelon, the matrix had two leading ones, which means the variables x and y are determined uniquely.

part 2 Are (1,2,1), (2,-2,1) and (-1,2,3) linearly independent?

This means is there a (non trivial) way to get a linear combination of these vectors to be zero.

Can a(1,2,1,)+b(2,-2,1)+c(-1,2,3)=(0,0,0)

One way to solve this is to write a vector equation:

/ 1 \ / 2 \ / -1 \ / 0 \
| 2 | a + | -2 | b + | 2 | c = | 0 |
\ 1 / \ 1 / \ 3 / \ 0 /

and then an augmented matrix:

/ 1 2 -1 | 0 \
| 2 -2 2 | 0 |
\ 1 1 3 | 0 /
Which we get to reduced echelon form to show whether a=0, b=0, c=0 is the only solution or not.

But we can also notice that these vectors have top half the same as in part 1 of this question. So since:

/ 1 \ / 2 \ / -1 \ / 0 \
| 2 | a + | -2 | b + | 2 | c = | 0 |
\ 1 / \ 1 / \ 3 / \ 0 /
We also have:

/ 1 \ a + / 2 \ b + / -1 \ c = / 0 \
\ 2 / \ -2 / \ 2 / \ 0 /
But we had a solution to this: a=1, b=-2, c= -3. And this was unique (though now we can multiply each coeffience by some fixed number and get a new solution). So we can take a=1 , b=-2 , c=-3. We have:

/ 1 \ / 2 \ / -1 \ / 0 \
| 2 | - 2 | -2 | - 3 | 2 | = | 0 |
\ 1 / \ 1 / \ 3 / \ -10 /

We don't get zero like this, so there's no way to get zero, so these vectors must be linearly independent.

Lecture 2 Back to the Linear Algebra Notes Index. Lecture 4

Please send comments, questions, suggestions, corrections, ideas, to me.

• Welcome Home • Origami •

Queen's Mathematics and Statistics
Queen's University

/	2	-1	\|	1	\				/	2	-1	\|	1	\		R1+R2		/	2	0	\|	4	\		R1/2		/	1	0	\|	2	\
\	-2	2	\|	2	/		R2+R1		\	0	1	\|	3	/				\	0	1	\|	3	/				\	0	1	\|	3	/