Transcript

Okay, good. The final class in linear algebra at MIT this fall is to review the whole course. And you know the best way I know how to review is to take old exams and just think through the problems. So it'll be a 3-hour exam next Thursday. Uh anybody who's got I mean nobody will be able to take an exam before Thursday. Anybody who needs to take it in some different way after Thursday should see me next Monday. I'll be in my office Monday. Okay. Shall may I just read out some problems and uh I'll let me bring the board down. And let's start. Okay. Here's a question. This is a this is about and a 3 by n matrix.

And we're given so we're given given Ax equals 100 has no solution. And we're also given Ax equals 010 has exactly one solution. Okay. So you can you can probably anticipate my first question. What can you tell me about m? It's it's an m by n matrix of rank r as always. What can you tell me about those three numbers? So what can we tell me about m? The number of rows and the number of columns and r the rank. Okay. See, do you want to tell me first what m is? How many rows in this matrix? Must be three, right? We can't tell what n is, but we can certainly tell that m is three. Okay. And what do we know about um So what do these things tell us?

Let's take them one at a time. When when this when I do discover that some equation has no solution that there's some right-hand side with no answer. What does that tell me about the rank of the matrix? It's smaller than it it it's smaller than m. Is that right? That this if if there's no solution, that would tells me that the rank that the that some rows of the matrix are combinations of other rows. Because if if if I had a pivot in every row then I would certainly be able to solve the system. I would have particular solutions and all all the good stuff. So if if anytime that that there's a system that has with no solutions, that tells me that r must be below m.

What about uh the fact that if when there is a solution, there's only one? What does that tell me? Well, normally there'd be one solution and then we could add anything in the null space. So this is telling me the null space only has the zero vector in it. There's just that there's just one solution period. So what does that tell me? The null space has only the zero vector in it. That tells me what does that tell me about the relation of r to n? So this is one solution only. That means the null space of the matrix must be just the zero vector. And what does that tell me about r and n? They're equal.

The columns are independent. So I've got now r equal n and r less than m and now I and I also know m is three. So those are really the facts I know. N equals r and those numbers are smaller than three. Uh sorry, yeah. Yeah, r is smaller than m and n of course is also. So I guess this summarizes what we can tell. In fact, why not give me a matrix? Cuz I would often ask for an example of such a matrix. Can you give me a matrix A that that's an example that shows this shows this possibility that exactly that? That that there's no solution with with that right-hand side, but there's there's exactly one solution with this right-hand side.

Anybody want to suggest a matrix that that that does that? Let's see. What do I what vector do I want in in the column space? I want 010 to be in the column space because I'm I'm able to solve for that. So let's put 010 in the column space. Actually, I could stop right there. That would be a matrix with m equal three, three rows and n and r are both one. Rank one. One column. And of course there's no solution to that one. So that's perfectly good as it is. Or if you kind of have a prejudice against matrices that only have one column, I'll I'll accept a second column. So what could I have included as a second column that would just be a different answer, but equally good?

Uh I could put this vector in the column space too if I wanted. That would now be a case with r equal n equal two. But of course three m m is still three and this vector is not in the column space. So you're this is just like prompting us to remember all those things. Column space, null space, all that stuff. Now I probably asked second question about this type of thing. Uh Okay. Oh, I even asked write down an example of a matrix that fits the description. Um hm. I guess I haven't learned anything in uh 26 years. Okay. Uh Cross out all statements that are false about any matrix with these So again, these are this is the preliminary state These are the facts about my matrix.

This is one example, but of course by having an example it'll be easy to check some of these facts or non-facts. Let me uh let me write down some facts. Some some possible facts. True So this is really true or false. The determinant uh this is part one. The determinant of A transpose A is the same as the determinant of AA transpose. Is that true or not? Second one. A transpose A is invertible. Is invertible. Third possible fact. AA transpose is positive definite. So you see how on an exam question I try to connect the different parts of the course. So well I mean the simplest way would be to try it with that matrix as a as a as a good example.

