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...
 A: 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). 
