Main content
Linear algebra
Course: Linear algebra > Unit 1
Lesson 7: Null space and column space- 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)
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
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
http://www.freebookcentre.net/SpecialCat/Free-Mathematics-Books-Download.html(4 votes)
- 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 cant 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)
2:30Video transcript
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.