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

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

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.