Transcript

Okay, here's the last lecture in the chapter on orthogonality. So, we met orthogonal vectors, two vectors. We met orthogonal subspaces like the row space and null space. Now, today we meet an orthogonal basis and an orthogonal matrix. So, we really this is This chapter cleans up orthogonality. And really, I want to I should use the word orthonormal. Ortho- orthogonal is So, my vectors are Q1, Q2 up to QN. Can I use the letter Q here for to remind me I'm talking about orthogonal things. Not just any vectors, but orthogonal ones. So, what does that mean? That means that every Q is orthogonal to every other Q.

It's a natural idea to have a basis that's got that's headed off at 90° angles. The inner products are all zero. Of course, if Q is Certainly, QI is not orthogonal to itself. But, there we'll make the the best choice again, make it a unit vector. Then, QI transpose QI is one. For a unit vector, the length squared is one. And that's what I would use the word normal. So, ortho for this part, normal normalized unit length for this part. Okay. So, first part of the lecture is How does having an orthonormal basis make things nice? It certainly does. It makes all the calculations better. A whole lot of numerical linear algebra is built around working with orthonormal vectors cuz they never get out of hand.

They never overflow or underflow. And I'll put them into a matrix Q. And then the second part of the lecture will be suppose my basis my my columns of A are not orthonormal. How do I make them so? And the two names associated with that simple idea are Gram and Schmidt. So the first part is we've got a basis like this. Let's put those Let's put those into a the columns of a matrix. So So uh So a matrix Q that has I'll put these orthonormal vectors Q1 will be the first column. QN will be the the nth column. And I want to say I want to write this property QI transpose QJ being zero. I want to put that in a matrix form.

And just the right thing is to look at Q transpose Q. So this chapter has been looking at A transpose A. So it's natural to look at Q transpose Q and the beauty is it comes out perfectly. Cuz Q transpose has these vectors in its rows. The first row is Q1 transpose. The nth row is QN transpose. So that's Q transpose. And now I want to multiply by Q. That's as Q1 along to QN in the columns. That's Q. And what do I get? You really this is the first simplest most basic fact that how do orthonormal vectors orthonormal columns in a matrix What happens if I compute Q transpose Q? Do you see it? If I take the first row times the first column, what do I get?

A one. If I take the first row times the second column, what do I get? Zero. That's the orthogonality. The first row times the last column is zero. And so I'm getting ones on the diagonal and I'm getting zeros everywhere else. I'm getting the identity matrix. You see how that's it's just like the right calculation to do. If you have ortho orthonormal columns and the matrix doesn't have to be square here. We might have just two columns. And they might have four lots of components. So but they're orthonormal and when we do Q transpose times Q, that Q transpose times Q or A transpose A just asks for all those dot products.

Rows times columns. And in this orthonormal case, we get the best possible answer, the identity. Okay. So this is this is like So I mean now now we have a new bunch of important matrices. What have we seen previously? We've seen in the in the distant past we had triangular matrices, diagonal matrices, permutation matrices. That was early chapters. Then we had row echelon forms. Then in this chapter, we've already seen projection matrices. And now we're seeing this new class of matrices with orthonormal columns. That's a very long expression. I am sorry that I can't just call them orthogonal matrices.

But that word orthogonal matrices, or or maybe I should be able to call it orthonormal matrices. Why don't we call it orthonormal matrix? I mean, that would be a absolutely perfect name for Q. Call it an orthonormal matrix because its columns are orthonormal. Okay, but the convention is that we only use that name orthogonal matrix. We only use this this word orthogonal. We don't even say orthonormal for some unknown reason. Matrix when it's square. So in this in the case when this is a square matrix, that's the case we call it an orthogonal matrix. And what's what's special about the case when it's square?

When it's a square matrix, we've got its inverse. So So in the case if Q is square, then Q transpose Q equals I tells us Let me write that underneath. Tells us that Q transpose is Q inverse. There we have the easy-to-remember property for a square matrix with orthonormal columns. That I need to write some examples down. Let's see. Uh some examples, like if I take any permutation so examples. Let's do some examples. Any permutation matrix. Let me take just some random permutation matrix. Permutation. Q equals, let's say, I'll make it 3 by 3. Say 0 0 1, 1 0 0, 0 1 0. Okay. That certainly has unit vectors in its columns.

