Generalized eigenvalue problem

The generalized eigenvalue problem of two symmetric matrices ${\bf A}={\bf A}^T$ and ${\bf B}={\bf B}^T$ is to find a scalar $\lambda$ and the corresponding vector ${\bf\phi}$ for the following equation to hold:

$${\bf A}{\bf\phi}_i=\lambda_i{\bf B}{\bf\phi}_i, \;\;\;\;\;\;\;(i=1,\cdots,n)$$

or in matrix form

$${\bf A}{\bf\Phi}={\bf B}{\bf\Phi}{\bf\Lambda}$$

The eigenvalue and eigenvector matrices ${\bf\Lambda}$ and ${\bf\Phi}$ can be found in the following steps.

• Solve the eigenvalue problem of ${\bf B}$ to find its diagonal eigenvalue matrix ${\bf\Lambda}_B$ and orthogonal eigenvector matrix ${\bf\Phi}_B=({\bf\Phi}_B^T)^{-1}$ so that
  
  $${\bf B}{\bf\Phi}_B={\bf\Phi}_B{\bf\Lambda}_B, \;\;\;\;\;\;... ...}{\bf\Phi}_B={\bf\Phi}_B^T{\bf B}{\bf\Phi}_B ={\bf\Lambda}_B$$
  
  

• Left and right multiplying both sides of the second equation above by ${\bf\Lambda}^{-1/2}$ (whitening) we get
  
  $${\bf\Lambda}^{-1/2}_B ({\bf\Phi}_B^T{\bf B}{\bf\Phi}_B) {\b... ...f\Lambda}^{-1/2}_B{\bf\Lambda}_B{\bf\Lambda}^{-1/2}_B={\bf I}$$
  
  
  We define
  
  $${\bf\Phi}'_B={\bf\Phi}_B{\bf\Lambda}^{-1/2}_B$$
  
  
  and get
  
  $$({\bf\Phi}'_B)^T{\bf B}{\bf\Phi}'_B={\bf I}$$
  
  
  Note that ${\bf\Phi}_B'$ is not orthogonal
  
  $$({\bf\Phi}')^{-1}_B=({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B)^{-1}... ...hi}^T_B \ne {\bf\Lambda}^{-1/2}_B{\bf\Phi}^T_B={\bf\Phi}^T_B$$
  
  

• Apply the same transform to ${\bf A}$:
  
  $$({\bf\Phi}'_B)^T{\bf A}{\bf\Phi}'_B =({\bf\Lambda}^{-1/2}_... ...Phi}_B^T){\bf A}({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B) ={\bf A}'$$
  
  
  Note that ${\bf A}'$ is symmetric as well as ${\bf A}$:
  
  $${\bf A}'^T=({\bf\Phi}'_B^T{\bf A}{\bf\Phi}'_B)^T ={\bf\Phi}'_B^T{\bf A}{\bf\Phi}'_B={\bf A}'$$
  
  

• Diagonalize ${\bf A}'$

  As ${\bf A}'$ is symmetric,, it can be diagonalized by its orthogonal eigenvector matrix ${\bf\Phi}_A$:
  

  $${\bf\Phi}_A^T{\bf A}'{\bf\Phi}_A={\bf\Lambda}$$
  
  
  i.e.,
  

  $${\bf\Phi}_A^T ({\bf\Lambda}^{-1/2}_B{\bf\Phi}_B^T{\bf A}{\bf\Phi}_B{\bf\Lambda}^{-1/2}_B) {\bf\Phi}_A = ({\bf\Phi}_A^T {\bf\Lambda}^{-1/2}_B{\bf\Phi}_B^T){\bf A}( {\bf\Phi}_B{\bf\Lambda}^{-1/2}_B {\bf\Phi}_A)$$

  $$= {\bf\Phi}^T {\bf A}{\bf\Phi} ={\bf\Lambda}$$

  
  
  where we have defined
  
  $${\bf\Phi}={\bf\Phi}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A$$
  
  
  which is not orthogonal:
  
  $${\bf\Phi}^{-1}=({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A... ...e {\bf\Phi}_A^T{\bf\Lambda}^{-1/2}_B{\bf\Phi}_B^T={\bf\Phi}^T$$
  
  

• This ${\bf\Phi}$ also diagonalizes ${\bf B}$:
  

  $${\bf\Phi}^T{\bf B}{\bf\Phi} = ({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A)^T {\bf B}({\bf\Phi... ...da}^{-1/2}_B ({\bf\Phi}_B^T{\bf B}{\bf\Phi}_B){\bf\Lambda}^{-1/2}_B{\bf\Phi}_A$$

  $$= {\bf\Phi}_A^T{\bf\Lambda}^{-1/2}_B{\bf\Lambda}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A ={\bf\Phi}_A^T{\bf\Phi}_A={\bf I}$$

  
  

• Now we have
  
  $$\left\{ \begin{array}{l} {\bf\Phi}^T{\bf A}{\bf\Phi}={\bf\Lambda}\\ {\bf\Phi}^T{\bf B}{\bf\Phi}={\bf I}\end{array}\right.$$
  
  
  Right multiplying both sides of the second equation by ${\bf\Lambda}$ and equating the left-hand side to that of the first equation, we get
  
  $${\bf A}{\bf\Phi}={\bf B}{\bf\Phi}{\bf\Lambda}$$
  
  
  i.e., ${\bf\Lambda}$ and ${\bf\Phi}$ are the eigenvalue and eigenvector matrices of the generalized eigenvalue problem. Note, however, as shown above, ${\bf\Phi}$ is not orthogonal.

The Rayleigh quotient of two symmetric matrices ${\bf A}$ and ${\bf B}$ is a function of a vector ${\bf w}$ defined as:

$$R({\bf w})=\frac{{\bf w}^T{\bf A}{\bf w}}{{\bf w}^T{\bf B}{\bf w}}$$

To find the optimal ${\bf w}$ corresponding to the extremum (maximum or minimum) of $R({\bf w})$, we find its derivative with respect to ${\bf w}$:

$$\frac{d}{d{\bf w}}R({\bf w}) =\frac{2{\bf A}{\bf w}({\bf w}^... ...\bf w}({\bf w}^T{\bf A}{\bf w})} {({\bf w}^T{\bf B}{\bf w})^2}$$

Setting it to zero we get

$${\bf A}{\bf w}({\bf w}^T{\bf B}{\bf w})={\bf B}{\bf w}({\bf... ...bf B}{\bf w} =R({\bf w}){\bf B}{\bf w}=\lambda {\bf B}{\bf w}$$

The second equation can be recognized as a generalized eigenvalue problem with $\lambda=R({\bf w})$ being the eigenvalue and and ${\bf w}$ the corresponding eigenvector. Solving this we get the vector ${\bf w}={\bf\phi}$ corresponding to the maximum/minimum eigenvalue $\lambda=R({\bf w})$, which maximizes/minimizes the Rayleigh quotient.