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.

• I'm not entirely sure what the question here is. Are you asking about specific forms of matrices, or the general case (in which case a simple counting argument seems to work)? – Joe Fitzsimons Aug 18 '10 at 0:03
• @Joe, as mentioned, I'm asking for an explicit family of matrices, e.g., Hadamard matrices. As usual, random matrices are cheating. This is much in the same way as we aren't happy with the fact that a random function requires large circuits. I added a paragraph to stress this point. – Moritz Aug 18 '10 at 0:09
• maybe that should be reposted as an answer :) – Suresh Venkat Aug 18 '10 at 1:58
• Ok, will do so. – Joe Fitzsimons Aug 18 '10 at 2:02
• Actually, I believe my method may have been flawed. – Joe Fitzsimons Aug 18 '10 at 4:47

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.

• Also, Gowers on his blog had a discussion involving complexity of Gaussian elimination. I haven't read it carefully (it's in the form of a long dialogue), but it may be helpful: gowers.wordpress.com/2009/11/03/… – Andy Drucker Aug 18 '10 at 4:42
• Just to understand this correctly, the width restriction comes in because you have at most n operations per column, and you can proceed column by column? – Moritz Aug 18 '10 at 17:07
• I'm thinking in terms of row operations. The width n restriction corresponds to the fact that we have n rows to work with in which all of our intermediate work would take place. The n circuit gates at depth t represent the states of the n rows after t applications of row operations. (maybe you're saying the same thing as me) – Andy Drucker Aug 19 '10 at 16:04
• If we instead allowed extra 'auxiliary workspace' rows in our Gaussian elimination, I believe we would get an exact correspondence between complexity of reducing A to the identity, and the linear arithmetic circuit complexity of Ax (which is essentially the arithmetic ckt complexity, since multiplications don't help compute linear functions beyond a constant factor). – Andy Drucker Aug 19 '10 at 16:05
• Yes, that's what I meant. I also agree with the second statement. A general linear circuit can sort of create new rows whenever it wants to :-) – Moritz Aug 20 '10 at 15:03

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.