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
Current time:0:00Total duration:21:35

Proof: Any subspace basis has same number of elements

Video transcript

let's say I've got some set a of the vectors a1 a2 all the way to a N and I know for a fact that it's a basis 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 and elements right here that any set that spans V has to have at least n elements so any any spanning spanning set must have at least n elements and elements or n members or cardinality of n there's all just a ways of saying you got n vectors in this set so let's see if we could if we could if we have if I'm saying that every set that spans V must have at least n elements if this sum basis set has n elements for V what let's let's see if we can kind of run with a set that has less than n elements and see if we reach any contradictions so let's say that I have some set B here and it's equal to the vectors v1 v2 all the way to be M and M is less than n so I have some set of vectors here that have fewer elements than my set a and let's say that B spans have you come to me one day and you say look I got I found you the set of vectors right here and not only it does it have fewer elements than a but it spans V it spans V and I look at you very suspiciously because I always thought that this green statement was true so we start out a little bit of a thought experiment and I say ok you you claim that your set spans V so let's do something let me define a new set let me call this new set B 1 Prime and you'll see why I'm doing this kind of strange notation what what I what's essentially going to be is the set B plus my vector a 1 so it's a 1 and then I have all of my elements of B so B 1 B 2 all the way to I am now I think you and I could both agree that this set is linearly dependent 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 a one I mean it's one of the basis vectors for V is for this definition of a basis but all of the basic spec basis vectors our members are members of V right you can obviously represent you can obviously the the the if this if this set is a basis for V then this means that this set spans B 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 said you know the coefficient on a want to be zero and everyone else the coefficient on a one to be one and the coefficients on everyone else to be zero so obviously a one is also in the set so if a one 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 a one so you could say a one is equal to maybe one where the DS are the constants D 1 B 1 plus D 2 B 2 all the way to DM BM and at least one of these have to be nonzero we know that a is a nonzero vector if it was a zero vector this couldn't be a basis because it wouldn't be linearly independent because you can always represent a zero vector as a as a as really just a zero times any other vector so this won't be a zero vector so at least one of these are nonzero so let's just say for the sake of argument that GJ so the coefficient on BJ is nonzero so DJ does not equal zero so we could actually do is we could solve for that term you know so over here someplace you have the term DJ BJ and it's plus a bunch of other stuff we can solve for this term if we subtract four from both sides of the equation and then divide both sides by Nimai DJ and put this - a1 on the other side what do we get I know there 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 we could solve for our BJ term and say that is equal to 1 sorry that should be equal to minus 1 over its coefficient times and if we subtract the a1 from both sides minus a 1 and then plus all of these guys plus D 1 B 1 plus all the way you're gonna you're gonna 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 and I'm doing all of this just to show you that by definition you can write a 1 as a linear combination of these other guys but you can just rearrange things you can rearrange it so that you can write you can write one of the other guys as a linear combination of the rest of the other guys and a 1 and you say you know what and this guy is now redundant I don't need I don't need this guy any longer to continue to span V clearly this set still span V I mean I added extra in for an extra vector here but I can remove this guy right here I can remove him from my set B 1 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 AI or my a1 so let's get rid of him and let's call that set b1 and actually just for the sake of notation let me just change his name let me just say this is a 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 these guys that are embedded someplace in in the middle of the stream I mean these these names B 1 B 2 BM they're arbitrary names so let me just rename let me swap the labels let me just say that BJ is equal to V 1 and that B 1 is equal to BJ I'm just swapping their names so I'm essentially just gonna remove I took that guy I renamed him B 1 Irene a to be 1bj so that I could swap them so I'm essentially just going to remove b1 from the vector just to make my notation easier you could just keep saying I'm gonna 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 removed that I've renamed is b1 let me just call that straight-up b1 so my straight-up set B 1 is equal to a 1 a 1 and then remember I removed the BJ and I rename that as b1 and then I rename b1 is BJ so now my set looks like this let me go to the other color b2 and you know for all we know BJ might have been b1 we don't know and it doesn't I mean there might have there's probably multiple of these that are nonzero so we could have picked any of those to be our BJ but anyway we were so we removed we took our BJ renamed it b1 and removed the b1 and so now our set looks like this b3 all the way to BM and this will still span this set still spans 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 let me create the vector B let me do a new color let's say I have the vector B 2 prime and what I'm gonna do here is now I'm going to take another element from our spanning from our basis of V I'll take the second element I'll take a - I'll take a 2 and throw it on this guy so now we have the set let me write it this way B 2 is B 2 prime is equal to I'm just going to add a 2 to this guy so you have a 1 a 2 and then you have all the rest of these guys B 2 B 3 all the way to BM and 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 I just may or may not be but when you add this other vector that's in V you definitely know that your linear dependent because these guys can construct that guy similarly we know that this vector b1 this bands V so when we add this new element here 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 a 2 a 2 is equal to you know some constant times c1 times a 1 plus let me put some constants so plus d2 actually let me just write it this way since plus C 2 B 2 plus C 3 B 3 all the way to CM BM now what I'm going to claim is that at least one of these coefficients is nonzero so at least one of the CIS does not equal to 0 and I'll make the further claim that it's it's if there's at least one that's outside of this one there's at least one that's outside of that one that it has to be that at least one of the coefficients on these bees on these B terms has to be nonzero and the way you can kind of think about it is what if all of these guys were zero if all of these guys were zero then that means that a 2 is a linear combination of a 1 right all of these guys would cancel out here to have a 2 is equal to some nonzero constant times a 1 but we know that's not the case because these two guys come from the same linear linearly independent set they come they both come from that spanning basis spanning beta the the fact that they are a basis that would 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 these one of the coefficients on the B terms has to be nonzero and let's once again let's just say that you know it's the coefficient someplace you're gonna you're gonna have a CJ BJ this is a different one than we had before and we know that this guy one of them at least one of them has to be nonzero because if all of these guys were nonzero then you wouldn't be able to say that these get this vector and that vector are linearly independent because if they would be scalar multiples of each other so we're gonna do the same exercise this guy right here that's some place you know CJ beat CJ BJ right here obviously this coefficient is nonzero so we can solve for our BJ once again we could say that BJ is equal to minus 1 over CJ times now it's minus a 2 plus C 1 a 1 all the way to CM BM so we have some BJ here that is 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 gonna rename him just for the city just for solely for the purpose of notational simplicity I'm just gonna rename our BJ B 2 and our B 2 is equal to BJ so I'm just rearranging the names and I'm gonna remove our b2 or I'm gonna remove what what I now call our b2 it was that it was it was whatever was out here that could be represented as a linear combination of everything else including our new a2 so let me call that set when I remove that that one of those terms right here and now I renamed it be - I call this set B - and now it's equal to a-1 a-2 and now I have the leftovers of my B's so I have b3 b4 all the way to BM I used to notice I still have exactly M elements and this still spans so this 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 needed that I can construct that vector with some combination of these guys so it wasn't necessary so it still spans V so this process I'm doing I can just keep repeating it I can add an a3 i can define I can define b3 prime as I can just add a 3 to this to this set right here a 2 a 3 and then have my B 3 B 4 all the way to BM and I'll say oh this is linearly independent 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 a 3 is equal to sum a 1 plus some a 2 plus C 3 B 3 all the way to CM BM and we know that at least one of the coefficients on the B terms on the B terms has to be nonzero because if all of those were zero then you would be saying that a three could be a linear combination of the a terms and we know that a three can't be represented as a linear combination of the eight terms because it lays all these eight terms come from a linearly independent set so you do the same operation you find you can solve you know let's say that CJ you know some term right here the CJ is nonzero then you can solve for that BJ and then you I do that little renaming little thing I do or I rename the BJ be three and rename be three BJ and then I remove be three and I get the set and I get the set B 3 is equal to a1 a2 a3 and then I have B 4 all the way to BM and this still spans this still spans V and I keep doing it so what's going to happen eventually what's gonna happen if I keep doing this process over and over and over again eventually I'll I'll essentially replace all of the BMS right or I'll replace all of the N terms right so eventually I'll have a set that looks like this I'll have a set that looks BM well I will replaced each of these guys with an A where I would have replaced each of these guys with an A so I'll have a 1 a 2 a 3 all the way to a em 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 viii now let me let me write this this is the result we got by starting off with a spanning set B by starting with a spanning set B that has m elements where we said that M is less than n right 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 bands V but we already said we already said that the set a the set a which is equal to a1 a2 all the way to a m and then a M plus you know 1 I don't know how you know and then we have I don't know how many more terms there are between m and n but then you go all the way to a n remember we said that n is greater than M or when we define B we said that M is less than and same thing that this was a smaller set now we're saying that this bands V but at the same time we said that this was a basis right this was just our this is just our starting fact that this is a basis for V basis for V basis means two things it means it's bands 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 so this the result we got is that this fans V but if this if this subset of a spans V then a becomes linearly independent because of this sub this subset spans V we can write that means that a n can be represented as some linear combination of these guys which would imply so that implies that you're linearly dependent which is a contradiction with our original statement that 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 this is if there are some smaller spanning set you get the result that a has to be linearly dependent even though we said it was linearly independent so we now know we get our contradiction we say that there cannot be there cannot be so this leads us to there cannot be let me there cannot be a set a let me write this a spanning spanning set B that has has fewer elements has fewer elements than a and this is a pretty neat outcome because now if anyone tells you that you know if I come up to you and I say hey I found some set X so set X spans the subspace subspace I don't know let's just call that V again then you know that you know an X has 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 X is a basis for V and I told you that and it has five elements and Y is a basis for V y is another basis my handwriting is degrading Y is let me write it a little nicer Y is also a basis also a basis for V you know that Y also has to have exactly five elements Y has five elements how do I know that how do I know that well if Y is a basis then it has to have then that means that it spans V and we know it can't have anything less than five elements we just proved that so you know 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 we know that 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 Y has to have greater than X or let me call it wise elements wise elements have to be greater than X's elements because why 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 wise elements because Y is a basis Y is elements I know this is you can you can't read that but if these if this guy's elements are less than this guy's elements and this and but it's also greater than or equal to we know that X the number of elements that X has so X's elements or the cardinality or the number of elements in it is equal to Y's elements y's elements and so now that we know that any basis for a vector space so let's say let's say that X though let me just go back to our set a a is equal to a1 a2 all the way to a n we can now say that any basis for some vector force firms for some subspace V they all have the same number of elements and so we can we can define a new term called the dimension the dimension of V sometimes it's written just dimension of V is equal to the number of elements sometimes called the cardinality of any basis of V and I went through great Franzen's video 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 5 or they both have to have 6 and so we can define our dimensionality