# Row operations do not change the dependency relationships among columns?

My book says this but doesn't explain it:

Row operations do not change the dependency relationships among columns.

Can someone explain this to me? Also what is a dependency relationship? Are they referring to linear dependence?

• Yes, they are referring to linear dependence, but the notion of a "dependency relationship" is that you have a nontrivial linear combination of vectors equal to zero (so it is the "evidence" of linear dependency). – hardmath Dec 31 '16 at 23:21

## 3 Answers

Consider an $m\times n$ matrix with columns:

$$\begin{pmatrix} v_1 & v_2 & \ldots & v_n \end{pmatrix}$$

Now a dependence relation on the columns would express zero as a nontrivial linear combination of them:

$$\sum_{i=1}^n c_i v_i = 0$$

where $c_1,c_2,\ldots,c_n$ are scalars.

We can consider the effect of various elementary row operations on the matrix composed of the columns above, one definition of which would be:

• switching places of two rows
• multiplication of a row by a nonzero scalar
• adding a multiple of one row to another

[NB: The first of these row operations can be effected by a combination of the other two, so this is not a minimal list.]

A concise way to show that such operations preserve any linear dependence relation that may exist among the columns is by appealing to a matrix multiplication form. That is, the linear dependence relation above is:

$$\begin{pmatrix} v_1 & v_2 & \ldots & v_n \end{pmatrix} \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$

If $E$ is an elementary matrix that effects one of the elementary row operations, the multiplying by $E$ on the left in this last equation:

$$E \begin{pmatrix} v_1 & v_2 & \ldots v_n \end{pmatrix} \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$

leaves the linear dependence relation unchanged. Thus the associative property of matrix multiplication gives an easy way to prove the required claim once we understand that elementary row operations correspond to multiplication by elementary matrices.

• The way I think of it is that an elementary row operation amounts to a change of basis for the column space, which can’t affect linear dependence/independence among sets of vectors. – amd Apr 16 '17 at 7:02

I just figured out a way that makes sense of it, so I searched for such a question to post it. And gladly it's slightly different than hardmath's above.

If two vectors $$\vec{a}$$ and $$\vec{b}$$ are dependent, $$\vec{a}=c\vec{b}$$.

One can consider a row operation as performing an identical linear transformation on all the columns of a matrix. A linear transformation is just a mapping from one vector space to another vector space, $$T: V \mapsto W$$ such that if $$\vec{x}, \vec{y}$$ are two vectors in $$V$$ and $$c$$ a scalar, $$T(\vec{x})+T(\vec{y})=T(\vec{x}+\vec{y})$$ and $$T(c\vec{x})=cT(\vec{x})$$.

Proof for "Row operations do not change the dependency relationships among columns":

We want to show that after a row operation, one column $$\vec{a}$$ will be linearly dependent on another column $$\vec{b}$$ iff it had been linearly dependent on $$\vec{b}$$ beforehand.

So beforehand, $$\vec{a}=c\vec{b}$$. Let $$T$$ be a row operation, which we said is a linear transformation. Then $$T(\vec{a})=T(c\vec{b})=cT(\vec{b})$$. And this shows that after the row operation, two linearly dependent columns remain linearly dependent.

We've shown that "after a row operation, one column $$\vec{a}$$ will be linearly dependent on another column $$\vec{b}$$ iff it had been linearly dependent on $$\vec{b}$$ beforehand." The contrapositive is: "after a row operation, one column $$\vec{a}$$ will be linearly independent of another column $$\vec{b}$$ iff it had been linearly independent of $$\vec{b}$$ beforehand. Every conditional statement is equivalent to its contrapositive, so the contrapositive is true as well.

$$\square$$

Suppose a matrix A and one of its columns $$v_k$$ is a linear combination of the others, we can form an equation as such:

$$a_1v_1 + \ldots + a_{k-1}v_{k-1} + a_{k+1}v_{k+1} + \ldots + a_nv_n = a_kv_k$$

If the column vectors of A are linearly independent, $$a_1, a_2, \ldots, a_n$$ are all zero. This doesn't affect our proof.

Now we can rewrite the equation to:

$$A'x = b$$

where the columns of A' are $$v_1, \ldots, v_{k-1}, v_{k+1}, \ldots, v_n$$, and x = $$[a_1, \ldots, a_{k-1}, a_{k+1}, \ldots, a_n]^T$$, and $$b = a_kv_k$$.

Since we know that the equation still holds after row operations on the augmented matrix of A', thus they don't change the linear relationship of columns of A.