Show that the rows of a binary matrix in REF are linearly independent I know that a matrix in REF if the leading 1 of a non-zero row is to the right of any nonzero row’s leading 1 which is above it and that all zero rows are at the bottom. Further, I know that the rows of a binary matrix will be linearly independent if 
$$\lambda_1r_1 + \lambda_2r_2 + \dots + \lambda_kr_k = 0 \rightarrow \lambda_1, \dots, \lambda_k = 0$$
where $r_i$ is the $i_{th}$ row of the binary matrix.
I'm just having trouble getting started showing this.
 A: It seems that you want to show that the non-zero rows of a matrix in rref are linearly independent.
Let $r_1,\dots,r_k$ denote the non-zero rows.  Let $j_1,\dots,j_k$ be such that for any $p$, the $j_p$th entry of $r_p$ is the leading one for that row.  Because the matrix is in REF, we may state that for $p=1,\dots,k$, $r_p(j_p) = 1$,
and if $p < q$, then $r_q(j_p) = 0$.
For example, in the matrix
$$
\pmatrix{
1&1&0&1\\
0&0&1&1\\
0&0&0&1\\
0&0&0&0\\
0&0&0&0
} 
$$
we would be considering rows $1,2,$ and $3$.  We have $j_1 = 1,j_2=3,j_3 = 4$.  We can verify that in this instance, we have $r_2(j_2) = 1$ and $r_2(j_1) = 0$ because the matrix is in REF.
Now, consider the equation $\lambda_1 r_1 + \lambda_2 r_2 + \cdots + \lambda_k r_k = 0$.  If we look at the $j_1$ entry of the vector on both sides, we get the equation $\lambda_1 = 0$.  If we look at the $j_2$ entry, we get the equation $r_1(j_2) \lambda_1 + \lambda_2 = 0$.  Looking at each of the $j_p$th entries for $p = 1,\dots,k$, we end up with the system of equations
$$
\pmatrix{1&0&0&\cdots&0\\
r_1(j_2)&1&0&\cdots&0 \\
r_1(j_3)&r_2(j_3)&\ddots&\ddots&\vdots\\
\vdots&&\ddots&1&0\\
r_1(j_k)&\cdots&&r_{k-1}(j_k)&1} 
\pmatrix{\lambda_1 \\ \lambda_2\\ \vdots \\ \\ \lambda_k} = 
\pmatrix{0\\ 0\\ \vdots \\ \\ 0}
$$
This system of equations is easily solvable with forward-substitution.  That is, the first equation tells us $\lambda_1 = 0$.  Plugging that into the next equation yields $\lambda_2 = 0$.  Plugging those into the next yields $\lambda_3 = 0$, etc.
