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
OK. Let's get started.
Welcome to Lecture 10 and the last lecture for Module 1.
So you've come a long way from the start of the semester where we starting with just defining even what a matrix and a vector was.
And today we're going to wrap it up with connecting back to the imaging lab, which is where we started out.
We started this entire module saying that we wanted to learn how to design good tomography machines. How do MRIs work? How do CT scans work?
How can we set these problems up so that we can solve these to make sure that we design things well?
And today we're going to end that by using properties of eigenvalues and eigenvectors to really understand what kinds of masking matrices are particularly good and particularly useful
for problems such as understanding inversion and imaging problems. OK, so before we get started, just some announcements. There's a midterm.
It's in exactly one week. Please don't forget. Please mark your calendars. Please don't be late.
The scope of the midterm will go up until today's lecture and the associated discussions. So there will be a discussion tomorrow, which will be useful.
There will be a discussion on Monday, the day of the midterm as well. This discussion will be geared towards helping you prepare for the midterm.
So it will be useful for you to attend that discussion as well. There will be a review for the midterm, which will be Thursday evening.
Our GSIs, we will be conducting the review, and we encourage you to attend.
The plan will be to just give a summary of all of the concepts that have been covered in Module 1 and that are in scope for the midterm.
I think we will also be going over some exam problems from previous midterms.
So if you've been looking at previous exam problems and want to ask them questions or go see some previous exam problems solved out, I encourage you to go to the midterm review.
Any major questions about any of this? OK, so then let's start out with what we're going to be doing today.
We're going to be picking up from last lecture where we talked about eigenvalues and eigenvectors. And we will talk about more properties of eigenvalues and eigenvectors.
I'm just going to write them as e values and e vectors to be quick. And we will talk in particular about how these are useful for understanding systems.
So we've been thinking about these systems that are of the form x at time t plus 1 is equal to a times x of t. And this is just one example.
We've been looking at examples of what more generally are sometimes called dynamical systems. And these are often studied in the context of control and robotics.
We've been looking at them largely in the context of pump systems and from the example of or from trying to understand page rank.
But more generally, these can be used to model multiple other phenomena.
And finally, after we're done talking about all of these, we will connect back to the imaging lab and talk about what you're going to be doing in imaging lab three.
So the two questions that we're really going to think about.
There is a question that actually someone asked on Piazza, and I thought that that would be a good question to try and address in lecture.
Which is that we know that if we start in the steady state for a dynamical system, we're going to stay in the steady state. We've understood this.
But what if we initialize in a state that is not the steady state? What if it's something else?
How do we understand exactly how the system will behave if I initialize with some arbitrary x0? And this is the question that we want to try and understand first.
So what if we initialize with an arbitrary initial State And how is this connected to basically eigenvalues,
eigenspaces, and eigenvectors?
And the second question really is, you've all done the imaging lab, and you've seen that in imaging two, you were able to use the idea of matrix inversion to reconstruct the image.
Everyone remembers that lab? But you might have noticed that there was the image where it was a little bit blurry. It wasn't exactly as clear.
And your TAs probably told you that what we can do is we can take multiple pixels, measurements of multiple pixels at once, and use this to actually improve our ability to image.
And we're going to talk exactly about how we can improve that today.
So improve imaging performance.
So these are the two questions motivating the lecturer.
To be able to answer these, we're going to rely on a key theorem. And that's how I want to start out. And the theorem that I want to talk about is the following.
Let a be a square matrix and let lambda 1, lambda 2, lambda n be the eigenvalues of a.
Let us have it so that all of the eigenvalues are distinct.
That means that lambda 1 does not equal to lambda 2 for all of the pairs. So lambda 1 does not equal to lambda 2.
Lambda 1 does not equal to lambda 3. Lambda 1 does not equal to lambda n. Lambda 2 does not equal to lambda 3. So on and so forth.
So instead of writing out all of these pairs, I can just write this as lambda i does not equal to lambda j for all i and j.
And let's say that v1, v2 all the way up to vn are the eigenvectors corresponding to each of these eigenvalues.
So they are representative vectors from the eigenspace. Remember, for every eigenvalue, there's actually an entire space of vectors. It's not just one vector.
But we're just picking one vector from each eigenspace and calling them the eigenvectors.
Our theorem says that if all of the eigenvalues are distinct, then v1, v2, vn form a basis for rn.
So what does it mean if we can show that all of the eigenvectors form a basis for rn? It means that every point can be represented.
Every point in rn can be represented as a linear combination of these eigenvectors.
And so if you can represent any point as a linear combination of these eigenvectors, that means that we can use these eigenvectors as basic building blocks to understand how arbitrary vectors might behave under linear transformations.
Eigenvectors are easy to understand under linear transformations. What happens to an eigenvector when it's transformed by the matrix? It just scales. It doesn't change direction.
It doesn't do anything crazy. It just changes its magnitude. So if we can have this understanding, this will help us build towards understanding generic vectors in the space.
The full proof of this is something that is possible to cover but is a little bit more challenging.
So what we're going to do today is we're going to prove this in a special case where we're going to think of a as a 2 by 2 matrix.
And we're going to prove for this case.
OK. So I'm going to give you just a little bit of time to — can people read this at the back? Is it too small?
Too small.
Is this better? Yeah, OK. Everyone can read at the back? Yes?
OK, great. So take a minute and think about how you would go about proving this. Remember how we do proofs. You know something.
You want to prove something. Try to write that down and proceed step by step.
Feel free to talk to each other. Just think about how you can proceed.
Brainstorm with your neighbors.
So how many people think they have a good idea in which they can make progress? And how many people maybe are feeling stuck? Some people are feeling stuck.
OK, so what I want you to do is think about why you're stuck. Try to write down what you have and and note the points. In your head, note how you've gotten stuck.
Because the goal is to figure out when you get stuck, how do you unstick? That's what we want to learn how to do.
So now that you've all tried for a little bit, let's think about this together.
So one common point that it's possible to get stuck at is to try to not be able to really start. What do you even say? What is known?
What is unknown? How do you even start about this — what you want to show and what is known? So let's try.
We want to prove this, and we want to prove it in the 2 by 2 case.
So first one easy thing to do would be to say, well, let me write out the theorem statement again specialized to the 2 by 2 case. So a is 2 by 2.
And so I have eigenvalues lambda 1 and lambda 2. And what do I know about lambda 1 and lambda 2? They are not equal to each other.
And I have eigenvectors v1 and v2.
And I want to show that v1 v2 form a basis for r2.
So one way to get stuck is to not write this statement out. So if you're ever feeling unsure, make sure you write it out explicitly. Then let's go to the next step.
Let's see what do we know. We are given whatever you feel like calling it. What do you know? What are you given?
Well, you know v is the eigenvector corresponding to eigenvalue lambda 1. So what happens when I take a times v1?
This is lambda 1 v1. Is this known to me? This is known. What else is known to me?
a times v2 is equal to lambda 2 v2.
And I know lambda 1 is distinct from lambda 2.
What do I want to prove?
I want to show that v1 and v2 form a basis for r2.
So another point that I have seen people get stuck at is here.
You write out this, you write out this, and then you say, well, we want to show that v1 and v2 form a basis.
Now what? This doesn't look like a basis. How do I figure out what a basis is? How do I go from here?
So when you're in this kind of situation, look at what you have and see, can you unpack anything? And the one word here that is unpackable is this term basis.
We have a definition for what a basis is. What does it mean for a set of vectors to be a basis for a vector space?
It means first that v1 and v2 — what do we need to have about v1 and v2? They must be linearly independent.
And the second thing you must have is that v1 v2, they must span r2.
Now you're looking at this, you know that v1 v2 are two dimensional vectors. If you can prove that they're linearly independent, can you immediately infer that they must span r2?
So now what does it remain to be shown to complete your proof?
That they're linearly independent. OK, so now you know that what you want to focus on is this condition.
You want to show that v1 and v2 are linearly independent.
So what have we said when we're talking about things that sometimes you want to show something is linearly independent, something is not invertible?
When you have this kind of negation, what is a trick that we've seen that can be useful?
Proof by contradiction. So what do you want to assume here? Assume that they're linearly dependent.
So let's say if possible, assume v1 v2 are linearly dependent.
Here is another possible point to get stuck.
Because we're writing this out, but we haven't yet written this out mathematically. How do you move from this point onwards?
Use a definition of linear dependence. When I have two vectors and what is the definition of linear dependence for just two vectors?
One is a multiple of the other. So if I was to say, I can write this as, let's say, v1 is some alpha times v2.
Yeah, we're good?
And what do we want? We basically want this to be an actual multiple. We want alpha to not be 0. We want to say it's a multiple.
It's not just 0.
But we don't want to consider 0 vectors here.
So we have this. Now you have this and you have this. Somehow you need to connect these things up.
When you see a v1 and you know you know something about a times v1, what do you feel like doing to this equation? Multiply by a. So let's try multiplying by a.
So let's say I have a v1 is equal to a times alpha v2.
Can I rearrange this product? I can write this further as alpha times a times v2, which is equal to alpha times — what is a times v2?
Lambda 2 times v2.
If this is 1, this is 2. This follows from 2.
But what else do we know about av1? If I think about av1, that's one way of writing av1. What else do I know about av1?
This is equal to lambda 1 times v1.
So these two quantities must be equal.
But they're kind of not in the right form that we want. There's a v1 on one side and a v2 on one side, and we don't really know anything about v1 and v2.
But is there something else that we do know? Oops.
What did we assume about v1?
We have this. So we can rewrite this as lambda 1 alpha v2.
And now what do we have?
So now we have lambda 1 alpha v2 is equal to lambda 2 alpha v2.
But is this possible?
What was our assumption? Lambda 1 isn't equal to lambda 2. This is given to us, actually.
Therefore, this is a contradiction.
Hence v1 v2 must be linearly independent.
Therefore, they span r2. Therefore, they form a basis.
Does everyone see how we got to this conclusion?
Do you see potential ways where — do you see where along the way you got stuck and how you could have potentially unstuck yourself?
Whenever you're doing proofs, I really encourage you to try and do this. If you get stuck and then you see the solution later, try to go back and think through your thought process.
Where did I get stuck and what was the unsticking? This will help you get better as you go on.
Are there any questions about any of this? Yes, in the back.
STUDENT
Does an invertible n by n matrix always have n eigenvectors or eigenvalues?
PROFESSOR
Does an invertible n by n matrix always have n eigenvectors and eigenvalues? You will always have n eigenvalues, yes. They might not always be distinct, but you will always have that, yes.
Yes?
STUDENT
Is it possible to start this proof using an example two by two matrix [INAUDIBLE] abcd and go from there?
PROFESSOR
Great question. Is it possible to start this proof by thinking of abcd and going from there? It might be possible. I don't know whether or not that proof approach will fully work out.
But one way is explicitly calculating out every single eigenvalue and every single eigenvector. You will have to impose some conditions on the abcd to make sure that you can get distinct eigenvalues though.
So assuming that you can choose abcd and make sure that these constraints are satisfied, it's possible to do it, but I think this approach will be much more straightforward.
Yeah. Yes?
STUDENT
[INAUDIBLE] the size of the basis for rn is always going to be size n?
PROFESSOR
Yes. The question is how many vectors will be there in the basis for rn? And the answer is always n. Yes, because the dimension of rn is n.
And so you will have n elements in the basis.
So we've proved this here. Again, I want to point out only in this 2 by 2 case. We haven't proven this more general statement.
This is true, and it's something that you are able to prove, but it's just a slightly more challenging proof. I encourage you to try it at home.
And if you have questions, definitely come talk in office hours. But because it's just a little bit more challenging, I'm not going to be covering it in lecture.
So if you understand the 2 by 2 proof, you should be good. We're not going to be asking you to prove this for n by n on the exam.
What I want to do, though, is now use this to understand general initial states.
So for a system such as x of t plus 1 is equal to some a times x of t.
This can be thought of as a general dynamical system. Maybe this represents your segue or your inverted pendulum. Maybe it represents your pumps. Maybe it represents a quadcopter.
It could represent a lot of different things.
But now we know that if x at time 0 is in steady state, then the state does not change, no matter how many times you apply it.
But now what if you start in a state that isn't the steady state? What if you start at some arbitrary state x?
What can you do? How can you understand how this arbitrary initial state is going to behave?
And now that we have this theorem about the eigenvectors, what might be a good way of trying to explore how an arbitrary initial state will behave?
Find the eigenvectors of a. Yep. And then what do we know? We know that the eigenvectors form a basis.
So what does that mean? It means that every vector can be expressed as a linear combination of the eigenvectors.
We can write x as a linear combination of the eigenvectors.
So I can write basically x is equal to some alpha 1 times v1 plus alpha 2 times v2 plus alpha n times vn.
v1, v2, vn are eigenvectors and lambda i's are distinct, let's say.
Yeah, question?
STUDENT
Why do we know that the eigenvalues for this matrix are [INAUDIBLE]?
PROFESSOR
Great question. The question is why do we know that the eigenvalues for this matrix are distinct? The answer is that we're assuming that they're distinct.
We will talk more about what happens if they are not distinct in five minutes.
Yes?
STUDENT
[INAUDIBLE] how you can write x as a linear combination of eigenvectors?
PROFESSOR
OK, good. The question was why can x be written as a linear combination of eigenvectors? We know why is this possible.
We know that v1, v2, vn form a basis for rn.
And what does it mean for a set of vectors to be a basis? It means two things. First that they're linearly independent.
And second, it means that any vector in the space can be written as a linear combination of those vectors. Any vector in the space is in the span of those vectors.
So because we just proved this theorem that says that the eigenvectors form a basis, we're using that theorem now to write this in the following way. Good question.
Everyone with me here? OK. So now when I think about a times x, how can I write it out further using what I have seen here?
I can write a times x is a times alpha 1 v1 plus alpha 2 v2 plus alpha n vn.
And what do we know about a applied to the eigenvectors? Eigenvectors are the invariant vectors. Eigenvectors are the ones that don't change direction. All that happens is their magnitude might change.
So when a acts on v1, what are you going to get out?
STUDENT
[INAUDIBLE] PROFESSOR: Exactly. Lambda 1 v1. You're just going to get a scaled version of v1. What about v2?
So what we can do is we can write this as a. We can use the distributive property to pull a into this.
And now write this as alpha 1 av1 plus alpha 2 av2 plus alpha and avn.
This is equal to alpha 1 lambda 1 v1 plus alpha n lambda n vn.
What happens now? So this is what happens to an arbitrary. Remember, x is arbitrary. I apply a once.
And this is what I'm getting. So this is basically the next state. What happens when I apply a one more time.
If I think about a squared times x, can I do the same thing? I can write a times this.
And so I'm going to get — what is going to happen to a times v1 now? I'm going to get alpha 1 lambda 1 squared times v1.
What happens if I apply a t times?
Alpha 1 lambda 1 to the t v1 plus alpha n lambda n to the t vn.
So let's look at the components of x as t grows. What if a particular lambda i is exactly equal to 1?
Does that component change? Remember, these are now all of the components.
Of x expressed in the basis of these vectors.
So if lambda — let's say lambda 1 was equal to 1. No matter how many times I apply a, is the coefficient of v1 going to change? Nope.
What if I had lambda i that was strictly greater than 1?
What's going to keep happening? Is that component — it's going to keep increasing. It's going to keep getting bigger and bigger and bigger. And what happens if lambda is strictly less than 1?
As time goes to infinity, is that component even going to exist?
So any components in the direction of transient eigenvectors are going to die off. Everything else is what is going to stick around.
So when you think about the kinds of pump systems that we've been thinking about, if you think about conservative systems, there you know that you always have an eigenvalue of 1 and the rest of the eigenvalues are smaller than 1, in which case, no matter where you start out, you're going to end up exactly in the steady state.
So I want to do a simple example to show that. But before that, does anyone have any questions about this part? Yes?
STUDENT
[INAUDIBLE] as far as [INAUDIBLE] PROFESSOR: The question is what happens about the sign of lambda?
If they're greater than 1, less than 1, does the sign matter? And do you have to take the absolute values? You don't really have to take absolute values.
You will have whatever that power is. It will show up.
So for example, if your eigenvalue is minus 1, like we had at the example at the end of the last lecture, your vector will basically still have the same magnitude but it'll keep flipping its sign.
You might have an eigenvalue that is less than 1 but still negative. Even so, that's still going to decay to 0 even though it's flipping its sign. Yes?
STUDENT
So we know v1 up to vn, each of these eigenvectors have an eigenspace associated with it?
PROFESSOR
Yes.
STUDENT
How does that eigenspace related to [INAUDIBLE]?
PROFESSOR
So the question is that each of the eigenvectors v1 to vn has an eigenspace associated with it. How does that relate to rn?
Basically, it relates in the case of distinct eigenvalues through this theorem. All of those eigenspaces are each spanned by one of these eigenvectors.
All of the eigenspaces together make up rn in the case of distinct eigenvalues. Yes? White t-shirt at the back.
STUDENT
Can you go over why the [INAUDIBLE] all the eigenvalues are 1 or less than 1?
PROFESSOR
That's exactly the question on the homework. And we will see it in just a minute. Yeah, but if you look at the homework question — the homework question on the homework last time.
Yeah. But we'll talk about it in one example in just a minute. Yeah?
STUDENT
For lambda i is greater than 1, is a to v times x increase time by the scalar amount above the same line, or is it actually changing angles?
PROFESSOR
It's changing exactly by that factor lambda. a times v, if v is an eigenvector, never changes angle. It never changes direction. Yeah.
Yeah, the question that you're asking about the eigenvalue v1, that's basically, you can derive that from the problem on the homework that was given. But yeah.
OK, so to answer that question, we won't fully prove it, but we will do a simple example that will hopefully elaborate. So let us consider the following example.
a, b.
3/4, 1/4, 1/2, 1/2.
So we have, let's say, this system of websites or a system of pumps or transferring energy.
And we want to understand this. So we can write out the transition matrix for this as 3/4, 1/4, 1/2, 1/2.
And then we can say we want to find the eigenvalues and the eigenvectors.
We want to figure out what is the system going to end up in when I start out in some arbitrary initial state?
So I have some arbitrary initial state x0. What happens? And per our analysis here, what do we want to be able to do to understand this arbitrary initial state?
We want to find the eigenvalues and the eigenvectors. So let's do that. So for that, we want to look at basically the determinant of q minus lambda i.
You must have done a lot of these examples in discussion yesterday. So hopefully, that helps. So what is now q minus lambda i, the determinant?
It's 3/4 minus lambda times 1/2 minus lambda minus 1 over 8.
3/4 minus lambda, 1/2 minus lambda. The determinant is just ad minus bc, which is just equal to lambda squared minus 5/4 lambda plus 1 over 4.
Everyone get the same determinant? OK, so what are the roots of this?
This just splits as 1 and 1/4. So I get this as lambda minus 1 times lambda minus 1/4.
So the eigenvalues are lambda equal to 1 and lambda equal to 1/4.
So we have this. Take a minute just for practice and compute the eigenvectors.
OK, how many people are done? OK, good. So what are the eigenvectors?
What is the first eigenvector? 2, 1, great. I have a question. Did anyone write down something other than 2, 1?
What did you write down? 1, 1, 1/2. Did someone write something else? Are both of these correct answers?
Yes. Both of these are eigenvectors. There's multiple ways to write an eigenvector. It's important to remember this.
Good. What about for lambda 2?
What was v2?
Negative 1, 1. Or 1 negative 1. Again, it's exactly the same vector. So you have this.
Now let's take our x and write it as a linear combination of these two. So are these two linearly independent? Let's just verify our theorem.
Neither can be written as a multiple of the other. Therefore, they form a basis.
So let us now write x0 is some, let's say, alpha 1 times 2, 1 plus alpha 2 times minus 1, 1.
And we can write x at time t is basically a to the t times x0.
And what do we know? This is going to be alpha 1 times lambda 1 to the t times v1 plus alpha 2 times lambda 2 to the t times v2.
So what part is going to stick around and what part is going to die off?
So here this is basically alpha 1 times 1 times v1. Exactly the same, because lambda 1 is 1. Plus alpha 2 times 1 over 4 to the t times v2.
Therefore, as t tends to infinity, at x0 tends to alpha 1 times v1.
Because this thing tends to 0.
As t goes to infinity.
Is everyone with me here? Any questions about this?
OK, great.
Sorry.
So does this explain to people how even if you were starting in some arbitrary initial state, you could still get to an understanding of what your final state is going to be?
You might have different combinations of things, of eigenvalues, eigenvectors, but you can just express them out and get to your solution. Question in the back?
STUDENT
[INAUDIBLE] PROFESSOR: Ah, good question. The question was how did I get x0 equal to alpha 1 times 2, 1 plus alpha 2 times minus 1, 1?
We said that the eigenvectors form a basis. v1 v2 are a basis.
And so I can express any vector in r2 as a linear combination of these vectors. So by choosing different alpha 1 alpha 2, I can get to any x0.
So I'm saying let alpha 1 alpha 2 be some constants. x0 is now an arbitrary vector in r2. Yeah?
STUDENT
Did we need to find the eigenvectors in order to do the second part [INAUDIBLE] PROFESSOR: Did we redefine the eigen — STUDENT: Did we need to find the eigenvectors?
PROFESSOR
The question, yes, good question.
Did we need to actually write out 2, 1 and minus 1, 1 as the eigenvectors to be able to figure out that this component is going to go to 0?
And the answer is no. You knew that as long as — you knew that because you had distinct eigenvalues you were going to have linearly independent eigenvectors.
And so you could have just said that this is the only component that's going to matter.
But to find out what this final component is and to know that your steady state is always going to be in the span of 2, 1, for that you needed to find out what it was.
Good question.
Other questions? Yes?
STUDENT
Is there anyway we can ever figure out what alpha 1 is going to be or is it just going to be [INAUDIBLE]?
PROFESSOR
The question was, is there any way we can figure out what alpha 1 is going to be? This is an important question.
If I tell you x0 is equal to 5, 6, how do you figure out what alpha 1 and alpha 2 are?
We can solve a system of linear equations to find out alpha 1 alpha 2. So given whatever x0 is, you find alpha 1 alpha 2.
You can always find alpha 1 alpha 2, in fact. Yes?
STUDENT
Is there a way for us to know that all the eigenvalues are going to be 1 or less than 1 without explicitly finding all of them?
PROFESSOR
The question is, is there a way for us to know that all of the eigenvalues are going to be 1 or less than 1 without explicitly finding all of them?
In general, just by looking at a matrix, you cannot.
You can prove, similar to the question over there, that if your matrix is conservative, which means that all of your columns add up to 1, then one must be an eigenvalue.
It's not a proof that we have done explicitly in the class, but basically using the proof that you built up in homework four, I believe, you can go one more step to prove that.
Yeah?
STUDENT
So x0 has to be in the eigenspace of [INAUDIBLE] PROFESSOR: x0 is not associated with any eigenspace.
It is an arbitrary vector.
So now we understand this, and we want to think now about the following.
Let's say v. Actually, what do I want to do?
So we've thought here in particular about what was the condition that we had for all of the analysis that we've done so far? We've always thought about distinct eigenvalues.
What happens if there's a repeated eigenvalue? Can we say anything about that case? And that's what I want to explore next.
So the full exploration of what happens when you have repeated eigenvalues is actually quite involved and it shows up in a lot of very important physical systems, particularly in the context of control.
Here we're just going to give a couple of examples. 16b, we'll do the full treatment of how to handle things when you have repeated eigenvalues.
But just to give you a sense for why this is a non-trivial issue, consider this matrix. What are the eigenvalues of this matrix?
Lambda 1 equal to 1. Lambda 2 equal to 1.
And what are the eigenvalues? v1 is equal to 1, 0. And v2 is equal to 0, 1.
Do you v1 and v2 form a basis for r2?
So here we have repeated eigenvalue 1 and v1 v2 form a basis for r2.
What if we consider this other matrix, which is the following? 0, 1, 0, 0.
What are the eigenvalues of this?
If I take a minus lambda i, what am I going to get on the diagonal? Lambdas. So what is the determinant of a minus lambda i?
It's lambda squared, exactly. So what are the eigenvalues for this matrix? Lambda 1 equal to 0, lambda 2 equal to 0.
What is an eigenvector for this matrix corresponding to the eigenvalue 0?
What if I consider this v1?
What does a times v1 give me?
a times v1 gives me 0, which is equal to 0 times v1.
So v1 is an eigenvector corresponding to eigenvalue 0.
Are all vectors eigenvectors for this matrix?
No. What happens if I chose 0, 1 as opposed to 1, 0?
What does 0, 1 go to? It flips. So all vectors are not eigenvectors.
Just for this specific case, you have that v1 equal to 1, 0 is an eigenvector.
Is there a second eigenvector? Here what you have, it turns out that there's only one eigenvector. So the eigenspace is how many dimensional? One.
The eigenspace corresponding to eigenvalue 0 is actually just one dimensional. So here you're seeing a collapse of dimension is what is happening.
Basically, when a multiplies a vector, it projects everything onto just one line. The entire r2 space gets pushed into just exactly one line.
And this is why you're seeing here that this basically eigenvector, there's no second eigenvector. The eigenvectors do not form a basis for r2. So it's possible with repeated eigenvalues to form a basis.
It's possible to not form a basis. When they don't form a basis, there are techniques that you can use to build up a basis and then solve problems.
But this is all currently outside the scope of 16a, and you will see this much, much more in 16b.
So I just wanted to give you a flavor of the idea that this is not a trivial problem. It's not obvious.
It's not like, oh, if it's a repeated eigenvalue, it never forms a basis. Sometimes it can, sometimes it can't. Yeah. Question at the back?
STUDENT
Does 0, 0 have an eigenvector in second example?
PROFESSOR
The 0, 0 count in an eigenvector for the second example. Typically we don't call the 0 vector an eigenvector. It's part of the eigenspace.
But because 0 is a trivial example, it's a trivial solution, but it's not an interesting solution. So we wouldn't consider it as an eigenvector. Yeah. Yes?
STUDENT
So so far it kind of seems like our eigenspaces goes to one vector, but say the eigenspace for an eigenvalue has two vectors.
So we're working with larger [INAUDIBLE] PROFESSOR: The question was what if sometimes your eigenspace corresponding to an eigenvalue has two eigenvectors.
And that actually does show up, in this case. So there is one eigenvalue, but it has basically a two dimensional eigenspace associated with it. So that can happen sometimes.
And in some cases, you can analyze it exactly as the case of non-repeated eigenvalues. Sometimes you can't. 16b will go into a lot of detail on this. Yes?
STUDENT
[INAUDIBLE] PROFESSOR: Can you speak up, please?
STUDENT
Could you [INAUDIBLE] v1 and v2 for the first example?
PROFESSOR
Oh, for how did I get v1 and v2 for the first example? I just got them by inspection.
But you can basically solve them out exactly using the method that we always use to get v1 and v2.
But here it turns out that you can actually find any two vectors that are linearly independent as eigenvectors.
STUDENT
[INAUDIBLE] PROFESSOR: These are eigenvectors, yes.
We went in — like here v1 and v2 are eigenvectors. But what is true about the identity matrix? If I take the identity matrix times any vector ab, what do I get out?
ab. So is any vector ab an eigenvector for the identity matrix? Yes, because the eigen — every eigenvalue corresponds to an eigenspace.
The eigenvector isn't a unique thing, necessarily. It's important to understand this. Does everyone understand why any vector ab is an eigenvector for the identity matrix?
OK, good questions. OK, so we're here now.
And what we've been seeing is that these eigenvalues and eigenvectors generally help us understand this system very well.
The one eigenvalue that is interesting is often eigenvalue equal to 0. What does it mean if a matrix has an eigenvalue of 0?
This means that there is some vector av such that a times v is equal to 0 times v is equal to 0.
What this means is, basically, that this eigenvector v is in the null space of a.
What do we know about a non-zero v being in the null space of a? What does that mean about a?
It means that the columns of a are linearly dependent and that a is not invertible.
So this means that columns of a are linearly dependent and a is not invertible.
And what does it mean if a is not invertible for our system of equations?
Means it might not have a solution or it might not have a unique solution. It might have infinitely many solutions or it might be inconsistent.
You basically can't solve it using our standard inversion technique.
So basically, we know that if we end up with an a that has an eigenvalue of 0, we're going to have trouble solving the associated system of equations.
This we know.
We want to now kind of try and generalize this idea and say, well, 0 is one thing, but what if I had an eigenvalue that wasn't 0 but it was like 0.000000001?
Does my matrix have a null space?
It doesn't. Because I would have v equal to 0.000001 times v, which is not 0. It's distinct from 0. But it's really, really small.
And it turns out that having really small eigenvalues can also make things, in a sense, challenging for inversion.
This is something that we're not going to explore fully in 16a at all. It is a topic that, again, you will see come up in 16b.
It will show up in classes like 127 and 189 and then further like numerical linear algebra classes will really start to cover this in detail.
But now, this is the principle that we're going to build up lab on.
Small eigenvalues versus large eigenvalues.
So what is the problem that we have in the lab? The lab basically says that I have some image.
I have some picture. And what do I do? I have a projector and I project some light onto this. There's a mask.
And then I measure basically the reflected light onto some sensor.
Everyone remember this setup from lab? And how did you model this? You said you had some — you vectorize this image. So i is your unknown image.
And you modeled this projection as a mask. And you said, well, I'm going to take h times i is equal to some s. And this s is what the sensor reads.
Everyone remember this?
But then if h is an invertible matrix, what should I be able to do? I should be able to then write i is equal to h inverse times s.
And since h is invertible, I should get back exactly i from s. But do you get back exactly i from s? No.
Did the image that you reconstructed look exactly like the image that was there? It didn't. It was blurry and it had sometimes it was a little bit off.
There were some errors in it. And why does that happen in real life?
Basically, that happens because your sensor doesn't just measure the reflected light from here, but it also gets some other noise.
So maybe there's some other noise that shows up in your sensor.
So your s, you think is your s, is basically your h times i, but actually what you're getting is just some s is equal to h times i plus some noise w.
And now when you try and apply h inverse, what happens?
I can have h inverse times s is equal to h inverse times h times i plus h inverse times w, which is just equal to i plus h inverse times w.
So ideally, what do you want h inverse s to be equal to? You want it to be equal to just this i.
So if you could make all of this disappear, would you do it? Yes.
Turns out you can't, because the real world keeps doing stuff, and you can't stop it.
You're trying to measure only the light reflected from the image, but some other light from somewhere keeps coming in. And you want to try and figure out, well, what can you do?
Well, if you can't make this disappear, do you want this to be big or do you want this to be small? You want it to be as small as it possibly can be.
And it turns out that one way to make this small is to notice that actually the effect of this matrix h is related to the eigenvalues of the matrix h.
So what I want is for h inverse w to be small.
What this means is that this is connected to the eigenvalues of h inverse being small.
And turns out that this means that you want the eigenvalues of h to be large.
I'm not going to do this full argument out right now in lecture, because this is exactly the problem that you're going to do on your homework this week.
What that homework problem is showing to you is how you can use the eigenvectors of a matrix to understand how this matrix impacts an arbitrary vector that it is acting on.
So what you want to do is you want to think of this, basically, as a linear combination of the eigenvectors and use this to understand how you're going to affect this w vector when it's multiplied by h inverse.
So now if you wanted to have w, the h inverse w be as small as possible, you're going to basically want to have the eigenvalues of h inverse be as small as possible.
And you will prove in your homework that the eigenvalues of h and h inverse are reciprocals of each other.
And so if you have small eigenvalues for h inverse, that means that you must have large eigenvalues for the matrix h itself.
And so what you will be doing in imaging three is you will be choosing a particular matrix h that has large eigenvalues.
And that will help you actually recover your system — your image much better.
Is everyone clear on what this connection to lab is? Yes, question.
STUDENT
[INAUDIBLE] PROFESSOR: Great question. Does large eigenvalues mean greater than 1? That's a really, really great question. We're being somewhat vague about this.
Larger eigenvalues typically means greater than 1, but it also means the larger the better. So an eigenvalue of a million is better than an eigenvalue of half a million.
STUDENT
[INAUDIBLE] PROFESSOR: Because of this reciprocal connection. So when you do the homework problem, hopefully this will become clearer to you. Yeah, but it's a very good question.
So in the last little bit, I wanted to do two things. First, I wanted to just give you a little bit of a wrap up of the final of this entire module.
This Module 1, what we just completed, is the module that is an introduction to systems.
And what did we start out with? We started out basically with the imaging lab. And we said we wanted to understand tomography.
And we went basically through a circular path that has now brought us back to understanding tomography better. We use this to basically define systems of linear equations.
And basically talked about the most important algorithm from Module 1 which is Gaussian elimination.
And we talked about how this connects to matrices and vectors and largely linear transformations.
And this basically connected into ideas around inversion of these linear transformations as well as linear dependence and independence.
From here, this is also obviously connected to these transformations. All of this is depending on matrix multiplication.
This allows us to better understand vector spaces, define them, talk about column space, null space, and finally, eigenspaces and determinants.
And these are connected to steady states for systems and dynamical system in particular.
And this understanding of eigenvalues and eigenvectors and how they're connected to steady states basically allows us to go back and say, well, which matrices do we want to have as masking matrices?
Which matrices — is just being invertible good enough or can we do better?
And what we've just argued here, and you will prove rigorously in your homework, that there are some matrices that are better than others in terms of being masking matrices.
If you have basically large eigenvalues for your masking matrix, you will actually do better imaging.
And the goal of this entire module is basically to think about these smaller, conceptual blocks and put them together.
And one of the main things we try to do throughout this was introduce you to these ideas of proofs. Basically taking little building blocks and putting them together.
And in Module 2, this is exactly what you're going to be picking up on and building on, because Module 2 is all about design.
What you're going to try and think about is how to take simple components and put together something that can actually interact with the real world.
And this is basically where in the second lab sequence, you're going to be building an actual touchscreen. So when you think about a machine learning pipeline, what does this pipeline involve?
You gotta take data from the real world, build a model, and then analyze it.
And so the second module is really thinking about how do you design some of these physical components to do that?
In Module 3, will come back to talk about how can you take this information to build predictors, to learn from data, and how do you build simple machine learning modules?
So after this lecture, I'm going to be passing off to Professor Boser, and I will be back for lecture starting in Module 3. But good luck on your midterm, and see you on Thursday.
[APPLAUSE]
Đă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.