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

[mattTch]

TL;DR

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).

 

[pasmith]

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.

 

[mattTch]

Why does 3 follow from the definition of RREF?

 

[Steve4Physics]

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.