Lower bounds on Gaussian complexity

Question

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.

Answer 1

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.

Answer 2

There are references, and they're quite old. I came across them while working on combinatorial algorithms for Boolean matrix multiplication.

In 1966, Moon and Moser proved that computing the inverse of a matrix over GF(2) needs $\Theta(n^2/log n)$ row operations, providing an upper and lower bound. (You can squeeze an extra $\log n$ out when you work over a finite field.)

J. W. Moon and L. Moser. A Matrix Reduction Problem. Mathematics of Computation 20(94):328– 330, 1966.

The article should be accessible on JSTOR.

I am pretty sure that the lower bound is just a counting argument, and no explicit matrices achieving the lower bound were given.