Let's say I've got some set A of the vectors a1, a2,
all the way to an.
And I know for a fact that it's a basis for
the subspace V.
What I want to show you in this video is that if this guy
has n elements right here, that any set that spans V has
to have at least n elements, [typing]
or n members, or cardinality of n.
There's all different ways of saying you had n
vectors in this set.
I'm saying that every set that spans V must have at least n
elements, if the sum basis set has n elements for V.
Let's see if we can kind of run with the set that has less
than n elements and see if we reach any contradictions.
So let's say that I have sum set B here and it's equal to
the vectors b1, b2, all the way to bm.
And m is less than n, so I have sum set of vectors here
that have fewer elements than my set A.
So you come to me one day and say, look I found you this set
of vectors right here.
And not only does it have fewer elements than A,
but it spans V.
I look at you very suspiciously because I always
thought that this green statement was true.
So we start a little bit of a thought experiment.
And I say OK, you claim that your set spans
V, so let's do something.
Let me define a new set.
Let me call this new set B1 prime, and you'll see why I'm
doing this kind of strange notation.
What's essentially going to be is a set B plus my vector a1.
So it's a1, and then I have all of my elements of B.
So be b1, b2, all the way to bm.
Now I think you and I could both agree that this set is
How do I know that?
Linear dependence means that at least one of the elements
of the set can be represented as a linear
combination of the others.
Well, we know that a1 is one of the basis vectors for V for
this definition of a basis.
But all the basis vectors are members of V.
If this set is a basis for V, then this means that this set
spans V, or that every member of V can be represented as a
linear combination of these guys.
Or in other ways every linear combination of
these guys is in V.
And one of the linear combinations of these guys is
you just set the coefficient on a1 to be 1, and the
coefficients on everyone else to be 0.
So obviously a1 is also in the set.
So if a1 is in V, and all of these guys span V, by
definition if these guys span V some linear combination of
these guys can be used to construct any member of V.
So you can take some linear combination of these guys to
So you could say a1 is equal to d1, where the d's are the
constants, d1 b1 plus d2 b2, all the way to dm bm, and at
least one of these have to be non-zero.
We know that a is a non-zero vector.
If it was a 0 vector, this couldn't be a basis because it
wouldn't be linearly independent, because you can
always represent a 0 vector as really just 0
times any other vector.
So this won't be a 0 vector.
So at least one of these are non-zero.
So let's just say, for the sake of argument, that dj --
so the coefficient on bj is non-zero.
So dj does not equal 0.
So we could actually solve for that term.
So over here someplace you have the term dj bj, plus a
bunch of other stuff.
We can solve for this term if we subtract it from both sides
of the equation, and then divide both sides by minus dj,
and put this minus a1 on the other side, what do we get?
I know that was a lot of operations, but that's just
straight up algebra.
I think you can say that we could rewrite this right here.
We can solve for bj.
That should be equal to minus 1 over its coefficient.
And, if we subtract the a1 from both sides and then plus
all of these guys, plus d1 b1 plus all the way -- you're
going to have a little bit of a gap here.
I'll just draw it like that.
It's very unconventional notation where this guy sat.
All the way to dm bm.
I'm doing this all of this to show you that, by definition,
you can write a1 as a linear combination
of these other guys.
But you can just rearrange things.
You can rearrange it so that you can write one of the other
guys as a linear combination of the rest of the
other guys and a1.
This guy's now redundant.
I don't need this guy any longer to continue to span V.
Clearly this set still spans V.
I added an extra vector here.
But I can remove this guy right here from my set b1
prime and still span V.
And how do I know that?
Because I can achieve him.
By removing him, I don't lose anything.
Because if I needed this vector to create some other
vector, I can construct him with a linear combination of
the rest of the b's, plus my a1.
So let's get rid of him, and call that set v1.
And actually, just for the sake of notation, let me just
change his name.
This is little unconventional.
You won't see it done like this in any textbook.
But I think it's a little bit easier, instead of having to
keep talking about these little guys that are embedded
someplace in the middle of the stream.
I mean these names, b1, b2, bn, they're arbitrary names.
Let me swap the labels.
Let me just say that bj is equal to b1, and that b1 is
equal to bj.
I'm just swapping their names.
I took that guy, I renamed him b1.
I renamed b1, bj, so that I could swap them.
So I'm essentially just going to remove b1 one from the
vector just to make my notation easier.
You could just keep saying I'll remove this bj from the
middle, but it becomes very confusing then.
So let me call my new set after removing the bj that
I've renamed as b1, let me just call that straight up B1.
So my straight set B1 is equal to a1, and then remember I
removed the bj and I renamed that as b1, and then I
renamed b1 as bj.
So now my set looks like this -- let me go
to the other color.
b2 -- and for all we know bj might have been
b1, we don't know.
There are probably multiple of these that are non-zero, so we
could pick any of those to be our bj.
But anyway, we took our bj renamed it b1,
and removed the b1.
So now out set looks like this: b3 all the way to bm.
This set still spans V.
And we know that because the guy we removed can be
constructed with any linear combination of these guys.
So we haven't lost our ability to construct all of the
vectors in V.
Now let me create another vector.
We'll do a new color.
Let's say I have the vector B2 prime.
And what I'm going to do here is now I'm going to take
another element from our basis of V.
I'll take the second element; I'll take a2.
I'll take a2 and throw it on this guy.
So now we have the set B2 prime is equal to -- I'm going
to add a2 to this guy.
So you have a1, a2, and then you have all the rest of these
guys, b2, b3 all the way bm.
Of course this still spans V, I just added something here.
But this is definitely linearly dependent.
Remember I didn't say in the beginning whether this was
linear dependent or not.
It may or may not be.
But when you add this other vector that's in V, you
definitely know that you're linear dependent, because
these guys can construct that guy.
Similarly we know that this vector B1 spans V.
So when we add this new element here, we know that it
can be written as a linear combination of the other one.
So we know that this right here is linearly dependent.
And we could say that a2 is equal to some constant times
c1 times a1 plus c2 b2 plus c3 b3, all the way to cm bm.
Now what I'm going to claim is that at least one of these
coefficients is non-zero.
So at least one of the ci's does not equal to 0.
And I'll make the further claim that there's at least
one that's outside of this one.
That at least one of the coefficients on these B terms
has to be non-zero.
And the way you can think about is, what if all of these
guys were 0?
If all of these guys were 0, then that means that a2 is a
linear combination of a1.
All of these guys would cancel out, and you'd have a2 is
equal to some non-zero constant times a1.
We know that's not the case because these two guys come
from the same linearly independent set.
They both come from that spanning basis.
The fact that they are a basis -- the word spanning basis, I
shouldn't say it like that, because it's redundant.
A basis is a spanning set that is linearly independent.
If they're linearly independent we know that a2
cannot be represented as some linear combination of the rest
of these guys.
So we know that one of the coefficients on the B terms
has to be non-zero.
And let's just say that you're going to have a cj bj, this is
a different one than we had before.
And we know that this guy, at least one of them has to be
non-zero, because if all of these guys were non-zero, then
you wouldn't be able to say that this vector and that
vector are linearly independent, because they
would be scalar multiples of each other.
So we're going to do the same exercise.
This guy right here, cj bj, obviously this coefficient is
non-zero so we can solve for our bj.
Once again we can say that bj is equal minus 1 over cj times
minus a2 plus c1 a1, all the way to cm bm.
So we have some bj here that can be represented as a linear
combination of the rest of the people, including our new a2.
And so, just like we did before, let's remove him.
Let's take him out of the set.
And before I take him out of the set, I'm
going to rename him.
Just solely for the purpose of notational simplicity, I'm
just going to rename our bj, b2, and our b2 is equal to bj.
So I'm just rearranging the names.
And I'm going to remove our b2.
Or I'm going to remove what I now call b2.
It was whatever was out here that could be represented as a
linear combination of everything else,
including our new a2.
When I remove one of those terms right here, and I
renamed it B2.
And now it's equal to a1 a2, and now I have the
leftovers of my b's.
So I have b3, b4, all the way to bm.
Notice I still have exactly m elements, and
this still spans V.
It spans V because the element that I took out of it can be
represented as a linear combination of these guys.
So if I ever want to construct anything that need that, I can
construct that vector with some
combination of these guys.
So it wasn't necessary.
It still spans V.
So this process I'm doing, I can just keep repeating it.
I can add an a3.
I can define B3 prime.
I can just add a3 to this set right here, a2 a3.
And then I have my b3, b4, all the way to bm.
And I'll say this is linearly dependent because
this guy spans V.
So everything but this guy spans V.
So obviously you can construct this guy with a linear
combination of the rest of them.
So you could say a3 is equal to sum a1 plus sum a2 plus c3
b3, all the way to cm bm.
And we know that at least one of the coefficients on the B
terms has to be non-zero.
Because if all of those were 0, then you would be saying
that a3 could be a linear combination of the A terms.
And we know that a3 can't be a representative linear
combination of the A terms, because all these a terms come
from a linearly independent set.
So you do the same operation.
Let's say that cj is non-zero.
Then you could solve for that bj.
And then I do that little renaming thing I do, where I
rename the bj b3, and rename b3 bj, and then I remove b3.
And I get the set B3 is equal to a1, a2, a3.
And I have b4 all the way to bm.
And this still spans V.
And I keep doing it.
So what's going to happen eventually?
What's going to happen if I keep doing this process over
and over and over again?
Eventually I'll essentially replace all of the bm's.
Or I'll replace all of the n terms, so eventually I'll have
a set that looks like this.
I'll have a set that looks Bm, where I will have replaced
each of these guys with an a.
So I have a1, a2, a3, all the way to am.
You can always do this by definition if you started with
that initial set B that is a spanning set.
And once you do this process you'll get the same result
that this also spans V.
Now let me let me write this.
This is the result we got by starting off with a spanning
set B that has m elements, where we said that m
is less than n.
So we always have enough a elements to do this, because
we have more a elements than there were b
elements to begin with.
And we get result that this spans V.
But we already said that the set A which is equal to a1,
a2, all the way to am, and then am plus 1, I don't know
how many more terms there are between m and n, but then you
go all the way to an.
Remember we said that n is greater than m.
Or when we defined B, we said that m is less than n.
Same thing, that this was a smaller set.
Now we're saying that this spans V, but at the same time
we said this was a basis.
This is just our starting fact, that this
is a basis for V.
Basis means two things: it means it spans V and it means
it's linearly independent.
Now we just got this result by assuming that we had some set
B that's smaller than this set here that spans V.
We were able to construct this by saying that a1 through am
also spans V.
The result we got is that this spans V.
But if this subset of A spans V, then A becomes linearly
Because if this subset spans V, that means that an can be
represented as some linear combination of these guys.
So that implies that you're linearly dependent, which is a
contradiction with our original statement that set A
is a basis for V, because that means it's linearly
If you're able to do this, then this means that there was
some smaller spanning set, you get the result that A has to
be linearly dependant, even though we said it was linearly
So we now know, we get our contradiction, we say that
there cannot be [typing]
a spanning set B that has fewer elements than A.
And this is a pretty neat outcome, because now, if I
come up to you and say I found some set X spans
the subspace V again.
Then you know that X has five elements.
You now know that no set that spans the subspace V can have
fewer than five elements.
Even better, if I told you that X is a basis for V, and I
told you it has five elements, and Y is a basis for V.
You know that Y also has to have exactly five elements.
How do I know that?
Well, if Y is a basis, then that means that it spans V.
And we know it can't have anything
less than five elements.
We just proved that.
One way we know that Y has to have greater than or equal to
But on the other hand we know if Y is a basis for V and X is
a basis, X also spans V.
So we know that X has to have fewer elements than Y.
So we know that [typing]
Y's elements have to be greater than X's elements,
because any spanning set has to have more elements, or at
least as many elements, as a basis set, X's elements.
And then since X is a spanning set, X's elements have to be
greater than or equal to Y's elements,
because why is a basis.
But if this guy's elements are less than this guy's elements,
but it's also greater than or equal to, we know that the
number of elements that X has-- X's elements, or the
cardinality or the number of elements in it --is equal to
And so now that we know that any basis for a vector space--
Let me just go back to our set A.
A is equal to a1 a2, all the way to an.
We can now say that any basis for some vector, for some
subspace V, they all have the same number of elements.
And so we can define a new term called the
dimension of V.
Sometimes it's written just as dimension of V, is equal to
the number of elements, sometimes called the
cardinality, of any basis of V.
And I went through great pains in this video to show that any
basis of V all has the same number of elements, so this is
You can't have one basis that has five elements and
one that has six.
By definition they would either both have to have five,
or they both would have to have six.
And so we can define our dimensionality.