# Computing the number of positive and negative eigenvalues

Given a $n \times n$ symmetric matrix $A$ with integers as entries I would like to compute the number of strictly negative $\rm{nn}(A)$ and positive $\rm{np}(A)$ eigenvalues of $A.$

My question is

What is the most efficient way to do this?

I am currently just computing the eigenvalues of $A$ and counting negative/positive eigenvalues. But it turns out that this is the bottleneck in the program using this, hence I am wondering if there's any more efficient way to compute these two quantities.

You can simply use a variant of Gaussian elimination in combination with the Sylvester's law of inertia, which says that for any nonsingular matrix $B$, the matrices $A$ and $B^TAB$ have the same inertia (the number of positive, negative, and zero eigenvalues).
Any symmetric matrix $A$ can be factorized as $A=LDL^T$, where $D$ is block diagonal with the sizes of the blocks at most 2. Computing this factorization and looking at the signs of the eigenvalues of $D$ will give you the answer.