Transcriber's Name: Crescendo Transcription Pvt. Ltd. Mathematics for Data Science - 2 Professor Sarang Sane Department of Mathematics, Indian Institute of Technology Madras The null space of a matrix finding nullity and a basis - Part 1 Hello, and welcome to the Maths 2 component of the online B.Sc. program on data science. In this video, we are going to study the idea of the null space of a matrix. And once we define what the null space is, we will also study, so it will be a subspace of of some vector space. So, in particular, it will be a vector space. We will also study what is its dimension and we will study how to find a basis for it. This is what we have studied in the previous video. And we will use that to, similar ideas to find the basis and the dimension of whatever the null space is. So, let us begin by quickly going over the contents of this video. So, we are going to study what is the null space of a matrix. This is equivalent to asking what is the solution space corresponding to a homogeneous system of linear equations. Now, that second question is something you already have seen in previous videos. But I am going to refresh that and that is what is exactly going to correspond to the null space of a matrix. What is the nullity of a matrix? So, once we define what is null space, we will study what is nullity. It is nothing but the dimension of the null space. How do we find the basis for the null space? Let us look at a few examples. We will study what is called the rank nullity theorem. So, I am not going to give any proofs. But I am going to state this theorem and stated in some sort of computational way. And then finally, this is a somewhat standalone topic. We will use determinants to check if a given set of vectors is a basis for a vector space, okay. So, let us start with the beginning. Of course, we will also do examples of, using determinants to check if something is a basis. So, let us start with what is the null space. But before that, let us recall what we have done in that previous video that I just mentioned, that we can find the dimension and a basis for a vector space spanned by a set of vectors using Gaussian elimination or row reduction. So, we are going to use this idea again, but in a slightly different way, ok. So, the solution space or the null space of a homogeneous system of linear equations. So, let A be an m by n matrix. The subspace W consisting of x in Rn, such that Ax is 0. So, this is a subset of Rn and it is a subspace, meaning it is a vector space in its own. This is called the solution space of the homogeneous system of linear equations Ax equals 0, my bad, this is a typo here, it should have been equations, or it is called the null space of A. So, when we say null space of A, there is no reference to any system of linear equations, but you just have a matrix. But what do you have to do is in your mind you have to form this system Ax equals 0 and then ask what are all the solutions that is exactly the null space. Why null, because we are finding those vectors x such that Ax equals 0. So, as we know, null is another name for 0, fine. So, note that the null space is a subspace of Rn. The dimension of the null space is called the nullity of A. So, let me justify this statement about a subspace. So, remember, what is a subspace? It is a vector space in its own right. But to check that something is a subspace, all I have to do is, remember, for a vector space there is a large number of axioms. But if it is a subspace that means many of those axioms are already satisfied, because any subset will satisfy those axioms. For example, we know that if you have x in the subspace W and you have lambda in the real numbers and let us say lambda 1 and lambda 2. So, I have lambda 1 and lambda 2 in R, then lambda 1, lambda 2 multiplied by x is equal to lambda 1 times, lambda 1 multiplied by lambda 2 times x. So, this equation we know already, because this is true in the entire space Rn. So, if you want to take something is a subspace, we need not take all the axioms of a vector space. We have to take only a couple of them. Namely, we have to check that if you have x and y belonging to W, so I will just erase this, then x plus y belongs to W. Indeed, that is true in this case. So, if x and y belong to W, that means Ax is, Ay is 0. That also means that A times x plus y, we know that this is Ax plus Ay, this is 0 plus 0, which is 0. So, what does that mean? That means x plus y is also in W, because, remember, W consists of all those vectors, so that when you operate A on that vector, you get 0. When you multiply A to that vector, we get 0. And similarly, if you take x in W and lambda in R, then if you do A times lambda x, well, lambda is a scalar it is a constant. So, we can take that lambda out. This was one of the things that we have seen in matrix multiplication. One way of doing this is to recall that lambda can be, lambda times anything can be thought of as the scalar matrix lambda, meaning you have a diagonal matrix with lambda on the diagonals. And then you can flip that around in any way you want, except that you have to bother about size. But, so you can pull out that lambda. So, this is lambda times Ax, but Ax is 0, because x is in W. So, this is lambda times the 0 vector, which we know is a 0 vector. So, the upshot is that if x and y are in W, then so is x plus y. And if lambda is in, is a scalar, meaning a real number, and x is in W, then lambda times x is also in W. So, that is enough to say that this is a subspace. That means it is a vector space in its own right. So, W is a vector space in its own right. So, we can talk about, now we can talk about what is the dimension of W or we can talk about what is the basis for W. And indeed, this dimension is what is defined as a nullity. So, this justifies what is written here as the nullity. So, let us see how to do that. Let us try to see how we can find a basis for the null space and of course, along with that the nullity, meaning the dimension. So, we have seen how to find the dimension and the basis for the row space of A using row reduction. So, we will use a row reduction to also find the nullity and a basis for the null space of A. Only thing is you have to be slightly, I mean, there is a slight difference in the two, which I am going to come to in a few few slides. So, first, let us recall how to do this idea of Gaussian elimination. Why do we, why are we bothering about the Gaussian elimination, because after all what is the null space? The null space is the set of solutions of Ax equals 0. So, really, we want to ask what is the set of solutions, and then once we know what is the set of solutions, we can try and answer the question about what is its dimension or what is a basis for that. So, first, we have to try and find a way to describe the set of solutions. And we know that to describe a set of solutions the method that we have studied is the Gaussian elimination method. So, let us recall the Gaussian elimination method. So, you have a system Ax is b. In our case, we actually have a system Ax is 0, but let us do the general case. So, you form the augmented matrix A augmented with B. Apply the same row reduction operations on the augmented matrix that are used to row reduce A to obtain the augmented matrix Rc. C is the rightmost column, where R is in reduced row echelon form and that is the matrix that you obtain by applying row reduction on A. Now, if the i-th column has the leading entry of some row, recall what is reduced row echelon form or row echelon form, so that means you have a bunch of rows, where you have a 1 in the leading position, the first non-zero entry is 1 and after that you could have other entries. But the next row has a 1 which is after the 1 in the previous rows. So yeah so, keep that in mind. As we go ahead that is crucial to what is going to happen. If the i-th column has the leading entry of some row, the i-th column, remember, then we call xi a dependent variable. And if the i-th column does not have the leading entry of some row, we call xi an independent variable. By leading entry, we mean the first 1, right? It starts with the 1, leading entry is always a 1. So, that particular 1, whichever column has that 1 those columns, the corresponding variables are called dependent variables and the others are called independent variables. And then how do we find the solutions? Well, before that, let us make a computational remark. From here we already know what is the nullity. The nullity of A is the number of independent variables. So, already this method is going to tell you what is the what is the nullity of A, so the dimension of the null space. And we will explore why that is the case later. So, now let us recall how we got the solution space. So, assign arbitrary values ti to the i-th independent variable. So, there are some independent variables and some dependent variables, you take the independent variables. The first independent variable you assign the value t1, the second one you assign the value t2 and so on. And then for the dependent variables, you use the equations left from R. You have Rc which is the augmented matrix that you get at the end of the process. So, that corresponds to Rx equals c. And each dependent variable appears in exactly one of these equations. And all the other variables occurring in that equation are independent variables. So, you can back, you can push the independent ones to the other side, substitute ti for that and compute the value of the dependent variable. So, compute the value of each dependent variable in terms of tis from the unique row it occurs in. And every solution is obtained by letting tis vary in R. So, as t1 varies over R, t2 varies over R, and so on, all the tis vary over R, you get all possible solutions. This was how we found the solution space for Ax equals 0. So, now how do we find a basis? So to find a basis, we substitute ti equals 1. You fix an i, substitute ti equals 1, and substitute tj equals 0 for all j which are not equal to i. And you let i vary, of course, over all possible integers where it is defined, so as many independent variables as there are. And the vectors that you get are exactly the basis for the null space or the basis for the solution space of Ax equals 0. Let us do this. This is slightly, I mean, I have written all this, but it might be difficult to visualize what is going on. So, let us do this in an example or a couple of examples. So, let us do a three by three example. So, consider the matrix representation of the homogeneous system of linear equations of the form Ax equals 0, where A is 1, 1, 1, 2, 2, 2, 3, 3, 3, so rather easy matrix. We do not really need to do all this to find the solution space. You can directly write down the equations and find it yourself. But let us do it the way that we have described and you will see it is it is a one or two step process. So, what was the method? We find the augmented matrix. So, remember, here we are always solving for the homogeneous system. So, always on the right, you will have 0, 0, 0. So, you have 1, 1, 1, 0, 2, 2, 2, 0, 3, 3, 3, 0. Let us do row reduction. So, if you row reduce, well, in this case, row reduction is very easy. You subtract 2 times the first row from the second row and 3 times the first row from the third row. So, you are going to get 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0. So, now, how many independent variables are there, how many dependent variables are there? So, for that we have to look for the non-zero rows. There is one non-zero row. And within that row, look for the leading 1. So, the leading 1 is in the first column. That means x1 is a dependent variable and everything else is independent. That means x2 and x3 are independent variables. So, the independent variables are x2 and x3. The dependent variable is x1. That already tells me what is the nullity. So, the nullity of A is 2. Now, let us find a basis for this for this vector space, namely the null space. So, to find a basis, let us recall how to find the solution space in the first place. So, to find the solution space, we put x2 as t1 and x3 is t2, right. You look for the independent variables and the first independent variable you call t1, you assign the value t1, the second independent variable, you assign the value t2, and you allow t1 and t2 to vary over R. Of course, what is x1? X1 you can obtain from the equation that we had for the reduced echelon form. So, remember that the reduced echelon form was 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, that corresponds to the equation x1 plus x2 plus x3 is 0, which gives me x1 is equal to minus x2 minus x3. So, if you substitute t1 and t2 in place of x2 and x3, you get x1 is minus t1 minus t2. So, the null space of A is the set of vectors minus t1 minus t2 comma t1 comma t2 as t1, t2 vary over R. So, what are examples of solution vectors? For example, one possible solution is minus 5 comma 2 comma 3. Another possible solution is minus 20 comma 10 comma 10. I hope you understand how we are getting these solutions. Now, I want a basis for this vector space. So, how do I get a basis? You put t1 equals 0 and see what, and t2 equals, let us do it the other way. Let us put t1 equals 1 and t2 equals 0 and see what that gives you. If you do that, you get the basis vector minus 1 comma 1 comma 0. You interchange their roles, put t1 is 0 and t2 is 1 that uses the basis vector minus 1, 0, 1. And so basis for this null space is minus 1, 1, 0, minus 1, 0, 1. These two vectors are clearly linearly independent. You can check that. And they also span this vector space. Why do they span? They span because if you have any vector in this vector space, it looks like minus t1, minus t2 comma t1 comma t2. So, any such vector can be written as a linear combination of these two. How, it is exactly t1 times the first vector plus t2 times the second vector. So, you can see that this method very easily tells you a spanning set for for your solution space. And the main point is that because of all of this, the independence property, namely the 0 and 0s will occur in different positions, it will be forced to be linearly independent. So, I am not proving this, but I will suggest you try to prove this yourself. It is very doable from this point on. So, what do we have geometrically? Geometrically, this is what we get. This is the plane x plus y plus z is equal to 0. So, I will just make a remark before we do another example. So, notice that in our computation, when we did our computation, we did Gaussian elimination on Ax equals B, sorry, Ax equals 0, so that B was 0. So, in the procedure for row reduction, 0, that 0 vector, means that 0 column never changes, because you keep adding multiples of 0s to each other and that is not going to change the 0. So, in this process, we can actually drop that 0, 0, 0. Where did we need that 0 augmented column, we needed it to find the basis. Over there, we said, let us do Rx equals 0 and back calculate to compute what are the values for the dependent variable. That is where we need it. So, to reduce our computations, remember, after all this is a data science course and we are interested in things like efficient calculation. So, we would like to do things as efficiently as possible. So, we need not write that 0, 0, 0. So, what we will do from, in the next example is we will not create the augmented matrix or rather we would not row reduce the augmented matrix, we will reduce just the original matrix. But at the end, we will remember that we have to solve for Rx equals 0. So, that is what this slide is saying that notice that in our computation since the system is homogeneous, that is exactly, that exactly means we have Ax equals 0. So, we have a 0 column. The augmented 0 vector remains unchanged. So, we will drop the 0 column augmented to the matrix while performing the row reduction computations and use it only for solving for the dependent variables.