Eigenvalue Deflation

Eigenvalue Deflation

Power iteration finds only the dominant eigenvalue. Deflation lets you find all eigenvalues one by one.

Idea

After finding $(\lambda_1, \mathbf{v}_1)$, subtract its contribution from $A$:

$A' = A - \lambda_1 \mathbf{v}_1 \mathbf{v}_1^T$

For symmetric $A$, $A'$ has the same eigenvectors as $A$ but eigenvalue $\lambda_1$ becomes 0. Applying power iteration to $A'$ now converges to $\lambda_2$.

Why This Works

If $\mathbf{u}$ is an eigenvector of $A$ with eigenvalue $\lambda \neq \lambda_1$:

$A'\mathbf{u} = A\mathbf{u} - \lambda_1 (\mathbf{v}_1 \cdot \mathbf{u})\mathbf{v}_1 = \lambda\mathbf{u} - 0 = \lambda\mathbf{u}$

(Since eigenvectors of a symmetric matrix are orthogonal: $\mathbf{v}_1 \cdot \mathbf{u} = 0$.)

Example

$A = \begin{pmatrix} 6 & 2 \\ 2 & 3 \end{pmatrix}, \quad \text{eigenvalues: } 7, 2$

After deflation by $\lambda_1 = 7$, $\mathbf{v}_1 = [0.8944,\ 0.4472]$:

$A' = \begin{pmatrix} 0.4 & -0.8 \\ -0.8 & 1.6 \end{pmatrix} \quad \Rightarrow \quad \text{dominant eigenvalue} = 2$

Your Task

Implement deflate(A, lam, v) that removes the $(\lambda, \mathbf{v})$ component from $A$, then use it with power iteration to extract the second eigenvalue.