Related Eigenproblems

1. Consider the GNHEP $Ax = \lambda Bx$, where $A$ and $B$ are square and $B$ is nonsingular. The matrix $B^{-1}A$ has the same eigenvalues and right eigenvectors as $Ax - \lambda Bx$. If $y$ is a left eigenvector, i.e., $y^*A = \lambda y^*B$, $B^*y$ is a left eigenvector of $B^{-1}A$. Analogous statements are true about $AB^{-1}$. If $B = B_L B_R$ is a factorization of $B$ (from Gaussian elimination, QR decomposition, or anything else), $B_L^{-1} A B_R^{-1}$ has the same eigenvalues as $A$, right eigenvector $B_R x$, and left eigenvector $B_L^*y$. If $B$ is well-conditioned, or $AB^{-1}$, $B^{-1}A$, or $B_L^{-1} A B_R^{-1}$ can be accurately computed, this is an effective way to solve $Ax = \lambda Bx$. If $B$ is ill-conditioned, it is preferable to treat it as the GNHEP, see §2.6.

2. Let $p( \lambda ) = \lambda^n - \sum_{i=0}^{n-1} a_i \lambda^i$ be a monic polynomial. Define the $n$ by $n$ companion matrix of $p(\lambda)$ as
   
   $$C = \bmat{ccccc} 0 & 1 & & & \\ & \ddots & \ddots & & \\ ... ... & & 0 & 1 \\ a_0 & a_1 & \cdots & a_{n-2} & a_{n-1} \emat,$$
   
   
   where all entries not explicitly shown are 0. Then the eigenvalues of $C$ are the roots $\lambda_i$ of $p(\lambda)=0$, and the right eigenvectors are $x_i = [ 1, \lambda_i , \ldots , \lambda_i^{n-1}]^T$. $C$ is not diagonalizable if $p(\lambda)$ has multiple roots. A reliable, but not optimally efficient, algorithm for finding roots of a polynomial $p(\lambda)$ is to find all the eigenvalues of $C$.

3. Let $p( \lambda ) = \lambda^n - \sum_{i=0}^{n-1} A_i \lambda^i$ be a monic matrix polynomial, where each $A_i$ is an $m$ by $m$ matrix. An eigenpair $(\lambda_i, x_i)$ of $p(\lambda)$ satisfies $p(\lambda_i)x_i = 0$. Define the $nm$ by $nm$ block companion matrix of $p(\lambda)$ as
   
   $$C = \bmat{ccccc} 0 & I & & & \\ & \ddots & \ddots & & \\ ... ...& & & 0 & I \\ A_0 & A_1 & \cdots & A_{n-2} & A_{n-1} \emat,$$
   
   
   where all entries are $m$ by $m$ blocks and all entries not explicitly shown are 0. Then the eigenvalues $\lambda_i$ of $C$ are the eigenvalues of $p(\lambda_i)$. Note that there are $mn$ eigenvalues. If $(\lambda_i, x_i)$ is an eigenpair of $p(\lambda)$, then $[ x_i^T, \lambda_i x_i^T , \ldots , \lambda_i^{n-1} x_i^T]^T$ is a right eigenvector of $C$ [194].