Those vectors are certainly perpendicular to each other. And if I figure And so that's it. That makes it a Q. And if I multiply if I took its transpose, if I multiplied by Q transpose, shall I do that? Let me stick in Q transpose here. Just to do that multiplication once more. Transpose it'll put the put make that into a column, make that into a column, make that into a column. And the transpose is also another Q, another orthonormal matrix. And when I multiply that product, I get I. Okay. So there's an example. And actually, there's a second example. But those are really easy examples, right?

I mean, to get orthogonal matrix orthogonal columns by just putting ones in different places is like too uh easy. So, let me keep going with examples. So, here's another simple example. cos theta sin theta There's a unit vector. Oh, let me even take it Well, yeah. cos theta sin theta and now the other way I want sin theta cos theta but I want the inner product to be zero. And if I put a minus there, it'll do it. So, the that's a unit vector. That's a unit vector. And if I take the dot product, I get minus plus zero. Okay. For So, for example, uh Q equals say 1 1 1 -1 Is that an orthogonal matrix?

I've got orthogonal columns there, but it's not quite an orthogonal matrix. How shall I fix it to be an orthogonal matrix? Well, what's the length of those column vectors? The dot product with themselves is Right now, it's two, right? The The length squared. The length squared would be 1 + 1 would be 2. The length would be square root of 2. So, I better divide by square root of 2. Okay. So, there's a There's Now, I have got an orthogonal matrix. In fact, it's this one when when theta is pi over 4. The cosines and Well, almost. I guess the minus sign is down there. So, maybe I don't know. Maybe minus pi over 4 or something.

Okay. Oh, let me do one final example just to show that you You get bigger ones. Uh Q equals Let me take that matrix up in the corner. And I'll sort of repeat that pattern. Repeat it again. And then minus it down here. That's one of the world's favorite orthogonal matrices. I hope I got it right. Is it Can you see whether If I take the inner product of one column with another one, let's see. If I take the inner product of that column with that, I have two minuses and two pluses, that's good. When I take the inner product of that with that, I have a plus and a minus, a minus and a plus, good. I think it all works out.

And what do I have to divide by now to make those into unit vectors? Right now, those those the vector 1 1 1 1 has length two. Square root of four. So, I have to divide by two to make it unit vector. So, there is another. That's my entire array of simple examples. This This uh This construction is named after a guy called Hadamard. And uh We know how to do it for for two, four, 16, 64, and so on. But uh we Nobody knows what what exactly which size matrices have which size which sizes allow orthogonal matrices of ones and minus ones. So, a Hadamard matrix is an orthogonal matrix that's got ones and minus ones.

And a lot of ones some we know, some other sizes or couldn't be a 5 by 5, I think. But there are some sizes that nobody yet knows whether there could be or can't be a a matrix like that. Okay. You see those orthogonal matrices. Now, let me ask what why is it good to have orthogonal matrices? What calculation is made easy? Uh if I have an orthogonal matrix. And and let me let me remember that the matrix could be rectangular. So I put down a I better put a rectangular example down. So these were all square examples. Can I put down just a a rectangular one just to be sure that we realize that this is possible.

Uh let's help me out. Let's see if I put like uh um a 1 2 2 and minus 2 minus 1 2. That's an that's an that's a matrix. Oh, its columns aren't normalized yet. I always have to remember to do that. I always do that last cuz it's easy to do. What what's the length of those columns? So if I wanted them if I wanted them to be length one, I should divide by their length, which is so I look at 1 squared plus 2 squared plus 2 squared. That's 1 and 4 and 4 is 9. So I take the square root and I need to divide by 3. Okay. So there is Well, without that, I've got one orthonormal vector. I mean just one unit vector.

