1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.