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

<p>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.) </p>

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

<p>The article should be accessible on JSTOR. </p>

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

CC BY-SA 2.5
2010-08-18T21:36:04.007Z
2010-08-18T21:36:04.007Z
Ryan Williams
<p>This appears to be a very hard problem, related to a more widely-studied one.</p>

<p>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.</p>

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

<p>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.</p>

<p>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 <em>width</em> 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-19T16:04:19.953Z
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
CC BY-SA 2.5
2010-08-19T16:05:12.620Z
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
CC BY-SA 2.5
2010-08-20T15:03:54.250Z
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
CC BY-SA 2.5
2010-08-18T04:42:08.480Z
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:

http://gowers.wordpress.com/2009/11/03/a-conversation-about-complexity-lower-bounds-ix/
Andy Drucker
CC BY-SA 2.5
2010-08-18T17:07:51.240Z
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
CC BY-SA 2.5
2010-08-18T04:40:38.810Z
2010-08-18T04:40:38.810Z
Andy Drucker
<p>Define the <em>Gaussian complexity</em> 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.</p>

<p>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:</p>

<p><em>Are there any non-trivial explicit lower bounds known?</em></p>

<p>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 <em>explicit</em> 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.</p>

CC BY-SA 2.5
2010-08-18T00:03:38.970Z
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
CC BY-SA 2.5
2010-08-18T00:09:16.197Z
@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
CC BY-SA 2.5
2010-08-18T01:58:20.783Z
maybe that should be reposted as an answer :)
Suresh Venkat
CC BY-SA 2.5
2010-08-18T02:02:00.930Z
Ok, will do so.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-18T04:47:09.690Z
Actually, I believe my method may have been flawed.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-18T04:56:52.423Z
Joe, I believe the lower-bound criterion you suggested may provably fail.  The Sylvester matrices are a family of matrices with rows of n/2 ones, such that any two rows have n/4 ones in common; yet they are computable by linear-size arithmetic circuits, as was shown by Alon, Karchmer, Wigderson in 'Linear circuits over GF(2)'.  I'm not sure if their circuits meets the width restriction discussed in my Answer below, but if it does then we have a counterexample here.
Andy Drucker
CC BY-SA 2.5
2010-08-18T04:58:48.580Z
(Just to record the proposal since the  answer was retracted: the suggestion was that if a square matrix has rows of n/2 ones, such that any two rows have n/4 ones in common, then it might require superlinearly many row operations to reduce to triangular form.)
Andy Drucker
CC BY-SA 2.5
2010-08-18T05:10:46.520Z
Andy, that jars with my understanding of what a Sylvester matrix is. Do you have a reference?
Joe Fitzsimons
CC BY-SA 2.5
2010-08-18T05:19:11.653Z
Joe--see the AKW paper I mentioned.  One has to exclude the zero row to get n/2 ones per row.
Andy Drucker
CC BY-SA 2.5
2010-08-18T05:31:02.430Z
Thanks, certainly the matrices in the paper are pretty much what I was thinking of, though they use Hamming distance (which is necessary, rather than the condition I gave, since mine produces insufficiently many rows). However I don't think the linear bound is an issue. The gates do not map on to individual row or column operations, but rather on to groups of exponentially many such operations.
Joe Fitzsimons
<cc.complexity-theory><lower-bounds><matrices>
Lower bounds on Gaussian complexity
Moritz
# Lower bounds on Gaussian complexity

(Asked by: username_0 on 2010-08-17)

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.

**Tags:** cc.complexity-theory, lower-bounds, matrices
> **Comments:**
> **username_1**: 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)?  
> **username_0**: @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.  
> **username_2**: maybe that should be reposted as an answer :)  
> **username_1**: Ok, will do so.  
> **username_1**: Actually, I believe my method may have been flawed.  
> **username_3**: Joe, I believe the lower-bound criterion you suggested may provably fail.  The Sylvester matrices are a family of matrices with rows of n/2 ones, such that any two rows have n/4 ones in common; yet they are computable by linear-size arithmetic circuits, as was shown by Alon, Karchmer, Wigderson in 'Linear circuits over GF(2)'.  I'm not sure if their circuits meets the width restriction discussed in my Answer below, but if it does then we have a counterexample here.  
> **username_3**: (Just to record the proposal since the  answer was retracted: the suggestion was that if a square matrix has rows of n/2 ones, such that any two rows have n/4 ones in common, then it might require superlinearly many row operations to reduce to triangular form.)  
> **username_1**: Andy, that jars with my understanding of what a Sylvester matrix is. Do you have a reference?  
> **username_3**: Joe--see the AKW paper I mentioned.  One has to exclude the zero row to get n/2 ones per row.  
> **username_1**: Thanks, certainly the matrices in the paper are pretty much what I was thinking of, though they use Hamming distance (which is necessary, rather than the condition I gave, since mine produces insufficiently many rows). However I don't think the linear bound is an issue. The gates do not map on to individual row or column operations, but rather on to groups of exponentially many such operations.  

---

## 2 answers

### Answer by username_3 on 2010-08-18. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_3**: 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:  http://gowers.wordpress.com/2009/11/03/a-conversation-about-complexity-lower-bounds-ix/  
> **username_0**: 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?  
> **username_3**: 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)  
> **username_3**: 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).  
> **username_0**: 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 :-)  

---

### Answer by username_4 on 2010-08-18. Score: 9

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.


---