Now, put that guy in. Now, I have a basis for the column space for a two-dimensional space. An orthonormal basis, right? These two columns are orthonormal. They would be an orthonormal basis for this two-dimensional space that they span. Orthonormal vectors, by the way, have got to be independent. It's easy to show that orthonormal vectors since they're headed off at all at 90°, there's no combination that gives zero. Uh now, if I wanted to create now a third one, uh I could either just put in some third vector that was independent and go to this Gram-Schmidt calculation that I'm going to explain, or I could be inspired and say, "Look, that with that pattern, why not put a one in there and a two in there and a two in there and try to fix up the signs so that they worked." Hmm.

I don't I don't know if I've done this too brilliantly. Uh how Let's see, what signs? That's minus. Maybe I'd like a minus sign there. How would that be? Um yeah, maybe that works. I think that those three columns are orthonormal. And they the beauty of this This is the last example I'll probably find where there's no square root. The The punishing thing in Gram-Schmidt, maybe we better know that in advance, is that because I want these vectors to be unit vectors, I'm always running into square roots. I'm always dividing by lengths and those lengths are square roots. So you'll see as soon as I do a Gram-Schmidt example, square roots are going to show up.

But here are some examples where we did it without any square root. Okay. Okay. So So great. Now next question is what's the What's the good of having a Q? What what form what formulas become easier? Suppose I want to project So suppose Q Suppose Q has orthonormal columns. I'm I'm I'm using the letter Q to mean this. I'll write it this this one more time, but but I always mean when I write a Q, I always mean that it has orthonormal columns. So suppose I want to project onto its column space. So what's the projection matrix? What's the projection matrix if I project onto a column space? Okay, that gives me a chance to review the projection section and including that big formula which used to be have four those four A's in a row, but now it's got Q's because I'm projecting onto the column space of Q.

So do you remember what it was? It's Q inverse Q transpose. That's my four Q's in a row. But, what's good here? What what makes this formula nice if I'm projecting onto a column onto a column space when I have orthonormal basis for that space? What makes it nice is this is the identity. I don't have to do any inversion. I just get QQ transpose. So, QQ transpose is a projection matrix. Oh, I can't help I can't resist just checking the properties. What What are the properties of a projection matrix? There There are two properties to know for for any projection matrix. And I'm saying that this is the right projection matrix when we've got this orthonormal basis in the columns.

Okay. So, there's the projection matrix. Suppose the matrix is square. First Just tell me first this extreme case. If If my matrix is square and it's got these orthonormal columns, then what's the column space? If I have a square matrix and I have independent columns and even orthonormal columns, then the column space is the whole space, right? And what's the projection matrix onto the whole space? The identity matrix. If I'm projecting in the whole space, I every every vector B is right where it's supposed to be and I don't have to move it by projection. So, this would be this will be I. This is This is I'll put in parentheses.

This is I if Q is square. Well, that we we said that already. If Q If Q is square, that's the case where Q transpose is Q inverse. We can put it on the right. We can put it on the left. We always get the identity matrix if it's square. But, if it's not a square matrix, then it's not. We don't get the identity matrix. We This we have Q Q Q Q transpose. And just again, what are those two properties of a projection matrix? First of all, it's symmetric. Okay, no problem. That's for certainly a symmetric matrix. So, what's that second property of a projection? That if you project and project again, you don't move the second time.

So, the other property of a projection matrix should be that Q Q transpose twice should be the same as Q Q transpose once. That's projection matrices. And that property better fall out right away because from from the from the fact we know about orthonormal matrices, Q transpose Q is I. Okay, you see it. In the middle here is sitting Q Q Q transpose Q. Sorry, that's what I meant to say. Q transpose Q is I. So, that's sitting right in the middle. That cancels out to give the identity. We're left with one Q Q transpose, and we're all set. Okay. So, this is the projection matrix. A- All the All the uh equation All the messy equations of this chapter become trivial when our matrix when we have this orthonormal basis.

I mean, what do I mean by all the equations? Well, the most important equation was the normal equation. You remember old A transpose A X hat equals A transpose B. But now now A is Q. Now I'm thinking I have Q transpose Q X hat equals Q transpose B. And what's good about that? What's good is that matrix on the left side is the identity. The matrix on the left is the identity. Q transpose Q. Normally it isn't. Normally it's that matrix of inner products and you've got to compute all those dopey inner products and and and solve the system. Here, the inner products are all one or zero. This is the identity matrix.

