Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
Okay, let's get started. Welcome to lecture 8.
We're going to pick up where we left off last time, but just a couple of quick announcements before we start.
So you might notice that the homework that was released — the homework that is due this current Friday has a lot of practice problems on it. These are not required to be done.
These are not necessarily — these are not going to be graded at all. But we got a lot of requests from students for practice problems for the exams.
And these are great ways to start working out extra problems in case you want to start preparing for midterm 1.
So if you feel like you have any questions or if you want to discuss these, please come to us in office hours and work these out together as well.
We'll try and do the same thing and have an extra practice problem or two on the next homework as well. This way you can have a chance to practice things.
So on the homework this week, we have a couple of different problems.
For those of you have looked at it, there's one problem that really builds on what we did in lecture last time and talks about traffic flows between different cities.
So that's a problem that for those of you who are interested potentially in traffic applications and want to really understand how linear algebra in particular null spaces can be useful in understanding traffic flows, that's a good problem to look at.
The other problem that we included on this week's homework was a step by step how to on doing proofs.
So there is a proof related to a pumps question that talks about the total amount of water or energy in a system. We talked about this a little bit in the last lecture, right?
And what you're being asked to show in that homework problem is, well, under what kind of pumps can you actually have the total amount of water or total amount of energy in the system be conserved and what happens in this case.
And the way the question is broken out is to say that, okay, let's say you're given a theorem statement. And you're doing this on an exam. You don't necessarily have anyone to discuss with.
You can't really go to office hours. The different sub parts are basically things that I would encourage you to try when you are doing the homework. So the question looks long.
It's a page of sub parts, but, really, each sub part is just a step-by-step given the style of proofs that we've been doing in the class — a step-by-step on how to do these kinds of proofs.
Are there any questions about any of this?
Okay, great. In addition to that, tonight I'm going to be hosting a special session on how to tackle proofs and application-based problems.
So I've been hearing from people that the homework in 16A is quite different from some of the other homework that you've dealt with before.
And one of the goals of 16A is to really try and contextualize the kind of linear algebra that we are doing and understand where and how these things are applied.
And as a result, we have problems on the homework that are inter leaving some of the linear algebraic concepts with more real world problems.
And sometimes these kinds of problems require an extra cognitive jump on your part, right?
Because you have to read through the problem, figure out what is important, what isn't important, figure out how to formulate.
And this question of how to model a problem, how to go from the English to the mathematics, is one of the learning goals of this class.
So this is something that when you're working in the industry or, you know, when you're doing research, problems will not come as a clear, like, solve this equation.
Often, you will have to say, well, here is some kind of real world problem. Let me figure out a model to understand this.
And this is what I end up doing a lot of times in my own research. And so these problems are modeling that.
And going from the words to a mathematical equation sometimes takes some work.
And so I'm going to be talking about specifically how to do this, as well as specifically how to work out proof-style problems, today at 6:00 PM.
So for those of you who are interested, please look at the Piazza post. And hope to see you there if you're — it's completely optional. Not required.
Nothing that I will be covering will not be available to everyone else. So it's not at all in any way required. If you can't make it, you won't be missing out on anything.
Okay, any questions about any of this? Yes?
STUDENT
Will it be [INAUDIBLE] PROFESSOR: It will not be webcasted, no.
It's after hours. Other questions? Yeah, we'll try to take notes and post them, but we'll see.
Actually, if someone comes to the lecture tonight and writes up nice notes that can be shared with everyone on Piazza, I'll be happy to offer this person extra credit.
STUDENT
[INAUDIBLE] PROFESSOR: 521 Cory — 521 Cory — Maybe the whole class will be there now.
Okay, other questions? No? Okay, let's get started. We have a lot of material to cover today.
So last time, we left off with talking about vector spaces and basis, right?
And we introduced the idea of a null space.
And we've also previously talked about this idea of column space.
The column space of a matrix A is just the span of the columns of A. So you will see, you know, span and column space being used interchangeably.
And just so that we can get all of the jargon out of the way quickly, sometimes this is also called the range of a matrix. Doesn't matter which word you use.
We don't care. They all mean the same thing. But you should just know this so that, you know — in case it ever shows up, you will be able to understand.
Okay, so the one thing that we didn't talk about or one thing that we did not define is the idea of a subspace.
So that's what we're going to define today.
We'll also introduced this word rank of a matrix.
We will talk about determinants.
And we will talk about eigenvalues and eigenspaces if we get time.
So what is a subspace?
A subspace is basically — you can think of it as a vector space that is inside of another vector space. So if I have a vector space, let's say, V,F is a vector space.
W,F is a subspace if W is a subset of V and W,F is also
a vector space.
So, for example, let's say I give you a span of 1, 0, 0 and 0, 1, 0.
First, Is this a vector space? How would you decide if this is a vector space?
We have a list of requirements, right? For something to be a vector space.
Can people read?
Sometimes you might see people talk about vector spaces, and they'll only say that what you have to verify is closure under vector addition and closure under scalar multiplication.
We talked about the fact that there's multiple things you have to verify, right? In this class, we will be introducing you to simpler vector spaces that are not necessarily the most complex format.
But, in general, you have to make sure that you can verify every single one of these properties.
Otherwise, there are weird counterexamples that you can come up with that will satisfy some of these properties and not others.
So it's important to make sure when you're deciding whether or not something is a vector space, that you actually look at every single one of these.
One of the things that you can do quickly, though, to check if something is a subspace is check whether or not it includes the zero vector.
The zero vector is something that always has to be included in a vector space and if something in the subspace, it also has to include that. So let's quickly check this.
Does this include the zero vector? Right? And if we were to draw a picture of it, let's say, what does this look like? These vectors are three-dimensional.
They have three entries. Let me call this the x-axis, the y-axis, and the z-axis.
Oops. Okay.
So what space can you show me by hand motions — like, what space is this — are these two vectors spanning? It's this plane, right? It's this plane that is being spanned.
So if you have a 3D space, the xy plane is what is being spanned by these two vectors. And you can go through and check.
And you'll see that this is actually fully a vector space. And you can see that this is actually, in fact, a subspace of R3.
Okay. What if I now ask you, is R2 a subspace of R3?
What is R2?
Its vector is of length 2, with two elements. Two real numbers gives you R2. What is R3?
STUDENT
Three elements.
PROFESSOR
Three elements — what does R2 look like? It looks like a plane, right? So it looks very much like this span.
But is R2 technically a subspace of R3?
It isn't, right, because are these vectors — two length vectors — are they subsets of all of the three length vectors? They're not really comparable at all, right?
So R2 kind of is isomorphic to a subspace of R3. R2 is like this span in some ways, but it's not actually a subspace of R3.
Does anyone have any questions about this? This is a little bit of a subtle point. That's why I wanted to bring it up.
Everyone with me? Yeah?
STUDENT
[INAUDIBLE] PROFESSOR: Great question. Isomorphic is a — isomorphic means that it has the same form. Iso means similar. Form — so it's like the morphism is the same.
So basically, if you were to, like, visualize R2, it looks like a plane. A plane that passes through the origin can, indeed, be a subspace in R3.
But then, you would have to write out the equation of that plane, using three element vectors, not two element vectors. Yes, good question. Thank you. Yes.
STUDENT
Can you [INAUDIBLE] a subspace that has the same [INAUDIBLE] as the [INAUDIBLE] PROFESSOR: Can you generalize to say that the subspace, the vectors in the subspace have to have the same number of entries — have to basically have the same dimension as the vectors in the actual vector space?
And the answer is yes, because all of the vectors in your set, W, have to also be members in the set, V, right?
So if your W has just vectors of length 2 and V has just vectors of length 3, they cannot be contained in each other. Yeah. Yeah.
STUDENT
Is a vector space a subspace of itself?
PROFESSOR
Is a vector space a subspace of itself? Yes, it is. There is no need for things being strict subsets. But this is a corner case.
We don't need to worry about it too much. Other questions? Yes.
STUDENT
Can you write the formal definition of a vector space?
PROFESSOR
This is the formal definition of a vector space.
STUDENT
Oh, okay.
PROFESSOR
Yeah.
Yeah, this is all on the website under Node 7. So okay. Great. What about another example?
What about the span of some vector, 3, 4? Is this a subspace of, let's say, R2?
What does the span of a vector in R2 look like? So I have some plane. This is my R2.
3, 4 is 1, 2, 3, 1, 2, 3, 4 into this vector.
All right. What is the span of this?
STUDENT
The entire line.
PROFESSOR
It's this entire line, right? What's the first thing you want to check? Does it contain the 0 vector?
STUDENT
Yes.
PROFESSOR
Yes, right? So we know that this additive inverse is actually going to exist. If you add two vectors along this line, does it say on the line? Yup.
Does minus V belong to it? If I have any vector V, do I have minus V, right? So is this a subspace?
STUDENT
Subspace.
PROFESSOR
Yup. What about is this a subspace of R2?
Yes or no? Maybe? Maybe not? Seems like a trick question.
STUDENT
Yes. [LAUGHS] PROFESSOR: Yes, three questions.
STUDENT
Yeah. [LAUGHS] PROFESSOR: Yes, it is a subspace. Why is it a subspace? Because for — let's check, right?
There's only one vector. So no matter how many times you add that vector, the associative property holds. The commutative property holds. The zero element is part of this set.
You know, the inverse of 0 is itself. You know, additive vector addition holds. No matter what scalar you multiply it by, you still get the 0 vector.
So every single one of these properties actually holds. So this is the one case, where you can have a single element and have it be a vector space.
Yup.
STUDENT
[INAUDIBLE] difference between 0, 0 and 0, 0, 0?
PROFESSOR
Great question — so when I'm asking about the 0 vector in R2, I'm implicitly meaning zero vector equal to 0, 0.
If I was to ask you, is the 0 vector a subspace of R3, I would have meant 0, 0, 0. Good question. Yes.
STUDENT
Is there a reason for, like, you didn't include the word "span" in this?
PROFESSOR
Yes, there is a reason I didn't include the word "span" for this, because here, span means that I can take any scalar multiple. But what is any scalar multiple of 0?
It's still 0, right? So here, typically when I say span, I do mean any number of linear combinations. Yes. Question?
STUDENT
So when you ask [INAUDIBLE] Can't any subset have zero vectors?
PROFESSOR
Can't any subset have a zero vector? Great question — so what if I ask the following question? I'll write here.
Is the set 1, 1 — notice I'm not writing span here — of subspace of R2 — so how many elements are in this set of vectors?
Exactly one, right? I'm not writing span of 1, 1. I'm just writing 1, 1. And it doesn't include the 0 vector.
But if I was to write span of 1, 1, then I could say 0 times 1, 1 gives me the 0 vector. That's a great question.
So that's why we explicitly had to check for whether the 0 vector is included or not. So this is not a subspace.
We're not going to be quizzing you in, like, technical details about, like, complicated questions on whether something is or is not a subspace.
The goal of these types of questions is not going to be to ask you some kind of trick — trip-you-up questions.
But there is just terminology that you need to know to be able to move forward in this. Like, these people will just end up using this kind of terminology.
Yes.
STUDENT
Is that 1, 1 you just write — is that even a vector space?
PROFESSOR
It is not a vector space.
STUDENT
So then, by that logic, can you say that this zero vector is the subspace of any vector space?
PROFESSOR
The zero vector with the appropriate number of elements is a subspace of any vector space. Yes. Yes.
STUDENT
[INAUDIBLE] subspace always composed of vectors? Or could it be [INAUDIBLE] something else, like polynomials?
PROFESSOR
Subspaces can be — vector spaces can be composed of many different things. They can be composed of things like polynomials. Maybe we'll make a problem about that.
But in general, almost all of these — these, like, quantities can be mapped to vectors.
So if you want to think about polynomials, you can stack the polynomials, the coefficients of the polynomials into a vector. And so you can treat them like a vector.
So vector spaces basically — you can use them to refer to many different objects just because vectors can be used to represent many different things, right? We've used vectors to represent flows.
We've used vectors to represent state. Just like that, you can use vectors represent polynomials or whatever else you might want. Okay. Last question.
STUDENT
So you basically just have a zero vector. What scalars are included in that [INAUDIBLE] PROFESSOR: In the case where you just have a zero vector, what scalars are included?
Great question. In any of these cases, if I don't include explicitly what the scalar is, I mean all of R, all of the real numbers.
And in this class, we will not be ever talking about a vector space, where the associated field is not the real numbers.
When you go to see a 70, you will see a slight generalization, where you will start to do mod math.
And then, you might see this replaced by something that is not the real numbers. But in this class, it will always be the real numbers. Okay.
Great — all very good questions.
Okay. So then, just as a reminder, we talked about some important specific vector spaces, right?
In particular, we talked about the null space of a matrix A, which is the set of solutions to the equation Ax equal to 0, right?
Notice here I'm writing a zero vector without actually saying what dimension it is. In this case, I'm implicitly inferring the dimension of the 0 vector based on the dimensions of A and x, right?
So if you see that ever a zero vector that's written without the dimensions explicitly written out, it just means here you will actually match to whatever the dimensions of this multiplication would give you.
Okay.
And then, there's the column space of A, which is basically the span of the columns of A.
So we saw last time we did some calculations on the dimension of the null space, right? In the traffic flow example, we computed the null space of the matrix that represented the graph.
And then, we said, well, the number of measurements that we need to take is basically the number of free variables, right? And we said that that was the dimension of the null space.
What about the dimension of the column space? What is the dimension of the column space?
So let's think of an example, right?
Whenever you're asked a general question like this, be it a proof or something that, you know, you don't really know how to handle, how do you tackle it?
You do a simple example, right? So let's just do some examples.
So for example, if I put A equal to 1, 2, 3, 4 — some matrix — what is the dimension of the column space of A?
STUDENT
2?
PROFESSOR
2 is what I'm hearing. Why is that? What is the first column of A? We have A1 is equal to 1, 3.
We have A2 is equal to 2, 4, right? And now, we want to say, well, let's look at the span of 1, 3 and 2, 4.
So are these columns — are these vectors linearly dependent?
STUDENT
Heck no.
PROFESSOR
No, they are linearly independent, right? So they span all of R2, which means that — what is the dimension of the span of these two vectors?
2, right, because the dimension of R2 is 2. How did we define dimension? We defined dimension as the number of elements in the set of basis vectors, right?
So let's remind ourselves what the basis is, or the number of elements in the basis is equal to the dimension.
And what is the basis? The basis is a set of vectors that, 1, spans your vector space. And 2, all these vectors are linearly independent, right?
So you need to make sure that no two vectors in your basis set can be expressed as linear combinations of each other.
And I think in discussion last — the previous discussion or yesterday, you did some examples of figuring out what was a basis and what wasn't a basis, right?
Everyone remember those?
So here, what would be a basis for R2?
1, 3, 2, 4 is a perfectly valid basis. You know, another basis might be 1, 0 0, 1 — also a perfectly valid basis.
1, 0, 0, 2 would also be a perfectly valid basis. Basically, any two linearly independent vectors will form a basis.
So in this case, we see that the dimension of the column space of A is exactly 2. What if instead my A was equal to 1, 2, and then 2, 4?
What is the dimension of the column space of A?
STUDENT
1.
PROFESSOR
1, right? Does this span all of R2?
STUDENT
No.
PROFESSOR
Nope, because basically, these are the same vector, right? The two columns are linearly dependent.
And so the column space has dimension 2 — oh, sorry.
STUDENT
1. [LAUGHS] PROFESSOR: Dimension 1 — what about if I had A equal to 1, 2, 2, 4 and 3, 4?
What is the dimension of the column space of this A?
STUDENT
[INAUDIBLE] PROFESSOR: 2, right? So here, the column space has dimension 2.
So this observation — what if I kept adding columns to A here — if I kept adding two-dimensional vectors?
What would be the dimension of A — the dimension of the column space of A?
STUDENT
It would still be 2.
PROFESSOR
It would still be 2, right, no matter how many I added.
And this leads us to the definition of rank — rank of a matrix.
This is equal to the number of linearly independent columns.
So if we look at this example, this matrix, A, has two linearly independent columns. And so its rank is 2.
This matrix — how many linearly independent columns are there?
STUDENT
Only 1.
PROFESSOR
Only 1, right? If I pick one element — if I pick one of these, then the other column becomes linearly dependent.
So the maximum number of linearly independent columns I can pick is basically just 1. So this is 1. What about here? I can pick the first column and the last column, right?
So here, I have two linearly independent columns. In this class, we're not going to rely heavily on the concept of rank.
The concept of rank is something that will come up a lot more when you take classes like 16B and 127 and 189.
Here, I just want to introduce this, because sometimes people will use the terminology, a matrix is full rank.
All that jargon means is that your matrix is going to be invertible if it's a square matrix, because what does it mean?
If you have full rank, it's saying that all of the columns of the matrix are linearly independent. And we know that linearly independent columns means that your matrix is invertible.
So this is a piece of jargon that is sometimes used. And that's the only reason I want to introduce this terminology. Yes. Question.
STUDENT
So the length of a matrix is the thing as the column space's dimension?
PROFESSOR
The rank of a matrix is the same as the column space's dimension. That is correct. Yes, back.
STUDENT
How is this rank different than basis?
PROFESSOR
How is a rank different than basis? That's a good question. So a rank — the rank is defined for a matrix. The basis is defined for a vector space.
So they're connected, in that the dimension of the column space is the number of elements of the basis of that column space. But there is certainly different. Yes.
STUDENT
So can a vector space be linearly dependent?
PROFESSOR
Can a vector space be linearly dependent? Vector spaces are collections of vectors, right? So for a subset of vectors in a vector space to be linearly dependent, that is, of course, possible.
For example, 1, 1 is an element in R2. And 2, 2 is also an element in R2. And these are linearly dependent vectors.
But you wouldn't ever say that a vector space is linearly dependent. Linear dependence is a property of a finite number of vectors.
Yes.
STUDENT
[INAUDIBLE] PROFESSOR: I — can you speak up?
STUDENT
Oh, I'm sorry. [INAUDIBLE] columns [INAUDIBLE] PROFESSOR: Sure.
The question was, if I keep adding columns here, why is the dimension of the column space still 2?
So let's consider this matrix.
A is equal to 1, 2, 3, 4, 8, 9, 121, 13, and something.
Okay. Great — lots of big matrix.
When I take linear combinations of the columns of A, what is the dimension of the vector that I'm going to get out?
When I take A times x, what is the dimension of the vector of the corresponding B?
STUDENT
2.
PROFESSOR
What kinds of vectors can I multiply here? What — I can multiply this vector here by — I'll do this row times this column.
So this can have four entries. But what is going to come out here?
STUDENT
[INAUDIBLE] PROFESSOR: Two rows of the matrix means, how many equations can I represent?
STUDENT
Two.
PROFESSOR
Two, right? So when I do A times x, whatever B comes out is going to be a 2 by 1 vector no matter what, right? So what is this B?
This B is a linear combination of all of these columns. So no matter what linear combination I take of the columns, it's always going to be two dimensional.
Is that part clear?
STUDENT
Yeah.
PROFESSOR
Okay.
Now, because any two dimensional vector is in R2 and you know that basically just two of these vectors is sufficient to span R2, the maximum number of linearly independent columns that you're going to find is going to be always 2.
Of course, you could rig an example where you just have 1, 2, 1, 2 1, 2, 1, 2 1, 2, 1, 2, 1, 2 forever.
What would be the dimension of the column space of that matrix?
What is the dimension of the column space of this matrix?
STUDENT
1.
PROFESSOR
1, right? So you had to check that you have the two linearly independent vectors.
But in general, if you have a sufficiently large number of vectors, you're going to have two of them be linearly independent. Does that answer the question?
STUDENT
Yeah.
PROFESSOR
Okay.
Yes.
STUDENT
If you have a zero vector, that would be [INAUDIBLE] PROFESSOR: If I have a zero vector, would I — STUDENT: It could be [INAUDIBLE] PROFESSOR: If I added a zero vector — if I added a zero vector here, I would still be able to span all of R2.
So in this case, the rank would still be — the matrix would still be 2.
Okay. Great.
So these are all concepts that are somewhat abstract but hopefully will, like, become clearer as time goes on.
Why do we care about vector spaces and bases and column spaces and all of these things, right? This is a question that I often get from a lot of students.
And I think one good example of where this really comes up for those of you in particular, who are interested in robotics and AI is thinking about control of robotic devices.
So for example, you had a problem on the homework that talks about a quadcopter flying around, right?
And when you're commanding a quadcopter, let's say to go somewhere, you're always telling the quadcopter to go somewhere in what we call Earth coordinates.
So your quadcopter, let's say, starts here on this doc cam. And you want it to fly to the exit sign at that door, right?
So you program — whatever you would say, you would say, here's a vector that goes from the origin, which is where you are starting, to that exit sign.
And that would be the kind of control input or command that you would want to give to your quadcopter. But the quadcopter can't just take that and go, right?
It has these four propellers. It has to decide, well, how much force do I apply to which propeller? And how do I actually get there, right?
It doesn't have a sense of where it is in the world, right?
Just like when you take your cell phone, your GPS uses satellites to figure out where you are relative to other locations in the world, right?
So it can only take actions in what are called its local frame of reference.
So it can only say, well, I want to move, you know, 1 foot to the left from my current position. It cannot really understand in the global frame of reference where.
And so often, what you end up doing is that you have a basis that represents the quadcopter's position in the Earth coordinates.
And then, you have a basis that represents the actions that the quadcopter is taking in its local frame of reference. So you have these two things.
And you translate back and forth between them to actually be able to achieve your goal.
So this is one example of something, where these ideas of bases and coordinates and vector spaces actually end up playing quite an important role.
So figuring out whether or not, for example, your quadcopter can actually read somewhere is a problem that builds on the span of the possible directions that your quadcopter can move in.
And if you think about the Segway problem that's on the homework for this week, that's not about a quadcopter. Obviously, it's about a Segway.
But it's exactly talking about the same robotic principles that can be used for controlling much more complex things. So these ideas are all connected up.
And hopefully, as you do the homework and things go — and you keep going on in the class, these things will become clearer. Yes. Question.
STUDENT
[INAUDIBLE] linearly [INAUDIBLE] problem [INAUDIBLE] PROFESSOR: Here? This one?
STUDENT
No, no, the [INAUDIBLE] PROFESSOR: Oh, column here — 3, 7.
STUDENT
[INAUDIBLE] PROFESSOR: This one — 1, 2, 2, 4, 3, 4, and 3, 7.
STUDENT
Yeah. [INAUDIBLE] PROFESSOR: So you're saying, let's add 3, 7 here?
Well, the dimension of the column space would still be 2, because you would still have at most 2 linearly independent vectors.
So you could pick, for example — this and this is a linearly independent pair. But then, the third one you can get as a linear combination of these two.
So no matter how many you added, you would still never be able to go beyond 2.
STUDENT
[INAUDIBLE] the number of [INAUDIBLE] PROFESSOR: So it's basically the size of the set that is linearly independent. So you want to make one set of linearly independent columns.
So here, given two dimensional vectors, the maximum number of vectors that you can have that will be linearly independent is actually just 2, right?
You can never have 3 vectors that are of size 2 by 1 that are all linearly independent.
Okay. So you can think about this as the maximum number of linearly independent columns. Like, what is the maximum set of linearly independent columns that you can make?
Okay.
So we've talked about the inevitability of a matrix. And we've seen a bunch of different, you know, conditions for a matrix being invertible, right?
You've seen basically that it's very deeply connected to the linear independence and dependence of the columns. So a matrix A is invertible.
We now know if and only if A has linearly independent columns.
This is sometimes referred to as the matrix is full rank.
You can also say that this is the same as Ax equal to B has a unique solution.
You can also see this as the null space of A is trivial. It's just a zero vector.
And now, I'm going to introduce another way of understanding this. So it's that the determinant of A is not equal to 0. And we haven't yet defined what this determinant means.
And remember, we've proven only some directions of these. We've proven all of the rightward going arrows. You have proved all of the leftward going arrows. You will prove when you get to 16B.
So what is this idea of a determinant? How do we decide when a matrix is invertible and when it isn't?
We know that this has something to do with the linear dependence and independence of the columns, right?
So to do this, some of your TAs helped me make a very nice demo that I wanted to show you. Let's see how this works.
Okay. So you don't need to read the code.
Okay. Could everyone see this?
Oh, dear — frozen computer.
Okay. This is visible, right?
So what we're doing here is we're plotting a set of vectors. So I have the vector 1, 0 and 0, 1 — 1, 0, 0, 1, right?
The blue vector is the first column. The red vector is the second column. Are these vectors linearly dependent?
STUDENT
Nope.
PROFESSOR
Nope. Great.
Here's another pair of vectors — 1 and point. 2 and 0.3 and — sorry. This should be 1.3 and 1.2.
But you have these two vectors — this one and this one. So this should be 0.2 comma 1. And this should be 0.3 — or 1 comma 0.3.
The label is a bit off. I'm sorry.
Are these linearly dependent, independent? Linearly dependent, right? Or linearly independent — okay. What about these two vectors?
Ignore the labels.
Linearly independent, right? What about these two?
What's happening to these vectors? What is the series of vectors that we're plotting? We keep getting closer and closer, right? What's going to happen as I keep bringing them closer and closer?
STUDENT
[INAUDIBLE] PROFESSOR: They're slowly going to end up being exactly on top of each other, right?
So if I wanted to interpret this geometrically — if I wanted to use this visualization to figure out whether or not my vectors were linearly dependent or independent, what are you ending up looking at?
You're ending up looking at this angle, right, between the vectors. And when they're linearly dependent, the angle is basically 0. When they're linearly independent, the angle is not equal to 0.
And what is this angle related to? What is the area of the triangle that is described by these vectors?
If I think of joining the endpoints of these two and making a triangle, what is happening to the area of that triangle?
STUDENT
[INAUDIBLE] PROFESSOR: It's going to 0, right? And this observation is what motivates our definition of the determinant.
So we're going to actually think about, not the area of this exact triangle, but the area of the parallelogram that is defined by these vectors. So the triangle is basically half of the parallelogram.
If the area of the triangle is 0, the area of the parallelogram is also 0, right?
So think about drawing a parallel line to the red vector here and a parallel line to the blue vector here.
And as these vectors keep coming closer and closer together, what is this area of that parallelogram going to be?
STUDENT
0.
PROFESSOR
0.
So this is what we want to use to — can I go back to the document camera, please — to understand the determinant.
So let me actually draw the same picture here.
So let's say I have a matrix A. And this is A, B, C, D. Okay.
And I'm going to, let's say, draw my vector A.
And so this is A. And this is C. And then, let's kind of draw this other vector, B. And now, this x-coordinate here
is B. This is D. And I'm going to complete the parallelogram.
So I want to figure out a way to compute the area of this parallelogram.
So we want to basically be able to do this. And what are we given? We're given that we have these two vectors. This is our first vector.
And this is our second vector. There's lots of ways to do it.
But we want to be able to find a way of doing it that only uses the A, C, B, and D numbers, right?
If we could, we would — we could use trigonometry and basically, you know, compute these angles in terms of, for example, other constructions we could do, right?
But we don't want to go down that route, because we don't have any other information. All we're told is what these two vectors are.
And we want to figure out what is the area of this parallelogram? So the one trick that we're going to do is we're going to — you know, what is easier?
Well, it's easier to compute the area of a rectangle than it is to compute the area of a parallelogram, right?
For a parallelogram, you basically have to now divide it into two triangles and compute the areas of the two triangles.
So you have to draw a perpendicular here, then do, like, the base times the height formula. We don't want to do that.
So what I'm going to do is I'm actually going to complete this rectangle.
Okay. And then, I'm going to complete this and complete this.
So here, this point is at B. So what is this length here?
This length here is B, right?
And this length here is D. So what is this length here?
STUDENT
[INAUDIBLE] PROFESSOR: This length is also D, right?
This length we know is exactly C. What is this length going to be here?
This length is going to be exactly C, right, as well, because these two triangles are basically exactly the same.
And so here, also we're going to have this length is going to be B.
Everyone, take a minute to convince yourself that the lengths that I just wrote out are actually correct. Like, take a minute. Talk to each other.
Make sure that you follow what — how that happened. [SIDE CONVERSATION] Yeah.
STUDENT
For the [INAUDIBLE] second part [INAUDIBLE]
on the second part for matrix [INAUDIBLE] invertible, is that [INAUDIBLE] what if, like, A is [INAUDIBLE] PROFESSOR: This is only — matrix A is invertible means we're talking about a square matrix.
STUDENT
[INAUDIBLE] for the Ax [INAUDIBLE] B has a unique [INAUDIBLE] PROFESSOR: Right. But when we're writing it in this context, we're talking about A being square.
STUDENT
Okay.
PROFESSOR
Yeah.
Okay. So where are we so far? What is the total length here? Is everyone with me on how we do this, right?
Basically, you're saying that this triangle is the same as this triangle. This triangle is the same as this triangle. These two sides are equal.
Therefore, these two rectangles are also equal, right? So you have a BC rectangle. You have a BC rectangle.
Here, this length is A. This length is C. Therefore, here, this length is A. This length is C, right? Everyone with me? Okay.
So let's now try — what are things that we know how to compute the areas of? Can we compute the area of this big rectangle?
STUDENT
Yes.
PROFESSOR
What are the sides of this? What is this length?
STUDENT
A plus B.
PROFESSOR
A plus B. What is this length?
STUDENT
[INAUDIBLE] PROFESSOR: B plus C, right?
So area of big rectangle is equal to A plus B times D plus C, right?
But we want the area of the parallelogram. So what areas do we have to take out?
STUDENT
[INAUDIBLE] PROFESSOR: Where do we move some areas, right? So what about the area of these squares — or these rectangles? Sorry.
Area of these blue rectangles — this is equal to BC, right, the product of the sides.
What about this triangle?
What is the area of these red triangles — red triangles?
STUDENT
[INAUDIBLE] PROFESSOR: It's a right angle triangle. So I have 1/2 times the base times the height, right?
And how many are there? So I have 1/2 times A times C plus 1/2 times A times C, because there's two red triangles, right?
Yup.
STUDENT
[INAUDIBLE] rectangles [INAUDIBLE] PROFESSOR: Yup. There should be two of these.
There's two blue rectangles. There's two BC's. There's two red triangles. There's two half AC's.
What are we missing?
STUDENT
[INAUDIBLE] PROFESSOR: These ones, right, these orange triangles.
The orange triangles — what is their area?
1/2BD plus 1/2BD — so what remains?
Therefore, area of parallelogram — it is A plus B times D plus C minus 2BC minus AC minus BD, right?
This is equal to AD plus AC plus BD plus BC minus 2BC minus AC minus BD is equal to AB minus BC, right?
So what did you just compute in terms of the elements entirely?
So if you didn't know the angle between the two vectors but you just were told, here are four vectors, is the angle between them 0 or not? What can you do?
Do you got to do this entire, like, picture every time. What are you going to compute? AD minus BC, right? This is called the determinant.
If you now have a three dimensional space — if I, let's say, had a third vector — like, let's say we augmented this to be a three space, right?
Would I look at the area of the parallelogram?
I would then look at the area — I would look at the volume of the parallelepiped, right — so basically, the three dimensional version of the parallelogram.
In third space, I have no idea how to even visualize this. But it turns out that the exact same idea generalizes.
And a way to check if a matrix has linearly dependent columns or not is to actually compute the determinant.
So for those of you who might have seen some of these new ideas before, this is the justification of why the determinant actually works.
And we want to now build on this to really connect it back to invertability. So let us now really think about this matrix, ABCD, and say, what is its inverse?
So how do I compute the inverse of this matrix, right? You've all done now Gaussian elimination. You all know how to compute the inverse of this matrix, right?
I'm going to write it as an augmented matrix.
And I'm going to go through and row reduce. So why don't you take a couple of minutes and actually try and find the inverse of this matrix?
Feel free to talk to each other. Make sure your work is correct.
[SIDE CONVERSATION] What is the first step that you want to do here?
STUDENT
Going to divide.
PROFESSOR
We're going to divide the first row by A, right? So I'll do my work quietly. And you can do your work quietly. You don't have to talk.
Do your steps match mine? No? Yes? What's the next step?
STUDENT
[INAUDIBLE] PROFESSOR: Okay. One more minute for you folks to do it on your own — then, I'll do the rest.
[SNEEZES] [LAUGHTER] Bless you.
[SIDE CONVERSATION] What is starting to show up?
What is this quantity equal to?
AD minus bc is starting to show up, right?
So what do you do in the first step? You make the first element here 1. Then, you use the first row to cancel out the second row. Now, you do that.
Now, I have an element here. I have a zero and a non-zero element. So now, what I want to do is I want to now divide.
I want to cancel this out to make this a 1. So I divide — basically, I multiply by a over ad minus bc. What allows me to do that step?
Can I always do the step from here to here? Can I do it if ad minus bc is equal to 0?
If ad minus equal — bc is equal to 0, what would I get here?
STUDENT
[INAUDIBLE] PROFESSOR: I would get a 0 in this entry, right?
So I go through. I finish the algebra. You should do it on your own time. What do I get?
A inverse is basically db minus ca. And all of these entries are divided by ad minus bc. So I can pull this out — ad minus bc times d, b, minus c, a.
So when am I allowed to write this formula? Can I always write this formula?
Yes. Question?
STUDENT
Should [INAUDIBLE] be negative [INAUDIBLE] PROFESSOR: Should b be minus?
STUDENT
Yeah.
PROFESSOR
Oh, did I get a sign wrong?
Yes, thank you.
Did everyone do the same algebra I did? I hope not. Thank you for pointing that out. Yes, I've made an algebra mistake.
So now, what you have derived is the formula for the inverse of the 2 by 2 matrix, right? Some of you may have seen this formula around in different textbooks.
Now, you have proven that this is true. You have derived this. We're not just asking you to memorize a formula that came out of nowhere.
But you now have both a geometric intuition for why the determinant matters and why it shows up when you're computing inverses and furthermore, an algorithmic verification of the fact that this formula actually works.
You've derived this formula, right? Does anyone have any questions about any of this?
Okay. So is everyone clear about determinants and inverses? Yes.
STUDENT
What if your steps for Gaussian elimination was dividing by a — PROFESSOR: Yes. STUDENT: --would our formula still work [INAUDIBLE] PROFESSOR: Our formula still works if a equals 0.
So that is correct. You can modify this exact calculation to figure out how we would do it in the case of where a is exactly equal to 0.
So this derivation that I did would not work in the case that a is equal to 0, because I divided by a — great question. Yes.
STUDENT
What if you use [INAUDIBLE] How did you make the top row 1, 0 [INAUDIBLE] PROFESSOR: How did I make the top row 1, 0?
I basically multiplied by the reciprocal of this and subtracted out. So I basically used this row to cancel out this.
So I multiplied this row by b — by a and then subtracted. So please go home and make sure that you can do this derivation on your own.
It's algebra. It's worth doing once carefully. Okay. Make sure you do not, for example, forget a minus sign.
Okay. Good.
So now, for the last part of the lecture, I want to basically go to where all of this buildup has been taking us.
And it's one of, I think, my favorite parts of the entire class. And I'm going to start with this example of what I call a tale of two websites.
And we're now going to build up together the algorithm for page rank.
Some people call page rank as basically the million dollar eigenvector problem. Page rank is the algorithm that basically led to the formation of Google.
This was developed at Stanford by the Google co-founders, Larry Page and Sergey Brin. And it basically relies entirely on things that we have been building up in this class so far.
And now, in the course of the rest of today's lecture and tomorrow's lecture, you are going to derive this algorithm on your own. This is what we have done so far.
We've built up tools to be able to finally understand how these folks were able to make sense of the complex network of websites.
So what is the key problem in search, right? You want to understand which websites are popular and which websites are not as popular.
And you want to have popular websites show up high in your search with search results. And you want to have less popular websites show up lower down.
But you can't measure all of the traffic to all of the websites necessarily. You basically have some knowledge of, you know, where people are going. You can measure inlinks and outlinks.
And you can have some sense of this. But how do you understand what happens at some notion of steady state?
And we're going to, again, do this in a simplified case and build out from there. So let's say you have two websites. Let's say that you have the Stanford website.
And you have the Berkeley website.
STUDENT
Yeah!
PROFESSOR
And what you see is that people, who are on each of these websites have the following behavior.
If you're on the Stanford website — [LAUGHTER] --there is a probability 1/2 with which you will return to the Stanford website.
There is a probability 1/2 with which you will jump to the Berkeley web page. Here on the Berkeley web page — [LAUGHTER] It's super interesting.
And you keep coming back to the Berkeley web page. Okay. If you notice, this model is very, very similar to the pumps of water or the energy models that we've been thinking about.
But this is exactly the model that was used by Page and Brin to actually model the internet. So you have these two websites. And you're observing people there.
So let's say you start out in an initial state, x0 is equal to 1, 0, where you have basically x, Stanford, and x, Berkeley.
So you have fraction 1 of all of your people — 100% of all of your people are at this node and 0 are over here. Okay.
So now, you can write out the transition matrix for this. What is Q? Well, Stanford has 1/2 the people returning to it and 1/2 the people going out.
At the next time step, Stanford gets 1/2 of the people that were at Stanford and 0 of the people at Berkeley. So this is 1/2, 0.
And here again, you have 1/2 and a 1. So now, I have x of 1 is equal to 2 times x of 0, right?
And so what is x of 1 equal to? This is equal to 100% of people were here. 1/2 returned. 1/2 went over here in the first time step.
So what do you have now?
STUDENT
1/2.
PROFESSOR
1/2, 1/2, right?
Just take Q and multiply 1, 0 by Q. Everyone with me here? What happens in the second time step?
What happens to the people that were here at the Stanford website? What do they get multiplied by?
STUDENT
[INAUDIBLE] PROFESSOR: Again, by 1/2, right? So you have 1/4. And those, again, go over to the Berkeley website. So now, you have 1/4 and 3/4.
And x of 3 is equal to 1/8 and 7/8.
And if you keep running this, keep running this, keep running this, every time step, the number of people at the Stanford website gets multiplied by 1/2.
So in t time steps, what will be the number of people that are at the Stanford website? It will be 1/2 to the t, right, if I've taken t steps.
And the remainder will be at the Berkeley website. I'm arguing this intuitively.
Make sure you go home and try actually the matrix multiplication way of doing this. So if I keep building this up, what is x of infinity?
If I keep running this in steady state, where will I end up?
STUDENT
0.
PROFESSOR
0, 1, right — no people at the Stanford website, 100% of people at the Berkeley website.
So here, we see that even if we started with all the people on this first website, we're going to end up with all of the people being on the second website.
What this is called is — or what this is evolving to is a notion of steady state. Now, let's say I start in the other direction.
If I start with 100% people at the Berkeley website and no one at the Stanford website — let's say I had if x of 0 was equal to 0, 1.
What is x of 1?
STUDENT
0, 1.
PROFESSOR
0, 1 — what is x of 2?
STUDENT
0, 1.
PROFESSOR
0, 1. x of 2,000?
STUDENT
0, 1.
PROFESSOR
Still 0, 1, right? What 0, 1 is — it's called a steady state for this system. It says that these people are on these websites. They're going around.
They're doing their business, you know, following links. And after this system has run for a very, very long time, you're going to end up in this steady state.
And once you're in this steady state, you're not going to change.
So we call a vector x a steady state if x of the steady state, even when it is multiplied by the transition matrix,
remains exactly the same.
We want to basically find out what allocation of people on this graph is such that even if the people keep jumping around, this relative proportions of people on the different websites remains exactly the same.
This is what we mean by a steady state.
And this is exactly the problem basically that Google or any search engine wanted to solve, which is that at steady state, because you know, people are constantly jumping around, trying to find information on the web, but if you just took a snapshot at steady state, what fraction of the total people would be on which website?
And you wanted to make sure that the websites that had the most people were ranked higher. And the websites that had fewer people were ranked lower.
So the problem that basically they wanted to solve was how can we find this vector x such that this is true?
We see here that it's true for some vectors and not true for other vectors. How can we set this up in the way that we can actually do this?
So here, we know basically how to do one thing in this class, right? What is the one algorithm that we know how to use?
STUDENT
Gaussian elimination.
PROFESSOR
Gaussian elimination, right? So if we wanted to solve this somehow, how would we want to reformulate it?
Can we somehow put this into a format that can actually allow us to use what we know? Is this a system of linear equations?
Kind of, but is it in the format? What is the format of equations we'd like to solve? Ax equal to B, right — this is, like, Ax equal to x.
So can we do some rearrangements to get it into the format that we want? So how would we do that?
What if I say I have Q times x equal to x? I want to find x. I can write this as Q times x minus x is equal to 0, right?
It's the same thing.
And I can further write this as Q times x minus identity times x is equal to 0.
And now, I can pull the x out. And now, I can write this as Q times — Q minus I times x is equal to 0, right?
All I did was rearrange these things. What is Q minus I? It's a matrix.
Do we know what x is? No, but now, we have a right-hand side that is a concrete vector. It's not a variable, right?
And this is a special kind of equation actually that we have learned how to solve. What vectors x satisfy this equation?
STUDENT
Null space.
PROFESSOR
The null space of Q minus I.
STUDENT
[INAUDIBLE] [LAUGHTER] PROFESSOR: So any vector that is of this form x is said to belong to the null space of Q minus I.
And it is an eigenvector belonging to the eigenspace corresponding to eigenvalue 1.
Okay. Why is the eigenvalue here 1? It's because Q times x is implicitly equal to 1 times x.
Think about this. We will generalize next class. [LAUGHTER] [SIDE CONVERSATION] STUDENT: Question about the homework.
PROFESSOR
Mm-hmm.
STUDENT
So there is a problem. What is the step-by-step —
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.