How to find eigenvectors in a subspace Let's say I have a matrix $A\in M^n(\mathbb{C})$. I would like to find the eigenvectors of $A$ that live in a certain $k$-dimensional subspace, $k<n$, if such eigenvectors exist.
Question: Is there some algorithm or algebraic method that will produce these eigenvectors when they exist, and give some failure signal when they don't exist?
I would like something better the obvious method, which is "project A into the subspace, find the eigenvectors of the projected A, and then check if these are eigenvectors of the original A." This method does produce the eigenvectors when they exist, but also produces a lot of extraneous eigenvectors without giving a "failure signal" beyond just double checking every eigenvector.
 A: Choose a basis $b_1,\dots, b_k$ in the given subspace, then form 
$$A':=[Ab_1|\dots | Ab_k], \quad B:=[b_1|\dots|b_k]$$
both $k\times n$ matrices, and you basically have to find the kernel of $A'-\lambda B$ to get (the $b_j$-coordinates of) the eigenvectors for eigenvalue $\lambda$. 
A: Let $B$ denote a matrix spanning the given $k$-dimensional space. We are going to find matrices $X$, $R$, such that $X$ is nonempty matrix with full column rank and
$$(A B)X = BXR \tag{1}$$
Then $BX$ spans an invariant subspace of $A$ and a subspace of $B$. Having invariant subspace $BX$ we can easily find required eigenvectors.
Let $N$ be any matrix, which spans the space $\ker (\left[AB, B\right])$. The matrix $N$ has size $2k\times l$, where $l\leq k$, since $B$ has full column rank.
Observe, that $\left[\begin{array}{c}X \\XR\end{array}\right] = NY$ for some nonempty matrix $Y$ with full column rank. Therefore necessary condition for existing $X$ and $R$ with required properties is $\ker (\left[AB, B\right]) \ne \emptyset$.
Let $N = \left[\begin{array}{c}N_1 \\N_2\end{array}\right]$, where $N_1$ and  $N_2$ have the same number of rows. We have $X = N_1 Y$, $XR = N_2 Y$ for some matrice $Y$, $R$. Hence 
$$N_2Y = N_1YR \tag{2}$$
If $N_1$ is invertible, then we can take $Y = I$ and $X = N_1$, $R = N_1^{-1}N_2$. If $N_1$ is square, but rank deficient, then $Y$ and $R$ can be found using the generalized Schur decomposition of the matrix pair $(N_1, N_2)$. In this case $B$ contains at least one eigenvector of $A$ associated with zero eigenvalue.
Suppose, that $N_1$ is not square ($l < k$). Observe, that (2) is the same problem as (1) and we can repeat this procedure. That is if $\ker (\left[N_1, N_2\right]) = \emptyset$, then solution does not exist, otherwise we are looking for a matrix Z, such that $\left[\begin{array}{c}Y \\YR\end{array}\right] = MZ$, where $M$ is any matrix, which spans the space $\ker (\left[N_1, N_2\right])$. The matrix $M$ has size $2l\times m$, where $m\leq l$, since $N$ has full column rank. Therefore this iterative procedure terminates.
