How fast can you determine if vectors are linearly independent? Let us suppose you have $m$ real-valued vectors of length $n$ where $n \geq m$.
How fast can you determine if they are linearly independent? 
In the case where $m = n$ one way to determine independence would be to compute the determinant of the matrix whose rows are the vectors. I tried some googling and found that the best known algorithm to compute the determinant of a square matrix with $n$ rows runs in $O \left ( n^{2.373} \right )$. That puts an upper bound on the case where $m = n$. But computing the determinant seems like an overkill. Furthermore it does not solve the case where $n > m$.
Is there a better algorithm? What is the known theoretical lower bound on the complexity of such an algorithm?
 A: Forming a matrix $A$, this problem is equivalent to determining whether $Ax = 0$ has nontrivial solutions. Solving a linear system can be decomposed into a series of matrix multiplications, so it will always have the complexity of the fastest matrix multiplication algorithm. 
A: Like Christopher A. Wong said this comes down to solving $Ax=0$ and checking for a nontrivial solution. There are a few approaches to doing this in the case $n>m$. One way would be to solve by finding the LU decomposition of $A$ and then using forward and backward substitution. This can be accomplished in $O(\frac{2}{3}n^3)$ floating point operations. You could also find the QR decomposition of $A$. Then the rank of $A$ will be the same as the rank of $R$. Since $R$ is triangular it is easy to see it's rank. This can be accomplished in $O(n^3)$ floating point operations. There are many ways to implement the QR decomposition. If you are going to do it I suggest using the Householder transformation approach, it is the most numerically stable. A good place to read about this stuff is Fundamentals of Matrix Computations by Watkins.
A: Please use the following steps


*

*Arrange the vectors in form of a matrix with each vector representing a column of matrix.

*Vectors of a matrix are always Linearly Dependent if number of columns is greater than number of rows (where m > n). 

*Vectors of a matrix having number of rows greater than or equal to number of columns (where n >= m) are Linearly Independent only if Elementry Row Operations on Matrix can convert it into a Matrix containing only Mutually Orthogonal Identitity Vectors (An Identity Vector is a Vector having 1 as one of the component and 0 as other components). Otherwise the vectors are Linearly Dependent
So, the only thing that is required is a fast algorithm to do elementry row operations on a matrix with n>=m to check whether the vectors in it can be converted to Mutually Orthogonal Identitity Vectors
If someone thinks this answer is wrong, please prove it by giving some counter  examples of Matrices.
