# Connection between power iterations and QR Algorithm

I am seeking an intuitive understanding of why the QR Algorithm solves the symmetric eigenvalue problem. In class, and also in Golub and Van Loan, it has been suggested that there is somehow deep connection between the power method for finding the largest eigenvector. In fact, the power method can be generalized to "Orthogonal Iterations," where you repeatedly apply the matrix to an n-by-r random matrix (instead of just one random vector), and then orthogonalize at each step, which gives the top-r eigenvectors of the matrix (from which the eigenvalues can be calculated).

The QR Algorithm (with or without shifts) also gives the eigenvalues of the matrix by first making it tridiagonal, and then applying Givens rotations on both sides so that it is diagonal, and the eigenvalues are on the diagonal. Is there a connection between these two techniques? Perhaps these orthogonal Givens rotations are somehow analogous to the random matrix in the "orthogonal iterations" above?

Keeping the discussion simple, let $A\in\mathbb{C}^{n\times n}$ be a regular complex square matrix with eigenvalues having pairwise distinct absolute values.
The QR algorithm without shift is defined by the iteration \begin{align*} &\text{Start}&A_1 &:= A\\ &\text{QR-decomposition}& Q_i R_i &:= A_i &&@i=1,\ldots\\ &\text{rearranged new iterate}&A_{i+1} &:= R_i Q_i \end{align*} Representing $R_i$ as $R_i = Q_i^H A_i$ and substituting this into the formula for $A_{i+1}$ gives $A_{i+1} = Q_i^H A_i Q_i$. Thus, the matrix $A_{i+1}$ is similar to $A_i$ and has the same eigenvalues. Defining the combined orthogonal transformation $\bar Q_i := Q_1\cdot\ldots\cdot Q_i$ for $i=1,\ldots$ we obtain \begin{align*} A_{i+1} &= \bar Q_i^H A \bar Q_i&&@ i=1,\ldots \end{align*} or $A_i = \bar Q^H_{i-1} A \bar Q_i$ for $i=2,\ldots$. We substitute $A_i$ in the above QR-decomposition with this formula and obtain \begin{align*} Q_i R_i &= A_i = \bar Q_{i-1}^H A \bar Q_{i-1}\\ \bar Q_i R_i &= A \bar Q_{i-1} \end{align*} Taking the first column on both sides of the last equation one gets \begin{align*} \bar Q_i(:,1)\cdot R_i(1,1) = A\cdot \bar Q_{i-1}(:,1) \end{align*} (with Octave notation of the matrix elements) which shows that $R_i(1,1)$ and $\bar Q_i(:,1)$ are just the approximations for the eigenvalue and the eigenvector, respectively, in the power-iteration for the matrix $A$. The elements $R_i(1,1)$ with $i=1,\ldots$ converge to largest of the eigenvalues whose eigenvectors belong to the invariant subspace of $A$ spanned by the vectors $A^k Q_1(:,1)$ with $k=0,\ldots,n-1$.
Analogously to the above procedure we use the formula for the rearranged new iterate of the QR-algorithm to get \begin{align*} \bar Q_i^H A \bar Q_i &= A_{i+1} = R_i Q_i\\ \bar Q_i^H A &= R_i \bar Q_{i-1}^H \end{align*} The last row of the last equation results to \begin{align*} \bar Q_i^H(n,:) \cdot A &= R_i(n,n)\cdot \bar Q^H_{i-1}(n,:). \end{align*} Theoretically, one can calculate the sequences $\bar Q_i^H(n,:)$ and $R_i(n,n)$ for $i=2,\ldots$ from $\bar Q_1^H(n,:)=Q_1^H(n,:)$ by the inverse power iteration \begin{align*} &\text{Solve}& x\cdot A &= \bar Q_{i-1}^H(n,:)&&\text{for }x\in\mathbb{C}^{1,n}\\ &\text{Normalize} & \bar Q_i^H(n,:) &:= \frac{x}{|x|}\\ &\text{Set}& R_i(n,n) &:= |x| \end{align*} where $R_i(n,n)$ are the approximations for the smallest of the eigenvalues of $A$ with corresponding left-eigenvector in the subspace spanned by the vectors $Q_1^H(n,:)\cdot A^k$ with $k=0,\ldots,n-1$.