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 7.
And today we're going to pick up basically where we left off last time. And what did we cover last time?
The main point of the lecture was essentially talking about matrix inversion.
Let me move this to this camera. It's still visible. Okay, great. So the main thing we talked about was matrix inversion.
And what was the thing about finding an inverse? Was there anything new that we had to do to find an inverse? Not really, right?
We used the same tried and tested method, Gaussian elimination, to be able to find our matrix inverse, A-inverse.
Except what we did was, instead of solving one system of linear equations, we simultaneously solved multiple systems of linear equations, right?
So when we were, for example, finding the inverse of a 3 by 3 matrix, we simultaneously solved three systems of linear equations instead of solving one system of linear equations.
Does everyone remember that? Yeah? And then we saw some examples that said, well, an inverse doesn't always exist, right?
And the last thing we did was we proved a theorem.
And the theorem we proved said that if the columns of A are linearly dependent — can people see at the back?
Yeah?
Then A is not invertible. Right, this was what we proved.
So I'm going to just ask, how many people would like me to go over the proof of this theorem one more time in lecture today?
Okay, that's a fair number.
It is an important thing to understand. So I'm going to quickly talk us through it again.
This was the theorem we started out to prove last time. We said, if the columns of are linearly dependent, then matrix A is not invertible.
And we introduced this idea of another way of saying the same thing.
We said that this is equivalent to proving, if the matrix A is invertible, then the columns of A are linearly independent.
We argued that if we want to show p implies q, that is equivalent to showing not-q implies not-p.
Does everyone remember this, about when it was raining and whether there were clouds?
Which one did we end up actually showing? Did we actually show the second statement or the first statement? The first statement, right?
So sometimes it's really confusing because sometimes we use this idea of a proof by contradiction.
A contradiction proof says we assume there exists a unicorn, and then we show that something else must be contradicted. Therefore, no unicorn exists. That's basically a proof by contradiction.
What this is called is called contrapositive. The contrapositive of a statement is not necessarily related to a proof by contradiction. They have the word, contra, in there.
But just because we can write a contrapositive of a statement, doesn't necessarily mean that we have to do a proof by contradiction. We can sometimes do a proof by contradiction.
We can sometimes not do a proof by contradiction. All of these are valid. These are just two different words that both have the syllable, contra, in them.
So make sure that you don't confuse them. This is confusing. And then we had a proof, right? This is the proof from last time.
I'm not going to write it out again.
But what we did we say? We started and we said, Okay, if the columns of A are linearly dependent, then matrix A is not invertible. So this is what we are trying to prove.
So the first thing we do, which is what we always do, is we write out what we know. What do we know? We know that the columns of A are linearly dependent.
What does that mean? That means that there exists some linear combination of the columns which is equal to 0.
How many definitions for linear dependence did we examine? We introduced two definitions, right? There's not just one. We're using one of the two definitions here.
Could have equivalently written out that one of the columns is a linear combination of the other column. That's another way to write out what is known.
If you're not sure which one to use, write out both.
Try out both. In this particular case, I chose to use this definition. We could have also arrived at a proof using the other definition. I just chose this one.
But when in doubt, you should try both. In proofs, sometimes you don't necessarily know which approach is going to work, or which attack you're going to be able to succeed with.
So the strategy is to basically try everything. You don't have to be sure that what you're writing on the piece of paper is the correct approach.
You try it, if it doesn't work, you erase it, and you try something else. Or you first try it out on scratch paper.
So here we now say, let's use this definition, we write out what is known, and we say that there is a linear combination. And we say, what do we know about the CI?
We say that not all of the CIs are zero. So there is at least one of them that is non-zero. That's our definition. And we want to get to this end point.
What is the end point we want to get to? We want to show that A-inverse doesn't exist. But showing something doesn't exist is pretty hard, right? That's very hard to write out algebraically.
How do you say that? It's easier — algebra statement. The easier thing to write in math is to say, well, let's pretend it does exist.
Because if something does exist, then you can use it in an equation, you can manipulate things with it.
So often when you want to prove that something doesn't exist, a good strategy is to say — this is not a strategy that will necessarily always work, but it's a good one to try — to say, well, let's pretend it did exist hypothetically and see what happens.
If you arrive at a contradiction, that means your assumption must have been wrong. Is that approach clear to everyone?
So we said, we assume this exists. And then we write out, again, our linear dependence definition.
But now in terms of the matrix A instead of explicitly in terms of the columns. I can write this linear combination, just as this matrix vector product, equal to 0.
We're good? What do we know about this vector? We know that this vector is not identically equal to zero because of the definition. Now what can we do?
We're assuming that A-inverse exists. So what that allows us to do is it allows us to multiply both sides of this by this A-inverse.
And now we can say, well, A-inverse times A times C, which is just A-inverse times zero — A-inverse times zero, we know is zero. The A-inverse and the A cancel to give identity.
And so I basically arrive at the conclusion that, well, this C must be identically zero. But by my assumption and by what I was given, I know that C is not identically zero.
So what is this? A contradiction. Does everyone see the logical steps that we took to arrive here? Are there any questions?
Okay, so we will keep giving you more and more practice for proofs. Don't worry if, the first time you see something, it doesn't make sense. That's fine. This is hard.
And we will keep giving you practice that hopefully will make things easier as time goes on.
Okay, so since we now have that, I want to move to the rest of today's topics.
And today we're going to do a little bit more about inversion.
I want to connect this back to what you've been doing in lab.
And we're going to talk about the experiment that you're doing in the lab. And finally we will introduce the idea of null spaces and vector space.
So the first thing I want to do is I want to connect invertibility directly to systems of linear equations. So in the lab, remember, what are you trying to do?
You're trying to basically read the playing card or whatever image you have. Some of you have already done this.
Some of you will be doing this lab basically either later today, or tomorrow, or on Monday.
But the larger setup is that, well, you have some image, and you're trying to basically get that — you're trying to reconstruct that by measuring it in various ways.
So that's basically solving a system of linear equations.
Because you're taking some measurements, just like we did in the tomography example, just like we did when we talked — the very first lecture, we talked about MRIs.
So we talked about how tomography machines work. Here you're saying, I want to take some measurements, I want to use those measurements to reconstruct my image. That's what you're doing, exactly, in lab.
Now we have all these linear algebra tools we don't necessarily have to solve systems of linear equations the way we've been solving them. We can actually use the more sophisticated things for learning.
So I want to prove this theorem.
If A is an invertible double matrix, then the system A x equal to b has a unique solution.
This is the theorem that I want to prove.
How are we going to prove this?
So what does it mean to prove that this has a unique solution?
Unique means two things. It means that first you have to show that there's at least one solution. If there are no solutions, can it have a unique solution?
Second, you have to show if it has another solution.
If your friend comes and says, hey, guess what, you thought it was unique, but here, I found another one, you have to be able to prove that the other solution is exactly the same as what you had.
So in terms of the end of this, what you want to prove is two parts.
One is that there is at least one solution.
And second is that all other solutions are equal to this.
So now that you know this, why don't you take a couple of minutes and try to do this on your own. If you get stuck, just try writing different ideas out.
They don't have to be right, they can be completely weird, no one cares. Try writing stuff up. Feel free to of course talk to your neighbors, chat, whatever.
Yes, question?
STUDENT
[INAUDIBLE].
PROFESSOR
I'm sorry.
STUDENT
Would it [INAUDIBLE] nearly independent?
PROFESSOR
We'll come to that.
Okay, let's try to do it together.
So this proof is going to actually introduce another type of proof strategy a little bit.
And this proves strategy is what I call the guess-and-check strategy, which is you guess what the answer is and then hope it's correct. And if that answer is wrong, then you try another one.
So if you wanted to get a solution of this — well, actually, what should I do first? I should write out what do I know.
What is known to me? I know that Ah inverse exists. That is what is given to me. And I want to use this now to complete my guess-and-check strategy.
Because first I have to show that there is at least one solution.
So I am going to say, consider x0 equal to A-inverse b.
Why am I allowed to write this x0? Because I know A-inverse exists. This is what it's allowing me to even write this statement.
Without knowing this, can I write this? x0 might be completely in my imagination. It might not exist if A-inverse doesn't exist.
So I can say, let us consider this. Now, let's check.
What is A times x0 equal to? This is just A, times A-inverse, times b, which is equal to identity times b, which is equal to b.
So can I say I'm done now? I'm not done yet, right? Yes, question.
STUDENT
What is x0 represent?
PROFESSOR
I made it up. I said let x0 equal to be this. Yeah, good question. I completely made it up.
I could have called it x11 or whatever.
Yeah.
STUDENT
So instead of defining a [INAUDIBLE] solution, why didn't you just start with A x equals b, and multiply by the inverse [INAUDIBLE] PROFESSOR: That would be another possibly valid way to do it.
But I want to introduce different ways of doing this. And we are going to do that step in a little bit. Yeah, there is a question here.
STUDENT
So, so far, what have you proved?
PROFESSOR
What have I proved? Good question.
STUDENT
Is it just that, like, if b equals b, does mean that there is a solution?
PROFESSOR
Have I shown b equals b? I haven't shown b equals b. I have shown A times x0 equals b. So there is some x0 such that A times x0 equal to b.
When we write out the system of equations, we don't know that any such x exists at all.
So here what we're saying is that, OK, we found one solution. So we have done basically only part 1 of the proof.
But we haven't yet proven the entire statement. So what do you need to do now to do it? Yes, back.
STUDENT
[INAUDIBLE]..
PROFESSOR
Speak up, speak up.
STUDENT
How do you come up with your guess [INAUDIBLE] PROFESSOR: How did I come up with my guess at the beginning? That's a great question. I know I want to somehow cancel out this A.
And I want to multiply A by something and get b. The right-hand side doesn't have a b. So I have only one thing with me.
And I want to get rid of A. That's why I put A-inverse next to A. That was the strategy by which I came up with it.
It's basically saying, I want to get rid of A, I have only one tool that gets rid of A, let me try to stick it in there. That's basically all that was done.
Okay, so now we have to show the next part. So we say, well, what if there was another solution? What if someone came and told me that x1 is another solution?
So let x1 be another solution.
Then because x1 is a solution, I'm saying A times x1 is equal to b.
Now what can I do again? What do I want to show?
STUDENT
[INAUDIBLE].
PROFESSOR
I want to show x1 is equal to x0. So now what can I do to — what do you feel like doing? Again, I want to get rid of this A.
We only have one tool to get rid of A. What are we going to do? Multiply by A-inverse. So we then have A-inverse A x1 equal to A-inverse b.
These guys give me identity.
So x1 is equal to A-inverse b, which is equal to x0.
Yes, question?
STUDENT
Do you have to show that there is only one A-inverse?
PROFESSOR
Do we have to show that there is only one A-inverse. That's a great question. It turns out that a matrix inverse is indeed unique.
In this proof, we don't actually need to use that because you can just say, use the exact same A-inverse that you used over there. But we can also show a matrix inverse is unique.
Maybe we'll ask that of the homework question or as a practice homework question. Yes.
STUDENT
Why do you say there [INAUDIBLE PROFESSOR: So the question is why did we divide it into two parts, basically.
Because if you only found one solution, you don't know that it's necessarily unique. Basically, unique, the word means two things.
One, it means that when you want to show a unique solution, it fundamentally means that you have to make sure that there is at least one solution.
But you can just show that if a solution exists, then all other solutions are equal to it. But that first solution might not exist.
So you then have to show that the first solution also exists. That's why there's two parts. This is a good question. It's a subtle point.
And it's important to understand why, even for a simple proof like this, we're going through these steps. So these are all great questions to be asking. Yes.
STUDENT
How does the [INAUDIBLE] for x1 actually show [INAUDIBLE]? Because it seems like it's the same thing described twice?
PROFESSOR
The question is, what is different about these two parts? They seem very, very similar. And they are very similar because this is a very small, simple example.
In a larger, more complicated setting, these might be more complex. But basically what we want to show is that we want to explicitly show these two things.
And because I want to really go step by step through every single thought process, we're showing these two things. So we want to explicitly show both of these.
So they're very related, but they're subtly, subtly different. First one is showing that something exists.
Second one, you could potentially write a proof that just says, let's try this, and show in one step that A-inverse b is a solution and all other solutions must be equal to it.
But because this is the first time we're writing proofs, I want to be super careful.
Does that answer the question? Talk to me after class. Yes.
STUDENT
Are we able to start with x0 equals A-inverse?
PROFESSOR
How did I start with x0 equals A-inverse b? Great question. I made it up entirely. That was the question at the back, why did I choose x0 equals A-inverse b?
It is just basically saying I want to make it equal to b, I just have a little bit of maneuverability, let me try this.
Another good thing that maybe someone would have tried is — like you can try other things. Some things will work, some things might not work.
Yes.
STUDENT
Why dd you choose the guess and check method? guess-and-check [INAUDIBLE]?
PROFESSOR
The question is, why did I choose a guess-and-check strategy instead of a proof by contradiction or something else? This is just years of practice.
[CLASS CHUCKLING] And partly you will get a sense of — because it seems like you want to find one solution.
When you want to find one solution, proved by contradiction isn't really going to work. Because you have to create that one solution out of somewhere.
So a constructive proof is more likely going to yield you the result that you want. By reading the statement, you can get hints on this.
If you want to prove something doesn't exist, then probably a proof by contradiction might be a better strategy.
So do you see that there are subtle hints in the statement that tell you which one? Last question.
STUDENT
How come this proof doesn't only prove it for the case where x0 equals A negative 1 times b? How come it's [INAUDIBLE]?
PROFESSOR
Because the statement is saying — the question is, why is this proof correct, basically. And the proof is correct because we're seeing that we have one solution. We've proved one solution.
And all other solutions are equal to this.
STUDENT
But shouldn't it only for the case where the solution will be equal to the [INAUDIBLE] times the [INAUDIBLE]?
PROFESSOR
Well, we're not saying that A-inverse equal to b — we're not saying what that solution is, we're just saying it has a unique solution.
So the theorem statement doesn't say, prove it for this solution or that solution. It says it has one unique solution.
So we provide what that solution is, and then show that there can be no other. Okay, I have to move on.
Come to office hours if you still have questions.
So now that we have these theorems, we now know two things, that if A is invertible, this implies, we just said, that A x equal to b has a unique solution.
We also proved last time, in the last lecture, in the proof we just did at the beginning, proved that A has linearly-independent columns.
So we proved both of these statements. And notice what we have proved is we have proved one-way implications.
We have not proved that if A x equal to b has a unique solution, then it is invertible. Have we proved this?
Have we proved that if A has linearly-independent columns then A is invertible? We have not proved this. We have proved one direction of this.
To see the other direction to the proof, it requires one slightly more complicated step. And as a result, you will see a full proof of these statements when you get to 16b.
Because this is an introduction to proofs, the extra step is something that we decided is — we don't want to give you all of every kind of proof all in one class your very first semester at Cal.
So we're going to prove the second part later when you get to 16b. But you can know that this implication actually holds both ways in the case where A is a square matrix.
Okay, we're also going to now show that this invertibility and linear dependence and independence are connected to what we call null spaces.
And we will see that this is also saying that A has a trivial null space. And we will define what this means and understand exactly what this means.
So you don't understand what the statement means yet because we haven't told you. But we will define exactly what this means going forward.
And in the future, when you take 16b, you'll figure out exactly all of the connections of all of these. So why do we want to understand null spaces?
Well one of the motivations is really coming from lab. And for those of you who have done lab, you might have seen that — how many people have already done Imaging 2?
How many people have not done Imaging 2? Right, so you're about half-half.
So what you will see if you've done it today, or if you're going to do it in the next couple of days, is that you're able to actually recover the picture that you're trying to create.
So let me see if I can get this going.
What you will see in the lab is this set of slides. And you will actually — this is the setup that you're going to be using in lab.
Some of you have seen this, some of you are going to be seeing it. Let me make this bigger.
So what you're trying to do is you're trying to reconstruct this particular image. And when you reconstruct it, you get something like this.
This is a sample image that has been constructed using a lab. And what you see is that this is quite clear.
For example, this is the picture taken by an actual multi-pixel camera as opposed to the single-pixel camera that you're making. And this is the image from the single-pixel camera.
And this is kind of blurry, right? It's not exactly perfect. And how are you actually reconstructing that image?
The basic idea is that, well, you're going to take all of the pixels of the unknown image, and you're going to stack them into this vector. You make, basically, pixels for every image.
And say these are the unknowns. And then you do experiments. You take measurements by projecting different masks onto the image. And you construct this masking matrix, H.
You have this unknown vector. And then you have these recorded measurements, s.
You have the equation basically s is equal to H times i. And then you want to figure out, well, what was i? i is your image.
And now we've learned, basically, conditions on H under which you can solve this. What do we need to have for H for this to be solvable? It has to be invertible, right?
We also know that basically this is connected now to the linear dependence/independence of the columns of H. So you know that some H's are good and other H's are bad.
So you know that if you're designing your imaging system or your tomography system, you can check H beforehand to see if it's good or not.
But it still turns out that some of the images that you construct are blurry. And where is the blurriness coming from?
If I give you a system of equations and I tell you that it has a unique solution, why is the image blurry?
The blurriness is coming because there's some errors that are somehow happening in the computation of the reconstructed image.
And your team might have asked you — I'm not going to go through any of the details — or will ask you, well, are some H's better than others?
Are some masks, are some tomography machines better than others? Are some systems of equations better than others?
And how do you construct a system of equations that is the best, or pretty good? How do you make sure that the image that you reconstruct is as clear as it possibly can be?
And so in the two labs that you're going to do, imaging 2 and imaging 3, you're going to use systematically better strategies, better masking, and construct better H's to get better images back.
And to be able to understand basically how to construct these good H's or these better H's, we now know that you know H being invertible is something that we want.
But it turns out that even among the invertible H's, there are some that we prefer and some that we don't prefer. And the next few lectures are going to think about investigating this.
And this will end and culminate, basically, with imaging 3, where we will give you and you will discover why a certain H is better than the other H's.
So I just wanted to make this connection for you. You're all going to see it in lab. Some of you have already seen it. Some of you will be seeing it.
But keep this lecture and these things that we're talking about in mind when you're thinking about your labs. Okay, can we go back to the document camera, please.
Thank you.
So to be able to answer that question, which I'm not going to be able to fully answer today, but I'm going to build up to answer it over the course of today's lecture and the next two lectures, I want to focus on this equation, A x equal to 0.
This is very much like A x equal to b. In fact, it's a subset of all of the problems represented by A x equal to b.
This is just choosing a special case where b is equal to 0. I want to study this special case. And the question is, well, how many solution does this have?
What if a is equal to, let's say, 1, 0; 0, minus 1. How many solutions does this have?
One. Does it how exactly one? Does it have a unique solution?
STUDENT
[INAUDIBLE].
PROFESSOR
Yes, right? This is an invertible matrix. We just proved that if A is invertible, then A x equal to b has a unique solution. So in this case, it has a unique solution.
Great. What if A is equal to 1, 2; 0, 0?
How many solutions does this equation have?
Infinitely many.
So what is one solution?
For example, I can write, 1, 2; 0, 0 times, let's say, minus 2, 1 is equal to this row times this column is 0.
And the row 0 gives me just a 0.
So the matrix A is not equal to 0, this is vector is not equal to 0, yet my right-hand side is a zero. This is different from how scalars behave.
Usually, if two things multiply and give you a zero in the scalar land, one of them is zero. Here, neither of them is a zero.
And if I tell you now that here is — if A x is equal to 0 has a solution, x0, which is not equal to 0, then alpha
x0 is also a solution for any alpha that's a real number.
So basically what I'm saying is that once you know that this is a solution, can I multiply this vector by 2?
5, 13, whatever — any scalar multiple of this vector is still always a solution. So how could you write this using the notation that we now know?
We know that, therefore, span of minus 2, 1 is a solution.
All of the scalar multiples of this are a solution and if I was to draw a picture of this, I basically have — so minus 2 and then 1 is basically this vector.
And this entire line is a solution.
So given this, this basically suggests that there is not one — this is something that basically doesn't just happen in special cases.
It happens a lot. So what if now, for example, A was equal to 1, 0; 2, 0; and let's say 3, 0.
And I consider the equation A x equal to 0. How many solutions does this have? First, what does the dimension of x need to be for this to be a valid multiplication?
STUDENT
[INAUDIBLE].
PROFESSOR
3 by 1. It needs to be a 3 by 1 vector. And how many solutions does this have? Also infinitely many.
This is not just a two-dimensional thing. It's not something that's restricted to square matrices. This is something that you will see happening for many different kinds of matrices.
So this basically leads to this definition of a null space of a matrix.
The set of all solutions to the equation A x equal to 0 is called the null space of A. This
is one type of vector space. And we'll talk more about what vector spaces are in a bit. But we haven't talked about them yet.
Yes.
STUDENT
So you said the first one's at 1, 0; 0, negative 1, and then you flipped them. Is that because it's just 0, 0?
PROFESSOR
Yeah. The only solution here is x0 equal to 0, 0.
STUDENT
So that's scaling the 0, 0.
PROFESSOR
So if you scale it by whatever, it's still 0, 0. So for the scaling trick to work and give you a different solution, the original solution has to be non-zero.
Good question.
Okay, so we have a definition. The question is, why do we care about this and what do we want to do with this?
So one reason to basically try to understand null spaces is you've seen, in your Gaussian elimination examples, that sometimes you end up with a bunch of free parameters.
You have infinitely many solutions, and then you need to figure out how to write these. How do you say which vectors are actually solutions?
And so null spaces can help characterize solutions to the system of linear equations.
In particular, say x0 is a solution to A x equal to 0 — not A x equal to b, A x equal to 0.
This is sometimes called a homogeneous equation.
When I set something equal to 0.
And let's say x1 is a solution to A x equal to b. This is sometimes called a particular equation.
Because A x is being set to something particular, that is not zero.
Then what can I say about the vector v, which is x1 plus some alpha times x0?
It's also a solution to A x equal to b.
So basically if A has a non-trivial null space — a non-trivial null space means that the null space isn't just one vector, which is the 0 vector — if the null space has many solutions or has many vectors in it, then A x equal to b also
has infinitely many vectors in it. Do you see this connection that we're talking about?
So this alpha is basically a parameter.
Remember there was a homework problem where you had to show that some vector plus t times some other vector is a solution to a system of equations? This is exactly like that.
Where x0 is basically a vector in the null space of A. And x1 is your particular solution.
So this is one reason to try and understand, basically, null spaces, because they help us characterize these families of equations.
But I wanted to give you also another example for how null spaces can help us solve interesting things.
Yeah, question?
STUDENT
Where did you get the equation for your V vector again?
PROFESSOR
Oh, again, I said, let me think of V vector which is x1 plus some scalar times x0.
I'm saying, let us consider this vector. When I consider this vector, I say, now A times V is equal to A times x1 plus alpha times x0.
I know A times x1 is equal to b, because I know x1 is a solution here.
A times alpha times x0 equal to alpha times A times x0. But what is a times x0? 0, which gives me b.
So any vector here, for any real number — any real number.
Does that clarify it? Yep.
STUDENT
Can we scale x1, or does it not scale?
PROFESSOR
Can we scale x1? Let's try it. What if I put some beta times x1 here? What would I get here?
Would A times x1 give me b? I would get beta times b. So it wouldn't give me the solution that I wanted. So you can only scale the vectors in the null space.
You cannot scale the particular solutions. Good question.
So at one of these roundtables, one of the students was telling me that, actually, they were really interested in understanding traffic flows and understanding how the tools that we're learning here can be used to help model these kinds of different types of flows.
So I thought today we would do another example on modeling traffic flows.
STUDENT
[INAUDIBLE].
PROFESSOR
Oh, thank you.
And we're going to see how null spaces can potentially be useful.
And you can use the same kind of ideas to model flows of charge, for example, or flows of many other things. Some of these we will see later on in this course.
Some of these you will see when you go on to take other courses. So here, the setup is the following. Let's say I have three cities.
Let's say I have Berkeley, I have San Francisco, and I have Oakland.
And I have traffic flowing between these cities. So let's say there's only certain roads connected.
So you can go from Berkeley to San Francisco, and let's say there is x1 cars on this path. You can go from San Francisco to Oakland. There's x2 cars on this path.
And you can go from Oakland to Berkeley, and there is x3 cars on this path.
And we want to be able to understand how many cars are there on these roads. What is the traffic flow?
Of course, the true road network is much more complex, and you can build up these ideas. But we're going to start with a very, very simple example.
And we're going to assume no cars stop in cities — or they don't build up.
There's no accumulation of cars. You can't just drive from Berkeley to San Francisco and stop there. You drive from Berkeley to San Francisco, then you have to keep moving.
This is our assumption, right? No accumulation.
So we want to figure out basically what x1, x2, x3 are.
How many measurements do we need to make? How many measurements?
So when you're driving on the freeway, you might have noticed sometimes there's these big metal rings that are embedded in the street surface.
These are actually sensors that are often measuring the traffic that is flowing across those roads.
If you're interested in this kind of research, professor Alex Bayen as well as Professor Pravin Varaiya have a big transportation center here at Berkeley, where they actually study traffic, congestion, strategies for reducing congestion, the impact of apps like Lyft and Uber,
the potential impact of self-driving cars.
All of these are things are studied and modeled to be able to first make predictions on what will happen, second to try and introduce certain designs, to reduce the flow, to reduce congestion, so on and so forth.
We're of course not going to get into anything at that level in this class. But in case you're interested, definitely go check out their websites. And you can see there's more information on this.
But we want to figure out now, if we want to measure these flows, which sensors do we need to put and where. These sensors are quite expensive to put.
So we now know that no cars are stopping in any of the cities, and they're not accumulating. So we can use this to write out equations.
So let's say I write my first equation for San Francisco. I know that there's x1 cars coming in and x2 cars going out.
And if I know no cars are stopping in San Francisco, then what do I know? I basically know that x1 minus x2 had better be equal to 0.
So that's my first equation.
What can I say for Oakland?
Anyone?
STUDENT
[INAUDIBLE].
PROFESSOR
X2 minus x3 is equal to 0. And for Berkeley, I can say x3 minus x1 is equal to 0.
And now since we're in 16a, we're going to write this is a matrix.
And I can say 1, minus 1, 0; 0, 1, minus 1; minus 1, 0, 1; x1, x2, x3 is equal to 0, 0, 0.
So how do we solve this? This now — notice, what type of equation is this? It's this null space type of equation. It's a homogeneous equation.
It's something equal to 0. But it's still a system of linear equations. We can still solve it the same way that we solve any other system of linear equations.
We just know now that the solutions are going to be related to the null space of A. So let's solve it.
Why don't you just take a minute to solve this system of linear equations.
I'll solve it too.
So everyone's done solving this? So what do you see when you do Gaussian elimination? Does everyone get the same setup?
So here you see, basically, the first column, you have a leading 1.
A leading 1 is basically when you look from the right, and you hit — or you look from the left, sorry, but you go right, and you see a 1 after 0's.
So this is a leading 1, this is a leading 1. So the first column has the leading 1, the second column has a leading 1, the third column does not have a leading 1.
So now what do we know? This is basically a row of zeros. Is there any constraint on the third variable here? No, right?
So what is the free parameter that we have?
STUDENT
X3. PROFESSOR: x3. But once I pick x3, once I know what x3 is, is x2 unknown to me? No.
Is x1 unknown to me? Why?
Because I know here, this tells me that x2 minus x3 equal to 0, so basically x2 equal to x3.
And this here — oh, I should have done one more step here. Yeah, OK, thank you. No one stopped me.
What is the step I should have done?
STUDENT
[INAUDIBLE].
PROFESSOR
I should have basically removed this minus 1. I should have made this completely as close to an identity as I could have.
So I would get 1, 0, minus 1; 0, 1, minus 1; 0, 0, 0. I should have done r1 plus r2 after this 0, 0, 0. Good.
Ad here, these folks are the leading 1's.
This is basically what you would call row reduced — row echelon form, this is the reduced form. It doesn't matter what these names are. Don't worry about it.
But the same thing is still true, which is that there is no leading 1 in this column. And so x3 is your free variable.
And once x3 is fixed, this tells you that x2 is equal to x3. And the first row tells you that x1 is also equal to x3. Is everyone with me?
Yes, question.
STUDENT
Why is it more preferable to have [INAUDIBLE] PROFESSOR: The question is, why is it more preferable to have this step over the step? Because here, in the second column, I have a leading 1.
This is called a pivot or a leading 1.
And if you have a leading 1, you want to try and have zeros in the entire column so that you can get everything in terms of your potentially free variable.
So you assign free variables from the bottom up. It's not that this is wrong or that you couldn't get your answer by doing this. It's just more systematic this way.
But this is not wrong.
So here now what we can say is, therefore, if we have a vector, V, so this says basically that if I choose x3 — let's choose x3 is equal to some t.
I have x3 equal to some t. This implies x1 is equal to t, and x2 is equal to t. So what does my solution vector look like?
t, t, t.
All vectors x equal to t, t, t are solutions.
Yes.
STUDENT
So when we're [INAUDIBLE],, why can't we just say [INAUDIBLE] t?
Why can't you say that the x vector [INAUDIBLE] PROFESSOR: The question is, why can't you say the x vector is equal to x3, x3? Why do you have to write t?
There's no reason. You could write x3, x3 just to avoid confusion.
Now I can also write this as, therefore, the span of the following vector, 1, 1, 1, is a solution — or are solutions.
And in fact the null space of this matrix A — if you call this matrix A, this null space is equal to the span.
So basically what is this saying?
This is saying something that we kind of knew by looking at this, which is that do I need to measure x1, x2, x3 if I know that they have this low relationship between them?
I can just measure x3. And I can therefore infer what x2 and x1 are.
So basically this is saying that, in a sense, the dimension of the null space is telling me how many measurements I need to make.
I haven't yet told you what a dimension of a vector space is, but we are going to get to that.
Basically because there is only one free parameter here, you need to do one measurement.
One variable is what is uncertain or unknown. If you fix that, everything else will get fixed.
And this intuition is what is going to help us understand the dimension of a null space, and then also move on to understanding vector spaces more generally.
But before we get to that, I wanted to think about a different example.
So what if now I have my Berkeley and I have Oakland, and let's say I have x1 flow from Berkeley to Oakland, and now I have some flow back, x2.
But here let's say I have New York and I have Boston.
And here I have, let's say, x3, and I have x4.
By looking at this graph, if I want to figure out x1, x2, x3, x4, how many measurements do I have to take? Two.
Does it work to just put sensors on the west coast to measure the east coast traffic? Not going to work. There is no interconnections here.
So now if you were to write out this full system as a set of linear equations, how would you do it?
You would get basically an equation for Berkeley. So you would have minus x1 plus x2 equal to 0. You would have an equation for Oakland.
So you would have x1 minus x2 equal to 0. You would have an equation for New York — minus x3 plus x4 equal to 0.
And you would have an equation for Boston, which would be x3 minus x4 equal to 0.
You could then write this out as a matrix.
So you would have minus 1, 1, 0, 0; 1, minus 1, 0, 0; 0, 0, minus 1, / 0, 0, 1, minus 1; 0, 0, 0, 0.
How many free parameters does this system of equations have? When you row-reduce this, do Gaussian elimination, what are you going to get?
STUDENT
[INAUDIBLE].
PROFESSOR
You're going to get two rows of zeros, right? I'm not going to do it out.
But trust that, after row reduction — and go home and check — that you will get something like this, 1, minus 1, 0, 0; 0, 0, 1, minus 1; 0, 0, 0, 0; 0, 0, 0, 0; 0, 0, 0, 0.
So how many free variables are there now? Two.
So now if I was to ask you, without telling you really fully what the dimension is, what would be the dimension of the null space of this matrix here?
STUDENT
[INAUDIBLE].
PROFESSOR
Two. So we have this strong intuition. Let us use the last part of class to actually formalize this.
And this is where I want to introduce the idea of a vector space.
And I'm not going to actually write out all of these — I wouldn't want to write out all of these properties again.
So we've already put this all in the notes for you. This is note 7. It is on the website.
It looks like it's a lot, but it's actually not that complicated. So let's walk through it step by step. What is a vector space?
A vector space is basically a set of vectors along with some scalars. V comma f, V is a set of vectors, f is a set of scalars, and these two operators.
Usually, when we're talking about a vector space, we will be talking about — we will usually just be referring often to the V, which is this vector space.
So for example, we will say things like, R2 is a vector space. But we're implicitly meaning that there is an associated set of these scalars that is going with it.
So this set of vectors is called vector space if, first, you have an associative property. Is this big enough to read?
STUDENT
[INAUDIBLE].
PROFESSOR
Now?
STUDENT
[INAUDIBLE].
PROFESSOR
Okay. So you want the vectors to be associative. We know what associative means. It means that the order of addition doesn't matter.
So for vectors, we know this is true. It doesn't matter if you do u plus v plus w, or you do v plus w first, or you do u plus v first.
That's called associativity. For vectors in Rn, we know that this holds. Commutative — if you have u plus v equal to v plus u.
Additive identity — it means that basically 0 has to be an element of your set of vectors.
The 0 vector must always be present if you want to call your set of vectors a vector space. And with 0, you also have to have an additive inverse.
So with every v, you also have to get a minus v. So if you think about these null spaces, you'll see that they're always going to have this 0 vector in it.
If you think of A x equal to 0, the 0 vector is always a solution to this. Even if there's infinitely many solutions, the 0 vector is always one of them.
So that's why, for example, null spaces are vector spaces. And finally there is this thing called closure under vector addition.
All that means is that if you take one vector and you add it to another vector, you can't go outside the set. You got to stay in the same set.
And then there's some properties on scaling. So for example, you have to make sure that scalar multiplication is associative.
So it doesn't matter if you do alpha beta times v or alpha times beta times v — holds for most of our cases.
You have to have a multiplicative scalar identity, not a vector inverse.
So you don't have to have — this is important to note — you have to have a scalar such that 1 times v is equal to v. This doesn't have to hold for a vector.
Then you have to have these distributive properties. Some of these you explored to some extent in your discussion in the context of matrix vector multiplication.
So you have to have, basically, alpha times u plus v is alpha times u plus alpha times v. You also have to have alpha plus beta times v is equal to alpha v plus beta v.
And finally, you want what is called closure under scalar multiplication, which is, for any vector v and scalar alpha, alpha v must also be in the set.
Often the most kind of interesting of these ends up being the last two, the closure under vector addition and closure under scalar multiplication.
And then checking that these identities are actually valid members of your set.
So if you remember, when we were talking about linear transformations, we also had two very similar properties.
We had, for a function to be a linear transformation, f of x plus y must be f of x plus f of y. So these are very related in that perspective.
And now when you have a vector space — let me zoom in — what's an example?
An example that you all know is R2 comma R.
This is a vector space.
What is a basis for this vector space?
A basis for a vector space is a set of vectors V1, V2, all the way up to Vn such that V1, V2, Vn are linearly independent, and two,
all v belonging to our vector space, V, are in the span of this set.
So let us say we have some vector space, Vf, like we have over here.
We're going to say that there is a basis for this vector space if we can find such a set.
So if we're considering R2 and R as our vector space, what is this set?
1, 0; 0, 1.
Is this a basis for r2?
How do we check this? First, there is two vectors in here, V1 and V2. Are they linearly independent? Yes.
Second, can I express any vector in R2 as a linear combination of these? Is any vector in the span of these?
It is, right? We did a proof a couple of lectures ago that showed something very similar. So great, this is a basis.
What about the set 1, 2 and 4, 5?
Is this a basis for R2?
STUDENT
[INAUDIBLE].
PROFESSOR
Are they linearly independent? Yes. Can you express any vector as a linear combination of these? Yes, you just solve the system of equations.
What if now I consider 0, 1; 1, 0; and 1, 2? Is this a basis?
No, not a basis. Why is it not a basis? Because 1, 2 can be written as a linear combination of these folks.
So this is not a basis. So a basis is basically a minimum spanning set. It's the smallest set of vectors that spans the entire vector space.
And the number of elements of your basis is what is called the dimension. So this is your minimum spanning set.
And the dimension of the vector space is basically the number of elements of the basis.
So when you think about null spaces, they're vector spaces.
When we say there is a certain dimension to the null space, we're saying basically that this null space is of dimension 1 because we can write a basis for this null space with exactly one vector.
So 1, 1, 1 is a basis for this null space. In this case, worth it to go home and try and write out a basis for this null space.
You will find that basis has two elements. We'll pick up her next time.
Đă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.