Main content

## 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

# Dimension of the column space or rank

Dimension of the Column Space or Rank. Created by Sal Khan.

## Want to join the conversation?

- So I conclude from this and the last video that for a Matrix A with the form (mxn), n=rank+nulity. Is this always true?(42 votes)
- That's exactly right, nullity is the number of redundant (free variable) columns, rank is the number of non-redundant (pivot) columns, so together they add up to the total number of columns. I was just going through those videos and looked it up to be sure I'd drawn the right conclusion too. Nice work.(28 votes)

- So every matrix in reduced row echelon form is linearly independent? Correct?(2 votes)
- Rodrigo,

No, this isn't the case. If the columns of a matrix are not linearly independent, then the columns of the reduced row echelon form of the matrix will ALSO not be linearly independent.

For example, let's look at a matrix whose columns are obviously not linearly independent, like:

|1 2|

|2 4|

Obviously, we can get the second column by multiplying the first column by 2, so they are linearly dependent, not independent. Now let's put the matrix into reduced row echelon form.

Step 1. Get all zeros in the 1st column except for the top term. I can do this by adding -2 times the first row to the second row, to eliminate the 2nd term of the first column:

|1 2|

|0 0|

But notice, that this is as far as I can go. This IS reduced row echelon form for this matrix, and notice also that the columns are not linearly independent. The second column is STILL 2 times the first column.

Hope that helps.(37 votes)

- Isn't it clear that the vectors are linearly dependent? You have 5 vectors in R^4, it is obvious that (at least) one must be redundant.(11 votes)
- Yep. It's clear that at least one is redundant. So the rank of A must be 4 or less. But in order to find the rank, you need to figure out how many are redundant. Sal was kind enough to make this example with two columns redundant so we can see that the answer is not simply Rank(A) = 4.(22 votes)

- I watched all the linear algebra video's up to this point. I can construct RREF, find the null space, column space, the nullity and the rank. etc... but I still miss the point of it all. What is the purpose of these definitions. I still have no clue about the context, what problems will this help us solve?(5 votes)
- Great question! Linear Algebra has many applications - for instance almost anything in Physics is expressed as a vector of one form or another. Calculus is all about taking non-linear things and approximating them linearly, that was the whole point of derivatives. This is due to the fact that linear equations are relatively easy to solve, whereas non-linear ones can be very difficult. A standard technique in mathematics is looking at a non-linear system and finding a linear approximation. Often times in physics you have a taylor series expansion over differential pieces of length, area, volume, etc. so that the square and higher terms cancel. In Computer Science everything explicitly uses linear algebra. It's probably the most important mathematics, that and fourier analysis.(8 votes)

- Does the rank of A also equal to number of non-zero rows of RREF(A)?(5 votes)
- You are right, rank(A) = number of non-zero rows of rref(A).(4 votes)

- Hi, i am kind's new to khan academy and stuff, is there any way i can practice the knowledge above. I mean i have watched a bunch of videos, but i think i will forget all the concepts unless i practice them.(4 votes)
- is there any video talking a bout the rank of matrix ?(3 votes)
- This one? Rank is the dimensionality of the column space of the matrix, i.e. rank(A) = dim(C(A))(2 votes)

- I think "9:50" does not need a proof as they're just i j k l unit vectors.(2 votes)
- 9:54A proof may be simple, but still needed. That is the case here.(3 votes)

- Isn't 6-2(-3) =12 instead of zero?(3 votes)
- No thesergcan's answer was incorrect.

The question was correct as it does compute to 12. However, Sal mentions at6:03in the video that 6 + 2 times minus 3, which is 6+2(-3), does indeed equal 0.

However, "Here you multiply the numbers first: -2*(-3) = 6 ( you can think of the equation as 6+-2(-3) =12). So 6-6 = 0." will never result in 6-6 = 0.(1 vote)

- At7:28you state that r1, r2, and r4 are linearly independent. Are those columns (r1, r2, and r4 ) dependent variables though as they have a leading 1 value ?(2 votes)
- Yes, that's right (I didn't notice that). The pivot variables are dependent variables, and the non pivot variables are independent (free) variables. But the vectors in the pivot columns (in both "A" and "rref(A)") form a linearly independent set, and those in the non pivot columns are in their span, as Sal explains.(1 vote)

## Video transcript

