Connection between Krylov subspace and Arnoldi

Using the definition of the Krylov subspace, we form a matrix whose columns are the vectors in the Krylov subspace

$$K_k=[q_1,A{q}_1,A^2{q}_1,\dots ,A^{k-1}{q}_1]$$

We prove that $K_k=Q_k{R}_k$, where $Q_k$ is the orthogonal basis from Arnoldi. See also Key idea of iterative methods for eigenvalue computation.

To prove this, we show that $Q^T{K}_k$ is upper triangular. Consider

$$Q^T{A}^{j-1}{q}_1=Q^{T}Q{H}^{j-1}{Q}^T{q}_1=H^{j-1}{e}_1$$

We define matrix $R$ as:

$$[R_k{]}_{ij}=H^{j-1}(i,1)$$

We find that $H^{j-1}(i,1)=0$ for $j<i$. So matrix $R_k$ is upper triangular.

$Q_k$ is an orthogonal basis of the Krylov subspace $\mathcal{K}(A,q_1,k),$ and $Q_k{R}_k$ is the QR factorization of $K_k$.