Proof of Column Extraction Theorem for Finding a Basis for Col(A)

In summary, the columns of a matrix that correspond to leading ones in the reduced row echelon form form a basis for the column space of the matrix. This is because any non-basis columns can be expressed as a linear combination of the basis columns, which is a result of the linearity of linear maps. This follows from the definition of RREF, as columns without leading ones are linear combinations of columns with leading ones.
  • #1
mattTch
2
0
TL;DR Summary
Let A be an m×n matrix. I am not sure why it's immediately obvious that the set B containing all and only the column vectors of R = RREF(A) which have leading ones, forms a basis for R. In particular, why is it the case that Span(B) = Col(R)? FYI: The linear independence of B is obvious to me.
Theorem: The columns of A which correspond to leading ones in the reduced row echelon form of A form a basis for Col(A). Moreover, dimCol(A)=rank(A).
 
Physics news on Phys.org
  • #2
Consider:

1. If [itex]\alpha : V \to W[/itex] is a linear map and [itex]B = \{b_i\}[/itex] is a basis for [itex]V[/itex], then [itex]\alpha(B)[/itex] spans [itex]\alpha(V)[/itex]. This follows from linearity of [itex]\alpha[/itex]: If [itex]v \in V[/itex] then [itex]v = \sum_i a_ib_i[/itex] and [tex]
\alpha(v) = \alpha\left(\sum _ia_i b_i\right) = \sum_i a_i \alpha(b_i).[/tex]

2. The [itex]i[/itex]th column of a matrix is the image of the [itex]i[/itex]th standard basis vector.

3. It follows from the definition of RREF that columns which don't have a leading 1 are linear combinations of the columns which do.
 
  • #3
Why does 3 follow from the definition of RREF?
 
  • #4
mattTch said:
Why does 3 follow from the definition of RREF?
Can chip in? If I've understood your question this might help.

Consider an example RREF matrix:

##\begin{bmatrix}
1 & 0 & 2 & 0 & 8\\
0 & 1 & 7 & 0 & 3\\
0 & 0 & 0 & 1 & 2\\
0 & 0 & 0 & 0 & 0
\end{bmatrix} ##

Some columns contain a leading '1' (with zeroes for all other elements). These are the basis columns.

Other columns do not contain a leading '1'. These are non-basis columns.

The basis columns here are ##C_1 = \begin{bmatrix}
1\\
0\\
0\\
0
\end{bmatrix}##, ##C_2 = \begin{bmatrix}
0\\
1\\
0\\
0
\end{bmatrix}## and ##C_4 = \begin{bmatrix}
0\\
0\\
1\\
0
\end{bmatrix}##.

From inspection it should be clear that any non-basis column can be constructed as a linear combination of the basis columns, e.g. ##C_5 = 8C_1 + 3C_2 + 2C_4##.

That’s because every non-zero coefficient in a non-basis column is a simple multiple of the ‘1’ in a basis column.
 

Similar threads

  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
832
Replies
3
Views
2K
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
9
Views
4K
Replies
1
Views
3K
Back
Top