It's gone. And there's the answer. There's no inversion involved. Each component of X is a Q times B. What what that what that equation is saying is that the ith component is the ith basis vector times B. That's the that's the simple probably the most important formula in in some major parts of mathematics. That if we have orthonormal basis then the component in the in the ith along the ith, the projection on the ith basis vector is just Qi transpose B. That that that that that number X that we look for is is just a dot product. Okay. Okay, so I'm ready now for the sort of like second half of the lecture where we don't start with an orthogonal matrix or orthonormal vectors.

We just start with independent vectors and we want to make them orthonormal. So I'm going to Can I do that now? Now, here comes Gram-Schmidt. So so Gram-Schmidt. So this is a calculation. I won't say I can't quite say it's like uh elimination because it's it's different. Our our goal isn't triangular anymore. With elimination, our goal was make the matrix triangular. Now our goal is make the matrix orthogonal. Make those columns orthonormal. So let me start with two columns. So I start with vectors A and B. And they're just like here, let me draw them. Here's A. Here is B. For for example. A isn't specially horizontal, wasn't meant to be.

Just A is one vector, B is another. I want to produce Tho- Those two vectors, they might be in 12-dimensional space or they might be in two-dimensional space. They're independent anyway. So I I I I better be sure I say that. I started with independent vectors. And I want them produce out of that Q1 and Q2. I want to produce orthonormal vectors. And Gram and Schmidt tell me how. Okay. Well, actually you could tell me how. I We don't need Frankly, I don't know. The There's only one idea here. If the Gram had the idea uh I don't know what Schmidt did. But uh Okay. Let's We'll see it. You We don't need either of them actually.

Okay. So, what am I going to do? I'll take that this first guy. Okay. Well, he's fine. That direction is fine except Yeah, I I I'll say okay. I'll settle for that direction. So, I I'm going to I'm going to get So, what am I going to My goal is I'm going to get orthogonal vectors. And I'll call those capital A and B. So, that's the key step is to get from any two vectors to two orthogonal vectors. And then at the end, no problem. I'll get orthonormal vectors. How will What will those Those will be my Qs, Q1 and Q2. And what will they be? Once I've got A and B orthogonal well, look. It's no big deal.

Maybe that's what Schmidt did. He brilliant Schmidt thought, "Okay, divide by the length." All right. That's Schmidt's contribution. Okay. But Graham had a little more thinking to do, right? We haven't done Graham's part. This part except okay, I'm happy with A can be A. That that first direction is fine. Why should no complain about that? The trouble is the second direction is not fine cuz it's not orthogonal to the first. I'm looking for a vector that starts with B but makes it orthogonal to A. What's the vector? How do I do that? How do I produce from this vector a piece that's orthogonal to this one?

And the remember these vectors might be in two dimensions or they might be in 12 dimensions. I'm just looking for the idea. So what's the idea? I Where did we have orthogonal a vector showing up that was orthogonal to this guy? Well, that was the first basic calculation of the whole chapter. We We did a projection and the projection gave us this part which was the part in the A direction. Now, the part we want is the other part, the E part. The this part. This is going to be our This is This is That guy is that guy. This is our vector B that's that gives us that 90° angle. So B is you could say B is really what we previously called E.

The the the error vector. And And so and is it? I mean, what do I what is B here? A A is A, no problem. B is Okay, what's this what's this error piece? Do you remember? It's It's I start with the original B and I take away what? It's projection, this P. This the vector B, this error vector, is the original vector removing the projection. So, instead of wanting the projection, now that's what I want to throw away. I want to get the I want to get the part that's perpendicular. And there will be a perpendicular part, it won't be zero. Because these vectors were independent, so so B what if B was along the direction of A, then if the original B and A were in the same direction, then I'm I've only got one direction.

But here they're in two independent directions, and all I'm doing is getting that guy. So, what's its formula? What's the formula for that? If I If I'm I'm I want to subtract the projection. So, do you remember the projection? It's some multiple of A. And what's that multiple? It's It's that thing we called X in the very very first lecture on this chapter. There's an A transpose A in the bottom. And there's an A transpose B, isn't that it? I think that's Gram's formula. Or Gram-Schmidt. No, that's Gram. Schmidt has got to divide the whole thing by the length. So, he his formula makes a mess which I'm not willing to write down.

