# How to see which vectors are linearly independent given a set of vectors without computing every possibility?

I have a set of vectors $S= \{v_1,v_2,v_3,v_4,v_5\}$ with $v_1=(0,-1,0,1)$, $v_2=(1,1,0,3)$, $v_3=(1,3,0,1)$, $v_4=(0,1,-1,-1)$, $v_5=(0,1,2,-1)$. I am asked to find a subset which is a basis of V. My question is how can I see without computing every possible combination of four vectors the linearly independent set. I have computed the determinant of $v_1,v_2,v_3,v_4$ and $v_1,v_2,v_4,v_5$ and got $0$ for both indicating linear dependence. Is there an easy way to see this ?

If you only need to find one linearly independent subset, then form a matrix with the vectors as columns and row-reduce. The columns of the rref that contain pivots correspond to columns in the original matrix that are linearly independent.

Incidentally, the set $S$ that you have in the question doesn’t span all of $\mathbb R^4$, so every subset of four vectors that you try will end up being linearly dependent.

There is no simple and immediate way, apart from very simple systems.

You could take the matrix whose rows are the components of the vectors and find its rank, by reduction in row echelon form, or by looking for a non null minor by and incremental search.

The non null rows in row echelon form represent the vectors in a maximal linear independent subsystem.
Alternatively, the rows in the maximal non null minor represent the vectors in a maximal linear independent subsystem.

Form a matrix by arranging these vectors row-wise and apply elementary row operations to reduce it into echelon form. Now the non-zero rows correspond to the linearly independent vectors.

• Yes but those vectors may are not necessarily be the ones in the set S since they have undergone row operations so they are different. I am looking to find a linearly independent set which consists of the vectors in the set S. – april analysis May 18 '17 at 17:58
• Not quite. The non-zero rows of the rref form a basis of a row space of the matrix—the span of $S$—but they don’t necessarily correspond to the rows of the original matrix. Try it with this particular set of vectors, in fact: the first three rows of the rref are non-zero, but the first three vectors are not linearly independent. – amd May 18 '17 at 19:57