9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Jack Poulson Apr 14 '12 at 21:20
  • $\begingroup$ @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.) $\endgroup$ – Arnold Neumaier Apr 15 '12 at 8:33
  • $\begingroup$ Certainly; it seems that I mistakenly left the word "dense" out of my comment. $\endgroup$ – Jack Poulson Apr 15 '12 at 16:05
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ A downvote without any constructive criticism? $\endgroup$ – Jack Poulson Apr 15 '12 at 5:00
  • 2
    $\begingroup$ 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. $\endgroup$ – Shuhao Cao Apr 16 '12 at 0:53
  • $\begingroup$ 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. $\endgroup$ – Shuhao Cao Apr 23 '12 at 14:22
  • $\begingroup$ @Jon: Sigh. That is not what the downvote is for. $\endgroup$ – Jack Poulson Apr 24 '12 at 16:53
  • $\begingroup$ I know! I already told him "please read the rule" after I found that he used my account to downvote a relevant answer! $\endgroup$ – Shuhao Cao Apr 24 '12 at 16:56

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.