So, let's just see that What am I saying here? I'm saying that this vector B is perpendicular to A. That these are orthogonal. A is perpendicular to B. Can you check that? How How do you see that? Yes, of course we Our picture is telling us yes, we did it right. How would I check that this matrix is perpendicular to A? I would multiply by A transpose and I better get zero, right? I should I should check that. A transpose B should come out zero. So, this is A transpose times Now, what did we say B was? We start with the original B and we take away this projection. And that should come out zero.

Well, here we get an A transpose B. Minus And here is another A transpose B and the and it's an A transpose A over A transpose A a one, those cancel, and we do get zero. Right. Now, I guess I can do numbers in there. But I have to take a third vector to be sure we've got this system down. So, now I have to say if I have independent vectors A, B, and C, I'm looking for orthogonal vectors A, B, and capital C, and then of course the third guy will just be C over its length. The unit vector. So, this is now the problem. I I got B here. I got A very easily. And now if you see the idea, we could figure out a formula for for C.

So, we So, now that So, this is like a typical homework quiz problem. I give you two vectors, you do this. I give you three vectors and you have to make them orthonormal. So, you do this again. The first vector is fine. The second vector is perpendicular to the first. And now I need a third vector that's perpendicular to the first one and the second one. Right? That's that's This is the end of the the lecture is to find this guy. Find this vector this vector C that's perpendicular At this point, we know A and B. But C, the little C that we're given, is off in some uh it's come it's got to come out of the blackboard to be independent.

So, so can I sort of draw off Off comes a C somewhere. I don't know. Where am I going to put the darn thing? Maybe I'll put it off Oh, I don't know. Like that. Somehow. C. Little C. And I already know that perpendicular direction that one and that one. So, now what's the idea? Give me the Gram-Schmidt formula for C. What is this C here? Equals what? What am I going to do? I'll start with the given one. As before. Right? I start with the vector I'm given. And what do I do with it? I want to remove out of it. I want to subtract off so I'll put a minus sign in. I want to subtract off its components in the A capital A and capital B directions.

I just want to get those out of there. Well, I know how to do that. I did it with B, so I'll just So let me let me take away What if I do this? What have I done? I've I've got little C and what have I subtracted from it? Its component its projection if you like in the A direction. And now I've got to subtract off its component B transpose C over B transpose B that multiple of B is its component in the B direction. And that gives me the vector capital C that if anything is if there's any justice this C should be perpendicular to A and it should be perpendicular to B. And the only thing it's hasn't got is unit vector, so we divide by its length to to to get that too.

Okay. Let me do uh an example. Can I Let me I'll make my life easy. I'll just take two vectors. So let me do a numerical example. If I'll give you two vectors, you give me back the Gram-Schmidt orthonormal basis, and we'll see how to express that in matrix form. Okay. So, let me give you the two vectors. So, So, I'll take the vector A equals, let's say, 1 1 1. Why not? And B equals, let's say, 1 0 2, okay? I just I didn't want to cheat and make them orthogonal in the first place, cuz then Gram-Schmidt wouldn't be needed. Okay, so those are not orthogonal. So, what is capital A? Well, that that's the same as big A.

That was fine. What's B? So, B is this B is the original B, and then I subtract off some multiple of the A. And what's the multiple? What goes in here? B Here's the Here's the A. This is the This is the little B. This is the big A, also the little A. And I I want to multiply it by that right that right ratio, which has A transpose A. Oh. Here's my ratio. I'm just doing this. So, it's A transpose B. What is A transpose B? It looks like three. And what is A Oh my What's A transpose A? Three. I'm sorry. I didn't know that was going to happen. Okay, but it happened. Why should we knock it? Okay, so so do you see it all right?

