# Manipulating a generalized eigenvector problem to plain eigenvector problem

Let $X\in\mathbb{R}^{n\times p}$ denote a matrix with $p$ linearly-independent columns, and let $L\in\mathbb{R}^{n\times n}$ denote a symmetric matrix. Furthermore, let $D\in\mathbb{R}^{n\times n}$ denote a diagonal matrix with positive-entries.

Now suppose that we are interested in computing solutions to the symmetric generalized-definite eigenproblem,

$$A v = \lambda B v,$$

where the symmetric matrices $A$ and $B$ (where $B$ is also positive-definite) are implicitly given by the matrices $X$, $L$, and $D$ above, where $A = X^T L X$, and $B = X^T D X$.

I ran into a paper which claimed that we may solve an equivalent standard eigenvalue problem involving a modification of $X$. In particular, if we orthogonalize $X$ with respect to $D$, say $\tilde X^T D \tilde X = I$, then eigenpairs of

$$\tilde X^T L \tilde X u = \lambda u$$

are also eigenpairs for the original generalized eigenproblem. How can we show this to be true?

• Could you clarify what your assumptions on $A$ and $B$ are? For instance, is $B$ symmetric/Hermitian and positive-definite? – Jack Poulson Oct 3 '12 at 20:00
• @JackPoulson Edited: $A$ is symmetric, and $B$ is positive definite. However, I'm interested in the specific problem: $A=X^TLX$ and $B=X^TDX$ – usero Oct 3 '12 at 20:18
• I am still not sure what you're getting at with your notation, would you mind providing a citation rather than saying "found in the literature"? Have you looked into the Cholesky-Wilkinson algorithm? It also reduces a problem of your form to a standard eigenvalue problem (though it should not be used if B is ill-conditioned). – Jack Poulson Oct 3 '12 at 23:23
• No citation still? Part of what doesn't make sense is that your (1) equation is $p \times p$, and your original $Av=\lambda Bv$ equation is $n \times n$. It would really help clear things up if you said how $X$, $L$, and $D$ relate to $A$ and $B$. – Jack Poulson Oct 4 '12 at 14:27
• I hate to sound like a broken record, but, no citation? – Jack Poulson Oct 4 '12 at 16:58

Let $X=\tilde X Z$, where $\tilde X^T D \tilde X=I$. Then we may rewrite

$$(X^T L X)v = \lambda (X^T D X) v$$

as

$$(Z^T \tilde X^T L \tilde X Z) v = \lambda (Z^T Z)v.$$

Now, put $u=Z v$, and premultiply both sides of the previous equation by $Z^{-T}$ to find

$$\tilde X^T L \tilde X u = \lambda u.$$

It is worth noting that, contrary to your last sentence, the $u$ and $v$ are not the same, but are related through the equation $u=Z v$. Thus, after solving the standard eigenvalue problem with $\tilde X^T L \tilde X$, linear systems will need to be solved with $Z$ in order to find the original eigenvectors.

It is also important to notice that the fact that $D$ is positive is crucial to the ability to orthonormalize $X$ with respect to $D$. Consider the case where $D=-I$. Then requiring that $\tilde X^T D \tilde X = I$ is equivalent to requiring that $\tilde X^T \tilde X = -I$, which is not possible for real $\tilde X$ (nor in the complex case, when we replace transposes with Hermitian-transposes). When $D$ is positive, we may define

$$Z = \sqrt{X^T D X},$$

which will exist because $X^T D X$ will be positive-definite.

• Thanks. Now it is clear why I do not want to point so publicly to mistakes of some works. – usero Oct 4 '12 at 18:05
• @usero No, it really is not "clear". If a paper is erroneous, it is much better if that is documented somewhere. If the paper is correct, it would greatly clarify the question. Successive paraphrasing of even simple statements has a tendency to change them, so even if you are happy with evaluating the paper based on Jack's answer here, it would still help the community if you included a citation. – Jed Brown Oct 4 '12 at 19:07
• @usero Jack's answer is great, but it would have been very simple to show that the claim is false by counterexample. (Simple exercise left to you.) Adding a citation would have greatly simplified his guess-work and editing of your post. – Stefano M Oct 4 '12 at 21:58
• The same answer, slightly different wording, is here math.stackexchange.com/a/206604/43193 Note that the same constraint on $D$ positive. – adam W Oct 21 '12 at 13:53