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

Dimension of the column space or rank

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

Want to join the conversation?

  • leafers tree style avatar for user JanHidding94
    So I conclude from this and the last video that for a Matrix A with the form (mxn), n=rank+nulity. Is this always true?
    (42 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user Jim Celia
      That's exactly right, nullity is the number of redundant (free variable) columns, rank is the number of non-redundant (pivot) columns, so together they add up to the total number of columns. I was just going through those videos and looked it up to be sure I'd drawn the right conclusion too. Nice work.
      (28 votes)
  • orange juice squid orange style avatar for user Rodrigo Alves
    So every matrix in reduced row echelon form is linearly independent? Correct?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot donald style avatar for user Jeremy
      Rodrigo,

      No, this isn't the case. If the columns of a matrix are not linearly independent, then the columns of the reduced row echelon form of the matrix will ALSO not be linearly independent.

      For example, let's look at a matrix whose columns are obviously not linearly independent, like:
      |1 2|
      |2 4|

      Obviously, we can get the second column by multiplying the first column by 2, so they are linearly dependent, not independent. Now let's put the matrix into reduced row echelon form.

      Step 1. Get all zeros in the 1st column except for the top term. I can do this by adding -2 times the first row to the second row, to eliminate the 2nd term of the first column:

      |1 2|
      |0 0|

      But notice, that this is as far as I can go. This IS reduced row echelon form for this matrix, and notice also that the columns are not linearly independent. The second column is STILL 2 times the first column.

      Hope that helps.
      (37 votes)
  • spunky sam blue style avatar for user Ethan Dlugie
    Isn't it clear that the vectors are linearly dependent? You have 5 vectors in R^4, it is obvious that (at least) one must be redundant.
    (11 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user mike.ellebrecht
      Yep. It's clear that at least one is redundant. So the rank of A must be 4 or less. But in order to find the rank, you need to figure out how many are redundant. Sal was kind enough to make this example with two columns redundant so we can see that the answer is not simply Rank(A) = 4.
      (22 votes)
  • blobby green style avatar for user G.Gulzt
    I watched all the linear algebra video's up to this point. I can construct RREF, find the null space, column space, the nullity and the rank. etc... but I still miss the point of it all. What is the purpose of these definitions. I still have no clue about the context, what problems will this help us solve?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • mr pants teal style avatar for user Moon Bears
      Great question! Linear Algebra has many applications - for instance almost anything in Physics is expressed as a vector of one form or another. Calculus is all about taking non-linear things and approximating them linearly, that was the whole point of derivatives. This is due to the fact that linear equations are relatively easy to solve, whereas non-linear ones can be very difficult. A standard technique in mathematics is looking at a non-linear system and finding a linear approximation. Often times in physics you have a taylor series expansion over differential pieces of length, area, volume, etc. so that the square and higher terms cancel. In Computer Science everything explicitly uses linear algebra. It's probably the most important mathematics, that and fourier analysis.
      (8 votes)
  • blobby green style avatar for user Qiyuan Gao
    Does the rank of A also equal to number of non-zero rows of RREF(A)?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • leaf blue style avatar for user Tarun Akash
    Hi, i am kind's new to khan academy and stuff, is there any way i can practice the knowledge above. I mean i have watched a bunch of videos, but i think i will forget all the concepts unless i practice them.
    (4 votes)
    Default Khan Academy avatar avatar for user
  • mr pink red style avatar for user Aya Elayyan
    is there any video talking a bout the rank of matrix ?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • purple pi purple style avatar for user alphabetagamma
    I think "" does not need a proof as they're just i j k l unit vectors.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Kingsley Pinder
    Isn't 6-2(-3) =12 instead of zero?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • marcimus pink style avatar for user Maat2
      No thesergcan's answer was incorrect.

      The question was correct as it does compute to 12. However, Sal mentions at in the video that 6 + 2 times minus 3, which is 6+2(-3), does indeed equal 0.

      However, "Here you multiply the numbers first: -2*(-3) = 6 ( you can think of the equation as 6+-2(-3) =12). So 6-6 = 0." will never result in 6-6 = 0.
      (1 vote)
  • marcimus pink style avatar for user noor.
    At you state that r1, r2, and r4 are linearly independent. Are those columns (r1, r2, and r4 ) dependent variables though as they have a leading 1 value ?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user InnocentRealist
      Yes, that's right (I didn't notice that). The pivot variables are dependent variables, and the non pivot variables are independent (free) variables. But the vectors in the pivot columns (in both "A" and "rref(A)") form a linearly independent set, and those in the non pivot columns are in their span, as Sal explains.
      (1 vote)

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.