Let $A \in \mathbb{R}^{n \times n}$ a matrix, and $r_0 \in \mathbb{R}^{n}$. Also, let $(\sigma)_i$ a sequence of complex scalars.
Consider the Krylov subspace $K_n(A,r_0)=\text{span} \{r_0,A r_0, \ldots, A^{n-1}r_0 \}$.
I want to show that $$K_n(A + \sigma_j I,r_0) = K_n(A+\sigma_i I,r_0)$$ i.e. the so-called "shift invariance of Krylov subspaces"
I consider $x \in K_n({A+\sigma_i I})$, therefore $$x= \sum_k^{n-1} \alpha_k (A+\sigma_i I)^k r_0$$
I search for scalars $\beta_k$ such that $$\sum_k^{n-1} \alpha_k (A+\sigma_i I)^k r_0 = \sum_k^{n-1} \beta_k (A+\sigma_j I)^k r_0$$
and therefore I obtain
$$\sum_k^{n-1} \Bigl( \alpha_k (A+\sigma_i I)^k – \beta_k (A+\sigma_j I)^k \Bigr) r_0$$
But now I don't know how to find $\beta_k$.
How can I move? Also other ways are really appreciated
Best Answer
It suffices to show that for any $\sigma$, we have $K(A + \sigma I, r_0) \subset K(A,r_0)$. To that end, we note by the binomial theorem that for any $0 \leq k\leq n-1$, we have $$ (A + \sigma I)^k = \sum_{j=0}^k \binom kj \sigma^{k-j}A^jr_0 \in \operatorname{span}\operatorname{span}\{A^k r_0 : 0 \leq k \leq n-1\} = K(A,r_0). $$ Since this holds for all $k$, conclude that $\operatorname{span}\{(A + \sigma I)^ k : 0 \leq k \leq n-1\} \subset K(A,r_0)$, which is what we wanted.
With that, note that $$ K(A + \sigma_j I,r_0) \supset K([A + \sigma_j I] + (\sigma_i - \sigma_j)I,r_0) = K(A + \sigma_i I,r_0). $$ By symmetry (i.e. by switching $i$ and $j$), we see that the reverse inclusion holds as well.