Non-pivotal columns of a row-reduced matrix in relation to linear independence

Question

My understanding is that when row-reducing a matrix, the non-pivotal columns correspond to "dependent" columns in the original matrix. In particular, if I construct a matrix $A$ with three linearly independent columns in $\mathbb{R}^3$, say $v_1, v_2, v_3$, then the third column of the row-reduced matrix may be $(2,3,0)$. I know that I can then read off $$ v_3 = 2v_1 + 3v_2. $$ This is something I've accepted, but I do not understand why this is the case. Why does a pivotal column correspond to an "independent" column and a non-pivotal column to a "dependent" column?

Answer 1

Recall that Gaussian elimination puts each pivot to the right of the preceding one, with all zeros underneath. Label the pivot columns of an echelon matrix $A$ as $A_{1}, \dots, A_{n}$ and consider a generic pivot column $A_{j}$ with pivot in row $k$, $A_{j_{k}}$.

Any linear combination of the pivot columns to the left of $A_{j}$ gives zero in the pivot row $k$ since zeros are underneath the pivots in each $A_i$ with $i<j$. On the other hand, if the last row in $A_j$ is to be zero, then $A_j$ can't be written as any non-zero multiple of the last pivot column. Similarly, if the second to last row in $A_j$ is to be zero, then it can't be written as any non-zero multiple of the last two pivot columns (since we already know the last column must be zero). Continuing in this fashion we see any non-trivial linear combination of the pivot columns $A_i$ with $i>j$ results in non-zero entries under $A_{j_k}$. This proves the pivot columns are independent.