Consider a finite-dimensional vector space $V_{n - 1} = \langle v_1, \dots, v_{n-1}\rangle \subseteq V$. Let $v_n \in V$. Extend $V_{n-1}$ by $v_n$ ($V_n := \langle v_1, \dots, v_n \rangle$). The question is: How are we able to efficiently check whether $\dim(V_n) > \dim(V_{n-1})$?
It is crucial that the computational complexity is as low as possible, since high dimensions of $V$ and high numbers $n$ may occur. Bonus: Do we get better results when the matrices are sparse?
In other words: Is there an efficient way to check whether $v_n$ is linear independent of $v_1, \dots, v_{n-1}$?
My idea would be to recursively find a basis of $v_1, ..., v_{n-1}$ and solve the resulting homogenous linear equation system with QR decomposition or similar, but is there a faster way, since it is only an "Is X bigger than Y" problem? Please note that $v_1, \dots, v_{n-1}$ are not necessarily linearly independent.
Background: The problem arose with vector $v_n$ being a tangent vector in a manifold of some function which was $n$ times differentiated. (Or similar; it occurred as a programming problem to a friend of mine, who explained it informally to me.)
