# How exactly does elimination discover linearly dependent rows of $A$ (in $AX=b$)?

At first this seemed obvious since elimination preserves row space and LHS$-$RHS equality. But I realized that I don't fully get it when I looked more closely.

For example, if I have a $3 \times 3$ matrix. I'll chose the $(1,1)$ entry as my pivot and eliminate the entries below it. If the entire row below it turns to zero, then it is dependent on the first. If not, it it not dependent on the first.

Next, I go to my second pivot at $(2,2)$. Now my row $2$ is actually a linear combination of row $1$ and row $2$ of the original matrix. Now I eliminate the entry below this pivot. If this operation turns the entire row $3$ to zero, row $3$ is linearly dependent on row $1$ and row $2$ of the original matrix. If not, it is independent.

This leads me to believe that the following property is at work:

Theorem 1: If one entry of row vector $R$ can be turned to zero through linear combination of some other row vectors without turning all the entries of $R$ to zero, then $R$ must be linearly independent of those vectors.

Is this true? How can I prove/disprove it?

I can make the following argument for a case with only two rows: Consider $$\begin{bmatrix} a_1 & a_2 \\ b_1 & b_2 \end{bmatrix}$$

Let $k_1$ be a scalar such that $k_1 a_1 = -b_1$ and $k_2$ be another such that $k_2 a_2 = -b_2$

Note that the operation $(k_1 \times \text{row }1)+(\text{row }2)$ eliminates the $(2,1)$ entry.

If $k_1 = k_2$ then $$(k_1 \times \text{row }1)+(\text{row }2)=0 \;,$$ so row $1$ and $2$ are linearly dependent.

If $k_1 \neq k_2$ then $$k_1 a_2 \neq -b_2 \;,$$ so there is no single scalar $k$ such that $(k \times \text{row }1)+(\text{row }2) =0$. Therefore row $1$ and row $2$ are linearly independent.

Thus Theorem 1 holds true for a case with two rows.

I run into all kinds of trouble for a more general case...

• If Gaussian elimination produces a zero row, it produces a certificate of linear dependence, because it produces a linear combination of rows that is $0$, though some of the coefficients are nonzero. If Gaussian elimination terminates without producing a zero row, one is then guaranteed that the reduced row echelon form (the result of Gauss-Jordan elimination) is the identity matrix, which is obviously full rank. In conclusion, the given matrix is full rank if and only if Gaussian elimination completes without producing a zero row. – Fabio Somenzi Jun 1 '17 at 4:02

It's not true in general, which is why you can't prove it.

\begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{bmatrix}

The third row can have its first entry made 0 by subtracting from it one times the first row plus two times the second. But its third entry will NOT be zero ... it'll be $-1$.

On the other hand, if we subtract the first plus the second, the third becomes zero, hence is linearly dependent on them.

Post-comment addition: What is true is that rows $1, \ldots, k$ are independent before a row-operation in which a multiple of some row $i$ with $1 \le i \le k$ is subtracted from some row $j$ (with $1 \le i < j \le k$), if and only if they are independent after as well.

A similar statement holds for row-swaps, but I'll let you formulate that one.

A proof of (half of) the claim is this: let $s_1, \ldots, s_k$ denote the rows AFTER the operation, and $r_1, \ldots, r_k$ denote the rows before.

Then $s_t = r_t$ for all $t$ except $j$, and $$s_j = r_j + c r_i.$$

Now suppose that the $s$ rows are dependent. I'll show that the rows $r$ were also dependent.

To say the rows $s$ are dependent is to say that there are numbers, not all $0$, with $$0 = a_1 s_1 + \cdots a_i s_j + \cdots + a_j s_j + \cdots a_k s_k$$ We can do some substitution to get \begin{align} 0 &= a_1 s_1 + \cdots a_i s_i + \cdots + a_j s_j + \cdots + a_k s_k \\ &= a_1 r_1 + \cdots a_i r_i + \cdots + a_j s_j + \cdots + a_k r_k \\ &= a_1 r_1 + \cdots a_i r_i + \cdots + a_j (r_j + c r_i) + \cdots + a_k r_k \\ &= a_1 r_1 + \cdots a_i r_i + \cdots + a_j r_j + ca_j r_i + \cdots + a_k r_k \\ &= a_1 r_1 + \cdots (a_i + c a_j) r_i + \cdots + a_j r_j + \cdots + a_k r_k \end{align} which shows that the rows $r_i$ are independent, as long as at least one of $a_1, \ldots, a_i + ca_j, \ldots, a_j, \ldots, a_k$ is nonzero.

Case one: one of the $a_n$ aside from $a_i$ is nonzero. In that case, that same $a_i$ is nonzero in the final linear combination above, showing that the $r_i$ are dependent.

Case two: all $a_n$ except $a_i$ are zero. In that case, the first long equation above reads

$$0 = a_i s_i$$ where $a_i$ is nonzero, which becomes $$0 = (a_i + ca_j) r_i.$$ But since $j \ne i$, we know that $a_j = 0$ as well, so we can rewrite this as $$0 = a_i r_i$$ where $a_i$ is nonzero, hence $r_i = 0$. From this we conclude that the $r$ rows are linearly dependent (because there's a nontrivial linear combination of them that's equal to the zero vector). QED

In short (once you write out the proof for row-swaps as well, and the dependence-implies-dependence proof for both cases): Gaussian elimination does not change the independence/dependence properties of a set of rows. So if you, during Gaussian elimination, make row $j$ be zero, then it was a linear combination of the previous rows (i.e., was dependent on them).

• By general do you mean an mxn matrix with real number entries? (Because that's the only thing i'm concerned about). How else can we show that elimination reveals dependent and independent rows? – jumpmonkey Jun 1 '17 at 3:38
• I mean "when there are more than two rows, it's easy to construct counterexamples like the one shown here." And I'm only talking about real matrices, yes. As for "how else can we show ...?", that's a different question, and you should ask it as a different question rather than changing this one after someone's already answered it. (Look up "chameleon question" to see what I'm talking about.) – John Hughes Jun 1 '17 at 3:41
• The title of my question is "how exactly does elimination discover dependent rows", the remaining content is only to give context and show my approach towards trying solve it. Thank you very much for replying and showing that my arguments don't work, but the original question is still unanswered. – jumpmonkey Jun 1 '17 at 3:47
• However ...the only actual question in the body is "Is this true? How can I prove/disprove it?", and that's what I answered. – John Hughes Jun 1 '17 at 10:12