Column Space Basis: Why Does Row Reduction Work?

[Ryker]

I am a bit puzzled by the following. You know how they teach you that in order to find column space you just need to row reduce the matrix, look at the columns with leading 1's in them and then just read off those columns from the original matrix? Well, why does that actually work? I'm trying to get my head around this, but so far I don't think I've quite gotten there. So if there's anyone that could expand this or link me to some online explanations, that would be greatly appreciated.

 

[HallsofIvy]

The "column space" of a matrix is, by definition, the space spanned by the columns thought of as separate vectors. That is why you can "get the column space" by looking at the columns! They don't have to be in echelon form, although that will simplify determining whether the columns are independent or not.

 

[Outlined]

Call the matrix A. Your column space is in fact {Ax : x in Rⁿ}. Row reducing is multiplying with an invertible matrix E, as E is invertible we have

{Ax : x in Rⁿ} = {EAx : x in Rⁿ}

 

[Ryker]

The "column space" of a matrix is, by definition, the space spanned by the columns thought of as separate vectors. That is why you can "get the column space" by looking at the columns! They don't have to be in echelon form, although that will simplify determining whether the columns are independent or not.

No, no, I understand that, but what I meant is why can you just look at the columns that have leading 1's in row echelon form and then look for the matching columns in the original matrix?

Call the matrix A. Your column space is in fact {Ax : x in Rⁿ}. Row reducing is multiplying with an invertible matrix E, as E is invertible we have

{Ax : x in Rⁿ} = {EAx : x in Rⁿ}

I understand that, as well, but again the same question as above still remains.

 

[ask_LXXXVI]

Call your matrix A and row reduced form matrix rref(A).
rref(A) is obtained by row operations on the original matrix.

Suppose two columns are independent in A, row operations on A can change the span of these two columns , but they will still remain independent.

Thus , the set of columns which were independent in A will remain independent even in rref(A). The columns with leading 1s in rref(A) are independent. Thus the columns at these positions in A are also independent.And the set of all independent columns in A,will be the basis for the column space of A.

Note that the column space for rref(A) maybe different from column space for A,hence you read off the independent columns from A and mark them as basis for column space of A.

As HallsofIvy said finding which columns are independent is easier if you have the row reduced echelon form.

 

[Ryker]

Thanks for the response. I spent some time thinking about this and basically came to the same conclusion, but it was great seeing this written down explicitly by someone else, as well, as I think it adds to the thought process I was going through and clears things up a bit.

 

[mathwonk]

its that the echelon matrix has the same solutions as the original, hence the same dependent columns.

 

[denysy1]

Call your matrix A and row reduced form matrix rref(A).
rref(A) is obtained by row operations on the original matrix.

Suppose two columns are independent in A, row operations on A can change the span of these two columns , but they will still remain independent.

Thus , the set of columns which were independent in A will remain independent even in rref(A). The columns with leading 1s in rref(A) are independent. Thus the columns at these positions in A are also independent.And the set of all independent columns in A,will be the basis for the column space of A.

Note that the column space for rref(A) maybe different from column space for A,hence you read off the independent columns from A and mark them as basis for column space of A.

As HallsofIvy said finding which columns are independent is easier if you have the row reduced echelon form.

Could you explain why the column space of A is different from the the column space of the RREF of A?

 

[jmblock2]

They span the same space, but the original question is asking about the basis of the column space. RREF is pointing out which are the important and which are the redundant vectors.

 

[wisvuze]

as mathwonk point it out, the RREF form has the same solutions as the original matrix ( there is a theorem on this, you can look it up ). Essentially, if you multiply your original matrix by an invertible matrix, then the solution sets are the same

 

[Deveno]

think about what it means for a column to have a "leading 1". it means all of the entries before the leading 1 in the ROW the leading 1 occurs in, are 0. that means that no linear combination of the columns before it, can possibly include it in their span.

say a leading 1 occurs in the 3rd column, in the second row. this means that the column 1 and column 2 vectors have 0 in their 2nd position (the 2nd row). so no matter what linear combination of column 1 and column 2 we take, it, too will have 0 in the second position. but column 3 has 1 in the second position. so it has to be linearly independent of all the column vectors before it.

by contrast, we know that column 2 has some non-zero entry in row 1, and column 1 is ALWAYS (1,0,0..,0). so column 2 is linearly dependent on column 1, so including it in a spanning set is redundant.

there's nothing special about choosing the columns of A that correspond to the pivot columns of rref(A), it's just that, after row-reducing A, and seeing what the rank of A actually is, they make an easy choice. we could find many other possible bases for col(A), but picking the columns that correspond to the pivot columns of
rref(A), ensures that we get a linearly independent set.

to pick a basis for col(A), we know that the columns of A are a spanning set. and we know that we need to pick rank(A) of them, to get a basis. we will always have rank(A) pivot columns in rref(A), since every pivot column has a leading 1, which "tags" a non-zero row; we know these columns correspond to the rank of A.

other choices of the columns of A might lead to a basis for col(A), or might not. the matrix A =

[1 1 0 1]
[0 0 1 2]
[0 0 0 1]

has rank 3, but columns 1,2 and 4 do not make a basis.