This is not an answer, but a response to this comment.
Assume that $A$ is the matrix which columns are the rows that we want to test for linear independence. I am putting them are columns for no other reason than personal comfort.
Doing the row transformations required in Gaussian elimination correspond to multiplying $A$ from the left by some elementary ...
It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform
basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.