- Matrix vector products
- Introduction to the null space of a matrix
- Null space 2: Calculating the null space of a matrix
- Null space 3: Relation to linear independence
- Column space of a matrix
- Null space and column space basis
- Visualizing a column space as a plane in R3
- Proof: Any subspace basis has same number of elements
- Dimension of the null space or nullity
- Dimension of the column space or rank
- Showing relation between basis cols and pivot cols
- Showing that the candidate basis does span C(A)
Showing that the candidate basis does span C(A)
Showing that just the columns of A associated with the pivot columns of rref(A) do indeed span C(A). Created by Sal Khan.
Want to join the conversation?
- any sample exercises to try out? there are questions in the calculas section, not sure if there are any here(39 votes)
- Yea, not sure why the Linear Algebra section doesn't get practice problems and all other sections have problems! WE NEED SOME PRACTICE PROBLEMS SAL!(69 votes)
- At2:30and2:37, didn't Sal mean a1, a2 and a4 rather than a1, a2 and aN?(8 votes)
- I believe so. Notice that he switched back. His 4's do look like n's.(8 votes)
- I don't understand how this is a thorough proof that the pivot columns span all of the column space. In the proof, he sets the free variables to -1 and 0. Doesn't this mean the result is only valid in the special case where the free variables are -1 and 0?(7 votes)
- Not exactly. x3 and x5 being free variables just means that the equation x1a1 + x2a2 + x3a3 + x4a4 + x5a5 = 0 holds true for any value of x3 and x5, since the pivot entries (x1, x2, and x4) will change values depending on the values of x3 and x5 to make the equation still hold true. The relationship among the actual columns DOES NOT change just because you pick different values for the free variables. To make this more clear, consider the smaller example x1a1 + x2a2 + x3a3 = 0, where x3 is a free variable and the a's are the column vectors of some matrix A. Let x1 = 2x3 and x2 = -3x3. Obviously in this case, the pivot entries are x1 and x2 and the free variable is x3. We'll now consider two different values of x3 and see that the relationship among the columns remains the same.
Before doing this, we rewrite x1a1 +x2a2 + x3a3 = 0 by rewriting x1 and x3 in terms of x3:
2x3a1 - 3x3a2 + x3a3 = 0
Scenario 1: x3 = -1
2(-1)a1 - 3(-1)a2 + (-1)a3 = 0
-2a1 + 3a2 - a3 = 0
a3 = -2a1 + 3a2
Scenario 2: x3 = 2
2(2)a1 - 3(2)a2 + (2)a3 = 0
4a1 - 6a2 + 2a3 = 0
4a1 - 6a2 = -2a3
-2a3 = 4a1 - 6a2
a3 = -2a1 + 3a2
As you can see, changing the value of the free variable does not change the relationship/equation between the columns. Picking -1 and 0 in the video is just a convenient way to show that the columns corresponding to the free vectors CAN be written as some linear combination of the pivot vectors. If a vector can be written as a linear combination of some other vectors, then that vector is redundant in the set. It doesn't matter if you later pick different values for the free variables and demonstrate that the vector can ALSO be written as a linear combination of the pivot columns and the other free columns.(7 votes)
- Thank you for everything you guys do. But alas, I am wanting more. Is there a possibility that there be videos on abstract algebra and even graduate level classes? I am having a blast relearning and gaining a better grasp on the topics covered in college, but my curiosity for where else can all this math go is consuming me. Never the less, thank you for everything up to this point. You have done a great job with how this website runs to the content provided. God bless you all my friends.(4 votes)
- Khan Academy doesn't cover college-level math material beyond linear algebra and some differential equations.
MIT offers most of its course material for free through MIT OpenCourseWare, including some video lectures and notes.
You can download free math textbooks in more advanced topics at
- What is a candidate basis? I don't understand that term.(3 votes)
- Just think of it as a possible basis, an assumed basis, a suggested basis that might or might not be a real basis, "this candidate basis would probably be a basis, let's check if it really is".(5 votes)
- I am a bit confused about the following:
1. the proof that the non pivot colums can be made as lineair combinations of the pivot colums is made by rewriting the non pivot parts of the equation that sal writes at5:21. Thats clear, but this can also be done for the pivot points.
2. In previous videos the proof is made that the pivot points cannot be written as lineair combinations of the other vectors by looking at the rref and trying to find a number with which you can multiply one of the vectors to get another. This can
t also be done for the non pivots, because they also contain zeros.
I don`t why the above exclusively proves the lineair dependence or indepences of the vectors.(3 votes)
- 1. Consider a set of n linearly dependent vectors, of which any k taken alone are linearly independent. There are lots of ways to choose k vectors from n. But say we establish some rules, so that everyone chooses the same k vectors. These k vectors we then choose to call the linearly independent vectors for the set, and demonstrate that the remaining n - k vectors are linear combinations of the independent k (and thus dependent). Of course, we could have selected a different subset of k vectors, and they would have been independent as well (the remaining n - k in the selection being dependent). The point is - and this is important - that the subspace generated by any selection of k vectors from this set is the same. As far as I understand, the notion of linear dependence/independence was created solely for subspaces. So, if the subspace remains the same, then which k vectors get selected to produce it doesn't matter. So, why not make everyone select the same k vectors and avoid confusion. That's where the "pivot columns are independent and non-pivot columns are dependent vectors" rules comes in. We choose to treat pivot column vectors as independent, and thus disallow them being shown dependent. Hope this long paragraph made sense. :)
2. The proof made was that a pivot column vector cannot be written as a linear combination of other pivot column vectors, since each has a 1 in a different component of the vector, while the rest of their components are all 0. We cannot get 1 by any linear combination of 0's. For the non-pivot column vectors, this is not true.(2 votes)
- 01:07Sal said ''Column span'' but he probably meant ''Column space'' correct me if I'm wrong(2 votes)
- Column span and column space are the same thing. The column span would mean the span of the column vectors, which is exactly what the column space is.(3 votes)
- So essentially, except for the column vectors of a matrix forming a basis for the column space of it, forms a basis for it's null space which I found while experimenting. Is that always the case?(2 votes)
- This makes intuitive sense for a number of reasons - the Kernel of a matrix (or nullspace) is dependent upon the matrix that you choose. So there should be some relation between the column (row) vectors and the Kernel. This holds true also for the Image. By Rank-Nullity theorem we get that if T maps V into W then dim(V) = dim(ImT) + dim(KerT). But any linear transformation has a matrix representation, so the dimension of the Kernel & Image is directly related to the number of linearly independent columns (rows) that the reduced row echelon form has, so it would make intuitive sense if this also depended on what the column vectors are in the matrix!(2 votes)
- And one more thing. He said the past few videos that the dimension of V will be the same as all basis of V will have the same cardinality. In that sense, is it even possible to have more than 1 basis for V? I would think that each subspace would have only one basis, I.e. One set of linearly independent vectors that can span the set. Am I wrong?(1 vote)
- Imagine a matrix A = [v1, v2], where v1 = [1,1,1] and v2 = [2,2,2].
As usual, we can say Col A = span (v1,v2). Now, in this case it is fairly obvious that v2 is a linear combination of v1, and so the set is linearly dependent; however it is still a spanning set for Col A.
A basis is defined as a minimal spanning set, or a spanning set with the fewest possible number of vectors. Since v2 is redundant, we can remove it to get a basis for Col A = v1 = [1,1,1]. But what if we wanted to use v2 instead? Well, we can easily remove v1, resulting in the basis [2,2,2].
Once again, it is obvious that this basis is a linear combination of the first one we solved, and in fact this gives us a way to find any number of bases for Col A: any linear combination of a basis will also be a basis.(3 votes)
- By reordering the columns in the matrix and reordering the x_1, x_2, etc to match, we can get any of the columns to be pivot or free columns, and so we can get any 3 column vectors of the matrix to be a basis correct? If this is correct, is it always the case?(2 votes)
- There will always be the same number of pivot columns/ variables. So once you have that many you can't have any more, so in that way you can't make "any" column a pivot column. you can make n columns pivot columns, where n is the number of pivot columns.
Another pice of the puzzle is linear independence. If two columns themselves are linearly dependent then only one of them can be a pivot column. for instance if one column was <1, 2, 3> and another was <2, 4, 6> only one of them would be a pivot column, no matter how you reordered the variables.
This continues, if two columns together are linearly dependent to a third column, you could never have all three, just two. of course it is difficult to tell which columns are linearly dependent before putting the matrix into rref.
I hope that made sense, but let me know if not. The main takeaway is that yes, there is some control you have, but if columns wind up being incompatible, that would be one limitation to the control you have. The most control you do have is the very first column you do, and you can guarantee that it will be a pivot column as long as there is at least one number in it that isn't 0(2 votes)
Two videos ago we asked ourselves if we could find the basis for the columns space of A. And I showed you a method of how to do it. You literally put A in reduced row echelon form, so this matrix R is just a reduced row echelon form of A. And you look at its pivot columns, so this is a pivot column. It has a 1 and all 0's, this is a pivot column, 1 and all 0's, and the 1 is the leading non-zero term in its row. And this is a pivot column, let me circle them, these guys are pivot columns, and this guy's a pivot column right there. You look at those in the reduced row echelon form of the matrix, and the corresponding columns in the original matrix will be your basis. So this guy, this guy, so the first, second, and forth columns. So if we call this a1, this is a2, and let's call this a4, this would be a3, and this is a5. So we could say that a1, a2, and a4 are a basis for the column span of A. And I didn't show you why two videos ago. I just said this is how you do it. You have to take it as a bit of an article of faith. Now in order for these to be a basis, two things have to be true. They have to be linearly independent, and I showed you in the very last video, the second in our series dealing with this vector. I showed you that by the fact that this guy is r1, this guy is r2, and this guy is r4, it's clear that these guys are linearly independent. They each have a 1 in a unique entry, and the rest of their entries are 0. We're looking at three pivot columns right now, but it's true if we had n pivot columns. That each pivot column would have a 1 in a unique place, and all the other pivot columns would have 0 in that entry. So there's no way that the other pivot columns, any linear combination of the other ones, could never add up to each of them. So these are definitely linearly independent. And I showed you in the last video that if we know that these are linearly independent, we do know that they are, given that R has the same null space as A, we know that these guys have to be linearly independant, I did that in the very last video. Now the next requirement for a basis, we checked this one off, is to show that a1 a2 and an, that their span equals the column space of A. Now the column space of A is a span of all five of these vectors, so I had to throw a3 in there and a5. So to show that just these three vectors by themselves span our column space, we just have to show that I can represent a3 and a5 as linear combinations of a1, a2, and a4. If I can do that, then I can say then these guys are redundant. Then the span of a1, a2, a3, a4, and a5 doesn't need the a3 and the a5 terms, that we can just reduce it to this. Because these guys can be represented as linear combinations of the other three. These guys are redundant. And if we can get rid of them we can show that these guys can be represented as linear combinations of the other, then we can get rid of them. And then the span of these three guys would be the same as the span of these five guys, which is of course the definition of the column space of A. So let's see if we can do that. Let me fill in each of these column vectors a1 through a5, and then each of these column vectors let me label them r1, r2, r3, r4, and r5. Now let's explore the null spaces again. Or not even the null spaces, let's just explore the equations Ax is equal to -- let me write it this way -- instead of x let me write x1, x2, x3, x4, x5 is equal to 0. This is how we define the solution set of this. All the potential x1's through x5's or all the potential vectors X right here, that represents our null space. And then also let's explore all of the R times x1, x2, x3, x4, x5's is equal to 0. This is the 0 vector, in which case you would have four entries in this particular case. It would be a member of Rm. So these equations can be rewritten. I can rewrite this as -- what were the column vectors of A? They were a1, a2 through a5. So I can rewrite this as x1 times a1 plus x2 times a2 plus x3 times a3 plus x4 times a4 plus x5 times a5 is equal to 0. That was from our definition of matrix vector multiplication, this is just a bunch of column vectors a1 through a5, I drew it up here. I can just rewrite this equation like this. Similiarly, I can rewrite this equation as the vector r1 times x1 or x1 times r1 plus x2 times r2 plus x3 times r3 plus x4 times r4 plus x5 times r5 is equal to 0. Now we know that when we put this into reduced row echelon form the x variables that are associated with the pivot columns are -- so what are the x variables associated with the pivot columns? Well, the pivot columns are r1, r2, and r4. The x variables associated with them, we can call them pivot variables, and the ones that are not associated with our pivot columns are free variables. So the free variables in this case, x3 and x5, are free variables. And that applies to A. All of the vectors x that satisfy this equation also satisfy this equation, and vice versa. They're the exact same null space, the exact same solution set. We can also call this x3 and this x5 as free variables. Now what does that mean? We've done multiple examples of this. The free variables, you can set them to anything you want. So x3 in this case and x5 you can set it to any real number. You can set to anything you want. And then from this reduced row echelon form we express the other pivot variables as functions of these guys. Maybe x1 is equal to Ax3 plus Bx5. Maybe x2 is equal to Cx3 plus Dx5. And maybe x4 is equal to Ex3 plus Fx5. That comes directly out of literally multiplying this guy times this equals 0, you'd get a system of equations that you could solve for your pivot variables in terms of your free variables. Now given this, I want to show you that you can always construct one of your -- in your original matrix. So if we go to our original matrix, you can always construct one of the vectors that are associated with the free columns. You can always construct one of the free vectors using the linear combination of the ones that were associated with the pivot columns before. And how do I do that? Well, let's say that I want to find some linear combination that gets me to this free column, that gets me to a3. So how could I do that? Let me rearrange this equation up here. So what do I get? I'm sorry. That's x3 a3. If I subtract x3 a3 from both sides of the equation, I get minus x3 a3 is equal to x1 a1 plus x2 a2 plus -- I don't have the 3 there -- plus x4 a4 plus x5 -- sorry, x isn't a vector-- x5 a5. This, I guess salmon colored statement here, is just another rewriting of this equation right here. And all I did is I subtracted this term right here, x3 a3, from both sides of the equation. Now x3 is a free variable. We can set it to anything we want, and so is x5. So let's set x3 is equal to minus 1. Then this term right here becomes a 1, because that was a minus x3. And let's set x5 equal to 0. So if x5 is equal 0, this term disappears, and I did that because x5 is a free variable. I can set them to anything I want. Now I've written a3 as a linear combination of, I guess you could call it my potential basis vectors right now, or the vectors a1, a2, and a4. They're the vectors in the original matrix that were associated with the pivot columns. Now in order to show that I can always do this, we have to show that for this combination there's always some x1, x2, and x4 that satisfy this. Well, of course there's always some x1, x2 that satisfy this, we just have to substitute our free variables, x3 is equal to minus 3 and x5 is equal to 0, into these equations that we get from our system when we did it with the reduced row echelon form. In this case you have x1 is equal to minus A plus 0, x2 is equal to minus C, so on and so forth. So you can always do that. You can always express the vectors that are associated with the non-pivot columns as linear combinations of the vectors that are associated with the pivot columns. What I just did for a3, you could just as easily have done for a5 by subtracting this term from both sides of the equation. Setting x5 to negative 1 and setting x3 to 0 so that the 3 term disappears, and you could run the same exact argument. So given that, I've hopefully shown you, or least helped you see or made you comfortable with the idea, that the vectors -- let me do them in a nice vibrant color -- these magenta color vectors here that are associated with the free columns or with the free variables, the free variables were x3 and x5, those were these columns right here, that they can always be expressed as linear combinations of the other columns. Because you just have to manipulate this equation, set the coefficient for whatever you're trying to find a linear combination for equal to minus 1, and set all the other free variables equal to 0 that you're not solving for. And then you can get a linear combination of the vectors that are associated with the pivot columns. So given that, we've shown you that these free vectors, and I'm using my terminology very loosely, that these ones that are associated with the non pivot columns can be expressed as linear combinations of these guys. So they're unnecessary. The span of this is equivalent to the span of this, the span of this is the column space of A, so the span of this is the column space of A. So in the last video I showed you that these guys are linearly independent, and now I've showed you that the span of these guys is the column space of A. So now you should be satisfied that these vectors that are associated -- let me do it in a blue color -- that that column vector, this column vector, and this column vector, that are associated with the pivot columns in the reduced row echelon form of the matrix, do indeed represent a basis for the column space of A. Anyway, hopefully you didn't find that too convoluted.