do the columns of rref(A) linearly independant => columns of A are linearly independant

Question

Im having trouble seeing this. I tend to think that if the columns of RREF(A) are linearly independent then the columns of A are too. But I cannot convince myself this is true. I think if you have a matrix A whose columns are linearly independent and try to solve $$c_{1}Col(A_{1})+...+c_{n}Col(A_{n})=0$$ you will end up with: $$ I_{n}|\vec0 $$ Any help appreciated

Answer 1

The point is that the row operations on a matrix $A$ preserve the null space of $A$: if $A x = 0$ then $rref(A) x = 0$ and vice versa. A linear combination of columns of $A$ is $A x$ for some vector $x$: the entries of $x$ give you the coefficients of the linear combination. Thus $$ \eqalign{A\ \text{has linearly independent columns} & \iff\cr x=0\ \text{is the only solution of}\ Ax = 0& \iff\cr x=0\ \text{is the only solution of}\ rref(A)x = 0& \iff\cr rref(A)\ \text{has linearly independent columns} & }$$

Answer 2

There is an "indirect way" to see that, at least if $A$ is quadratric. For a quadratic matrix $A$ we have: $$A\text{ is invertible} \Leftrightarrow \det A \neq 0 \Leftrightarrow A\text{ has linearly independent columns}$$

If $A$'s columns are linearly independent, then $\det A\neq 0$. If you apply any kind of gauss elimination to $A$, the determinant might change by a factor of $\lambda\neq 0$, but ultimately $\det\operatorname{rref}(A) \neq 0$.

Answer 3

Let $a_1,...,a_n$ represent the columns of $A$.

The columns of $A$ are linearly independent means that the only solution to the equation: $c_1a_1+...+c_na_n=0$, for $c_i\in \mathbb{R}$ (or any other field you are working in)

is $c_1=...=c_n=0$.

If we let $c=[c_1,...,c_n]$ then this is equivalent to the saying that the equation $cA=0$ has the unique solution $c=0$.

But the reason we row reduce a matrix, is because if $D$ is the row reduced matrix with columns $d_1,...,d_n$, then the solutions $c$ to the equation $cD=0$, are the same as the solutions $c$ to the equation $cA=0$.

Thus the columns of $A$ are linearly independent

$\iff$ $c_1,...,c_n=0$ is the only solution to $c_1a_1+...+c_na_n=0$

$\iff$ $c=0$ is the only solution to $cA=0$

$\iff$ $c=0$ is the only solution to $cD=0$

$\iff$ $c_1,...,c_n=0$ is the solutions to $c_1d_1+...+c_nd_n=0$

$\iff$ the columns of $D$ are linearly independent.