# Why do elementary row operations preserve linear dependence between matrix columns?

I know that I can find a basis for the column space of a matrix $A$ by reducing the matrix to reduced row echelon form $J$. The columns of $A$ corresponding to the linearly independent columns of $J$ then form a basis for $Col(A)$, because linear dependence is preserved under elementary row operations. I can't figure out why this is true though, and a google search returns nothing, so I'm sure it's simple. Can someone give me a proof?

• Elementary row operations are invertible. If $S$ is vector space and $A$ an invertible linear operator, then $\dim S = \dim A(S)$. – copper.hat Apr 7 '13 at 23:47
• Elementary row operations do not change the row space of a matrix but they do change the column space; only the dimension of the column space is preserved. – lhf Apr 8 '13 at 1:17

Let's start out from the standard basis $e_1,..,e_n$. Let $a_1,..,a_k$ be the column vectors of $A$.

Check that the step on rows $r_i':=r_i+\lambda\,r_j$ corresponds to the basis transformation $e_j':=e_j-\lambda\,e_i$, that is, for a vector $v$ we have $$v=\sum_i\alpha_ie_i=\sum_i\alpha_i'e_i'$$ where the row transformation is made for the coordinate vector $\pmatrix{\alpha_1\\ \alpha_2\\ \vdots} \leadsto \pmatrix{\alpha_1'\\ \alpha_2'\\ \vdots}$.

So, in this interpretation the column vectors all "stay" where they are in the $n$ dimensional space, but we keep on changing the basis. Of course, the vectors stay (in-)dependent. The crucial thing here is that we get another basis when applying (the inverse of) each step of the row transformation.

Here is a geometric way of looking at it (it's not a rigorous proof, but gives a nice way to understanding, non-algebraically, why it's true): The geometric meaning of the determinant of a matrix is that it is the algebraic volume of the parallelepiped spanned by the columns (or rows) of the matrix (algebraic volume means that the volume can be negative, depending on the orientation of the parallelepiped). By volume here we mean $$n$$-dimensional volume. Thus, the determinant is $$0$$ iff the volume is $$0$$ iff the columns span a degenerate parallelepiped iff the columns (rows) are dependent.

Now, row operations have clear effects on the parallelepiped. Interchanging rows just reverses the orientation. Non-zero scalar multiplication lengthens or shortens the parallelepiped in one direction. Adding a row to another one happens in a two dimensional section of the entire space. Intuitively, all of these operations can't turn a degenerate parallepiped into a nondegenerate one, or vice versa. Thus, preserving the non-vanishing of the determinant.

Take your m x n matrix A, row reduce it to A', and determine that its rank is r. Form a new m x r matrix B' from the linearly independent pivot columns of A'. Note that the rank of B' is also r. Now run your row reduction sequence backwards on B' to produce B, which is composed of the original pivot columns of A. The rank of B is also r, which means that the r columns of B are linearly independent.

For this example, let hypothetical matrix $A$ be 3x3. Let the columns of $A$ have a linear dependence relation satisfied by a non-zero vector $\mathbf{x}$: $\ x_1\mathbf{a_1}+x_1\mathbf{a_2}+x_1\mathbf{a_3}=\mathbf{0}$. Here, $\mathbf{a_1}, \mathbf{a_2}, \mathbf{a_3}$ are column vectors of $A$ and $x_1, x_2, x_3$ are the elements of $\mathbf{x}$. This can be written in a few equivalent ways:

$$\left[ \begin{array}{ c } a_{11} \\ a_{21} \\ a_{31} \end{array} \right]x_1 + \left[ \begin{array}{ c } a_{12} \\ a_{22} \\ a_{32} \end{array} \right]x_2 + \left[ \begin{array}{ c } a_{13} \\ a_{23} \\ a_{33} \end{array} \right]x_3=\mathbf{0} \ \Leftrightarrow \ \left[ \begin{array}{ c c c } a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right] \left[ \begin{array}{ c } x_1 \\ x_2 \\ x_3 \end{array} \right]=\mathbf{0}$$

which is the same as $$a_{11}x_1+a_{12}x_2+a_{13}x_3=0 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3=0 \\ a_{31}x_1+a_{32}x_2+a_{33}x_3=0$$

Now, recall the three elementary matrix row operations:

• Interchange: interchanging two rows
• Scaling: multiplying all entries in a row by a nonzero constant
• Replacement: replacing one row by the sum of itself and a multiple of another row.

Individually, each row operation preserves the linear dependence relation. Any sequence of row operations also preserves the linear dependence relation. To illustrate, let's sequentially do row interchange, scaling, and row replacement:

