Signature of a quadratic form This may be a really dumb question, but here goes: is there any algorithm to compute the signature of a quadratic form (or a symmetric matrix, if you prefer)  more efficient (asymptotically or otherwise)  than actually computing the eigenvalues?
 A: Thursday morning. Noam has suggested that this is equivalent to performing Gram-Schmidt without normalization. That would explain why I could not find any explicit point where anyone wrote "Here is a way to reverse Hermite's type of method." I'm going to try some 2 by 2 and 3 by 3 examples, see if I understand.
Here are explicit example(s) as links, in this first one the form is indefinite; 
https://math.stackexchange.com/questions/427946/orthogonal-basis-for-this-indefinite-symmetric-bilinear-form
Igor, there is an easy algorithm that creates $P^T A P = D$ with $D$ diagonal, $\det P = 1$ and the elements of $P$ in the same field as that needed for $A.$
I can describe the way I do it. Let $A_0 = A,$ then $A_{j+1} = P_j^T A_j P_j,$ where $P_j$ is one of three types:
(I) the identity matrix, except for the value $t$ at position $i,j$ in the upper triangle
(II) the identity matrix, except $p_{ii} = 0,$ $p_{jj} = 0,$ $p_{ij} = 1,$ $p_{ji} = -1,$ 
(III) the identity matrix, except for the fixed value $1$ at a position in the lower triangle.
Oh, after doing several of these, I realized that a bunch of type (I) matrices with the extra off diagonal elements in the same row can be combined into one matrix, as such matrices commute with each other.
I had never seen it before, I asked about it at  http://math.stackexchange.com/questions/1388421/reference-for-linear-algebra-books-that-teach-reverse-hermite-method-for-symmetr
In the most favorable cases, $P$ is also upper triangular. Not guaranteed.

A: There's a large literature on "inertia revealing factorizations" for real or complex matrices. Usually one uses MA57 of the HSL implementation to compute the signature, which does an sparse $LDL^T$ factorization: http://www.hsl.rl.ac.uk/catalogue/ma57.html
A: Gauss reduction gives you the answer. It writes, quite fast, the quadratic form $q$ as a sum
$$\sum_ja_j\ell_j(x)^2$$
where the $\ell_j$'s are independent linear forms. The number of squares gives you the rank of $q$. The signs of the coefficients $a_j$ gives you the signature. I teach that in my undergraduate course in Algebra.
Remark that you cannot calculate the eigenvalues, at least in close form, because this is computing the roots of quite a general polynomial, and this is impossible in dimension $\ge5$.
