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

• I
• mattTch
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.
mattTch
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).

Consider:

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

2. The $i$th column of a matrix is the image of the $i$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.

Why does 3 follow from the definition of RREF?

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.

• 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
• Linear and Abstract Algebra
Replies
3
Views
2K
• Linear and Abstract Algebra
Replies
4
Views
1K
• Linear and Abstract Algebra
Replies
15
Views
4K
• Linear and Abstract Algebra
Replies
9
Views
4K
• Linear and Abstract Algebra
Replies
1
Views
3K