Lecture 07 - Solutions of Linear Equations

[Music] [Music] remember our old problem we wanted to find out Solutions of axal to B and B equal to0 is in some sense the simplest case this is talking about the kernel of a so the first question is what does this look like and actually uh this question is very easy to answer when the solution set when I say this I mean let's say s is my set of feasible points in this uh constraint system when will spmt okay uh nontrivially empty good so it is never empty because zero is always there but when is it when is it non-al empty when rank of a is n now because of whatever we have discussed there are multiple ways to say it we can say that columns are linearly independent or n rows are linearly independent okay because s being empty means kernel is y uh with zero right so the dimension of that Subspace is zero that means this the uh size of the images or dimension of the imagees N dimension of the image being N means rank of a is so great there are two cases uh I should say non singular this is when Columns of a are linearly independent the other cases singular where kernel of a has some Dimension let's say k but how do we find these Solutions so we have we have to describe a vector space whose Dimension is K so we want to find a basis which has K elements how how do I describe this Vector space the answer is cian elimination see uh it's a good idea to believe your instructor right when I said gos and elimation is answer to everything and that is why we like gos so much no these are fundamental things so do people know what Goin elimination is yes no okay so probably once I describe it then you know okay so how do you solve this bunch of linear equations multiply so that one of the coefficient goes away right and if you have seen linear algebra you have these how many rows are there m right we can replace a row by R1 + Alpha J RJ or something right so any R can be replaced by correct you remember this operation and you can does this remind you people have seen this right linear algebra course we do this this is gosin elimination this is the simple strategy which we will apply here kind of try to remove one variable at a time right so once you have this operations allowed right why are these operations allowed because they don't change linear Independence right this is why this is allowed and without changing the image when we do this changes what we can do is make the Matrix look like a diagonal matrix when is ax equal to be easy to solve when a is D so all these attempts are trying to make this Matrix look like a diagonal matrix right this is what you were doing even here so what do you do Suppose there there there has to be a uh a row whose first entry is non zero if it is not then I can forget about the First Column so get this at the first place use that to make all the entries below zero now look at the remaining rules there has to be a place where the second entry is is non zero okay if it is only in R1 then we can move the column here or something but uh yeah otherwise take this and then make everything zero here so that there is only one thing for right uh does this remind you of Goan elimination something which you all all of you have done right so when you do all this and even if uh if I allow you to you know rename your columns right uh renaming column means switching The Columns then your Matrix gets into this nice form this is 1 0 0 everything below here is zero there can be some entries here which I don't know right so this is called the yeah reduced Ro seems like a distant memory when you studied this and passed the course right welcome back these things were useful that's why you studied them right so you can you can do this but once you do this your life is set now you can solve linear equations why so let's worry about ax equal to Z that is the simplest case we divide our variables into two sets these are called the leading variables or the awesome variables okay and these are called the free variables okay why are they free we don't care about them you can do whatever with them and still I will have a solution right so now why why is that true because if you look at ax equal to 0 what is the first equation it is saying X1 plus something in free variables what is the second equation it is saying X2 plus something in free variables right so then you can set uh so actually yes whatever value you set for the free variables this will give me some value of X1 X2 up to xn minus K so that I get ax = Z so what is the number of free variables okay this is the dimension of my curve right okay this sounds okay so all this was to make sure that we can solve axal to 0 do we have any questions on this up to a x equal to Z right and then yeah actually it it's it doesn't take a much bigger leap to solve axal right because now okay but then if you kind of think deeply about it there are again going to be two cases or probably three right so uh two cases one is right simple uh this partitions everything uh so if B is not an element of image of him then no solution okay that basically means that uh sorry yeah there will be a some kind of a contradiction right so now but when B is element of image of M there are two ways one is when rank of M is n right then what do I know The Columns of a are linearly independent that means there is a unique solution the case we are left with is and kernel of M has some Dimension K right then what are the all possible solutions and here we can take help from Ax equal to0 how if x is a solution for axal to B and Y is a solution for a y equal to Z then x + y a let's say do I need to prove this fine right if if ax equal to b and a y equal to Z a of x + y is also equal to B right and on the other side if ax1 equal to B and ax2 equal to B implies sorry yeah thank you that means now we have a very very nice description of the solution set find one solution of uh axal B and then right given this now it is very easy to describe all all solutions of a x equal to B you pick a one solution you pick one solution and then all solutions of a equal to Z are going to be there okay and how do I how do you pick one solution again set the free variables they will allow me to write something about the X1 to xus k okay so uh what we were to summarize what we were able to do today was uh we were able to look at axal to B as linear combination of columns find out these properties and that allowed us to have a nice description of solutions of axal to 0 and solutions of axal B we know these are subspaces we know their Dimensions we know the relation between these dimensions right now with this we will start exploring linear programming from the next lecture okay thank [Music] you [Music]