Uh but maybe we can answer uh even directly. Let let me take number two first. Cuz I'm you know I'm very very fond of that matrix A transpose A. And when is it invertible? When is the matrix A transpose A invertible? The The great thing is that I can tell from the from the rank of A that I don't have to multiply out A transpose A. A transpose A is invertible well if A has a null space other than the zero vector, then it it's no way it's going to be invertible. But the beauty is if the null space of A is just the zero vector. So the fact the key fact is this is invertible if r equals n. By which I mean independent columns.

Of A. In A. In the matrix A. If r equals n, if the matrix A has independent columns, then this combination A transpose A is square and still that same null space, only the zero vector, independent columns, all good. And so what's the what's the true false? Is it Is this middle one T or F for this in this setup? Well, we discovered that we discovered that that R was N from that second fact. So this is a true. That's a true. And of course, A transpose A in this example would probably be What would A transpose A be for that matrix? Can you multiply A transpose A and see what it looks like for that matrix?

What shape would it be? It'll be 2 by 2. And what matrix will it be? The identity. So checks out. Okay, what about AA transpose? Well, depending on the shape of A, it could be good or not so good. It's always symmetric, it's always square, but what's the size now? This is 3 by N and this is N by 3. So the result is 3 by 3. Is it positive definite? I don't think so. False. If I multiply that by A transpose, AA transpose, what would the rank be? It would be the same as the rank of A. That's that's It would be just rank two. And if it's 3 by 3 and it's only rank two, it's certainly not positive definite.

So what's What What could I say about AA transpose if I wanted to like say something true about it? It's true that it is positive semi-definite. If I made this semi-definite, it would always be true, always. But if I'm looking for positive definite, then I'm looking at the null space of whatever's here and in this case uh it's got a null space. So AA So we just figure it out here. AA transpose for that matrix will be 3 by 3. If I multiplied A by A transpose, what would the first row be? All zeros, right? First row of AA transpose could only be all zeros. So it's probably a one there and a one there or something like that, but uh I don't even know if that's right.

But it's all zeros there, so it's certainly not positive definite. Let me not put up anything I'm not don't check. What about this determinant? Oh, well, I guess that's a sort of tricky question. Is it true or false in this case? It's false, apparently. Because A transpose A is invertible, we just got a true for this one and we got a false We got a We got a non-invertible one for this one. So actually, this one is false. Number one. That surprises us, actually, because it's I mean Why was it tricky? Because what is true about determinants? This would be true if those matrices were square. If I have two square matrices, A and any other matrix B, could be A transpose, could be somebody else's matrix, then it would be true that the determinant of BA would equal the determinant of AB.

But if the matrices are not square, and it would actually be true that it would be that would equal that this would equal the determinant of A times the determinant of A transpose. We could even split up those two separate determinants, and of course, those would be equal. But only when A is square. So that's just that's a question that rests on the the falseness rests on the fact that the matrix isn't square in the first place. Okay, good. Um let's see. Uh Oh, now even asks more. Prove that A transpose Y = C Ha, God, it's this question goes on and on. Um Now I ask you about A transpose Y = C.

So I'm asking you about the equation about the matrix A transpose. And I want you to prove that it has at least one solution. One solution for every C, every right-hand side C. And in fact in fact infinitely many solutions for every C. Okay. Well, none of this is difficult, but it's been uh a little while. So we just have to think again. When I have a system of equations, this is this matrix A transpose is now, instead of being 3 by N, it's N by 3. It's It's N by M, of course. To show that a that a system has at least one solution, What When does a When does a system When is the system always solvable?

When it has full row rank, when the rows are independent. Here we have N rows and that's the rank. So at least one solution because because the number of rows, which is N for the transpose, is equal to R, the rank. This This has This A transpose has independent rows because A had independent columns, right? The original A had independent columns. When we transpose it, it has independent rows, so there's at least one solution. But now, how do I even know that there are infinitely many solutions? Well, I I What do I I want to know something about the null space. What's the dimension of the null space of A transpose?

So So the answer has got to be the dimension of the null space of A transpose. What's the general fact if if it's an If I have If A is an M by N matrix of rank R, what's the dimension of A transpose? Of the null space of A transpose? You remember that little fourth subspace that's tagging along down in our big picture? Its dimension was M minus R. And that's bigger than zero. M is bigger than R. So there's a lot in that null space. So there's always one solution because any This is speaking about A transpose. So for A transpose, the roles of M and N are reversed, of course. So I'm Keep Keep in mind that that this board was about A transpose, so the roles So it's the null space of A transpose and there are M minus R free variables.

