Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to find a quick method for evaluating the inertia of a real symmetric matrix, though I don't need to evaluate eigenvalues directly. The inertia of a matrix is a triple of the number of positive eigenvalues, negative eigenvalues and eigenvalues equal to zero.

Thus far I have implemented a method of using Householder matrices to reduce a real symmetric matrix to tridiagonal form (whilst preserving inertia). A textbook by Gilbert Stewart I found through a simple Google search suggests that this is in the right direction. Does anyone have any ideas for the last step?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Yes, you're in the right direction. Recall that a symmetric matrix's inertia is always preserved under congruence transformations $\mathbf A\mapsto\mathbf X\mathbf A\mathbf X^\top$, and your first step of reducing to tridiagonal form via Householder transformations (with $\mathbf X$ being orthogonal) is exactly a congruence transformation.

Now, from your original matrix $\mathbf A$ you have $\mathbf A=\mathbf Q\mathbf T\mathbf Q^\top$, with $\mathbf T$ tridiagonal. From here, there are a number of methods you can use for determining the inertia of a symmetric tridiagonal matrix. In most cases, you can try computing the $\mathbf L\mathbf D\mathbf L^\top$ decomposition of your tridiagonal matrix, where $\mathbf L$ unit lower bidiagonal, and $\mathbf D$ is diagonal, from which the inertia of your tridiagonal matrix is given by the number of positive, zero, and negative elements of the diagonal matrix $\mathbf D$.

Of course, that naïve strategy won't work if the leading principal submatrix of $\mathbf T$ is singular. There is, however, an algorithm by James Bunch (see this for more details, and this for a MATLAB realization (but written for clarity at the expense of storage efficiency)), where $\mathbf T$ is decomposed as $\mathbf L\mathbf B\mathbf L^\top$, where this time $\mathbf B$ is block diagonal, with either scalar or $2\times 2$ blocks. The inertia is then evaluated from $\mathbf B$. See the links for more details.

share|improve this answer
    
Thank you very much! You're a champion. –  Murray May 8 '12 at 23:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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