Gaussian elimination makes determinant of a matrix polynomial-time computable.   The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence of alternate negative signs (lack of which makes computing permanent is $ \#P\mbox{-}hard$ ie. harder then $NP\mbox{-}C$ problems). This leads to some sort of symmetry in determinant, eg exchange of a pair of rows or columns just reverses the signs. I read somewhere, probably in connections with holographic algorithms introduced by Valiant, that Gaussian elimination could be explained in terms of group action and this in turns leads to generic techniques in complexity reduction.Also, i feel that almost all source of complexity reduction for any computational problem is some sort of symmetry present. Is it true? Can we rigorously formalize this in terms of group theory?Edit I found the reference. (pg 2, last line of second paragraph). I did not understand the paper properly, If my question is based on wrong understanding of the paper, please correct me.
Gaussian Elimination in terms of Group Action
cc.complexity theory;time complexity;algebraic complexity;gr.group theory;determinant
In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as to @Tsuyoshi Ito's point that the symmetries of the permanent seem not to help compute it efficiently: although the permanent is also characterized by its symmetries, its symmetry group is much smaller than that of the determinant.)You can find a write-up of this - where the symmetries of the determinant are used to do Gaussian elimination, along the way proving that the determinant is characterized by its symmetries - in Proposition 3.4.3 of my thesis (shameless self plug - but also, I've never seen it phrased quite this way before and written in full detail, as the OP was asking for, though I'm sure it's been done; I'd be happy if someone had other references).As to the idea that symmetry always leads to complexity reduction (or not), in addition to things already in the comments, see this question and its answers.An interesting point is that in Valiant's first papers on what is now known as Valiant's version of algebraic complexity theory, he was trying to make the point that one reason the determinant is important computationally is because roughly all the (then) known efficient algorithms could be reduced to linear algebra and thence to the computation of the determinant, e.g. the FKT algorithm for counting matchings in planar graphs. This is of course an exaggeration, but continues to be borne out by research into holographic algorithms, which often reduce to computing the Pfaffian (a close relative of the determinant). Surely Valiant knew this was an exaggeration, but here's the exact quote just to make sure I'm not misrepresenting (L. Valiant. Completeness classes in algebra. ACM STOC 1979):Our main conclusions can be summarized roughly as follows:(a) Linear algebra offers essentially the only fast technique for computing multivariate polynomials of moderate degree(b) ...