Okay, that's like just some uh review. Can I take another problem that's also sort of Suppose the matrix A has three columns, V1, V2, V3. Those are the columns of the matrix. All right. Question A. Solve AX = V1 - V2 + V3. Tell me what X is. Well, there you're seeing the most the one absolutely essential fact about matrix multiplication. How does it work when it when we do it a column at a time? The very very first day, way back in September, we did multiplication a column at a time. So what's what's X? Just tell me. 1 minus 1 1. Thanks. Okay. Everybody's got that. Okay? Then the next question is, suppose that combination is zero.

Oh, yeah. Okay, so question B says Part B says Suppose this thing is zero. Suppose that's zero. Then the solution is not unique. Suppose No. So I want true or false and a reason. Suppose this this combination is zero. V1 minus V2 V3 Show that What kind of what does that tell me? So it's a separate question. Maybe I I sort of save time by writing it that way, but it's a separate totally separate question. If I know if I have a matrix and I know that column 1 minus column 2 plus column 3 is zero. What does that tell me about whether the solution is unique or not? If if is there are there are there is there more than one solution?

What you What is uniqueness about? Uniqueness is about is there anything in the null space, right? The solution is unique when there's nobody in the null space except the zero vector. And if that's zero then this guy would be in the null space. So so then So if this were zero then then this X is in the null space of A. So solutions are never unique. Because I could always add that to any solution. And it and AX would wouldn't change. So So it's always that question. Is there somebody in the null space? Okay. Third Oh, now here's a totally different question. Suppose those three vectors V1 V2 V3 are orthonormal.

So that's I mean they This isn't going to happen for orthonormal vectors. Okay, so part C Forget part B. C If V1 V2 V3 are orthonormal. orthonormal So that I would usually have called them Q1 Q2 Q3. Now what combination Oh, here's a nice question. If I say so myself. What combination of V1 and V2 is closest to V3? What point on the plane of V1 and V2 is the closest point to V3 if these vectors are orthonormal? So let me I'll start the sentence. Then the combination something times V1 plus something times V2 is closest is the closest combination to V3. And what's the answer? What's the What's the closest vector on that plane to V3?

zeros right We just imagine the XYZ axis the V V1 V2 V3 could be the standard basis. the XYZ vectors And of course the point on the XY plane that's closest to the to V3 on the Z axis is zero. So So if we're orthonormal then the projection of V3 onto that plane is it's it's perpendicular it it hits right at zero. Okay, so that's that's like a quick quick you know easy question but still brings it out. Okay. Let me see what um Shall I write down a a Yeah. a Markov matrix Tell and I'll I'll ask you for its eigenvalues. Okay. Here's a Markov matrix. this this and uh tell me its eigenvalues. So here I'll call the matrix A and I'll call the this is .2 .4 .4 .4 .2 .4 .3 .3 .4 Okay.

Let's see. It helps out by to notice that column 1 plus column 2 What's What's interesting about column 1 plus column 2? It's twice as much as column 3. So column 1 plus column 2 equals 2 times column 3. I I put that in there. Column 1 plus column 2 equals twice column 3. That's a observation. Okay, I want to I tell me the eigenvalues of the matrix. Okay, tell me one eigenvalue. zero because the matrix is singular. Tell me another eigenvalue. one because it's a Markov matrix the columns add to the all ones vector and uh that will be a eigenvector of A transpose. And tell me the third eigenvalue.

Let's see. To make the trace come out right which is .8 we need minus .2. Okay. Okay. And now suppose I start the Markov process. Suppose I start with a a mate with U of zero. So I'm going to look at the I'm going to look at the powers of A applied to U of zero. This is this is UK. And there's my matrix and I'm going to let U of zero be This is going to be 0 10 0. And I I want it My question is what does that approach? If If U of zero is equal to this If there is U of zero, shall I write it in? Maybe I just write in U of zero. A to the K starting with 10 people in state two and every step follows the Markov rule what's the What's the What What is the solution look like after K steps?

