Is it possible to find the signature of a matrix without finding the eigenvalues of the matrix?
I was hoping to use the Sylvester's Law of inertia but I don't remember any algorithm to diagonalize a matrix $A$ to the form $UDU^t$ where $D$ is a diagonal matrix.
The actual aim was to find the number of real solutions of a uni-variate polynomial using Pederson-Roy-Szpirglas theorem. http://link.springer.com/chapter/10.1007/978-1-4612-2752-6_15
The easiest way is to compute the LU decomposition (without pivoting) of the symmetric matrix and count the signs on the diagonal of the U factor. This of course fails if some early diagonal entry of U is $0$.
Justification: Decompose $U=DR$ with $D$ diagonal and $R$ with only $1$ on the diagonal. Then $A=LDR$ and $A=A^T=R^TDL^T$ and by the uniqueness of the LU decomposition, $R=L^T$. By the inertia theorem, the sign structure of $D$ is invariant, and thus the index can be computed from it.