If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Proof: Any subspace basis has same number of elements

Proof: Any subspace basis has same number of elements. Created by Sal Khan.

Want to join the conversation?

  • old spice man green style avatar for user newbarker
    At when Sal says/writes "set X spans subspace V and X has 5 elements you now know that no set than spans the subspace V can have fewer than 5 elements", isn't this statement incorrect? The set X didn't claim to be a BASIS for V, just span V. (I know Sal continues with "even better if X is a basis..." but it sounds like he's going on to make a separate statement).
    (57 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Terry Bollinger
    I am baffled as to how the existence of a minimum number of basis elements meaningfully defines "dimensionality." Doesn't the structure of the matrix itself define a deeper concept of dimensionality that pervades all of linear algebra, with certain data selections merely restricting that dimensionality in various subsets?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user SteveSargentJr
      I think you may be over-thinking things:

      When dealing with vector spaces, the “dimension” of a vector space V is LITERALLY the number of vectors that make up a basis of V.

      In fact, the point of this video is to show that even though there may be an infinite number of different bases of V, one thing they ALL have in common is that they have EXACTLY the same number of elements. For example, if X is a basis of V and X has 10 elements then any other basis of V will ALSO have exactly 10 elements (and we would say “V has dimension 10” or, equivalently, “dim(V) = 10”).

      Does this make sense?

      [NOTE: a vector space does not necessarily have to have a finite dimension, though this is probably something Sal will address much later in the playlist.]
      (17 votes)
  • blobby green style avatar for user Mohamed A. Haggag
    I am confused now !
    If the number of column vectors in some matrix represent its dimensionality, then what do the number of elements in each vector represent?
    Before introducing the concept matrices, Sal said (and correct me if I am wrong) that the number of elements in each vector represents the dimensionality of the space thatis vector lives in. For example, a vector with three components is living in a three dimensional vector space..now what :/ ?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Justin
      If the components of your vector can be anything, then your dimensionality is the number of components. So he's saying that for <x,y,z>, if x y and z can vary independently, then you have 3 dimensions.

      However, there are many subspaces in R^3 that have less than 3 dimensions. Remember that dimensionality is a property of vector spaces, not vectors. Take for example the subspace defined by the span of {<1,0,0>,<0,1,0>} -- the XY plane. This vector space only has two dimensions...because every element can be represented as a combination of those two spanning vectors. So <3,4,0> is a part of the space, etc.; the vector space is 2-dimensional. But that's because the three components aren't allowed to vary independently. The third one "always has to be zero"...you're restraining the dimensionality.
      (15 votes)
  • duskpin ultimate style avatar for user Caitlin Ducate
    Starting at , I don't understand how he resolves the contradiction. I see that there is one, but I don't know how he can draw the conclusion he does. If he can devise a subset that spans V and is smaller than the originally conceived span, why wouldn't he simply have been wrong that A is linearly independent?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Kyler Kathan
      The information we're originally given is as follows:
      A is a subspace created as the span of n basis vectors
      B is a subspace created as the span of m basis vectors
      m>n
      B spans A
      Since there's a contradiction once given these things, we can say that all of the above statements can't be true at the same time. Since the first two statements are just definitions, it's the bottom 2 statements that are incompatible.
      (6 votes)
  • mr pants teal style avatar for user Moon Bears
    How would one prove an n-dimensional linear subspace is a manifold?
    (4 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Mez Cooper
    What was the point of bringing up y is also a basis for V towards the end of the video? We knew x was a basis for V, too. Just looks an overcomplicated and unnecessary way of saying they have the same number of elements. Or what?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • old spice man green style avatar for user newbarker
    I have exactly the same question as Msrtra. Sal started with A as a basis for V, so by definition (of a basis) the number of vectors in A is the minimum! Sal then goes through the elaborate process to arrive at B_m. It seems to me the justification for B_m not being a basis for V relies upon the definition of basis (around ), so why not make the video a lot shorter and just use the definition?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user James
      This question misunderstands the definition of "basis." Let {a_1, ..., a_n} be a basis for a space V. The definition of a basis says that {a_1, ..., a_n} is "minimal" only in the following sense: no proper subset of {a_1, ..., a_n} can span V. In other words, if you're only allowed to include a_1, ..., a_n in your basis, then you need all n of them to span V. But in this video, we're considering a different situation: you ARE allowed to put different elements in your basis. It is conceivable that you could be clever and find some other b_1, ..., b_m which span V, with m < n; nothing in the definition of a basis automatically forbids this. Thus there is something interesting here that needs to be proven.

      It seems like a lot of people are confused by this point. Hopefully the video will be redone to make this clearer. Sal can also use that as an opportunity to clean up the part where he tried to rename b_j as b_1 (at ). Contrary to what he claims, most textbooks would have done the proof that way, using the phrase "without loss of generality" to rename b_j as b_1 from the start. I'm not sure if this was bad planning or a foolish attempt to avoid having to explain the meaning of "without loss of generality," but the result is a mess.
      (3 votes)
  • aqualine ultimate style avatar for user Tomás
    Stupid question here I know, but how come you know that b_j is redundant just because you've swapped it with -a_1? how come it is NECESSARILY redundant (in other words could it not be a coincidence that it is can be expressed as a linear combination of the others)?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Mez Cooper
    At , "So we know that X has to have fewer elements than Y". What? No, it doesn't. They're both bases. What is he on about?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • female robot grace style avatar for user loumast17
      He meant to say greater than or equal to, but didn't say equal to. Basically continuing off a previous point that a spanning set must have at least as much as a basis set. so if y is a spanning set it must be greater than or equal to x in terms of elements. Then he uses the same argument for x, since it is a basis. Then shows that means they must both be equal. Kinda linking up to the other question lol.
      (2 votes)
  • aqualine ultimate style avatar for user Shankar Kolluru
    At , why should a1 be removed, and bj be changed to b1?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Ahmil
      Why should they? Because we can, and doing so helps bring us closer to proving what he's trying to prove.

      Why can a1 be removed? Well, because you can always remove something from a set to get another set. In this case, he wanted to removed something such that the resulting set would still span V. Since he already proved that a1 can be represented as a linear combination of the other vectors already in the set, he can safely remove it and still span V.

      Why can bj be changed to b1? I would argue that, strictly speaking, it can't. The more "correct" proof would be to leave the "holes" in instead of renaming the vectors as we go along. But Sal's way of renaming helps make it clearer that the elements of B are being replaced with the elements of A. The replacing makes it look like it's happening in order, which is easier to understand, but not technically correct. But he explains what he means as we go along, so I'm okay with it.
      (2 votes)

Video transcript

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 linearly dependent. 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 construct a1. 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 independent. 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 independent. 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 independent. 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. [typing] 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 five elements. 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 Y's elements. 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 well-defined. 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.