Prove that pivot columns of row reduced form of any matrix forms a basis in column space of that row reduced matrix.

Question

$\newcommand{\Ran}{\operatorname{Ran}}$ $\newcommand{\b}{\mathbf}$If $A$ is $m\times n$ matrix and $A_{re}$ is its row reduced echelon form then I want to prove that pivot columns of $A_{re}$ forms a basis in $\Ran A_{re}$.

Let $\b v_1, ... ,\b v_p $ be the pivot columns, then by definition of pivots and reduced echelon form $\{\b v_1, ... ,\b v_p \} \subseteq \{ \b e_1, ... , \b e_m\}$ where $\b e_k$ are the standard basis of vector space $\Bbb R^m$. Therefore $\b v_1, ... ,\b v_p $ is a linearly independent system.

I need to prove that $\b v_1, ..., \b v_p$ is a generating set in $\Ran A_{re}$.

Let $\b w \in \Ran A_{re}$, $$\b w = A_{re} \b x = \sum^p_{r = 1} \alpha_r \b v_r +\sum^k_{r = 1} \beta_r \b u_r, $$where $\b u_1, ... , \b u_k$ are the columns of $A_{re}$ without pivot.

I am stuck here, how do I prove that $\b u_1, ... , \b u_k$ can be written as linear combination of $\b v_1, ... , \b v_p$ ?

Answer 1

So you have $\mathbf{v_1,v_2, \ldots, v_p}$ are column vectors with leading coefficients, where for any $i \le p$ then $(\mathbf{v_i})_{i,1}=1, (\mathbf{v_i})_{j,1}=0$ for all $j \ne i, 1 \le j \le m$. You've shown that this list is linearly independent.

Let $\mathbf{u_1,u_2, \ldots, u_{n-p}}$ are column vectors without leading coefficients, i.e. $(\mathbf{u_i})_{k,1}=0$ for all $m \ge k > p$.

And note that column space is $\mathbf{C}(A_{re})=\text{span }(\mathbf{v_1,v_2, \ldots, v_p,u_1, \ldots, u_{n-p}})$. So after all, we need to prove $\text{span } (\mathbf{v_1, \ldots, v_p})=\mathbf{C}(A_{re}),$ which is equivalent in proving that $\mathbf{u_i} \in \mathbf{C}(A_{re})$, or $\mathbf{u_i}$ can be written as linear combination of $\mathbf{v_1}, \ldots, \mathbf{v_p}$. This is true since $$\mathbf{u_i}=\sum_{k=1}^p(\mathbf{u_i})_{k,1} \cdot \mathbf{v_k}.$$

Answer 2

The columns span the range, thus one need to show that any column that does not contain a leading one is a linear combination of those that do. This follows since all non zero entries of any such column will lie in a row with in which a leading zero already occurs.