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ả.
[VIDEO PLAYBACK] - In a previous — [END PLAYBACK]
PROFESSOR
Okay, let's get started. I wanted to actually start today's lecture with showing off this video that I think is really cool from a lab at ETH.
And since you've all been doing the segue problem on the homework, the segue problem talks about one of the really basic principles behind control.
And it talks about it in the context of an inverted pendulum, which is basically saying, well, if I have — can I stabilize basically something that I'm trying to have standing up by moving the base, right?
And if you play this game with your pen, you'll see that it's possible, but can be quite challenging.
But turns out that using ideas from basic linear algebra and control, like you're exploring in the segue problem, and using the concept of eigenvalues and eigenvectors, which we're going to talk about today, we can build up some of the fundamental principles behind control.
And we're not going to be able to do all of the things that are done in this video in this class.
But if these are the kinds of things you're interested in, the fundamental principles that we're building up in 16A will help you get there. So let me just play this.
[VIDEO PLAYBACK] So this a quadcopter that is actually balancing an inverted pendulum.
It's pretty impressive. Like, you saw how hard it was for me to do it with my finger, but this is doing it automatically, and it can fly.
Not only this, what it can also do is the following.
- In previous ETH theory flying machinery in a video, we demonstrated how a quadcopter can balance an inverted pendulum.
Now, we will show how two quadcopters work together to throw and catch the inverted pendulum between them.
[STUDENTS GASPING] A 6 centimeter radius plate mounted on top of each quadcopter serves as a supporting base for throwing and catching the pole.
Shock absorbers attached to both ends of the pole dampen the impact when it hits the cage in place. As soon as physical contact is made, the quadcopter begins to balance the pole.
The throwing maneuver begins with the quadcopter hovering at the constant position.
By modeling the dynamics of the quadcopter pole system, we have identified a state in which the contact force between the pole and the quadcopter is zero, meaning that the pole will be launched off the quadcopter when optimal open loop trajectory is generated to maneuver to quadcopter to produce long state, and track using feedback control.
The catching quadcopter starts above the expected impact points and begins to fly down, and the other quadcopter throws the pole.
As soon as the pole is in the air, the system predicts the impact position.
In order to catch and balance the pole with minimum control effort to catch an instant is chosen such that the pole will rotate into the upright equilibrium position by itself.
The catching trajectory is recomputed 50 times per second to end at the predicted impact position.
Because the catch [INAUDIBLE] was only about 0.65 seconds to correct its position and catch the pole, we apply learning algorithms to the system in order to improve its performance over time.
[QUADCOPTERS BUZZING] [END PLAYBACK] [APPLAUSE] PROFESSOR: Yeah, it's very cool.
Anyway, so we're not going to, unfortunately, be able to get to doing all of this in this class, but we're going to talk today about eigenvalues and eigenvectors.
And these are some of the basic principles that are used in stabilization and control. Could I switch to the document cameras, please?
So we introduced this idea very, very briefly last lecture about eigenvalues and eigenvectors. And I know that last lecture introduced a lot of new terminology and jargon.
And I wanted to just say that we will build this up very, very carefully and slowly in today's lecture.
Today's lecture and tomorrow's — and the next lecture are basically the culminating lectures of module 1. Right?
So we are dealing now with some of the most advanced concepts in the first module of this class.
It's going to be slightly more — it's going to be slightly different, because we're starting to get into more involved material. So I'm going to ask you really to give it your best.
Pay as much attention as you can. Don't allow yourself to be distracted by your phones and your computers, and ask questions if things are unclear. And we'll build this up slowly together.
A lot of the ideas that we will talk about in today's class and the next class will be built up in the 16B to help you understand the connections between eigenvalues, and eigenvectors, and ideas and control that lead to the kinds of demos that you see here.
Okay, so let's get started. So last time — oh, right.
I forgot one quick thing, which is that I should remind you that we have a midterm coming up.
[LAUGHTER] It's going to be next week, and we will have a review session, which will be exactly a week from today.
So there will be an optional review session in the evening, which your GSIs and UGSIs will be hosting.
No new material will be covered, but if you want to like sit through and see all of module one in one go, it would be a good idea to attend that.
So last time — now moving on — we talked about determinants.
Right?
We introduced this idea, and we also introduced very, very briefly, and I will introduce them again, this idea of an eigenvalue and eigenspace, and an eigenvector.
And we talked furthermore about the PageRank algorithm, right? I looked up this morning and I just checked that Google is currently valued at $739 billion.
Billion — how do I spell billion? B-I-L-L-I-O-N, yeah.
And really, this company was founded based on the PageRank algorithm, which we will be talking about today.
So the fundamentals behind — like, I'm trying to understand the mathematics and developing the model for the internet. For example, the pumps analogy that we'd talked about last time.
That's not exactly how the internet behaves, right? Clearly, people don't exactly follow a model like that.
But being able to take something super complex and simplifying it down, and understanding that problem, and then being able to build it back up is basically what allowed for some of the fundamental advances in the search algorithms.
And that's exactly the same kind of thing we do when we're doing, for example, proofs for larger problems, right? We say, let's do a simple example.
Let's understand the simple example first, and let's build from there. So this is the same principle that we're applying in 16A, also, you know, has a big relevance in the real world.
So let's pick up where we left off last time. So just as a reminder, we talked about the determinant of a 2 by 2 matrix, right?
a, b, c, d — and we said — and we showed that, actually, this is equal to ab minus bc, right?
We showed that this is exactly the value of the determinant, and we connected the determinant to linear dependence and independence of the columns, as well as invertability, right?
So just as a quick reminder, think about what happens when ad minus bc is equal to 0.
In this case, this implies that ad is equal to b times c, right? I just changed the order.
And now, I can rewrite this as a over c is equal to b over d, right?
I did nothing here but just simple algebra. What if I set this value to be equal to alpha?
This implies that c is equal to alpha times a, and d is equal to alpha times b. What does this make my matrix?
I can rewrite my matrix as a, alpha a; b, alpha b, right?
When you write the matrix out in this way, what do you immediately see about the columns? They're linearly dependent, right?
So this is another way of reminding yourself of why the determinant is connected to linear dependence and independence, right?
You can see immediately in the two by two case that, when your determinant is zero, you can connect it to linear dependence and independence. This is true more generally.
We've only proved it in the two by two case, and you don't need to know how to prove it in, you know, the 3 by 3 case or the end by end case.
Following classes will deal with that. But the intuition from the two by two case, I hope, will carry you when you're dealing with matrices of larger dimensions.
Okay.
So we talked last time about the tale of two websites, right? Yes, question?
STUDENT
[INAUDIBLE] PROFESSOR: Can't really make it any bigger. Does this help?
STUDENT
Are we able to turn the lights down low?
PROFESSOR
STUDENT: Can we turn the lights off? I don't have control, but they might.
PROFESSOR
Does this help? Thank you. Yeah? Yes?
STUDENT
[INAUDIBLE] PROFESSOR: What? Sorry. First question is about visibility. Can everyone see?
Can everyone read? Thumbs up if you can read. Okay, everyone can read, great. Questions about material?
STUDENT
[INAUDIBLE] PROFESSOR: How did I get to c equals alpha a? I have a over c equal to alpha. So I have a equal to alpha c. Oh, did I?
Oh, sorry.
a is equal to alpha c, and b is equal to alpha d.
So I have — alpha cc and alpha dd.
Thank you. But you got the point I was trying to make. Everyone clear on this? Any questions?
Okay, moving on, to the tale of two websites that we talked about last time.
So we had two websites, the Stanford website and the Berkeley website, and we had this flow of people between them, right?
And let's say we started at x of 1 is equal to 1,0. Right?
So all the people are at the Stanford website; no one's at the Berkeley website. What did we see that would happen as time went on?
What did we say, that x of t would be?
Let's actually call this x of 0, just to be consistent with the notation we had last time.
We said that every single time, what would happen to the number of people on the Stanford website? It would be halved, right?
So in t time steps here, you would have one half to the t.
And here you would have all of the remainder, because no one ever leaves the Berkeley website, but here, people — there's constant attrition.
Are there any questions on how we arrived at this x of t? Is everyone with me here? Yeah? Okay, great.
And we wrote out basically what was the transition matrix for this, right? x of t plus 1 is equal to Q times x of t, where Q is equal to 1/2, 0, 1/2, 1.
Right? Everyone with me up til here? And what did we observe that as t went to infinity? What did x of t tend to in this limit?
0, 1, right? Where, even though you started with everyone at the Stanford website, everyone ended up exactly at the Berkeley website, right?
By slow, constant attrition. And we said, well, here's this. If we started out in this state, you're going to end up at 0, 1.
But what if they started — what if we started at x of 0 equal to 0, 1?
Would the reverse happen if we started at 0, 1? Maybe everyone would then end up on the other website. Does that happen? No, it doesn't happen, right?
If we start at 0, 1, what is Q times 0, 1? Q times 0, 1 equal to 1/2 0, 1/2, 1, times 0, 1, what is this matrix multiplication?
This gives me a 0 here. And this gives me exactly a 1 here, right?
So x-steady is equal to 0, 1 is a vector, such that Q times x-steady is equal to exactly x-steady it
doesn't change even when the transition matrix is applied to it.
This is what we call a steady state vector. So if you start out in a steady state vector, basically you never leave.
And so we see that this is one example of a steady state vector, right? For this transition matrix.
But the question we want to ask is, how, in general, would we be able to find all of the steady state vectors? Do we know if there is many?
Do we know if there is just one? How do we figure this out, right? That's the question that we want to try and answer.
Everyone clear on the question here? Yeah? Okay.
So, what is the general problem that we're trying to solve?
For some matrix Q, can I find which vectors solve this equation? Which vectors satisfy such an equation, right? This is basically the equation of a general steady state vector.
And we said, well, this is a — you know, it's like — it looks like a system of linear equations, but it's not exactly in the format that we liked, right?
Why is this not in the format that we like? Because there's x on both sides of the equation, and x is unknown, right? We don't like it when there's unknowns on both sides.
We like a times x equal to b. b is known, a is known, and x is the unknown. So how do we reformulate this to make it into the format that we like?
Subtract x, right? So I can write this as Qx minus x equal to 0.
Furthermore, I can rewrite this as Q minus the identity matrix times x is equal to 0, right?
Because x is just the same as the identity matrix minus x. And now, what are the x's that satisfy this?
All x in the null space of Q minus I satisfy this.
So this is basically solving a system of linear equations. It's solving. It's computing the null space of a matrix, which is something that, at this point, we know how to do.
Right? So let's just write out going back to our example, what is Q minus I?
1/2, 0, 1/2, 1, minus 1, 0, 0, 1, is equal to minus 1/2, 0, 1/2, 0, right?
And then what we did last time was we computed the null space of this matrix, right? How many people want me to do out the Gaussian elimination for this null space one more time?
If people want me to do it, I'm happy to do it again. Okay, so we now — is everyone with me on why we want to compute the null space of this matrix?
Are there any questions about why we care about this matrix?
Okay, good. So now to compute the null space, we're going to say minus 1/2, 0, 1/2, 0.
This is equal to 0, 0.
This basically goes to 1, 0, 0, 0, 1/2, 0, which goes to 1, 0, 0. And then I have 0, 0, 0.
Right? Everyone followed the Gaussian elimination? What is the free parameter here?
This is free, right?
Okay. So I set x2 equal to some parameter, t. What is x1 equal to? What does this row imply?
This means 1 times x1, plus 0 equal to 0, so what is x1? x1 is equal to 0, so x1 is not free. So x equal to 0 comma t is a solution.
How do I write this as a span or an entire vector space, as opposed to just writing it as, you know, zero t, where t is a parameter?
STUDENT
[INAUDIBLE] PROFESSOR: I can write it as a span, right? So therefore, null space of Q minus I is equal to span of 0, t.
Yes? Question?
STUDENT
[INAUDIBLE] PROFESSOR: Oh, sorry. You're exactly right. We can write it as the span of 0, t, we can write it as a span of 0, 1.
No matter what real number, we put there, it would still be fine. What is the span of 0, 1 versus the span of 0, 2? They're exactly the same, right?
But the simplest way to write it, as is correctly pointed out, is 0, 1.
STUDENT
[INAUDIBLE] PROFESSOR: t should not be equal to 0; you're correct.
Other questions?
So this span, which is the null space of Q minus I, we also call — we call this the eigenspace of the matrix Q,
corresponding to eigenvalue 1.
So, what does eigenspace and eigenvalue mean? We will define this in just a minute.
But fundamentally, eigenspace, eigenvalue, these are basically saying, what are the fundamental directions and what are the fundamental values that are part of this matrix?
That's basically what eigenspace and eigenvalue mean. So more generally, here we said, we're looking at Qx equal to x.
This is a way of saying that x is an invariant direction under the transformation Q, right?
x is an invariant direction. What does invariant mean? Invariant is the thing that isn't varying. It's not changing, right?
When Q is applied to it, you get back the same direction. But is x and 2x and 3x — are these the same direction, or are they different directions?
They're the same direction, right?
So more generally, we can consider the following.
For a matrix, Q, and we want this to be square.
If Q times x is equal to lambda times x, lambda is some real number. Lambda is just a Greek letter.
This is called lambda.
If Q times x equal to lambda times x, then we call lambda an eigenvalue value of Q, and x is an eigenvector of Q, corresponding to the eigenvalue
Q. More generally, you would write x belongs to the eigenspace corresponding to the eigenvalue lambda.
Yes, question?
STUDENT
[INAUDIBLE] PROFESSOR: Yes, correct.
STUDENT
[INAUDIBLE] PROFESSOR: OK.
Just to repeat the question that I received at the front, let's look at this definition, right? So lambda can be any real value.
In this case, in this equation here, what is the value of lambda? 1, right? So here, we're finding the eigenvector corresponding to the eigenvalue 1, or the eigenspace.
When we talk about the span of this vector, we call that the eigenspace. All of the vectors in this span, they're all eigenvectors. There's not just one eigenvector; there's many, many of them.
What's another value of lambda that we've interacted with before or seen before? Lambda equal to 0, right?
If lambda equal to 0, that means Q times x is just 0, right?
If Q times x is equal to 0, x belongs to the null space of Q, but also, x belongs to the eigenspace corresponding to the eigenvalue of 0.
Is that clear to everyone? So you've actually seen and interacted with this idea of eigenvalues and eigenspaces before, just, you know, in a slightly different form.
And what we're going to do now is we're going to build up on this. Yes, question?
STUDENT
In that example that you just did, if you had made your eigenvalues 2, would the only difference be instead of t minus I, would it be t minus 2I?
PROFESSOR
We'll do examples and get to that. Yeah, at the back?
STUDENT
Yeah. So every single time you said eigenvalue and you get eigenspace, is that eigenspace [INAUDIBLE] for all eigenvalues or only that one value?
PROFESSOR
The question was, if I say that — I say there's an eigenspace corresponding to an eigenvalue, is that eigenspace for that eigenvalue value or for all eigenvalues?
The answer is, these things come in pairs. There's an eigenspace for every eigenvalue. The eigenspace of one eigenvalue does not correspond to the other eigenvalue.
And we'll do an example that will explain just this in the next example. We'll clarify this, hopefully. There's another question somewhere over here? Okay, great.
So I'm going to do an example that will hopefully answer both of your questions.
So we had this Q, and we wrote — our Q for our Berkeley, Stanford example was the following, right?
And we did, by brute force observation, compute that, oh, you know, we checked — we did a guess and check style of argument here, right?
We said, oh, we think 0, 1 is a steady state. We think 0, 1 is an eigenvector. Let's try. Right?
That's what we did over here. We said, we think 0, 1 should work by just looking at the system. And oh, look, it actually does work.
But what if we wanted to compute this in a more principled way, right? Maybe we can't just look at this and check and guess, especially if the matrix isn't just a two by two.
So more generally, how do we find eigenvalues and eigenvectors, right?
So now, we want to find lambda and x — lambda is a real number; x is a vector — such that Q times x is equal to lambda times x.
Right?
So now, what we can do is look at this and do the same trick that we did last time, right?
We said, OK, you know, there's x on both sides of this; we don't like that.
So let's move the x's to the same side and write this as Qx minus lambda times identity times x is equal to 0.
This is the same as writing Q minus lambda-I times x is equal to 0, right?
So now, do we have this in the format of a system of linear equations that we can use Gaussian elimination to solve?
Kind of, but not really, right? What are our unknowns here?
x is unknown, but lambda is also unknown, right? Both of these are unknowns.
So, what do we do now? How can we get around this? We haven't really seen this type of problem before.
So this is where we want to use the fact that we've been building up this arsenal of tools and start to bring our concepts together.
So now, x is going to be a vector that is going to be in the null space of this matrix, Q minus lambda-I. Right? What is always an x that works?
STUDENT
Zero.
PROFESSOR
Zero, right? 0 is an x that always works, but 0 is an uninteresting x that works, right?
Because 0 is an element of every single eigenspace, because 0 is an element of every single vector space. Right? So zero is always going to be a solution.
So we want to see, when is the null space of Q minus lambda-I non-trivial?
What does that mean? When is it bigger than zero?
Just the 0 vector.
And did we just learn about something that helps us write an equation using the elements of the matrix and connected to the null space and the linear dependence and independence of the columns?
What did we learn about? The determinant, right? So can we use the determinant to help us solve this problem?
So our idea is to use the determinant.
So let's do this together. How are we going to do this? Let's first write out the matrix Q minus lambda times I. What does this matrix even look like?
Let's do it for our simple example here, where Q is equal to this. And we're going to say, 1/2, 1/2, 0, 1. What does the matrix lambda-I look like?
I have lambda, 0, 0, lambda, so this is equal to 1/2, minus lambda, 0, lambda, 1, minus lambda.
Right? So now, take a minute and write out the determinant of this new matrix that you have just written down.
Use this also as a minute to think about if you have any questions. Ask me or ask your neighbor, or — let's make sure we're all on the same page together.
[INTERPOSING VOICES] PROFESSOR: Are there any questions
ON how we've gotten here so far?
Yes?
STUDENT
Why do you want the [INAUDIBLE] PROFESSOR: Can you speak up?
Why do we want the matrix to be — have a null space?
So that's a great question. Why do we want Q minus lambda-I to have a null space? So let's go back to this example here, right?
Q is basically deciding our transitions, right? And we said that we want to find an x, such that Q times x is exactly equal to x.
But this problem, we said, is equivalent to finding the null space of this matrix Q minus I, right? Is this part clear?
So in the same way, instead of just having Q times x equal to x, we want Q times x equal to lambda-x.
That's equivalent to finding the null space of Q minus lambda-I, right?
But now, this — you know, the only x that satisfies this equation, and what's an x that trivially satisfies this equation? Zero, right?
So if we want to find an x that isn't just zero, right?
If we have zero people on each website, no matter how many times you run the pumps, you're still going to have zero people on each website. But that's not a very interesting setup.
So the more interesting case is when you have a steady state vector that is actually not equal to exactly zero.
And the only way that's possible is if this matrix, Q minus lambda-I, has a null space that is bigger than just zero. Is that clear to everyone?
Yep? Does that answer the question?
STUDENT
[INAUDIBLE] PROFESSOR: Why is the determinant equal to 0?
So that was basically exactly what we talked about in yesterday's lecture, or Tuesday's lecture. I don't have the full time to go over that argument again.
But if it's unclear, I'm happy to talk more in office hours. But go back and look at the webcast for the last time's lecture, and that's exactly where we talk about it.
But if you want a quick intuition, basically, this says that the determinant is zero when the columns are linearly dependent.
And we know that, when the columns are linearly dependent, the matrix is not invertible, and it also means that the null space has more than just the 0 vector.
So remember last time we had these set of statements that were all equivalent to each other? That's where that came from.
Okay, so what is the determinant, now, of Q minus lambda-I?
It's ad minus b times c, right?
We have this here — ad minus bc, so this is 1/2 minus lambda times 1 minus lambda, minus 1/2, times 0.
Right? Is this the determinant everyone wrote out? Can we write this as a quadratic equation? What is that quadratic equation equal to?
1/2 minus 3 by 2 lambda, plus lambda-squared, equal to 0, right?
And so, now what we get is basically 1/2 minus lambda times 1 minus lambda equal to 0.
So, what are the roots of this equation? Lambda 1 equal to 1/2, lambda equal to 1 — lambda 2 equal to 1 are solutions.
Yes?
STUDENT
So we don't know for sure that Q minus lambda-I is [INAUDIBLE] linear dependent. So how can we say [INAUDIBLE]?
PROFESSOR
I'm saying, for which values of lambda is the determinant 0? I'm going to find which lambdas make the determinant zero; that's exactly what I'm solving for.
What did we say here?
We said that the determinant is basically going to be exactly equal to 0 — determinant is equal to 0 if and only if null space is non-trivial, if and only if matrix
is invertible.
And we're saying, is this going to be true for all values of lambda? No, right?
Because the determinant is equal to this equation If I chose lambda equal to 42, is this going to be equal to 0? No, right?
But there are some special values of lambda, for which this is equal to 0. Yes, question? Yeah, green shirt. Yeah?
STUDENT
[INAUDIBLE] PROFESSOR: Yep.
STUDENT
Why [INAUDIBLE]?
PROFESSOR
So we'll come to that. Hold that question. Good question.
STUDENT
You said [INAUDIBLE]?
PROFESSOR
Matrix is non-invertible. Sorry, yes.
Other questions? Yes, question.
STUDENT
So the eigenvalue, it can span all reals? It's not limited to — PROFESSOR: The question is, can the eigenvalues be all reals? Yes, an eigenvalue can be any real number.
It turns out that eigenvalues can also be complex numbers, because, you know, if you have roots of a quadratic equation, are they always real? Sometimes they're complex, right?
Sometimes the idea is imaginary numbers. We're not going to deal with that right now. Right now, we're going to start with the simpler cases and move to the more complex cases later on.
Yes?
STUDENT
[INAUDIBLE] PROFESSOR: The question was, the determinant is equal to 0 means it has one solution. Do we want to show it has more than one solution?
What we want to do is we want to find all pairs of lambda and x that satisfy this.
So it turns out that, for a two by two matrix, you will typically have a quadratic equation here. This is sometimes called the characteristic polynomial. You will have, therefore, two eigenvalues.
They may be repeated eigenvalues, they may be real eigenvalues, they may be complex eigenvalues.
For most of today and tomorrow, we're going to be dealing with the simple case where the eigenvalues are not repeated and they're real numbers.
So basically in general, for a two by two matrix, you will have two eigenvalues and two corresponding eigenspaces. Yes, at the back?
STUDENT
So why is it [INAUDIBLE] PROFESSOR: So this, again, like, this is basically from the previous lecture.
The question is, why is the determinant equal to 0, meaning the null space is non-trivial? Determined equal to 0 means the columns are linearly dependent.
Columns are linearly dependent means you have a non-trivial null space. So this we discussed in the lecture where we introduced null spaces.
So if this isn't completely clear, like, I'm happy to talk about it more in office hours. Yes?
STUDENT
So right now, [INAUDIBLE] PROFESSOR: Yes, we will get to this.
Other questions? Okay. So we're here. We have, now, two eigenvalues, right?
And the question that was just asked is, well, how do we then get to the corresponding eigenspaces, right? We've only done part of our job so far.
So now, we know that for these particular values, we have that the null space of this has, you know, vectors in it other than 0.
So let's do it step by step. We consider, now, lambda-1 equal to 1 — or let's choose — let's choose the first one.
Which one should we do first? Let's do lambda-2 equal to 1 first.
Is an eigenvalue value.
Okay? Now, we want to find all of the vectors in this null space. If I tell you the value of lambda, here, are we now in the situation that we are comfortable with?
Yes, right? Now we're in the case where we have to now compute the null space of Q minus lambda-2I.
This is the null space of basically 1/2 minus 1, 0, 1/2, and 1 minus 1.
Here, I'm substituting lambda equal to 1, per what we just calculated. And I can now do Gaussian elimination to find this null space.
This is minus 1/2, 0, 1/2, 0. We just did this Gaussian elimination earlier, so I'm going to skip the steps.
Does everyone remember how to do Gaussian elimination for this to find the null space? Okay, so, dot, dot, dot. This gives you that.
Let's call this V2 is equal to 0 comma t is in the null space of Q minus lambda-2 times I. Therefore, the span of 0, 1 is the eigenspace corresponding
to eigenvalue lambda-2 equal to 1.
Okay?
When you have an eigenvalue equal to 1, the vectors in the corresponding eigenspace are called steady state vectors.
Because when you apply Q to them, you get exactly the same vector out, right? There's not even any scaling because the scaling factor, which is the lambda, is exactly equal to 1.
But we have seen now that it's possible to have eigenvalues that are not exactly equal to 1, right? We have this other eigenvalue here, eigenvalue lambda-1 equal to 1/2.
So let's now explore what happens in that case.
So for the case lambda-1 equal to 1/2, what is Q minus lambda-I?
this is 1/2 minus lambda-1, 0, 1/2, 1 minus lambda-1.
1/2 minus 1/2 is 0. This is the 0. This is a 1/2, this is a 1/2.
Let us now do Gaussian elimination to find the null space.
Just get 1, 1, 0, 0, 0, 0.
What is the free variable here? x2 is free, right? And what does this mean? This means x1 plus x2 equal to 0.
Right? So, what vectors are solutions?
These are all vectors that are in the span of negative 1, 1. Right? Because here we have x1 is equal to negative x2, and x2 is free.
Yes?
STUDENT
[INAUDIBLE] PROFESSOR: We'll get to that in a little bit.
Other questions? Is everyone with me up till here?
This is a calculation in the process of finding eigenvalues and eigenvectors.
It is basically something that is involving multiple pieces of things that you have learned in the past month, pulling them all together, right?
It's OK if everything isn't perfectly clear the first time you see it.
But hopefully, by doing the homework, by going to discussion, by doing all of this practice, you'll get, you know, used to these kinds of calculations. There's multiple steps that are involved.
Yes?
STUDENT
[INAUDIBLE] PROFESSOR: Would row reducing our original matrix, Q, change the eigenvalues? The answer is yes, in general. Yes?
STUDENT
So there are only those two eigenvalues for that matrix?
PROFESSOR
Yes. The question is, are there only those two eigenvalues for that matrix? The answer is yes, because those are the only two that make the determinant equal to 0.
The determinant of the matrix, Q minus lambda-I. Yes?
STUDENT
[INAUDIBLE] PROFESSOR: Yes. Is the number of eigenvalues dependent on dimensions? The answer is yes, for a two by two matrix, you would expect to have two eigenvalues.
What?
STUDENT
[INAUDIBLE] PROFESSOR: Can you have less? In general, no, because the quadratic will have two routes. You might have repeated and complex eigenvalues, but we're not dealing with those yet.
At the very back.
STUDENT
Are all vectors that are in the span of the eigenvalues [INAUDIBLE] PROFESSOR: Yes. The question is, are all vectors in the eigenspace eigenvectors?
Basically, all vectors that are in the span of an eigenvector, they're all called eigenvectors.
STUDENT
[INAUDIBLE] PROFESSOR: No.
Linear combinations of two distinct eigenvectors are not eigenvectors, just span of the individual eigenvector.
Okay.
So I want to explore this a little bit more. So now, here, I'm going to call this eigenvector w.
What happens when I take Q times w? What is the eigenvalues corresponding to the eigenvector, w?
What did we calculate the null space for?
1/2, right? So when I take Q times w, what do I expect to get out?
1/2 times w, right?
So, what is Q again? Q is equal to 1/2, 1/2, 0, 1, right? So why don't you quickly verify?
Quickly verifiable Q times w is. This is Q, this is w.
What do you get? What do you expect to get?
STUDENT
[INAUDIBLE] PROFESSOR: Q times w should be one half of the original, right? Can you do the simple matrix multiplication out?
You just do 1/2, 0, 1/2, 1, times minus 1, 1. What is this equal to? This row time this column gives me?
What do I get here?
PROFESSOR
So, what do I get? One half of the original, right? Is that what I expected?
Good. Now, what happens if I take Q times w, whole times Q?
What is Q times w? This is 1/2 w. This whole thing times Q gives me what?
STUDENT
[INAUDIBLE] PROFESSOR: 1/4 w. What happens if I take Q to the t times w?
STUDENT
[INAUDIBLE] PROFESSOR: Right?
Every time I multiply by the matrix, am I changing my direction? No. But what is happening to the length of my vector? Keeps shrinking, shrinking, shrinking, shrinking, shrinking, shrinking.
Right? Do you see how this is different from the case when lambda was equal to 1?
In this case, here, if I take Q times 0, 1, this is equal to 0, 1. What is Q to the t times 0, 1?
It is exactly equal to 0, 1, right? Here, 1 to the t is equal to 1. So this vector is not shrinking; that's why it's a steady state.
This vector, on the other hand, is shrinking away. Such a state is called transient.
Yes?
STUDENT
[INAUDIBLE] PROFESSOR: We'll get to that. Right now, let's just think about it as states that are shrinking.
STUDENT
[INAUDIBLE] PROFESSOR: Does it — how to preserve direction? Yes. Fundamentally, Q times x equal to lambda times x. So the direction is always the same.
STUDENT
[INAUDIBLE] PROFESSOR: Negative half — so any scalar multiple is though to be in the same. Direction so negative eigenvalues are totally permitted; we're going to come to that.
Yes?
STUDENT
So any eigenvalue less than 1 is considered transient? Like 1/3, 1/4?
PROFESSOR
Any eigenvalue less than one is considered transient, yes.
Basically, the direction, that state, is dying out. Yes?
STUDENT
[INAUDIBLE] PROFESSOR: What? How do you figure out which eigenvalues corresponds to?
STUDENT
[INAUDIBLE] PROFESSOR: Okay.
Okay, so you're all asking great questions. I want to do another example, just so that we can answer some of these questions.
Let's take another matrix. Let's take A is equal to 1, 2, 4, 3.
Find the eigenvalues and the eigenspaces corresponding to this matrix.
So, what is the first step?
Step one is to say, consider A minus lambda times I, right?
What is this matrix equal to? This is equal to 1 minus lambda, 2, 4, 3 minus lambda.
Next thing — we want to make sure that the determinant of this is 0, right? We want to find those lambdas for which this determinant is 0.
So now, if you think about the determinant of A minus lambda-I, this is equal to 1 minus lambda times 3 minus lambda minus 8.
Everyone with me on the determinant?
Now, we want to say, set the determinant equal to 0 to find the eigenvalues.
Okay, so I have — let me expand this. So I have 3 minus 4-lambda plus lambda-squared minus 8 equal to 0.
So I have lambda squared minus 4-lambda minus 5 equal to 0. This implies — what are the factors?
Lambda minus 5, lambda plus 1 equal to 0, right? This factors easily.
If, in general, you cannot factor this by just looking at it, what would you do to factor a quadratic equation? You have the quadratic formula, right?
So any such equation you can always find the roots, right?
So, what are the eigenvalues in this case?
STUDENT
[INAUDIBLE] Eigenvalues are lambda-1 equal to 5, and lambda-2 equal to negative 1.
So these are now of a different type than what we saw previously, right? First, one of the eigenvalues is negative. Right? Someone just asked a question about, what happens with negative eigenvalues?
Second, there was a question over here about transients and whether — what about when the eigenvalue is greater than 1, basically.
And so this is exactly what we are going to now be able to see. Yes, question?
STUDENT
[INAUDIBLE] PROFESSOR: So right now, we're just going to be dealing with 2 by 2 matrices.
We can generalize all of these concepts to n by n matrices, but we're not doing that yet, at all. Yeah. Don't worry about n by n matrices just yet.
We'll get there. Yes?
STUDENT
[INAUDIBLE] PROFESSOR: How do you define eigenvalues for matrices?
STUDENT
[INAUDIBLE] PROFESSOR: Yes. Can you only find eigenvalues for square matrices? The answer is yes. There is a generalized notion of these that works for rectangular matrices.
You'll get to that in 16B.
Okay. So, what do we want to do next?
If we want to find the again spaces corresponding to these eigenvectors, we want to now find the null space of A minus 5I, right?
So, what is this matrix? A minus 5I is equal to just plugging in five here.
I have minus 4, 2, 4, and minus 2, right?
How do I compute the null space of this? I use Gaussian elimination. Minus 4, 2, 4, minus 2, 0, 0.
This gives me basically minus 1, minus 1/2, 0, and 4, minus 2, 0.
And this gives me 1, minus 1/2, 0, 0, 0, 0.
So, what is the eigenspace here? What is the eigenspace of this matrix, A minus 5I?
Here, I have — x2 is free, and I have x1 minus x2 by 2 is equal to 0, so x1 is equal to x2 by 2.
So the eigenspace is the span of 1/2 comma 1.
Yes, question?
STUDENT
When do you [INAUDIBLE] PROFESSOR: The eigenspace corresponding to the eigenvalue of 5, so it's the eigenspace of the matrix corresponding to eigenvalue of 5.
But don't worry; we're not going to be testing you on correct use of terminology. Like, if you just say eigenspace is 5, you know, it's fine.
We're not trying to trip you up by using complicated jargon; that's not the goal at all. Yes?
STUDENT
[INAUDIBLE] PROFESSOR: Any vector in the span is called an eigenvector, yes.
Any vector in this span is called an eigenvector.
Okay, so we have this eigenspace, and we have — let's call this vector, v, is equal to 1 over 2 and 1.
Thank you. So, what happens if you take a times v? Would you expect to get?
5v. What if you take A-squared times v?
STUDENT
[INAUDIBLE] PROFESSOR: 25v, right? What if you take A to the 100 times v?
STUDENT
[INAUDIBLE] 5 to the 100 times v. So is this state disappearing? Is it transient? No, right? It's here to stay.
In fact, it keeps getting bigger.
So this is a state that you would say is blowing up. [LAUGHTER] This is definitely not a transient state.
[LAUGHTER] What is the last thing we have to do?
We have another eigenvector and eigenspace to deal with, right?
So now, what if I think about the null space of A minus minus I?
This is equal to the null space of A plus I. Right?
So why don't you take a minute to do this on your own? Now we've done a couple of these. I'll let you do it on your own.
Make sure that you can go through the mechanics.
First step is to write out A plus I.
[INTERPOSING VOICES] PROFESSOR: How many people feel like they're still
a little bit uncertain on how to proceed after writing out A plus I? How many people feel like they can follow through on this? Okay, a lot of people in the middle; that's fine.
So let's do it together, right? We have A plus I is — I'm basically plugging in minus 1 right here.
1 minus minus 1 is 2. That's all I did. Now I'm going to find the null space of this matrix.
For that I have 2, 2, 4, 4, 0, 0. Gaussian elimination gives me 1, 1, 0, 0, 0, 0.
I have x1 plus x2 equal to 0. X2 is free.
So all vectors that are of the form x2 minus x2 are in the eigenspace.
Therefore, the eigenspace corresponding to eigenvalue minus 1 is equal to minus 1, 1.
So, what's going to happen when you multiply minus 1, 1 by A? Minus 1,1, what does it look? Like minus 1, 1 is basically pointing in this direction downward, right?
Actually, yeah, minus 1, 1.
Upwards, this way. When you multiply it once by A, what's going to happen?
Oh, you can't see. Thank you.
This is equal to the span of this vector. This vector is just minus 1, 1 right here.
What's going to happen when you multiply A times minus 1, 1?
1 minus 1, right?
What's going to happen when you multiply it again? Go back to its original, so it's going to keep flip-flopping, flip-flopping, exactly like this. So I wanted to show you how this happens.
Let's see if I can get this up.
So can people see this, here?
This is a demo some of your TAs wrote to help out. So this is the first matrix that we thought about, right? The very first Q matrix that we talked about today.
Oh, you can't see this? Right. The Q matrix that corresponded to the tale of two websites, right?
It was 1/2, 1/2, 0, 1. And what this is doing is, it's saying, let's start with some vector. That's our initial state.
The second plot is showing, what are the eigenvectors corresponding to this matrix Q? Remember, we calculated them.
How do I make this smaller?
Now everyone can see? So here, this is the initial state. These are the eigenvectors. And if you multiply by the matrix, let's say, five times, where do you end up?
You end up exactly in the same position because this is an eigenvector. No matter how many times I multiply it, I get the same result. Okay.
Let's try putting in the matrix that we were just thinking about.
So let me input the matrix 1, 2, 4, 3, right?
And the eigenvector that we just thought about was minus 1, 1, right? This was the eigenvector we found. So let me now run this.
So I have this minus 1, 1 vector, and I haven't multiplied it by the matrix yet, so my transformed vector is exactly the same. What happens when I multiply by the matrix once?
It's exactly in the opposite direction now, right? What's going to happen when I multiply it twice?
And as I keep going, it's going to keep flipping. On the other hand, what was the other eigenvector that we found for this? We found 1/2 comma 1.
So let me set this to be 1/2 comma 1 and run this again.
When I haven't multiplied this at all, the transformed vector is exactly the same. What happens when I multiply it once? It's grown by 5.
What happens if I multiply it twice? It's now getting so big it's, like, going off. Basically, I can't even see it on the scale, right?
It started out tiny and it keeps getting bigger, and bigger, and bigger. But is the direction changing?
No, right? So regardless of what we're — like, regardless of how many times we multiply it, because it is an eigenvector the direction is not changing.
But now, what if I tried a vector that was not an eigenvector? Give me two minutes; this is going to be interesting. Just wait. Let me try something else, right?
1, 1 is not an eigenvector for this matrix, right?
So I haven't multiplied it yet. We have exactly the same thing. I multiply it. It changes direction, right?
It's not staying in exactly the same direction. Every time I multiply it keeps changing. If I try something else. If I have something, like, let's say something really bizarre.
Start here, you see that it keeps changing direction. So this is not an eigenvector, because every time I transform it I keep getting something different out.
So I'll post this on the website. Make sure you can play with it and try to understand what is exactly going on.
We'll continue on Tuesday where I'm going to connect up this lecture to more things about steady state, as well as imaging three, and understand how eigenvalues matter for the lab you're going to do.
[INTERPOSING VOICES] [AUDIO OUT]
Đă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.