We've seen in several videos
that the column space of a matrix is pretty straightforward
to find. In this situation the column
space of A is just equal to all of the linear combinations
of the column vectors of A. Another way of saying all of
the linear combinations is just the span of each of
these column vectors. So if we call this one
right here a1. This is a2, a3, a4. This is a5. Then the column space of A is
just equal to the span of a1, a2, a3, a4, and a5. Fair enough. But a more interesting question
is whether these guys form a basis for the
column space. Or even more interesting, what
is the basis for the column space of A? And in this video I'm going
to show you a method for determining the basis, and along
the way we'll get an intuition for maybe
why it works. And if I have time, actually I
probably won't have time in this video. In the next video I'll prove
to you why it works. So we want to figure out
the basis for the column space of A. Remember the basis just means
that vectors span, C, A. Clearly these vectors span
our column space. I mean the span of these vectors
is the column space. But in order to be a basis, the
vectors also have to be linearly, let me just write,
linearly independent. And we don't know whether these
guys or what subset of these guys are linearly
independent. So what you do-- and I'm just
really going to describe the process here, as opposed to the
proof-- is you put this guy in reduced row
echelon form. So let's do that. So let me see if
we can do that. Let's keep our first
row the same. 1, 0. Let me do it actually in the
right side right here. So let's keep the first
row the same. 1, 0, minus 1, 0, 4. And then let's replace our
second row with the second row minus 2 times the first row. So then our second row. 2 minus 2 times 1 is 0. 1 minus 2 times 0 is 1. 0 minus 2 times negative
1, so that's 0 plus 2. 0 minus 2 times 0 is just 0. And then 9 minus
2 times 4 is 1. Fair enough. Now we want to zero
out this guy. Well it seems like a pretty
straightforward way. Just replace this row with this
row plus the first row. So minus 1 plus 1 is 0. 2 plus 0 is 2. 5 minus 1 is 4. 1 plus 0 is 1. Minus 5 plus 4 is minus 1. And then finally we got this guy
right here, and in order to zero him out, let's
replace him with him minus the first row. So 1 minus 1 is 0. Minus 1 minus 0 is minus 1. Minus 3 minus negative 1, that's
minus 3 plus 1, so that's minus 2. Minus 2 minus 0 is minus 2. And then 9 minus 4 is 5. So we did one round. We got our first pivot
column going. Now let's do another round
of row operations. Well we want to zero all
of these guys out. Luckily this is already 0. So we don't have to change our
first row or our second row. So we get 1, 0, minus 1, 0, 4. Our second row becomes
0, 1, 2, 0, 1. And now let us see if we can
eliminate this guy right here. And let's do it by replacing our
blue row, our third row, with the third row minus
2 times the second row. So 0 minus 2 times 0 is 0. 2 minus 2 times 1 is 0. 4 minus 2 times 2 is 0. 1 minus 2 times 0 is 1. Minus 1 minus 2 times
1 is minus 3. All right. Now this last guy we want to
eliminate him, and we want turn this into a 0. Let's replace this fourth row
with the fourth row plus the second row. So 0 plus 0 is 0. Minus 1 plus minus 1 is 0. Minus 2 plus minus 2 is 0. Minus 2 plus 0 is minus 2. And then 5 plus 1 is 6. We're getting close. So let's look at our
pivot entries. We have this is a pivot entry. That's a pivot entry. And this is not a pivot entry,
because it's following obviously another. This guy is a pivot entry
right here, or will be. Zero this minus 2 out, and
I think we'll be done. So let me write my first row
just the way it is, because everything above it is
0, so we don't have to worry about it. So my first row I can just write
as 1, 0, minus 1, 0, 4. I can write my second
row, 0, 1, 2, 0, 1. I can write my third row
as 0, 0, 0, 1 minus 3. And now let's replace
my fourth row. Let's replace it with it plus
2 times the second row. So 0 plus 2 times 0, 0 plus 2
times 0, 0 plus 2 times 0, minus 2 plus 2 times
1 is just 0. 6 plus 2 times minus 3, that's
6 minus 6, that's just 0. And there we've actually put
our matrix in reduced row echelon form. So let me put brackets
around it. It's not so bad if you just
kind of go and just do the manipulations. And sometimes you kind of get
a headache thinking about doing something like this,
but this wasn't too bad. So this is let me just say the
reduced row echelon form of A. Let me just call
that matrix R. So this is matrix
R right there. Now what do we see
about matrix R? Well it has 3 pivot entries,
or 3 pivot columns. Let me square them out,
or circle them out. Column 1 is a pivot column,
column 2 is a pivot column, and column 3 is a
pivot column. And we've done this in
previous videos. There's two things
that you can see. These three columns are clearly
linearly independent. How do we know that? And that's just with respect
to each other. If we just took a set of, let's
call this r1, r2, and this would be r3, this would
be r4 right here. It's clear that the set r1,
r2, and r4 is linearly independent. And you say why is that? Well look, our one's got a 1
here, while the other two have a 0 in that entry, right? And this is by definition
of pivot entries. Pivot entries have 0's, or
pivot columns have 0's everywhere except for
where they have a 1. For any pivot column, it will be
the only pivot column that has 0's there. Or it'll be the only pivot
column that has a 1 there. So there's no way that you can
add up combinations of these guys to get a 1. You can say 100 times
0, minus 3, times 0. You're just going to
get a bunch of 0's. So no combination of these
two guys is going to be equal to that guy. By the same reasoning, no
combination of that and that is going to equal this. This is by definition
of a pivot entry. When you put it in reduced row
echelon form, it's very clear that any pivot column will
be the only one to have 1 in that place. So it's very clear that these
guys are linearly independent. Now it turns out, and I haven't
proven it to you, that the corresponding columns in
A-- this is r1, but it's A before we put it in reduced row
echelon form-- that these guys right here, so a1, a2,
and a4 are also linearly independent. So a1-- let me circle
it-- a2, and a4. So if I write it like this,
a1, a2, and a4. Let me write it in
set notation. These guys are also linearly
independant, which I haven't proven. But I think you can kind of
get a sense that these row operations really don't change
the sense of the matrix. And I'll do a better explanation
of this, but I really just wanted you to
understand how to develop a basis for the column space. So they're linearly
independent. So the next question is do they
span our column space? And in order for them to span,
obviously all of these 5 vectors, if you have all of
them, that's going to span your column space
by definition. But if we can show, and I'm not
going to show it in this video, but it turns out that you
can always represent the non-pivot columns as
linear combinations of the pivot columns. And we've kind of touched on
that in previous videos where we find a solution for the
null space and all that. So these guys can definitely
be represented as linear combinations of these guys. I haven't shown you that, but
if you take that on faith, then you don't need
that column and that column to span. If you did then, or I guess a
better way to think it, you don't need them to span,
although they are part of the span. Because if you needed this guy,
you can just construct him with linear combinations
of these guys. So if you wanted to figure out
a basis for the column space of A, you literally
just take A into reduced row echelon form. You look at the pivot entries
in the reduced row echelon form of A, and that's
those three. And then you look at the
corresponding columns to those pivot columns in your
original A. And those form the basis. Because any linear combination
of them, or linear combinations of them can be
used to construct the non-pivot columns, and they're
linearly independant. So I haven't shown you that. But for this case, if you want
to know the basis, it's just a1, a2, and a4. And now we can answer
another question. So a1, a2, and a4 form a basis
for the column space of A, because you can construct the
other two guys with linear combinations of our basis
vectors, and they're also linearly independent. Now the next question is what is
the dimension of the basis? Or what is the dimension-- not
the dimension of the basis-- what is the dimension of
the column space of A? Well the dimension is just the
number of vectors in any basis for the column space. And all bases have the same
number of vectors for any given subspace. So we have 1, 2, 3 vectors. So the dimension of our column
space is equal to 3. And the dimension of a column
space actually has a specific term for it, and that's
called the rank. So the rank of A, which is the
exact same thing as the dimension of the column space,
it is equal to 3. And another way to think about
it is, the rank of A is the number of linearly independent
column vectors that you have that can span your entire
column space. Or the number of linearly
independent column vectors that can be used to construct
all of the other column vectors. But hopefully this didn't
confuse you too much, because the idea is very simple. Take A, put it into reduced row
echelon form, see which columns are pivot columns. The corresponding columns are
going to be a basis for your column space. If you want to know the rank for
your matrix, you can just count them. Or if you don't want to count
those, you could literally just count the number of pivot
columns you have in your reduced row echelon form. So that's how you do it. In the next video I'll explain
why this worked.