That's A transpose B. There's A transpose A. That's the fraction. So So I take this away and I get 1 take away 1 is a 0. 0 minus this 1 is a minus 1 and 2 minus the 1 is a 1. Okay. And what's this vector that we finally found? This is B. And how do I know it's right? How do I know I've got a vector I want? I check that B is perpendicular to A and B are perpendicular. That A is perpendicular to B. Just look at that. That one the dot product of that with that is zero. Okay. So now what is my Q1 and Q2? Why don't I put them in a matrix? Of course, since I'm always putting these So the Q I'll put the Q1 and the Q2 in a matrix and what are they?

Now, when I'm writing Q's, I've I've I'm supposed to make things normalized. I'm supposed to make things unit vectors. So I'm going to take that A, but I'm going to divide it by square root of 3. And I'm going to take this B, but I'm going to divide it by square root of 2. To make it a unit vector. And there is my matrix. That's my matrix with orthonormal columns coming from Gram-Schmidt and it sort of it it came from the original 1 1 1 1 0 right? That was my original, guys. These were the two I started with. These are the two that I'm happy to end with because those are orthonormal. So, that's what Gram-Schmidt did.

It and Well, tell me about the column spaces of these matrices. How is the column space of Q related to the column space of A? So, I'm always asking you things like this and that makes you think, "Okay, the column space is all combinations of the columns." It's that plane, right? I've got two vectors in three-dimensional space. Their column space is a plane. The column space of this matrix is a plane. What's the relation between the planes? Between the two column spaces. They're one in the same, right? It's the same column space. I didn't All I'm taking is here this B thing that I computed, this B thing that I computed, is a combination of B and A.

It and A was little A. So, I'm always working here with this in the same space. I'm just like getting 90° angles in there. Where my original column space had a perfectly good basis, but it wasn't as good as this basis cuz it wasn't orthonormal. Now, this one is orthonormal and I have a basis then that for So, now projections, all the calculations I would ever want to do are are a cinch with this orthonormal basis. One final point. One final point in this chapter. And it's the is it's just like elimination. We we we learn how to do elimination, we know all the steps, we can do it. But then I came back to it and said look at it as a matrix.

In matrix language, and elimination gave me what what was elimination in matrix language? I'll just put it up there. A was LU. That was matrix that was elimination. Now, I want to do the same for Gram-Schmidt. Everybody who works in linear algebra isn't going to write out the columns are orthogonal or orthonormal and isn't going to write out these formulas. They're going to write out the connection between the matrix A and the matrix Q. And the two matrices have the same column space, but there's some those some matrix is taking and I'm going to call it R. So, A equals QR is the magic uh formula here.

It's the expression of Gram-Schmidt. And uh let me just let me just uh capture that. So, that's the my final step then is A equal QR. Maybe I can squeeze it in here. So, A has columns, let's say A1 and A2. Let me suppose N is two, just two vectors. Okay. So, that's some combination of Q1 and Q2. And times some matrix R. They have the same column space. This is just this matrix just includes in it whatever these numbers like three over three and one over square root of three and one over square root of two. Probably that's Probably that's what it's got. One over square root of three and one over square root of two, something there.

But actually, it's got a zero there. So, the the the main point about this A equal QR is this this R turns out to be upper triangle. It turns out that this zero is upper triangle. I could We could see why. Let me see. I can put in general formulas for what these are. This I think in here should be the inner product of A1 with Q1. And this one should be be the inner product of A1 with Q2. And that's what I believe is zero. And this will be something here and this will be something here with uh inner A1 transpose Q2. Sorry. A2 transpose Q1 and A2 transpose Q2. But why is that guy zero? Why is A1 Q2 zero?

That's the That's the key to this being this R here being upper triangular. You know why A1 Q2 is zero because A1 that was my This was This really A and B here. This was really A and B. So, this is A transpose Q2. And the whole point of Gram-Schmidt was that we constructed these later Qs to be perpendicular to the earlier vectors. To the earlier all the earlier vectors. So, that's why we get a triangular matrix. The the So, the it's the result is extremely satisfactory. That orthog- that if I have a matrix with independent columns, the Gram-Schmidt produces a matrix with orthonormal columns, and the connection between those is a triangular matrix.

That last point, that the connection is a triangular matrix, please look in the book. You have to see that one more time. Okay, thanks. That's great.