# 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). 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.) Apr 15 '12 at 8:33
• Certainly; it seems that I mistakenly left the word "dense" out of my comment. 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? 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. 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. Apr 23 '12 at 14:22
• @Jon: Sigh. That is not what the downvote is for. 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! Apr 24 '12 at 16:56