How to compute eigenvalues and eigenvectors recursively

73 Views Asked by At

I would like to write an algorithm (albeit inefficient) using the following algorithm.

I don't know whether this algorithm already has a name. If so what is the name of the algorithm, or a link to it?

Algorithm:

  1. Given an $n\times n$ matrix $A_n$ find (if possible) one eigenvalue/eigenvector pair $(\lambda_n, b_n)$.
  2. Produce a smaller matrix, $A_{n-1}$, of dimension $(n-1) \times (n-1)$ whose eigenvalues are the other eigenvalues of $A_n$.
  3. With a recursive call, find the eigenvalues and eigenvectors of $A_{n-1}$.
  4. Convert the $(n-1)$ dimensional eigenvectors of $A_{n-1}$ back to $n$-dimensional eigenvectors of $A_n$.

Questions:

  1. Given $A_n$, $\lambda_n$, and $b_n$, how can I produce $A_{n-1}$ (of size $(n-1)\times(n-1)$) whose eigenvalues are the other eigenvalues of $A_n$.
  2. Given a set of eigenvalue/eigenvector pairs of $A_{n-1}$, how can I produce the remaining eigenvectors of $A_n$.

Vague unknowns:

It seems to me that such an algorithm is possible and straightforward. I need to somehow perform a change of coordinates so that $b_n$ is translated to $[1, 0, \ldots, 0]$, and $A_n$ is converted to a matrix with $0$s in the first row (?and first column?) and a $1$ in the upper-left. Then take the sub-matrix simply removing the first row and column of $A_n$. After I get the eigenvectors of $A_{n-1}$, I need to change the coordinates back to the original coordinate system, I.e., convert $[1, 0, \ldots, 0]$ back to $b_n$.

But I don't know if this will work, how to change the coordinates, whether the submatrix will have the same eigenvalues, or whether I will need to somehow scale them by the change-of-cordinate matrix.