Transcript
okay when the camera says we'll start you want to give me a signal okay this is lecture eight in linear algebra and this is the lecture where we completely solve linear equations so ax equal B that's our goal if it has a solution it certainly can happen that there is no solution we have to identify that possibility by elimination and then if there is a solution we want to find out is there only one solution or are is there a whole family of solutions and then find them all okay can I use as an example the same Matrix that I had last time when we were looking for the null space so so th the Matrix has rows one two two 2 2 4 6 8 and the third row you remember the main point was the third row 368 10 is the sum of Row one plus row two in other words if I add those leftand sides I get the third leftand side so you can tell me right away what elimination is going to discover about the right hand sides what's there is a condition on B1 B2 and B3 for the system to have a solution most cases if I took these numbers to be 1 five and 17 there would not be a solution in fact if I took those first numbers to be one and five what is the only B3 that would be okay six if the left hand if if these leftand sides add up to that then B I need B1 plus B2 to equal B3 let's let's just see how elimination discovers that but but we can see it coming right uh that that if if let me say it in other words if some combination on the left hand side gives all zeros then the same combination on the right hand side must give zero okay so let's uh let me take that example and write down instead of copying out all the plus signs let me write down the Matrix 1 2 2 2 2 4 68 and that 63 810 were the third row is the sum of the first two rows now how do we deal with the right hand side that's we we want to do the same thing to the right hand side that we're doing to these rows on the left side so we just tack on the right hand side as another Vector another column so this is the augmented matrix it's it's the Matrix a with the vector B tacked on in mat lab that's all you would need to type okay so we do elimination on that can we just do elimination quickly the first pivot is fine I subtract two of this away from this three of this away from this so I have one 2 2 2 B1 two of those away will give me 0 0 2 and four 4 and that was B2 minus 2 B1 I I have to do the same thing to that third that last column and then three of these away from this Gave Me 0 0 24 B3 minus 3 b1s so that's the that's elimination with the First Column completed we move on there's the first pivot still here's here's the second pivot we're always remembering now these are then going to be the pivot columns and let me get the final result well let me can I can I uh do it by eraser we're capable of subtracting this Row from this row just by that'll knock this out completely and give me the row of zeros and on the right hand side when I subtract this away from this what do I have I think I have B3 minus a B2 and I had minus three b1s this is going to it's going to be a minus a B1 oh yeah that's exactly what I expect so now what's the last equation the last equation this represented by this zero row that last equation is says 0 equals B3 - B2 - B1 so that's the condition for solvability that's the condition on the right hand side that we expected it says that B1 plus B2 has to match B3 and if our numbers happen to have been 15 and six so let me take suppose B is 156 that's an okay B and when I do this elimination what will I have the B1 will still be a one B2 would be 5 - 2 this would be a three five 6 - 5 - one this will be this is the main point this will be a zero thanks okay so the last equation is okay now and I can proceed to solve the two equations that are really there with four unknowns okay I I I want to do that so this this B is okay it allows a solution we're going to be naturally interested to keep track what are the conditions on B that that uh are that that make the equation solvable so let me put it let let me write down what we already see before I continue to solve it let me first solvability solvability so which so this is the condition on the right hand sides and what is that condition this is solvability always of ax equal B so axal B is solvable well actually we had an answer in the language of the column space can you remind me what that answer is that that was like our answer from earlier lecture B had to be in the column space solvable if when exactly when B is in the column space of a right that just says that B has to be a combination of the columns and of course that's exactly what the equation is looking for so that that now I want to answer it the same answer but in different language another way to answer this if if some if a combination of the rows of a gives the zero row if a and this was an example where it happened some combination of the rows of a produced the zero row then what's the requirement on B that's since we're going to do the same thing to both sides of all equations the same combination of the components of B has to give zero right that's so if there's a combination of the rows that gives the zero row then the same combination of the entries of B must give zero and this isn't the zero row that's the zero number okay that this is another way of saying and it's it's not immediate right that these two statements are equivalent but somehow they must be because they're both equivalent to the solvability of the system Okay so we've got this this sort of like question zero is does the system have a solution okay I'll come back to discuss that further let's go forward when it does when there is a solution and so what's our job now abstractly we sit back and we say okay there's a solution finished it exists but we want to construct it so what's the algorithm the the the sequence of steps to find the solution that's what I and and of course the quiz and the final I'm going to give you a system ax equal B and I'm going to ask you for the solution if there is one and so it's this algorithm that you want to follow okay let's see so what's the so now to find the complete solution to axal B okay let me start by finding one solution one particular solution I'm expecting that I can because my system of equations now that last equation is 0 equals z so that's all fine I really have two equations actually I've got four unknowns so I'm expecting to find not only a solution but a whole bunch of them but let's just find one so step one a particular solution X particular how do I find one particular solution well let me tell you how how I how I find it there so this is since since there are lots of solutions you could have your own way to find a particular one but this is a pretty Natural Way set all free varibles to zero since those free variables are the guys that can be anything the most convenient choice is zero and then solve axal B for the pivot variables so what does that mean in this example which are the free variables which which are the variables that we can assign freely and then and then there's one and only one way to find the pivot variables they're X2 and so X2 is zero because that's in a column without a pivot the second column has no pivot and the what's the other one the fourth X4 is zero because that's those are the the free ones those are in the columns with no pivots so do you see what my so when I knock when X2 and X4 are zero I'm left with the what am I left with here I'm just left with see now I'm not using the two free columns I'm only using the pivot columns so I'm really left with X1 the first equation is just X1 and 2 x3s should be the right hand side which we picked to be a one and the second equation is 2 x3s as it happened turned out to be uh three I I just write it again here with the X2 and the X4 knocked out since we set them to zero and you see that we we're back in the normal case of having back we're back substitution will do it so X3 is three halves and then we go back up and X1 is 1 - 2x3 that's probably min-2 good so now we have the solution X particular is the vector minus 2 0 three Hales zero okay good that's one particular solution and we should and could plug it into the original system really if on the quiz please it's a good thing to do just so we did all this these row operations but this is supposed to solve the original system and I think it does okay so that's X particular which we've got so that's like what's new today the particular solution comes first you check that you have 0 equals z so you're okay on the last equations and then you set the free variables to zero solve for the pivot variables and you've got a particular solution the particular solution that has zero free variables okay now but that's only one solution and now I'm looking for all so how do I find the rest the point is I can add on two add on X anything out of the null space we know how to find the vectors in the null space because we did it last time but I'll REM remind you what we got and then I'll add so the final result will be that the complete solution this is now the complete guy the complete solution is this one particular solution Plus any any Vector all different vectors out of the null space xn okay why why this pattern because this pattern shows up through all of mathematics because it shows up everywhere we have linear equations let me just put here the the reasoning a XP so that's X particular so what does a x particular give that gives the correct right hand side B and what does a times an X in the null space give zero so I add and I put in parentheses so XP + xn is B+ 0 which is B so oh what am I saying let me just say it in words if I have one solution one solution I can add on anything in the null space because anything in the null space has a zero right hand side and and I still have the correct right hand side B so that's my system that's my complete solution now let me write out what that will be for this example so so this example in this example expert X General X complete the complete solution is X particular which is -2 0 32 0 with those zeros in the free variable plus you remember there were the special Solutions in the null space that had a one in the free variables or or one and zero in the free variables and then we filled in to find the others I've forgotten what they were but maybe it was that that was a special solution and then there was another special solution that had that free variable zero and this free variable equal one and I have to fill those in let's see can I remember how those fill in maybe this was a minus two and this was a two possibly I think probably that's right I'm not yeah to H does that look right to you I would have to remember what are my equations can can I rather than go way back to that board let me remember the first equation was 2x3 + 2x4 equaling zero now because I'm looking for the guys in the null space so I said X4 to be one and the second equation that I didn't copy again gave me minus two for this and then yeah so I think that's right 2 - 4 and two gives zero check okay those were the special Solutions what do we do to get the complete solution how do I get the complete solution now I multiply this by anything C1 say and I multiply this by anything I take any combination remember that's how we described the null space the null space consists of all combinations of so this is xn all combinations of the special Solutions there were two special Solutions because there were two free variables and we want to make that count uh com carefully now but just while I'm up here so there's that's what the that's the kind of answer I'm looking for is there a constant multiplying this guy is there a free constant that multiplies X particular no way right X particular solves a XP equal B I'm not allowed to multiply that by three but AXN I'm allowed to multiply xn by three or add to another xn because I keep getting zero on the right okay so so again XP is one particular guy xn is a whole Subspace right it's one guy plus plus anything from a Subspace let me draw it let me let me try to oh I want to draw I want to graph all this graph I want to I want to plot all solutions now X so what dimension am I in this is an unfortunate Point how many components does X have four there are four unknown so I have to draw a four-dimensional picture on this MIT cheap Blackboard okay so uh here we go X1 uh Einstein could do it but uh this this is th those are are four perpendicular axes in representing four-dimensional space okay where are my Solutions do my solutions form a Subspace do does the set of solutions to ax equal B form a Subspace no way what does it actually look like though there a Subspace is in this picture this part is a Subspace right that part is some like two-dimensional because I've got two parameters so it's I'm thinking of this null space as a two-dimensional Subspace inside R4 now I have to tell you and we'll tell you next time what does it mean to say a Subspace what's the dimension of a Subspace but you see what it's going to be it's the number of free independent constants that we can choose so somehow there'll be a two-dimensional Subspace not a line and not a three-dimensional plane but only a two-dimensional guy but it's doesn't go through the origin because it goes through this point so there's X particular X particular is somewhere here x particular so it's somehow a Subspace can I try to draw it that way it's a two-dimensional Subspace that goes through X particular and then onwards by so there's X particular and I added on xn and there's X there's xal XP + xn but the xn was anywhere in the Subspace so that filled out a plane it's it's a it's a Subspace it's not a Subspace what am I saying it's it's it's like a flat thing it's like a Subspace but it's been shifted uh away from the origin it doesn't contain zero okay thanks that's the picture and that's the algorithm so the algorithm is just go through elimination and uh find the particular solution and then find those special Solutions you you can do that that let me take our time here in the lecture to think uh about the bigger picture so let me think about uh so this this is my pattern now I want to think I want to ask you about a question I want to ask you some questions so when I mean think big I mean I'll think about an M by n Matrix a of rank R okay what's our definition of rank our current definition of rank is number of pivots okay first of all how are these numbers related can you tell me a relation between R and M if I have M rows in The Matrix and R pivots then I certainly know I know always what what relation do I know between r and m r is less or equal right because I've got M rows I can't have more than M pivots I might have M and I might have fewer also I've got n columns so what's the relation between R and N it's the same less or equal because a column can't have more than one pivot so I can't have more than n pivots all together okay okay so I have an M byn Matrix of rank R and I always know R less than or equal m r less or equal n now I'm specially interested in the case of full rank when the rank R is as big as it can be well I guess I've got two separate possibilities here depending on what these numbers M and N are so let me talk about the case of full column Rank and by that I mean means r equal n and I want to ask you what's what does that imply about our Solutions what does that tell us about the null space what does that tell us about uh the the complete solution okay so what does that mean so I I want to ask you what okay if the rank is n what does that mean that means there's a pivot in every column so how many pivot variables are there n all the columns have pivots in this case so how many free variables are there none at all so no free variables r equal n no free variables so what does that tell us about what's going to happen then in our in our little algorithms What will what will be in the null space the null space of a has got what in it only the zero Vector there are no free variables to give other values to so the null space is only the zero vector and what about our solution to ax equal B solution to ax equal B what what's the story on that one so now that's coming from today's lecture the solution X is what's the complete solution it's just X particular right if if if there is an if there is a solution it's xal X particular there's nothing you know there's just one solution if there's one at all so it's Unique solution unique means only one unique solution if it exists if it exists in other words I would say let me put it a different way they're either zero or one Solutions this is all in this case r equal n so I'm because many many applications in reality The Columns will be uh will will be what I'll later call Independent and we'll have uh nothing to look for in the null space and we'll only have particular Solutions okay everybody see that possibility but I need an example right so let me create an example what sort of a matrix what's the shape of a matric that has full column rank so can I squeeze in an example here if it exists let me put in an example and it's just the right space to put in an example because the example will be like tall and thin it will have well I mean here's an example 1 2 six 5 31 one one brilliant example okay so there's a matrix a and what's its rank what's the rank of that Matrix how many pivots will I find if I do elimination two right two I see a pivot there I I've certainly those two columns are headed off in different directions when I do elimination I'll certainly get another pivot here fine and I can use those to clean out below and above so the actually tell me what it's row reduced reduced row Echelon form would be can you carry that that elimination process to The Bitter End so what what does that mean I subtract a multiple of this Row from these rows so I clean up all zeros there then I've got some pivot here what do I do with that I go subtract it below and above and then I divide through and what's the what's R for that example maybe I can you'll allow me to put that just here in the next board what's the row reduced Echelon form just out of practice for that matrix it's got ones in the pivots it's got the identity Matrix a little 2x two identity Matrix and below it all zeros that's a matrix that really has two independent rows and they're the first two actually the first two rows are independent they're not in the same direction but the other rows are combinations of the first two so so uh is there always a solu solution to ax equal B tell tell me what's the picture here for this Matrix a this is a case of full column rank the two columns are give two pivots there's nothing in the null space there's no combination of those columns that gives the zero column except the z0 combination so there's nothing in the null space but is there always a solution to a x equal B what's up with ax equal B I've got four four equations here and only two x's so the answer is certainly no there's not always a solution if the so I may have Zero Solutions and if I make a random Choice I'll have Zero Solutions or if I make a great particular choice of the right hand side which just happens to be a combination of those two guys like tell me one right hand side that would have a solution tell me a right hand side that would have a solution well z00 z0 okay no prize for that one uh tell me another one another right hand side that has a solution would be 4376 I could add the two columns right what would be the total complete solution if the right hand side was 4376 there would be the particular solution one one one of that column plus one of that and that would be the only solution so there would be X particular would be one one in the case when the right side is the sum of those two colums and that's it so that would be a case with one solution okay that's this is the typical setup with full column rank now I go to full row rank you see the sort of natural symmetry of this discussion full row rank means r equal m so this is what I'm interested in now r equal m okay what's up with that um how many pivots M so what happens when we do elimination in that case I'm going to get M pivots so every row has a pivot right every row has a pivot then what about solvability what about this business of for which right hand sides can I solve it so that's my question I can solve ax equal B for which right hand sides four you see what's coming I do elimination I don't get any zero rows so there aren't any requirements on B I can solve a equal B for every B I can solve ax equal B for every right hand side so this is the existence exists a solution now tell me so the so every row has a pivot in it so how many free variables are there how many free variables in this case if I had n variables that to start with how many are used up by pivot variables R which is M so I'm left with left with n minus r free variables okay so this case of full row rank I can always solve and then this tells me how many variables are free and this is of course n minus M this is n minus M free variables can I do an example you know the best way for me to do an example is just to transpose that example so let me take let me take that Matrix that had column 1265 and make it a row and let me take 3111 as the second row and let me ask you this is my Matrix a what's its rank what's the rank of that Matrix sorry to ask but not sorry really because because we're just getting the idea of rank what's the rank of that Matrix two exactly two there will be two pivots what will the row reduce Echelon form be anybody know that one actually tell me not only you have to tell me not only there be two pivots but which will be the pivot columns which Columns of this Matrix will be pivot columns so the First Column is fine and then I go on to the next column and what do I get do I get a second pivot out of will I get a second pivot in this position yes so the pivots when I get all the way to R will be there and here will be some numbers I this is the part that I previously called f this is the part that so the the here the pivot columns in R will be the identity Matrix there are no zero rows no zero rows because the rank is two but there' be stuff over here and that will uh enter the special Solutions and the null space okay so this is a typical Matrix with Ral M smaller than n now finally I've got a space here for Ral m equal n I'm off in the corner here with the most important case of all so what's up with this Matrix so let me give an example okay brilliant example 1 12 31 tell me what how do I describe a matrix that has rank r equal m equal n so the Matrix is square right it's a square Matrix and if I know its rank is it's full rank now I don't have to say full column rank or full row rank I just say full rank because the count column count and the row count are the same and the rank is as big as it can be and what kind of a matrix have I got it's invertible so that exactly the invertible matrices Ral m equal N means the and what's the row Echelon form the the reduced row Echelon form for an invertible Matrix for a square nice Square invertible matrix it's I right so you you see that the the good matrices are the ones that kind of come out trivially in R you reduce them all the way to the identity Matrix what's the null space for this for this Matrix can I just hammer away with questions what's the null space for this Matrix the null space of that Matrix is the zero Vector only the zero Vector only what are the conditions to solve ax equal B which right hand sides B are okay if I want to solve ax equal B for this example so I a is this B is B1 B2 what are the conditions on B1 B2 none at all right so this is the case this is the case where I can solve so I'm coming back here I can since the rank equals m I can solve for every B and since the rank is also n there's a unique solution let me summarize the whole picture here here's the whole picture I could have r equal m equal n this is the case where this is the identity Matrix and this is the case where there's one solution that's the Square invertible chapter 2 case now we're into chapter three we could have r equal m smaller than n now that's what we had over there and the row Echelon form looked like the identity with some zero rows and that was the case where there are zero or ones solution to I'm when I say solution I mean to axal B so this case there's always one this case there's zero or one and now let me take the case of full column rank but some uh extra rows so now our has well the identity I'm almost tempted to write the identity Matrix and then F but that isn't necessarily right I have I have is that right am I sorry am I am I getting this correct here or oh I'm I'm not my God this is the case R equals n The Columns The Columns are are okay that's the case that was on that board r equal n full column rank now I want the case where m is smaller than n and I've got extra columns okay there we go so this is now the case of full row rank and it looks like if except that I can't be sure that the pivot columns are the first columns so the I and the F the F could be partly mixed into the I can I can I write that with just like that so the the the F could be sort of partly into the eye if if if the first columns weren't the pivot columns now how many solutions in this case there's always a solution this is the existence case there's always a solution we're not getting any zero rows there are no zero rows here so there's always either one or infinitely many solutions okay actually I guess there's always an infinite number because we always have some null space to deal with then the final case is where R is smaller than M and smaller than n okay now that's the case where R is the identity with some free stuff but with some zero rows too and that's the case where there's either no solution because we didn't get a zero equals z for some bees or infinitely many solutions okay do this board really summarizes the lecture and this sentence summarizes the lecture the rank tells you everything about the number of solutions that number the rank R tells you all the information except the exact entries in the solutions for that you go to the Matrix okay good have a great weekend and I'll see you on Monday