noc20-ma54-lec16 - Solution Set of a System of Linear Equations

[Music] [Music] so have you learned rref and so on how they are used and so on let's now go back to system of equation that is the basic idea for us trying to understand everything for system of equation so let's look at some examples again before I give you the main theorem so example about system of equations are going back to system of linear equations so our system of equation is ax is equal to B fine we can talk of rank of a B and rank of a so what can be the relation what I know is that rref of a is nothing but what we learnt was this is equal to the first so a is M cross n B is M cross 1 fine the first n columns of rref of a B this is what we learned since a is nothing but the first n columns of a B therefore rank of a will have to come from rref of a which is nothing but what we know is that our F of a will be equal to the first n columns of the rref of a B itself fine so therefore rank of a will be either equal to this or rank of this will be equal to rank of a plus one fine there is no other choice other than this because we have added one column this fine so what we are saying here is that we are going to have this as a B has one extra column as compared to e fine so rank of a that is the rank of the coefficient matrix can be either equal to the rank of the Augmented matrix so what we are going to write is either rank of a is equal to rank of the same as rank of coefficient matrix C n matrix is equal to rank of Augmented matrix or rank of a which is same as rank of coefficient matrix will be equal to rank of a woman Ted matrix - one fine so would like to look at this case first alright so let us look at this case first when the rank of Augmented matrix is rank of a plus one alright so when I say that rank of a Augmented matrix is rank of a plus one what does it mean alright it means that does it imply that there is a pirate in the n plus 1/8 is that okay so this you have to be careful you understand this nicely what we had learnt was that rref of a is same as the first n columns in the rref of a be alright therefore we had proved that theorem that if I pick the first s columns the rref is just taken from there itself fine so here what we are saying is that I have this matrix a B so a is here B is here the other F of a will remain in this part itself there is not going to be any change when I look at the RDF of so I am looking at rref of a B I am looking at this so this part is nothing but rref of a and this is something that I am having I'm not bothered what exactly it does but what it says is that the rank is more so there has to be a private at the n plus 1 at column now there is a private means I have an entry here which is 1 somewhere I don't know where 1 is fine because there is a pie or so there is a 1 and since there is a pivert it means that in this row in this row this is the first non-zero entry all right fine this is what the definition of pi what was what are the pivert look at any nonzero row the first nonzero entry in that row was the pivert so therefore if this is the pivert it means that the corresponding entry here in that row is 0 fine and this tells me that this equation corresponds to looking at 0 times x 1 plus 0 times X 2 plus 0 times xn is 1 which has no solution probably fine so this is what you have to understand that I will not have a solution as soon as rank of a B is greater than a rank of a a rank of the Augmented matrix is greater than this so let me write it down so as a corollary or as a understanding of what we have done if the rank of the Augmented matrix is greater than the rank of a then ax is equal to B is it ok fine so this is when B is nonzero alright so this can happen only when only one B is not 0 fine if B is equal to 0 then the last column cannot have been any non then the n plus 1s column of a B then the NF protocol of a B is 0 or which is same thing as saying that a B is same as a 0 implies the rref of a B cannot have a pirate in the n plus 1/8 column and this will imply that rank of a B will be same as that on coffee and we already know that for the system ax is equal to 0 X is equal to 0 is always a solution fine alright now let us take another example to proceed further so that was first example second example alright so let me write a small example and then build up on that idea so I'll tackle larger also let me take a B as I have some matrix a B I am looking at rref of a be fine so ad off EF is going to look like so now I'm assuming the take the case that so case rank of a B is same as a rank of a fine I'm taking this case and B is not 0 and then I will go to be equal to 0 fine so let me write this suppose I have got this so one is a pie Hertz I got 0 here 0 here there is another pivert at so I have got say 0 here 1 here 0 here and I have got say 2 here 0 here minus 1 to 0 0 so this is my a part alright a part and the B part is say 2 3 0 fine so you can see that rank of a so this is satisfied that you can see but this is the a part here there are 2 pi words and there is no private in the fifth column all right so this equation if I look at this crossbones - looking at X 1 plus 2 X 2 minus X 4 is equal to 2 and X 3 plus 2 X 4 is equal to 3 from here I can write here that this implies X 3 is equal to 3 - 2 X 4 and X 1 is equal to 2 minus 2 X 2 plus X 4 fine this is very very important all right have a look at it nicely fine so what exactly we are doing is I have written X 1 and X 3 in terms of so we have written so let me write it D 10 X 1 and X 3 in terms of constant and X 2 and X 4 look at the Pirates the Pirates are here this is a pirate and this is a pie what pie what is their pie what's in first and third columns all right what we know is that every column corresponds to a variable so 5 watt 1 corresponds to the first variable X 1 the second pivert in the third column corresponds to the variable X 3 so what we are doing is that we are writing the variables corresponding to the pirates in terms of non pirates so these so there is a notion here what are called basic variables and what are called free variables so what are basic variables the variables corresponding to by what L columns alright so in this example by what L columns are 1 & 3 so the basic variables are X 1 and X 3 what our free variable they correspond to correspond to non pivotal columns all right so non pivotal columns those what has non political second and four so therefore you have X 2 and X 4 here fine and for the free variables they where X 1 and X 3 is that okay so what we have done here is that we have written you have to be careful here we have written free variables in terms of a constant which are 3 and 2 which are coming from the side B part and the free variables that's always important because free variables can be given whatever value you want and still the system of equation will have a solution so let me rewrite this in the next page now so what I have is my rref of a B was 1 0 0 2 0 0 0 1 0 minus 1 2 0 2 3 0 fine X 1 was 2 minus 2 X 2 plus X 4 X 3 was 3 minus 2 X 4 so let us go back and rewrite it nicely now all right so let me add the solution X as X 1 X 2 X 3 X 4 what we see here is that X 1 is - - 2 X 2 plus X 4 X 2 there is no change in X 2 because it is just a free variable X 3 is 3 - 2 X 4 and X 4 is also free I can leave it as it is so this is same as 2 0 3 0 + X - x - 2 1 0 0 + X 4 x 1 0 - 2 1 alright so look at these solutions here look at this X fine this is obtained by so this is the solution I have this with X 2 and X 4 arbitrary these are solution I have fine I have written this in terms of this vector now how do I get this so here I have taken from here to here if I want to go I have taken here X 2 to be 1 and X 4 is equal to 0 to get -2 1 0 0 this is the thing I got look at here you put X 2 to be - to forget about this constant part you had minus 2 here 0 here and so on X 2 is 1 fine so here other than the constant we are looking at the remaining part this cross spawns - looking at X 4 put X 4 to be so X 2 is equal to 0 and X 4 is equal to 1 so X 4 is 1 in the first one so you get 2 here X 2 is already feed available that is 0 already for us and then - 2 coming from X 3 and this one is there okay so I would like you to check here that this x 1 0 0 2 0 0 0 1 0 minus 1 2 0 these times - 0 3 0 gives you this just multiply here 2 times this 0 times this three times this so you get to hear three here zero which is coming from the B part fine what else 1 0 0 2 0 0 0 1 0 minus 1 to 0 this times minus 2 1 0 0 gives me 0 0 0 0 similarly 1 0 0 2 0 0 0 1 0 minus 1 to 0 this times 1 0 minus 2 1 will also give you 0 0 0 fine so these two alright these two vectors they cross bond to the solution of ax is equal to 0 X is equal to 0 so they are what is called corresponding to solution set of set of homogeneous system alright and this was what is called a particular solution solution of a X is equal to fine let me take a slightly more complicated one bigger size and then I will write the theorem so now I am looking at only a X is equal to 0 I am NOT looking at and looking at ax is equal to 0 ax equal to B I am not bothered about call ax equal to 0 gives me all the ideas alright so suppose my corresponding matrix a rref of a is C and my matrix C looks like 1 1 2 3 2 + 3 5 2 3 4 5 0 1 2 1 minus 1 3 suppose this is a metric that I have alright so it is five cross three six one seven five cross all right so how many variables I have since it has seven columns implies seven variables or seven unknowns fine what are the Pirates this is a pirate this is a pirate this is a pirate this is a private four pirates all right and if you look at the pipe words they are in the first column second column first second fifth and sixth so therefore this implies that X 1 X 2 X 5 and X 6 are basic variables fine this also implies that X 3 X 4 and X 7 are three variables is it ok so when I want to write X as X 1 X 2 X 3 X 4 X 5 X 6 X 7 what we have is look at X 1 from here the first part so X 1 is it is coming from here so minus 2 X 3 then it is plus X 4 and minus 2 X 7 X 2 is another basic variable so X 2 is minus X 3 minus 3 X 4 minus 5 X 7 then the next day is X 5 X 5 is plus 4 X 7 and X 6 is minus X 7 now let's let you write it back minus 2 X 3 plus X 4 minus 2 X 7 X 2 is minus 3 - 3 X 4 - 5 X 7 X 3 there is no change X 4 there is no change because there are free variables X 5 is 4 X 7 and X 6 is minus X 7 and X only again of free variables I keep it as it is so this is same as X 3 x - 2 - 1 1 0 0 0 0 + x 4 x 1 - 3 0 1 0 0 0 + x 7 x - 2 - 5 0 0 4 - 1 1 fine so now some of the versions X 3 was a free variable alright since X 3 is a free variable this one appears at the 3rd place is that ok look at the other places here 3rd places are 0 all right 3rd places are 0 fine let us look at the next here you have X 4 1 at the 4th place fine so since it is the fourth variable X 4 is the fourth variable it corresponds to the fourth column the fourth entry here is 1 here it was 0 here also it is 0 fourth place 0 is there ok you can see here this also is 0 here fine the last one this is X 7 so look at the seventh place there is a 1 here alright and 7th place here everything is 0 so when I am looking at the solution here fine there were 4 basic variables basic variables or for pirates or rank of a is for fine so therefore seven minus four which is three was number of free variables each of these free variables have given me a solution set in the sense that I have got this vector which is solution of the above system you can see that minus 2 minus 1 1 times that will be 0 so what I am saying is just look at minus 2 times the first column minus 1 times the second column plus 1 times the third column just add these 3 minus 2 plus 2 is 0 minus 2 plus 2 is 0 minus 1 plus 1 is 0 so you get a solution of AX is equal to 0 similarly verify that this is also solution of AX is equal to 0 and this is also a solution of ax is equal to 0 is that ok so what we are seeing here is that they have some nice properties and not only that they again they cross bound to in some sense 1 0 0 0 1 0 0 0 1 all right but now it is with respect to the rows that we are looking at we are forming the rows 1 0 0 as the first row coming from X 3 coming from X 4 is 0 1 0 and from X n you are getting 0 0 1 fine so now let me conclude this by stating given the statement of the theorem so what is the theorem theorem let ax is equal to B be a linear system system in n variables fine with rref of AV is equal to CD CD then what if rank of a B is greater than rank of a so rank of the Augmented matrix is getting the rank of efficient matrix implies the system has no solution so note that when I am saying that this is greater it means that B is nonzero directly because you are saying that there is a private at the birthplace we already seen that B is not equal to 0 and there is a pivert in the n plus 1 at all right and therefore the other system 0 times x1 plus 0 times x2 plus 0 times xn is equal to 1 no solution so now that case is when they are equal so if the rank of a B is equal to rank of a now here we have two cases case a rank of a is n which is number of variables all right so since the rank of a is n it means that there are n pirates implies all variables our basic variables implies no free variable the variable implies a unique solution so look at it from this point of view B is there so B will have some entries fine now you are saying that rank is n rank is n means there are n pirates and not only that rank is n also means that I have got I sub n so I sub n is there in C all right because CD was the matrix already F so this is my C part and we are saying that I n is there so I n is there means I have got one here one here one here so this one every column has a pirate all right if every column has a pirate it means that I already have X 1 is equal to this X 2 is equal to this value so if this was d 1 this was d 2 they're already saying that X 1 is d 1 X 2 is d 2 X 3 is d 3 and so on till xn is DN whatever it is fine because this matrix was D for us this was the C for us fine so there is a unique solution and this also means that M is greater than equal to n all right so that we are not saying but since you are saying rank of a is n that implies that part alright the third part is not the third part but the be part of this is rank of a is strictly less than n suppose this is our so this will imply that there are our basic variables and implies n minus our free variables this will have infinite number of solutions Solutions and each free variable is going to give me a vector so is free variable free variable gives a solution of ax is equal to zero so suppose the free variables they give you vectors so u 1 u 2 u of n minus R alright so there are how many free variables n minus R free variables and therefore you have got n minus R vectors is that ok n minus R vectors they have some nice form in the sense that they have got if I look at you one will be have will have 1 0 0 somewhere you to elapsed 0 1 0 0 0 and so on so there n minus R vectors and a of UI will be 0 for 1 less than equal to I less than equal to n minus R is that ok we'll look at the implications of these ideas in the next class alright so I want you to understand that whenever the system of X equal to B whatever M sighs the whole thing the whole argument is the independent of choice of M it is only dependent on rank of Augmented matrix rank of a and the number of unknowns it has nothing to do with em that's all for now thank you [Music] [Music] [Music]