Interchange (e.g. swap rows 1 and 3): $$a_{31}x_1+a_{32}x_2+a_{33}x_3=0 \\ a_{21}x_1+a_{22}x_2+a_{23}x_3=0 \\ a_{11}x_1+a_{12}x_2+a_{13}x_3=0$$ This doesn't change the dependence relationship, only the order of the equations and therefore the column appearance: $$\left[ \begin{array}{ c } a_{31} \\ a_{21} \\ a_{11} \end{array} \right]x_1 + \left[ \begin{array}{ c } a_{32} \\ a_{22} \\ a_{12} \end{array} \right]x_2 + \left[ \begin{array}{ c } a_{33} \\ a_{23} \\ a_{13} \end{array} \right]x_3=\mathbf{0}$$ Scaling (e.g. multiply row 2 by constant $c$): $$a_{31}x_1+a_{32}x_2+a_{33}x_3=0 \\ c(a_{21}x_1+a_{22}x_2+a_{23}x_3)=c0=0 \\ a_{11}x_1+a_{12}x_2+a_{13}x_3=0$$ The linear dependence relationship for the second equation is preserved. Scaling is a linear transformation and by definition, $cT(\mathbf{u})=T(c\mathbf{u})$, which equals $0$ in this case. (Here, $\mathbf{u}=$ the 1x3 matrix $[a_{21} \ a_{22} \ a_{23}]$.)

This system of equations can again be written as a column matrix equation: $$\left[ \begin{array}{ c } a_{31} \\ ca_{21} \\ a_{11} \end{array} \right]x_1 + \left[ \begin{array}{ c } a_{32} \\ ca_{22} \\ a_{12} \end{array} \right]x_2 + \left[ \begin{array}{ c } a_{33} \\ ca_{23} \\ a_{13} \end{array} \right]x_3=\mathbf{0}$$ The linear dependence relationship of the columns is preserved (we haven't done anything to alter the values of $x_1, x_2, x_3$).

Replacement (e.g. replace the current row 3 by ($d$*Row 1 + Row 3)): $$a_{31}x_1+a_{32}x_2+a_{33}x_3=0 \\ ca_{21}x_1+ca_{22}x_2+ca_{23}x_3=0 \\ d(a_{31}x_1+a_{32}x_2+a_{33}x_3)+(a_{11}x_1+a_{12}x_2+a_{13}x_3)=d0+0$$ The last equation $=(da_{31}+a_{11})x_1+(da_{32}+a_{12})x_2+(da_{33}+a_{13})x_3=0$. This might not look like it necessarily has to equal zero, but all we've done is scale and add (perform individual linear transformations), and by the definition of linear transformation, $dT(\mathbf{v})+T(\mathbf{w})=T(d\mathbf{v+w})$, which again equals $0$ in this case.

The resulting column matrix equation is $$\left[ \begin{array}{ c } a_{31} \\ ca_{21} \\ da_{31}+a_{11} \end{array} \right]x_1 + \left[ \begin{array}{ c } a_{32} \\ ca_{22} \\ da_{32}+a_{12} \end{array} \right]x_2 + \left[ \begin{array}{ c } a_{33} \\ ca_{23} \\ da_{33}+a_{13} \end{array} \right]x_3=\mathbf{0}$$ Even though the columns look very different from those in matrix $A$, the linear dependence relation of the columns is preserved, because of our basic row operations (linear transformations). This can be continued until reaching reduced row echelon format, $J$.

Columns that were linearly independent in $A$ remain so, and columns that were linearly dependent remain so. Equivalently, columns which form a basis in $J$ correspond to basis columns in $A$. The column spaces are not identical, but the column linear dependence is preserved.

I just wanted to add one very fast proof that I find easy and useful. Noting $$r_i$$ the rows of a matrix $$A\in \mathbb R^{m\times n}$$ we can denote as matrix $$A_{1}$$, the matrix $$A$$ after the row operation $$r_i' = r_i + kr_j$$ for some $$k\neq 0$$. We know that the columns of $$A$$ are linearly independent iff $$A\boldsymbol{x}=0 \implies \boldsymbol{x}=0, \quad \boldsymbol{x}\in \mathbb R^n$$. Then, by proving $$A\boldsymbol{x}=0 \iff A_{1}\boldsymbol{x}=0$$ , we actually prove that the columns of $$A$$ and $$A_{1}$$ are similarly dependent or independent.

$$A\boldsymbol{x}=0\iff \begin{cases} r_1\boldsymbol{x}=0 \\ \vdots \\ r_i \boldsymbol{x}=0 \\ \vdots\\ r_j\boldsymbol{x}=0\\ \vdots\\ r_m\boldsymbol{x}=0 \end{cases} \iff \begin{cases} r_1\boldsymbol{x}=0 \\ \vdots \\ r_i\boldsymbol{x}+kr_j\boldsymbol{x}=0 \\ \vdots\\ r_j\boldsymbol{x}=0\\ \vdots\\ r_m\boldsymbol{x}=0 \end{cases} \iff \begin{cases} r_1\boldsymbol{x}=0 \\ \vdots \\ (r_i+kr_j)\boldsymbol{x}=0 \\ \vdots\\ r_j\boldsymbol{x}=0\\ \vdots\\ r_m\boldsymbol{x}=0 \end{cases}\\ \iff A_{1}\boldsymbol{x}=0$$