Orthogonal Matrices & Gram-Schmidt | Linear Algebra

[00:00:06]okay here's the last lecture in the chapter on orthogonality so we met orthogonal vectors to 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 us I should use the word orthonormal orthonormal 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 degree angles the inner products are all 0 of course if Q is certainly Q I is not orthogonal to itself but there will make the best choice again make it a unit vector then Qi transpose Qi is 1 for a unit vector the length squared is 1 and that's what I would use the word normal so or so 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 because they never get out of hand they never overflow underflow and I'll put them into a matrix q and then the second part of the lecture will be supposed my bassist Mike my columns of a are not orthonormal how do I make them sell and the two names associated with that simple idea our Graham and Schmidt so the first part is we've got a basis like this let's put those let's put those into the columns of a matrix so and so so a matrix Q that has or I'll put these orthonormal vectors Q 1 will be the first column Q n will be the length column and I want to say I want to write this property Qi transpose Q J being 0 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 because Q transpose has these vectors in its rows the first row is Q 1 transpose the N throw is QN transpose so that's Q transpose and now I want to multiply by Q that has Q 1 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 1 if I take the first Rho 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 noir so normal columns and the matrix doesn't have to be square here we might have just two columns and they might have for 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 ortho normal case we get the best possible answer the identity okay so this is this is like so I mean 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 form x' 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 maybe I should be able to call it worth of normal matrices why don't we call it orthonormal matrices but I mean it would be 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 some examples like if I take any permutation examples let's do some examples any permutation matrix let me take just some random permutation matrix permutation q equals let's say Oh make it 3x3 say 0 0 1 1 0 0 0 1 0 ok that certainly has unit vectors in its columns those vectors are certainly perpendicular to each other and if I figure that's it that makes it a Q and if I multiple if I took its transpose if I multiplied by Q transpose so I do that let me stick in Q transpose here just to do that multiplication once more transpose it will put though 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 real easy examples right I mean to get orthogonal matrices or thuggin or columns by just putting ones in different places is like too easy so let me keep going with examples so here's another simple example cos theta sine theta there is a unit vector oh let me even take it well yeah cos theta sine theta and now the other way I want sine theta cos theta but I want the inner product to be 0 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 0 okay for Excel for example Q equals say 1 1 1 minus 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 to write the the length squared the length squared would be 1 plus 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 at now I have got an orthogonal matrix in fact it's this one when when theta is PI over 4 the cosines inside 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 can get bigger ones 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 so 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 2 square root of 4 so I have to divide by 2 to make it unit vector so there's another that's my entire array of simple examples this this this construction is named after a guy called @mr and we know how to do it 4 4 2 4 16 64 so on but we nobody knows well wait exactly which size matrices have which size which size allow orthogonal matrices of ones and minus ones so Adam our matrix is an orthogonal matrix that's got ones and minus ones and a lot of ones some we know some other sizes there couldn't be a 5x5 I think but there are some sizes that nobody yet knows whether there could be or can't be 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 if I have an orthogonal matrix and let me let me remember that the matrix could be rectangular shall I put down a ring I better put a rectangular example down so these were all square examples can I put down just a rectangular one just to be sure that we realize that this is possible let's help me out let's see if I put like a 1 to 2 and minus 2 minus 1 2 that's an order that's an order that's a matrix oh it's columns aren't normalized yet I always have to remember to do that I always do that last because it's easy to do 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'd look at 1 squared plus 2 squared plus 2 squared that's 1 in 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 1 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 beta 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 degrees there's no combination that gives zero now if I wanted to create now a third one 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 it be inspired and say look that with that pattern why not put a 1 in there and a 2 in there and a 2 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 let's see what signs that's - maybe I didn't like a minus sign there how would that be 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 is 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 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 queue what what form what formulas become easier suppose I want to project so suppose Q suppose Q has orthonormal columns I'm using the letter Q to mean this I'll write at 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 on to 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 including that big formula which used to be have 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 Q transpose Q inverse Q transpose that's my 4 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 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 is 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 every every vector B is a right where it's supposed to be and I don't have to move it by a projection so this would be this will be I this is this is I'll put in parenthesis 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 QQ QQ 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 again you don't move the second time so the other property of a projection matrix should be that QQ transpose twice should be the same as QQ 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 QQ 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 1q q transpose and we're all set okay so this is the projection matrix all that all the 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 1 or 0 this is the identity matrix it's gone and there is 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 ice component is the ice basis vector times B that's the that's the simple that's probably the most important formula in some major parts of mathematics that if we have orthonormal basis then the component in the in the ice along the ice the projection on the ice basis vector is just Qi transpose B that is 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 ortho ortho normal vectors we just start with independent vectors and we want to make them orthonormal so I'm gonna 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 elimination because it's it's different or 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's B for for example a isn't especially horizontal wasn't meant to be just a is 1 vector B is another I want to produce those two vectors they might be in 12 dimensional space or they might be in two dimensional space they're independent anyway so I better be sure I say that I started with independent vectors and I want to produce out of that q1 and q2 I want to produce orthonormal vectors and Graham and Schmitt tell me how okay well actually you could tell me how we don't need frankly I don't know there's only one idea here if the Graham had the idea I don't know what Schmidt yeah but okay let's so you'll see it you know we don't need either of them actually okay so what am I gonna do I'll take that this first guy okay well he's fine that direction is fine except you know I'll say okay I'll settle for that direction so I I'm gonna I'm gonna get so what am I gonna my goal is I'm gonna 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 though those will be my Q's 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 Smith'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 a can be a that first Direction is fine why should no complained about that the trouble is the second Direction is not fine because 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 you remember these vectors might be in two dimensions or they might be in twelve 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 that 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-degree angle so B is you could say B is really what we previously called e the the error vector and and so and what 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 its projection this P this the 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 0 because these vectors were independent so so B what if B was along the direction of a then if the original BNA 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 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 Graham's formula or gram-schmidt no that's gram-schmidt has got to divide the whole thing by the length so he's his formula makes a mess which I'm not willing to write down so let's just see that well 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 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 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 1 those cancel and we do get 0 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 III got B here I get a very easily and now if you see the idea we could figure out a formula force 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 the first one and the second one right that's that's this is the end of the lecture is to find this guy find this vector this vector C that's perpendicular we at this point we know a and B but see the little C that we're given is often some 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 where am I gonna put the darn thing maybe I'll put it off I don't like that somehow C little C and I already know that perpendicular direction that one in that one so now what's the idea give me the gram-schmidt formula for see what is this C here equals what what am I gonna do I'll start with the given one as before right I started 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 that 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 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 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 hasn't got is unit vector so we divide by its length to get that to okay let me do 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 orthonormalization okay so let me give you the two vectors so so I'll take the vector a equals let's say one one one 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 because 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 bigoted that was fine what's B so B is this 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 that here's the a this is the this is the little B this is the big a also the little a and 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 Mike what's a transpose a 3 I'm sorry I didn't know that what's gonna happen okay what had happened why should we knock it ok so so do you see it alright that's a transpose B there's a transpose a that's the fraction so so I take this away and I get one take away one is a zero zero minus this one is a minus one and two minus the 1 is a one 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 that 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 and a matrix and what are they now what I'm writing Q's 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 can sort of it came from the original 1 1 1 1 0 2 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 pretty 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 plain right I've got two vectors in three-dimensional space their column space is a plane the column space of this matrix is a ply what's the relation between the plains between the two column spaces they're one in the same right it's the same column space I did 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 and a was little a so I'm always working here with this in the same space I'm just like getting 90-degree angles in there where my original column space had a perfectly good basis but it wasn't as good as this basis because 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 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 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 an elimination gave me 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 I'm gonna call it our so a equals QR is the magic formula here it's the expression of gram-schmidt and let me just let me just capture that so that's the my final step in is a equal QR maybe I can squeeze it in here so a has columns let's say a 1 and a 2 let me suppose n is 2 just two vectors okay so that's some combination of Q 1 and Q 2 and times some matrix R they have the same column space this is just this matrix just includes in it whatever at least numbers like 3 over 3 and 1 over square root of 3 and 1 over square root of 2 probably that's probably that's what it's got 1 over square root of 3 1 over square root of 2 something there but actually it's got a 0 there so the the the main point about this equal QR is this this R turns out to be upper triangular it turns out that this 0 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 a 1 with Q 1 and this one should be hmm be the inner product of a 1 with Q 2 and that's what I believe is 0 this will be something here and this will be something here with a 1 transpose Q 2 sorry 8 transpose q 1 and a 2 transpose Q 2 but why is that guy 0 why is a 1 q 2 0 that's the that's the key to this being this R here being upper triangular you know why a 1 q 2 is 0 because a 1 that was my this was this was really a and B here this was really a and B so this is a transpose Q 2 and the whole point of gram-schmidt was that we constructed these later Q's 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 that it's the result is extremely satisfactory that or thought 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