Lower bounds on Gaussian complexity Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity between $0$ and $n^2$ (via Gaussian elemination). The notion makes sense over any field.

This problem certainly seems very basic and it must have been studied. Surprisingly, I don't know of any references. So, I'll be happy with any reference there is. But, of course, the main question is:

Are there any non-trivial explicit lower bounds known?

By nontrivial I mean superlinear. Just to be clear: Over finite fields a counting argument shows that a random matrix has complexity order n^2 (a similar claim should be true over infinite fields). Hence, what we're looking for is an explicit family of matrices, e.g., Hadmard matrices. This is the same as with Boolean circuit complexity where we know that a random function has high complexity, but we're looking for explicit functions with this property.
This appears to be a very hard problem, related to a more widely-studied one.

Suppose we consider a square invertible matrix A, and define c(A) as the minimal number of elementary row operations needed to reduce A to the identity matrix.  This complexity measure is larger than the one Moritz suggests, so proving superlinear bounds for it can only be easier.

Now, row operations are reversible.  It follows that c(A) can be equivalently defined as the minimum number of row operations needed to produce A, starting from the identity matrix.  

Notice that producing A in such a fashion gives rise to an arithmetic circuit to compute the map taking x to Ax.  The fanin of each gate is 2, and the number of non-input gates corresponds to the number of row operations.

There isn't any obvious reduction in the reverse direction (from circuits to row-op sequences).  Still, we can characterize c(A) in terms of the arithmetic circuit complexity of Ax in a restricted circuit model: I claim that c(A) is equal to one-half the minimum number of edges in an arithmetic circuit for A, of fanin at most 2 and width n, where we don't charge for edges leading into gates of fanin 1.
(I'm using the usual notion of circuit width here.)  This can be shown using the simple idea sketched before.

Now here's the connection to well-studied problems: it's been a famous open problem for over 30 years to exhibit an explicit linear map Ax (over any finite field) which requires a superlinear number of gates in a fanin-2 circuit.  The classic reference is Valiant, "Graph-theoretic arguments in low-level complexity", and a recent FTTCS survey by Lokam is also helpful.

In studying c(A), we are imposing an additional width restriction, but since our restriction is so weak (width n) I don't anticipate the problem becoming much easier.  But hey--I'd love to be proved wrong.