Current time:0:00Total duration:12:48

0 energy points

# Dimension of the column space or rank

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

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.