Lecture 05 - Vector Space over real numbers

[Music] [Music] welcome to the second lecture on the course on linear programming we saw in the first lecture these questions right uh we wanted to answer these questions for our first lecture so let's just revise them first question we answered was what is linear programming so would someone like to tell me what is linear programming how would you like to describe it in one sentence two sentence probably a paragraph very nice it is an optimization problem or optimization class where what was what's the Restriction linear constraints as well as linear objective function good an optimization problem where we have linear constraints and linear objective functions is basically the class of linear programming problems second question is why are we worried about studying it why should we devote an entire course on this linear programming we kind of saw which subclasses were important right we asked uh when would I say this subass is important right and linear programming fit all the reasons what were those reasons very good it has diverse applications what else easier yeah it has hope of solution and now actually we know that we can solve it and this abstract idea of having a yes mathematical structure right this is the reason we are studying linear programming what are the contents of this course you go to course website you can find them out okay but mainly the focus is going to be computer science applications once we get to the background mathematically what is needed to study how do we come up with Solutions once we do that then most of the part would be how to use this knowledge to various applications in computer science that will form the bull workk of this course okay great we have the answer to these three questions let's move forward if you remember we discussed the standard form of linear program and can you tell me what is what was the form right so so answer right so this is the standard form and clearly I wanted uh objective function to be linear that is great I wanted my constraints to be linear with a positivity constraint so all my constraints are linear but the question is does it cover all kind of linear constraints we don't know yet but we will see that this covers all kind of linear constraints whatever linear constraints you can think of we can formulate them in this language but that is for later for now believe me that any linear program can be written like this and once this is true what should we do and kind of the first half of the course uh the story would be uh we would be like these explorers who are trying to figure out the world of linear program right suppose you are the first person who comes up with oh this class seems interesting then what will be the next thought you want to solve it but if you want to solve it as a researcher what will be your game plan what do you want to do good when you have a big problem in mind it's hard to solve what do we do change it in the sense that we simplify it we break it down into smaller steps right and when I look at it I will say oh forget about the objective function now let me just even find out whether there is an X which satisfies this condition or not right so my first simplification would be is there an X which satisfies constraints all constraints and from the one uh from the lecture one we actually know we can write it as the question which says is now what should come here what is s it is called feasible set right right and then even this has complication so what would be the second simplification does X great than equal to Z has a solution or not it has right we skip it we go to axal to B has a solution or not so the first question which we are going to tackle is and this is a question which is pretty appealing because we already know this has been studied a lot as a researcher once you find a sub problem which has already been studied we are happy because we know that ax equal to B is this fundamental problem for linear algebra not just linear equations but I would say linear algebra at least 50% of it right this is I think the beginning of linear algebra we know that ax equal to B is a fundamental problem for linear algebra that's great there is lot of work on that so we should learn what has been done for this equation and that is going to be the topic for today okay we want to understand how people have looked at this equation how they have solved it okay I think this is a refresher for you if this feels easy that is great that's a good sign if it doesn't then you should work more on it you should make sure that this seems okay to you okay let us start does axal to B have solution all the time no sometimes it has sometimes it doesn't right and the way we start looking at it is by by viewing it in a slightly different way if I give you an easy set of equations probably in two Dimension easy set of uh like two or three equations and two Dimensions you can obviously solve it but you realize that as soon as the number of Dimensions increases number of variables increases the life becomes difficult but at least computationally we have a very very nice way of handling this and the reason being somehow when we look at this equation right we do not view it as set of equations we view it as Matrix okay what else that's not the fundamental Insight not as a matrix that's that's not not it yeah that that is the reason why we call it a matrix but I would say that the way to look at this equation is this let me know if I miss a constant and what is going to be on the right hand side right so nobody agree nobody would disagree that these two are the same things but the question about linear equations we have converted it into the question of linear combination of vectors and we are asking are there coefficients are there numbers which when multiplied by this Vector this Vector this Vector are they allow to give me this Vector right and this is what we will look at and once you start looking at it you get many many uh of these constructs of linear algebra first of them would be a vector space what is a vector space that's a bad bad definition it is not set of vectors set of all H okay good good set of of vectors which satisfy some condition span of X or Y the idea is that we want to denote the set which is obtained by all possible linear combinations of this right we can ask what vectors can these three vectors generate that feasible set we want it to be a vector space but the better way to view it is set of vectors which have some constraints you can make it very difficult but for us a vector space is a set of vectors such that x + y if and right it is a set of vectors where any such linear combination is contained inside the vector in some sense it is some complete set where inside It Whatever Whenever I do this kind of an operation still Falls inside the set itself right and if you are an algebra fan then you might notice I have used real number here okay for our course we will only be worried about Vector spaces over real numbers but in general you can Define Vector Spaces by putting any field whatsoever here it could be F2 it could be FP it could be polinomial modul some reducible polinomial whatever but this is potentially any field we don't have to worry about it if you're only worried about this course okay in general Vector space is very strong but here we fix the field to be R so whenever I see what are the coefficients what are the scalars they are always real numbers okay good and now once we have the vector space uh we can ask how can we generate it right we saw that if we take all possible s all possible elements of the vector space V they will obviously generate the vector space V but is there a better way and it turns out since we are dealing linear with with this linear combinations this is a very very nice answer right and this comes from the notion of and Independence again I'm going quickly through it because I I'm giving you a refresher if any of this is not clear feel free to interrupt me feel free to ask okay so when are the vectors V1 to VK called linearly dependent right other way to say it is at least one vector I can write it in terms of other vectors in other way to say it is if the coefficient of V1 is non zero then I can forget about V1 when I'm trying to create the generator of the vector space and if the vectors are not linearly dependent they are linearly independent and a nice way to put that is right and here I should say there exist an I okay so this is the set of linearly independent vectors and now if you think about it we had the vector space this is Vector space V if I take all elements of it this obviously will will generate all all the elements in the vector space right is the idea of generation clear generation means you apply some coefficients add them up and get another vector and now but with very high probability they will be linearly dependent but now let's say I start with one vector can one vector be linearly dependent if it is not Z Z cannot be dependent right so then this is first set and the idea was again you take another set see if it is linearly dependent or not if it is linearly independent you increase your size probably you can get every Vector in the vector space through these two great is there a question so if you can get everything that is great suppose not then there is some element element which you can't get by definition it is going to be linearly independent because I can't write this element as a combination of these two right so then these three and then at some point I will end up at a maximal very good maximal linearly independent set okay and this maximum linearly independent set is called bis but clearly this is not unique right I can draw the same picture these might not look the same but they are same according to my drawing and then you can start with this Vector instead of the vector here then you will find some Vector here then some Vector here and then you realize that everything is a linear combination and this is a basis right this is another maximally linear linear independent set and what is a very nice theorem which makes our life easy in linear algebra yes so that means all these maximally linear independent sets are going to have same size this this is called the dimension of the vector space we just said it correct so this should surprise you this is not at all evident from the process we were doing right whatever information we had it's not clear probably just two because of the first we were very lucky the first Vector was so nice that this time only three will suffice no it doesn't happen every time we need four right everyone believes this statement right for every Vector space we have a single uh Dimension how many people can prove it interesting take a look at it but for linear algebra whenever you are stuck the best answer is goian elimination right in life the best answer is zero in linear algebra the best answer is gosan elimination okay it turns out most of the things in the beginning you can prove by applying gosin elimination but yeah uh it is not hard to prove but you have to get a start somewhere you can look at it but you should definitely know that one of the fundamental theorem right this is very very important okay the kind of vector spaces we look at R to the N this is the real Vector space with Dimension n and if you are familiar with it uh from your 12th class this is basically all the vectors of this kind which have n real numbers right and this is going to be the most interesting Vector space for us okay there are various ways to describe it you can also say uh this is the set of all functions from one 2 and 2 R okay so alpha 1 is the value at 1 Alpha 2 is the value at two Al is the value at the at n right also we have different kind of vector spaces C to the N set of all so on so there are lot of vector spaces but for us this is the important Vector space you should understand this this notation might be new but I'm sure you have seen this Vector a lot of times the name for it is going to be R to the n and why R to the N because our coefficients our numbers are coming from real and the dimension is n let's see uh if a linear algebra is okay with you then this is the claim let's say I have a basis B for a vector space which has Dimension n clear any any basis which you know of for General Vector spaces for the vector space like this why 3D in general for even n Dimension 1 0 0 0 1 0 0 right standard basis anything else n Dimension I don't want three dimension can't you create another basis create another basis sorry ah no don't cheat you can't use the same vectors with some scalar multiplication okay okay very good you can do uh 0 1 1 1 1 1 1 1 okay but this is probably harder to see as a vector SP as a bases but I would say that a better Vector space or this is a basis and actually any nice triangular form will give you a basis right okay great so now we know a lot of bases let me ask a more mathematical question we given a basis for a vector space of Dimension n and someone claims that any K vectors are contained in the span of some k + 1 vectors from B so B is a fixed basis V is a vector space the claim is if you pick any k k vectors from V you can always find some k+1 there are a lot of k+1 choice right and choose k+ one so you can find some k+1 vectors such that all the K vectors can be represented in terms of these k+1 vectors right is the term span clear span means all possible linear combinations of these cap one vectors right we take the vectors and write alpha 1 V1 Alpha 2 V2 is this claim correct or not correct B is some fixed basis you know how this problem came about in my first course in I kpur someone proved it using this CLP don't stare at it work that why you should say always have a pen and paper I don't know you you find out if then you find a counter example and you can show me the counter example in your write the counter example concretely and then I can look at it okay time to vote how many people in favor of this claim raise raise your hand okay you you agree you you agree right H yeah yeah that's okay by intuition right you agree how many people do not agree okay so to answer your question I failed the student who wrote this no I did not fail him but he did not get the marks for this let's say we have our favorite standard basis this is the vector there is not even there in any n minus one collections right so my K is equal to 1 here I take this Vector it is not even there in any minus one things of the basis right and the example I'm giving you this example because people get confused about this because you know we can go from any basis to any basis generally the dimensions are the same but d iions do not mean that you know this basis say you can always select some vectors which capture the entire thing what is so this is my standard basis this is B right no what is the stand oh my Dash Dash and my one seems the same that is my yeah one thing you can be sure of is that my my drawing skills are pathetic but uh yeah so this is the standard basis and if you take this Vector it cannot be written down as a linear combination of even n minus one of these right so this is false okay good uh another interesting thing which is sometimes useful is a inner product space and I'm just saying it because R to the N is also an inner product space what does it mean by inner product space what is an inner product yeah don't worry about the mathematical definition but this is going to be the dot product for this everyone knows what a DOT product is Yeah so basically it is dot product for us and it is basically this operation which has nice properties and if you're interested in finding out the nice properties look at Wikipedia or any place which is the definition of inner product okay but what this inner product does is allows us to talk about orthogonality it allows to measure angles between different vectors and then we can talk about orthogonal basis right so the basis which I wrote this was a basis but this was not an this clear to everyone right so I will not go into detail because this is not something we require a lot but we know that R to the N has lot of structure it's not just a simple Vector space but it has an inner product defined over it sounds good okay let's move on to more interesting [Music] stuff [Music]