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?

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.
