Efficient way of checking linear independence Suppose I have a $4 \times 4$ matrix $A$ whose columns represent vectors $v_1,v_2,v_3,v_4$ in $\mathbb{R}^4$. Now, given that $\det{A} = 0$ (i.e. the vectors are linearly dependent), I want to make sure that any three vectors out of the given 4, are linearly independent. What is the most efficient way of doing this? I can only think of checking linear independence of each three vectors out of all the possible combinations. But I feel that there must be some easier way to accomplish this. 
 A: In order to check whether any three columns are linearly independent, you would unfortunately have to examine all subsets of $3$ columns.
As a sidenote, this question is related to computing the spark of a matrix (see here: http://en.wikipedia.org/wiki/Spark_%28mathematics%29).
If all sets of $3$ columns have full rank (rank equal to $3$), then the spark of $A$ in your case is equal to $4$: $4$ is the smallest number of columns that are linearly dependent.  But, if there exists a subset of $3$ columns that is linearly dependent, then the spark is at most $3$.
Computing the spark is an NP-hard problem. 
A: Best way is as copper.hat suggested. Row-reduce. That will give you the linearly independent vectors. If you are asking which three because (for instance, $\vec v_3=2\vec v_2$), this procedure will tell you. As far as computational complexity, I believe that it is $N^3$, which isn't bad.
The reason that row-reduction works is it gives you the pivots. The columns with leading non-zero entries are the linearly independent set of vectors. If you are trying to figure out which other combinations work, try swapping the order of the columns in the matrix, and compute the row-reduction again.