Let me just ask you that. And then what happens as K goes to infinity? I This is a steady state question, right? I'm looking for the steady state. Actually the question doesn't ask for the K step answer. It just jumps right away to infinity. But how would I express the solution after K steps? It would be some multiple of the first eigenvalue times the first eigen to the K power times the first eigenvector plus some other multiple of the second eigenvalue times its eigenvector and some multiple of the third eigenvalue times its eigenvector. Okay. Good. And these eigenvalues are zero one and minus .2.

So what happens as K goes to infinity? The only thing that survives the steady state. So at at U infinity this is gone. This is gone. All that's left is C2 X2. So I better find X2. I've got to find that eigenvector to complete the answer. What's the eigenvector that corresponds to lambda equal 1? That's the the key eigenvector in any Markov process is that eigenvector. Lambda equal 1 is an eigenvalue. I need its eigenvector X2. And then I need to know how much of it is in the starting vector U0. Okay, so how do I find that eigenvector? I guess I subtract 1 from the diagonal right so I have minus .8 minus .8 minus .6 and the rest of course is just still .4 .4 .4 .4 .3 .3 and hopefully that's a singular matrix.

So I'm looking to solve A minus I equal the A minus I X equal zero. Let's see. Can anybody spot the solution here? I don't know. I didn't make it easy for myself. um What do you think there? Maybe those since those I'm just thinking aloud here. Those first Let me let me guess. Those first two entries might be Oh, no. What do you think? Any Anybody see it? We could use elimination if we were desperate. Are we that desperate? Anybody just call out if you see the vector here that's in that null space. There better be a vector in that null space or I'm quitting. Uh uh uh Okay. Well, I guess we could use elimination.

Seems It it I thought maybe somebody might see it from further away. Uh You think I Is there a chance that these guys are Could it be that these these two are equal and this is whatever it takes like something like 3 3 2 Would that possibly work? I mean that's great for this. No, it's not that great. 3 3 4 This is uh deeper mathematics you're watching now. 3 3 4 That That That It works. Don't don't mess with it. It works. Uh yeah, okay, it works. All right. And yes, okay. And uh so that takes two 3 3 4. And uh how much of that vector is in is in the starting vector? Well, we could go through We could go through a complicated process, but what's the beauty of Markov things?

That that the total number of the total population that the the the sum of these doesn't change. That the total number of people they're moving around, but they don't do do get born or die or or or get dead. So So there's 10 of them at the start, so there's 10 of them there, so C2 is actually one. Yeah. So that would be the the correct correct solution. Okay. That would be the U infinity. Okay. So I used there in that process sort of the main facts about Markov matrices to uh to get a jump on the uh answer. Okay. Um let me see. Okay, here's some uh kind of quick short questions. Uh maybe I I'll move over to this board and leave that for the moment.

I'm looking for 2 by 2 matrices. And I'll read out the property I want and you give me an example or tell me there isn't such a matrix. All right. Here we go. First, so 2 by 2s. First, I want a project I want the projection projection onto the line through A equals 4 minus 3. So it's a one one D a one dimensional projection matrix I'm looking for. And what's the formula for it? For What's the formula for the projection matrix P onto a line through A and then we'll just plug in this particular A. You remember that formula? There's an A and an A transpose. And we can do Normally we would have an A transpose A inverse in the middle, but here we just got numbers, so we just divide by it.

And then plug in A and we've got it. Okay. So equals You can put in the numbers. Trivial, right? Okay. Number two. The matrix that has eigenvalues zero and so this is a new problem. The matrix with eigenvalues zero and three and eigenvectors Well, let me write these down. Eigenvalue zero eigenvector 1 2 eigenvalue three eigenvector 2 1. I'm giving you the eigenvalues and eigenvectors instead of asking for them. Now I'm asking for the matrix. What's What's the matrix then? What's A? What's Here was a formula then we just put in some numbers. What's the formula here into which we'll just put the given numbers?

It's the S lambda S inverse, right? So it's S which is this eigenvector matrix. It's the lambda which is the eigenvalue matrix. It's the S inverse. Whatever that turns out to be. Let me just leave it as inverse. That has to be it, right? Because if we went in the other direction, that matrix S would diagonalize A to produce lambda. So it's S lambda S inverse. Good. Okay. Ready for number three. A real matrix that cannot be factored into A I I'm looking for a matrix A that doesn't that never could equal B transpose B for any B. A 2 by 2 matrix that could not be factored in the form B transpose B.

