Row reduced matrix $\Leftrightarrow$ vectors (rows) are linearly independent.

Question

Let $A$, a row-reduced matrix (after applying Gaussian elimination). Show that all rows which are different from $V_0$ (zero vector), are linearly independent.

We learned this as sort of an axiom, but I am curios how to prove it.

Answer 1

Take the first row with a leading non-zero entry (say this entry is $a_1$), all entries in the column below it is zero, so that no linear combination of the rows below it can produce the entry $a_1$: \begin{equation}(a_1, \ldots, a_n)\neq x_1(0,\ldots,b_n)+x_2(0,\ldots,c_n)+\cdots.\end{equation}

So this establishes that row 1 is linearly independent from all other rows in $A$. Now simply repeat the same argument for row 2 together with the rows below it, and then for row 3, etc. for all non-zero rows.

Answer 2

Each row that is non-zero has all leading zeros up until a non-zero element, and the positions of the first non-zero elements are all different for different rows. To show these rows are linearly independent, it suffices to show the rows are linearly independent for a subset of the columns. So choose the subset of columns to be the columns where a leading non-zero entry in a row occurs, and sort rows according to where the first non-zero entry occurs. Then you get an upper-triangular matrix (all entries below the diagonal are zero), where are diagonal entries are non-zero. The determinant of such a matrix is the product of the diagonal entries which is non-zero, so the matrix is invertible so the rows are linearly independent.