# Is there a generalization of the Sylvester Inertia Law for the symmetric generalized eigenvalue problem?

I know that in order to solve symmetric eigenvalue problem $Ax = \lambda x$, we can use the Sylvester Inertia Law, that is the number of eigenvalues of $A$ less than $a$ equals the number of negative entries of $D$ where diagonal matrix $D$ comes from the LDL factorization of $A-aI = LDL^{T}$. Then, by bisection method, we can find all or some eigenvalues as desired. I wish to know if there exists a generalization of the Sylvester Inertia Law for symmetric generalized eigenvalue problems, that is solving $Ax= \lambda Bx$, where $A$ and $B$ are symmetric matrices. Thanks.

Yes, if the pencil is definite, i.e., if $A$ and $B$ are Hermitian and $B$ is positive definite. Then the signature of $A-\sigma B$ has the same interpretation for the eigenvalue problem $(A-\lambda B)x=0$ as in the case $B=I$. A more general result of this kind holds for any definite nonlinear eigenvalue problem $A(\lambda)x=0$. See Section 5.3 of my book

Arnold Neumaier, Introduction to numerical analysis, Cambridge Univ. Press, Cambridge 2001.

For $(A-\lambda B)x=0$, the proof of my assertion can be deduced from the argument given by Jack Poulson upon noting that $C-\sigma I$ and $A-\sigma B$ are congruent, hence have the same inertia.

In particular, one can directly compute the inertia of $A-\sigma B$, and doesn't need a Cholesky factorization of $B$ to form $C$. Indeed, if $B$ is ill-conditioned then the numerical formation of $C$ degrades the quality of the inertia test.

• Good point about the ill-conditioning of B; I think that your approach is better if one truly is only interested in computing the inertia. The approach I suggested is typical for actually solving the eigenvalue problem (in the case where $B$ is well-conditioned). – Jack Poulson Apr 14 '12 at 21:20
• @JackPoulson: The inertia test is usually applied to get the eigenvalues in a specific interval when $A$ and $B$ are sparse and their joint sparsity pattern generates not too much fill in. But your $C$ will be dense already when $B$ is tridiagonal, hence using it is never suitable for finding the eigenvalues of a large sparse generalized eigenvalue problem. (Whereas if the problem is not large, there is little point in using inertia, as finding all eigenvalues is usually fast enough.) – Arnold Neumaier Apr 15 '12 at 8:33
• Certainly; it seems that I mistakenly left the word "dense" out of my comment. – Jack Poulson Apr 15 '12 at 16:05

In the case where $B$ is Hermitian and positive-definite, a Cholesky factorization of $B$, say $B = L L^H$, gives that

$$Ax=LL^H x \lambda,$$

and this equation can be manipulated to show that

$$(L^{-1} A L^{-H})(L^H x) = (L^H x) \lambda,$$

where it should be clear that $C \equiv L^{-1} A L^{-H}$ preserves the symmetry of $A$, and also has the same spectrum as the pencil $(A,B)$. Thus, after forming $C$, with a Cholesky factorization followed by a two-sided triangular solve, you can directly apply the Sylvester inertia law to $C$ to glean information about the eigenvalues of the pencil $(A,B)$.

Note that, since Sylvester's Law of Inertia is invariant with respect to congruence transformations, e.g., $S \cdot S^H$, then the matrix $C$ is congruent to $A$ through the transformation $L^{-1} \cdot L^{-H}$, and so $C$ has the same inertia as $A$. However, if the inertia of $C-\sigma I$ is desired, for some nonzero shift $\sigma$, then we can no longer simply consider $A$.

• A downvote without any constructive criticism? – Jack Poulson Apr 15 '12 at 5:00
• I haven't logged out on my office's computer, and my officemate happened to run into this tab in my browser and downvoted the answer, I apologize for the misunderstanding and will ask him why he downvoted this. – Shuhao Cao Apr 16 '12 at 0:53
• You were absolutely correct when $B$ is an spd matrix, for the pair $(A,B)$, we could simply look at $A$ to get what we want. However, my officemate said that you didn't answer the question if $B$ only has symmetricity. Sorry for the confusion. – Shuhao Cao Apr 23 '12 at 14:22
• @Jon: Sigh. That is not what the downvote is for. – Jack Poulson Apr 24 '12 at 16:53
• I know! I already told him "please read the rule" after I found that he used my account to downvote a relevant answer! – Shuhao Cao Apr 24 '12 at 16:56