So all you have to do is think, well, what does B transpose B look like and then pick something different. What What do you suggest? Uh let's see. What What What should we take for a matrix that could not be could not have this form B transpose B. Well, what do we know about B transpose B? It's always symmetric. So just give me any non-symmetric matrix that couldn't possibly have that form. Okay. And let me ask the fourth part of this question. A matrix that has orthogonal eigenvectors, but it's not symmetric. Tell me a matrix. How could a matrix What matrices have orthogonal eigenvectors, but they're not symmetric matrices?

What other matrices Tell me a different other families of matrices that have orthogonal eigenvectors? We know symmetric matrices do, but but others also. So So I'm looking for orthogonal eigenvectors. And what do you suggest? Uh the matrix could be skew-symmetric. It could be an orthogonal matrix. It could be symmetric, but but that was too easy, so I ruled that out. It could be skew-symmetric like like uh 1 minus 1 like that. Or it could be an orthogonal matrix. It could be an orthogonal matrix like cosine sine minus sine cosine. All those matrices would have complex orthogonal eigenvectors. But they would be orthogonal.

And so those those examples are fine. Okay. We can continue a little longer if you would like to uh um with uh um these from this from this exam. From these exams. Least squares. Okay, here's a least squares problem in which to make life quick, I've given the answer. It's It's like Jeopardy, right? Uh I I just give the answer and you give the question. Okay. Oops, we've uh Sorry, I'll Let's see. Can I stay over here for the for the uh next question. Okay. Least squares. So I'm I'm giving you the problem. 1 1 1 0 1 2 C D equals 3 4 1. And that's B, of course. This is A X equal B. And the least squares solution So may I put C hat D hat to emphasize it's not the true solution has So the least squares solution, maybe I should The hats really go here.

is 11/3 and minus 1. Of course, you could have figured that out in no time. So this year I'll ask you to do it probably. But suppose we're given the answer. Then let's just remember what what happened. What is the Okay. Good question. What's the projection P of this vector onto the column space of that matrix? What's So Should I write that question down? One. What is P the projection? The projection of B onto the column space of A is what? Hopefully, that's what the least squares problem solved. What is it? It's This was the best solution. This It's 11/3 times times column one plus or rather minus one times column two.

Right? That's what least squares did. It found the combination of the columns that was as close as possible to be. That's what least squares was doing. It found the projection. Okay? Secondly, draw the straight line problem that corresponds to this system. So, I guess that the straight line straight line fitting a straight line problem uh we kind of recognize. We recognize these are the heights and these are the points. And so, at 0 1 2, the heights are 3 and at at t equal to 1, the height is 4. 1 2 3 4. And at t equal to 2, the height is 1. So, I'm trying to fit the best straight line through those points.

God. Uh I could fit a triangle very well, but uh uh where is the best I don't even know which way the best straight line goes. Uh maybe it goes Oh, I do know how it goes cuz there's the answer. Yes. Uh it it has it has a height 11/3 and it has slope minus one. So, it's something like that. Okay. Great. Now, finally, and this completes the course. Find a vector a different vector b not all zeros for which the least squares solution would be zero. So, I want you to find a different b so that the least squares solution changes to all zeros. So, tell me what I'm really looking for here. I'm looking for a b where the best combination of these two columns is the zero column.

combination. So, what kind of a vector b am I looking for? I'm looking for a vector b that's orthogonal to those columns. It's orthogonal to those columns. It's orthogonal to the column space. The best possible answer is zero. So, a vector b that's orthogonal to those columns, let's see, maybe maybe uh one of those minus two of those and one of those. That would be orthogonal to those columns and the best vector would be zero zero. Okay. So, that's as many questions as I can do in an hour, but you get three hours. And uh let me just say as I've said by email, um thanks very much for your patience as this series of lectures was videotaped.

And um thanks for filling out these forms. Maybe just leave them on the table up there as you go out. And above all, thanks for taking the course. Thank you. Thanks.

Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

34. Final Course Review