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

Showing that the candidate basis does span C(A)

Showing that just the columns of A associated with the pivot columns of rref(A) do indeed span C(A). Created by Sal Khan.

Want to join the conversation?

  • blobby green style avatar for user Basil Ting
    any sample exercises to try out? there are questions in the calculas section, not sure if there are any here
    (42 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user devagarwal2001
    At and , didn't Sal mean a1, a2 and a4 rather than a1, a2 and aN?
    (8 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user parsonstaylorj
    I don't understand how this is a thorough proof that the pivot columns span all of the column space. In the proof, he sets the free variables to -1 and 0. Doesn't this mean the result is only valid in the special case where the free variables are -1 and 0?
    (7 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user Andrew Hung
      Not exactly. x3 and x5 being free variables just means that the equation x1a1 + x2a2 + x3a3 + x4a4 + x5a5 = 0 holds true for any value of x3 and x5, since the pivot entries (x1, x2, and x4) will change values depending on the values of x3 and x5 to make the equation still hold true. The relationship among the actual columns DOES NOT change just because you pick different values for the free variables. To make this more clear, consider the smaller example x1a1 + x2a2 + x3a3 = 0, where x3 is a free variable and the a's are the column vectors of some matrix A. Let x1 = 2x3 and x2 = -3x3. Obviously in this case, the pivot entries are x1 and x2 and the free variable is x3. We'll now consider two different values of x3 and see that the relationship among the columns remains the same.

      Before doing this, we rewrite x1a1 +x2a2 + x3a3 = 0 by rewriting x1 and x3 in terms of x3:
      2x3a1 - 3x3a2 + x3a3 = 0

      Scenario 1: x3 = -1
      2(-1)a1 - 3(-1)a2 + (-1)a3 = 0
      -2a1 + 3a2 - a3 = 0
      a3 = -2a1 + 3a2

      Scenario 2: x3 = 2
      2(2)a1 - 3(2)a2 + (2)a3 = 0
      4a1 - 6a2 + 2a3 = 0
      4a1 - 6a2 = -2a3
      -2a3 = 4a1 - 6a2
      a3 = -2a1 + 3a2

      As you can see, changing the value of the free variable does not change the relationship/equation between the columns. Picking -1 and 0 in the video is just a convenient way to show that the columns corresponding to the free vectors CAN be written as some linear combination of the pivot vectors. If a vector can be written as a linear combination of some other vectors, then that vector is redundant in the set. It doesn't matter if you later pick different values for the free variables and demonstrate that the vector can ALSO be written as a linear combination of the pivot columns and the other free columns.
      (8 votes)
  • blobby green style avatar for user Jon Cannaday
    Thank you for everything you guys do. But alas, I am wanting more. Is there a possibility that there be videos on abstract algebra and even graduate level classes? I am having a blast relearning and gaining a better grasp on the topics covered in college, but my curiosity for where else can all this math go is consuming me. Never the less, thank you for everything up to this point. You have done a great job with how this website runs to the content provided. God bless you all my friends.
    (5 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Danny
    What is a candidate basis? I don't understand that term.
    (3 votes)
    Default Khan Academy avatar avatar for user
  • duskpin ultimate style avatar for user Lotte
    Sal said ''Column span'' but he probably meant ''Column space'' correct me if I'm wrong
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user wouter Hilhorst
    I am a bit confused about the following:
    1. the proof that the non pivot colums can be made as lineair combinations of the pivot colums is made by rewriting the non pivot parts of the equation that sal writes at . Thats clear, but this can also be done for the pivot points.
    2. In previous videos the proof is made that the pivot points cannot be written as lineair combinations of the other vectors by looking at the rref and trying to find a number with which you can multiply one of the vectors to get another. This cant also be done for the non pivots, because they also contain zeros.
    I don`t why the above exclusively proves the lineair dependence or indepences of the vectors.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user Anant Sogani
      1. Consider a set of n linearly dependent vectors, of which any k taken alone are linearly independent. There are lots of ways to choose k vectors from n. But say we establish some rules, so that everyone chooses the same k vectors. These k vectors we then choose to call the linearly independent vectors for the set, and demonstrate that the remaining n - k vectors are linear combinations of the independent k (and thus dependent). Of course, we could have selected a different subset of k vectors, and they would have been independent as well (the remaining n - k in the selection being dependent). The point is - and this is important - that the subspace generated by any selection of k vectors from this set is the same. As far as I understand, the notion of linear dependence/independence was created solely for subspaces. So, if the subspace remains the same, then which k vectors get selected to produce it doesn't matter. So, why not make everyone select the same k vectors and avoid confusion. That's where the "pivot columns are independent and non-pivot columns are dependent vectors" rules comes in. We choose to treat pivot column vectors as independent, and thus disallow them being shown dependent. Hope this long paragraph made sense. :)

      2. The proof made was that a pivot column vector cannot be written as a linear combination of other pivot column vectors, since each has a 1 in a different component of the vector, while the rest of their components are all 0. We cannot get 1 by any linear combination of 0's. For the non-pivot column vectors, this is not true.
      (2 votes)
  • boggle blue style avatar for user Bryan
    By reordering the columns in the matrix and reordering the x_1, x_2, etc to match, we can get any of the columns to be pivot or free columns, and so we can get any 3 column vectors of the matrix to be a basis correct? If this is correct, is it always the case?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • female robot grace style avatar for user loumast17
      There will always be the same number of pivot columns/ variables. So once you have that many you can't have any more, so in that way you can't make "any" column a pivot column. you can make n columns pivot columns, where n is the number of pivot columns.

      Another pice of the puzzle is linear independence. If two columns themselves are linearly dependent then only one of them can be a pivot column. for instance if one column was <1, 2, 3> and another was <2, 4, 6> only one of them would be a pivot column, no matter how you reordered the variables.

      This continues, if two columns together are linearly dependent to a third column, you could never have all three, just two. of course it is difficult to tell which columns are linearly dependent before putting the matrix into rref.

      I hope that made sense, but let me know if not. The main takeaway is that yes, there is some control you have, but if columns wind up being incompatible, that would be one limitation to the control you have. The most control you do have is the very first column you do, and you can guarantee that it will be a pivot column as long as there is at least one number in it that isn't 0
      (3 votes)
  • blobby green style avatar for user Emma van Dongen
    This video confuses me a little. I recall the topic of nullity some video's back where Sal explicitly said that with a matrix B being [2x5] having 3 free variables, the basis was 3 vectors in R^5, not 2 column vectors of the original matrix B being represented in R^2 if i'm correct.

    Can anybody help me out here, since the basis is supposed to always have the same amount of vectors. Or is this only valid for the amount of n-dimensions of R^n it spans?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • female robot grace style avatar for user loumast17
      A basis is a set of vectors that span a subspace. Or, in other words, the combination of vectors can be used to get any value in a subspace.

      for instance looking at the two vectors <1,0> and <0,1> you could get to any value in R2, so it is a basis for R2. For proof come up with some point (x,y) in R2 and then to get to that with just those two vectors use scalar multiplication x<1,0> + y<0,1> and you will get a vector that goes to that point.

      Now for your example, if you could link the video hopefully I could clear up what he meant or an error in the video, you have some 2x5 matrix. this is 5 vectors of length 2. Say two of these vectors were what I mentioned in the last paragraph <1,0> and <0,1> You could use a combination of these two to get to any of the remaining three vectors, no matter what they are.

      I think you are thinking of the null space. The basis of the null space is equal to the number of free variables. This number is also called the nullity.
      (2 votes)
  • piceratops ultimate style avatar for user Akshaj Jumde
    What is a tensor? And why pressure is a tensor?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • aqualine ultimate style avatar for user Kyler Kathan
      A tensor is a special kind of n-dimensional array whose components transform from one coordinate system to another by applying the proper Jacobian to each index.

      For someone new to tensors, that's probably gibberish, so let's break it down. A scalar value is a 0-dimensional array, a vector is a 1-dimensional array, a matrix is a 2-dimensional array, etc.. All 3 of these things can be tensors since tensors are n-dimensional arrays (where n is an integer ≥0).

      Tensors are represented using upper and lower indices. An upper index represents a contra-variant part and a lower index represents a co-variant part. The number of indices is the order of the tensor. A vector could be represented as vi(subscript i) and a matrix could be represented as A^i j(i is upper, j is lower).

      When swapping from one coordinate system to another, we need ways of equating their values. For example, if we wanted to switch from polar to Cartesian coordinates, we'd need the equivalences: x = r*cos(θ) and y = r*sin(θ). The Jacobians take these sorts of equivalences and put them into a single (very special) object. There's a co-variant and a contra-variant Jacobian for every change of coordinate system. In order to change the values of a tensor from one coordinate system to another, you apply the contravariant Jacobian to each contravariant index and the covariant Jacobian to each covariant index. Since not all objects can use the Jacobians to transform from one coordinate system to another, this is an important property of tensors which separates them from other n-dimensional arrays.

      Tensors are very useful in physics and can describe just about any object, measurement, force, etc.. Pressure is a tensor because a) it can be described using an n-dimensional array, and b) the array has co- and contra-variant parts which transform according to the Jacobians.

      I realize that wasn't a very thorough explanation, but there's a lot more underlying knowledge you need in order to fully understand tensors. I'd recommend this youtube series if you're interested in learning tensor calc:
      https://www.youtube.com/playlist?list=PLlXfTHzgMRULkodlIEqfgTS-H1AY_bNtq
      (4 votes)

Video transcript

Two videos ago we asked ourselves if we could find the basis for the columns space of A. And I showed you a method of how to do it. You literally put A in reduced row echelon form, so this matrix R is just a reduced row echelon form of A. And you look at its pivot columns, so this is a pivot column. It has a 1 and all 0's, this is a pivot column, 1 and all 0's, and the 1 is the leading non-zero term in its row. And this is a pivot column, let me circle them, these guys are pivot columns, and this guy's a pivot column right there. You look at those in the reduced row echelon form of the matrix, and the corresponding columns in the original matrix will be your basis. So this guy, this guy, so the first, second, and forth columns. So if we call this a1, this is a2, and let's call this a4, this would be a3, and this is a5. So we could say that a1, a2, and a4 are a basis for the column span of A. And I didn't show you why two videos ago. I just said this is how you do it. You have to take it as a bit of an article of faith. Now in order for these to be a basis, two things have to be true. They have to be linearly independent, and I showed you in the very last video, the second in our series dealing with this vector. I showed you that by the fact that this guy is r1, this guy is r2, and this guy is r4, it's clear that these guys are linearly independent. They each have a 1 in a unique entry, and the rest of their entries are 0. We're looking at three pivot columns right now, but it's true if we had n pivot columns. That each pivot column would have a 1 in a unique place, and all the other pivot columns would have 0 in that entry. So there's no way that the other pivot columns, any linear combination of the other ones, could never add up to each of them. So these are definitely linearly independent. And I showed you in the last video that if we know that these are linearly independent, we do know that they are, given that R has the same null space as A, we know that these guys have to be linearly independant, I did that in the very last video. Now the next requirement for a basis, we checked this one off, is to show that a1 a2 and an, that their span equals the column space of A. Now the column space of A is a span of all five of these vectors, so I had to throw a3 in there and a5. So to show that just these three vectors by themselves span our column space, we just have to show that I can represent a3 and a5 as linear combinations of a1, a2, and a4. If I can do that, then I can say then these guys are redundant. Then the span of a1, a2, a3, a4, and a5 doesn't need the a3 and the a5 terms, that we can just reduce it to this. Because these guys can be represented as linear combinations of the other three. These guys are redundant. And if we can get rid of them we can show that these guys can be represented as linear combinations of the other, then we can get rid of them. And then the span of these three guys would be the same as the span of these five guys, which is of course the definition of the column space of A. So let's see if we can do that. Let me fill in each of these column vectors a1 through a5, and then each of these column vectors let me label them r1, r2, r3, r4, and r5. Now let's explore the null spaces again. Or not even the null spaces, let's just explore the equations Ax is equal to -- let me write it this way -- instead of x let me write x1, x2, x3, x4, x5 is equal to 0. This is how we define the solution set of this. All the potential x1's through x5's or all the potential vectors X right here, that represents our null space. And then also let's explore all of the R times x1, x2, x3, x4, x5's is equal to 0. This is the 0 vector, in which case you would have four entries in this particular case. It would be a member of Rm. So these equations can be rewritten. I can rewrite this as -- what were the column vectors of A? They were a1, a2 through a5. So I can rewrite this as x1 times a1 plus x2 times a2 plus x3 times a3 plus x4 times a4 plus x5 times a5 is equal to 0. That was from our definition of matrix vector multiplication, this is just a bunch of column vectors a1 through a5, I drew it up here. I can just rewrite this equation like this. Similiarly, I can rewrite this equation as the vector r1 times x1 or x1 times r1 plus x2 times r2 plus x3 times r3 plus x4 times r4 plus x5 times r5 is equal to 0. Now we know that when we put this into reduced row echelon form the x variables that are associated with the pivot columns are -- so what are the x variables associated with the pivot columns? Well, the pivot columns are r1, r2, and r4. The x variables associated with them, we can call them pivot variables, and the ones that are not associated with our pivot columns are free variables. So the free variables in this case, x3 and x5, are free variables. And that applies to A. All of the vectors x that satisfy this equation also satisfy this equation, and vice versa. They're the exact same null space, the exact same solution set. We can also call this x3 and this x5 as free variables. Now what does that mean? We've done multiple examples of this. The free variables, you can set them to anything you want. So x3 in this case and x5 you can set it to any real number. You can set to anything you want. And then from this reduced row echelon form we express the other pivot variables as functions of these guys. Maybe x1 is equal to Ax3 plus Bx5. Maybe x2 is equal to Cx3 plus Dx5. And maybe x4 is equal to Ex3 plus Fx5. That comes directly out of literally multiplying this guy times this equals 0, you'd get a system of equations that you could solve for your pivot variables in terms of your free variables. Now given this, I want to show you that you can always construct one of your -- in your original matrix. So if we go to our original matrix, you can always construct one of the vectors that are associated with the free columns. You can always construct one of the free vectors using the linear combination of the ones that were associated with the pivot columns before. And how do I do that? Well, let's say that I want to find some linear combination that gets me to this free column, that gets me to a3. So how could I do that? Let me rearrange this equation up here. So what do I get? I'm sorry. That's x3 a3. If I subtract x3 a3 from both sides of the equation, I get minus x3 a3 is equal to x1 a1 plus x2 a2 plus -- I don't have the 3 there -- plus x4 a4 plus x5 -- sorry, x isn't a vector-- x5 a5. This, I guess salmon colored statement here, is just another rewriting of this equation right here. And all I did is I subtracted this term right here, x3 a3, from both sides of the equation. Now x3 is a free variable. We can set it to anything we want, and so is x5. So let's set x3 is equal to minus 1. Then this term right here becomes a 1, because that was a minus x3. And let's set x5 equal to 0. So if x5 is equal 0, this term disappears, and I did that because x5 is a free variable. I can set them to anything I want. Now I've written a3 as a linear combination of, I guess you could call it my potential basis vectors right now, or the vectors a1, a2, and a4. They're the vectors in the original matrix that were associated with the pivot columns. Now in order to show that I can always do this, we have to show that for this combination there's always some x1, x2, and x4 that satisfy this. Well, of course there's always some x1, x2 that satisfy this, we just have to substitute our free variables, x3 is equal to minus 3 and x5 is equal to 0, into these equations that we get from our system when we did it with the reduced row echelon form. In this case you have x1 is equal to minus A plus 0, x2 is equal to minus C, so on and so forth. So you can always do that. You can always express the vectors that are associated with the non-pivot columns as linear combinations of the vectors that are associated with the pivot columns. What I just did for a3, you could just as easily have done for a5 by subtracting this term from both sides of the equation. Setting x5 to negative 1 and setting x3 to 0 so that the 3 term disappears, and you could run the same exact argument. So given that, I've hopefully shown you, or least helped you see or made you comfortable with the idea, that the vectors -- let me do them in a nice vibrant color -- these magenta color vectors here that are associated with the free columns or with the free variables, the free variables were x3 and x5, those were these columns right here, that they can always be expressed as linear combinations of the other columns. Because you just have to manipulate this equation, set the coefficient for whatever you're trying to find a linear combination for equal to minus 1, and set all the other free variables equal to 0 that you're not solving for. And then you can get a linear combination of the vectors that are associated with the pivot columns. So given that, we've shown you that these free vectors, and I'm using my terminology very loosely, that these ones that are associated with the non pivot columns can be expressed as linear combinations of these guys. So they're unnecessary. The span of this is equivalent to the span of this, the span of this is the column space of A, so the span of this is the column space of A. So in the last video I showed you that these guys are linearly independent, and now I've showed you that the span of these guys is the column space of A. So now you should be satisfied that these vectors that are associated -- let me do it in a blue color -- that that column vector, this column vector, and this column vector, that are associated with the pivot columns in the reduced row echelon form of the matrix, do indeed represent a basis for the column space of A. Anyway, hopefully you didn't find that too convoluted.