# Is it true to say that any matrix in row echelon form, with columns as vectors, has linearly independent vectors?

Is it true to say that any matrix in row echelon form, excluding the zero matrix, with columns as vectors, has linearly independent vectors (of the original matrix before performing elementary row operations)? I'm wondering if I can use this as a faster method of checking for linear independence between the vectors of a set.

Thanks! :)

• No. The zero matrix is already in row echelon form ... – Hagen von Eitzen Sep 17 '16 at 8:16
• That's true but let's classify that as an exception. :) – The Pointer Sep 17 '16 at 8:17
• Although a slight adjustment, instead of adding the disclaimer at the end just make the hypothesis 'any non zero matrix'. Not saying the hypothesis is then true, but a better way to pose the questions. – Prince M Sep 17 '16 at 8:18
• No: the matrix whose unique non-zero entry is $a_{11}=0$ is another counterexample. If you put a lot of zeroes in any matrix and you get a contraditcion. – Crostul Sep 17 '16 at 8:18
• If you add "non zero matrix" then the claim is painfully trivial: any nonzero matrix, whether in REF or whatever, has at least one linearly independent row/column, when seen as vector in some $\;\Bbb F^n\;$ . – DonAntonio Sep 17 '16 at 8:21

If you want to know whether all column vectors are linearly independent, then no, $$\begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$

is an example of a matrix in row-echelon form that has rank 2, which means it not all 3 column vectors can be linearly independent.

You can put any matrix in row echelon form, and then it is easier to determine the rank (number of linearly independent column vectors) of a matrix: The rank stays the same under Gaussian elimination, so a matrix has rank $n$ if and only if its row echelon form has rank $n$.

If you want to know whether a matrix has at least one linearly independent column vector, then any nonzero matrix has at least rank 1, as @DonAntonio said in the comments.

• @ThePointer In fact it is... – DonAntonio Sep 17 '16 at 8:33
• Oops, sorry. Of course it is. I'm confusing myself now. – The Pointer Sep 17 '16 at 8:34
• Haha, I was getting anxious for forgetting stuff. Linear algebra was a long time ago for me... – DWe1 Sep 17 '16 at 8:37
• I'm confused now. @DonAntonio, you said above that this method works. Or am I misinterpreting what you're saying? – The Pointer Sep 17 '16 at 8:42
• I think there is some confusion about the question. "has linearly independent vectors" can be interpreted as "having at least one linearly independent vector" or "has full rank". I went with the second one in this question. Going to edit in the other intrepretation. – DWe1 Sep 17 '16 at 8:45

Yes, you can use a row echelon form (REF) for checking linear independence of a set of vectors.

Let's call dominant a column in a matrix in REF if it contains a pivot (in reduced row echelon form it will be a leading $1$, the terminology varies).

It's easy to see that

Fact 1. The dominant columns in a REF matrix make a linearly independent set.

Fact 2. A nondominant column in a REF matrix is a linear combination of the dominant columns.

As a consequence, the dominant columns form a maximal linearly independent set among the columns of the REF matrix.

The other important fact is that if $U$ is a REF of the matrix $A$, there exists an invertible matrix $F$ such that $U=FA$. For ease of notation, let's write $a_i$ for the columns of $A$ and $u_i$ for the columns of $U$. With $\{i_1,i_2,\dots,i_k\}$ I denote any set of indices in $\{1,2,\dots,n\}$, where $n$ is the number of columns of $A$ and $U$; $\alpha_i$ will be scalars.

Theorem. $\alpha_1a_{i_1}+\alpha_2a_{i_2}+\dots+\alpha_ka_{i_k}=0$ if and only if $\alpha_1u_{i_1}+\alpha_2u_{i_2}+\dots+\alpha_ku_{i_k}=0$.

Just multiply by $F$ or $F^{-1}$, recalling that $u_i=Fa_i$.

Corollary 1. The set of columns $\{a_{i_1},a_{i_2},\dots,a_{i_k}\}$ is linearly independent if and only if $\{u_{i_1},u_{i_2},\dots,u_{i_k}\}$ is linearly independent.

Corollary 2. $a_i=\alpha_1a_{i_1}+\alpha_2a_{i_2}+\dots+\alpha_ka_{i_k}$ if and only if $u_i=\alpha_1u_{i_1}+\alpha_2u_{i_2}+\dots+\alpha_ku_{i_k}$.

Putting together facts 1 and 2 with the theorem and its corollaries, you can see that, given vectors $a_1,a_2,\dots,a_n$ in $\mathbb{R}^m$, you can form the matrix $A$ having them as columns, compute a REF $U$ (the RREF, if you want) and easily decide whether the given vectors form a linearly independent set (if and only if every column in $U$ is dominant), but also easily extract a basis of the subspace spanned by the vectors: just take the vectors with indices corresponding to the dominant columns in $U$.