QR algorithm for finding eigenvalues and eigenvectors of a matrix

Let $A$ be symmetric and diagonalizable, and let $\{\lambda_1, \cdots, \lambda_n\}$ be its spectrum. A consequence of the Spectral Theorem assures that $\exists Q$ orthogonal s.t.

$\begin{pmatrix} \lambda_1 & 0 &\cdots & 0\\ 0 & \lambda_2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & \lambda_n \end{pmatrix} = D = Q^{-1} A Q = Q^T A Q.$

I want to apply the QR algorithm for finding the spectrum of A and an orthonormal basis of A, such that the matrix is orthogonal.
$A^{(0)}=A$
FOR $k = 1,2,...$
1) get the factorization $A^{(k-1)}= Q^{(k)}R^{(k)}$
2) $A^{(k)} = R^{(k)}Q^{(k)}$
3) $\overline{Q}^{(k)} = Q^{(1)}\cdot ...\cdot Q^{(k)}$

I've read several notes and books and now I am quite confused. In some it is assumed that all eigenvalues are distinct, in others only symmetry is assumed.
It is easy to see that all $A^{(k)}$ are similar, and therefore they have the same eigenvalues, but in some notes they say that $A^{(k)}$ converges to a diagonal matrix as $k \rightarrow \infty$, in others $A^{(k)}$ converges to a triangolar matrix. I couldn't find a formal proof to this in any case though.
Last but not least, in all notes it is said that the matrix $\overline{Q}^{(k)}$ converges to a basis of eigenvectors of $A$ and that it is orthogonal, but is this holding also without assuming that all eigenvalues are distinct? And where may I find a formal proof to all this?
Ayone who could help me in making it all clear and give me some good references?

• QR only has $n-1$ steps, where did you see $k\to \infty$?
– tibL
Sep 20, 2016 at 11:20
• @tibL The terminology is a bit confusing; there is a standard eigenvalue routine for symmetric matrices called the QR algorithm. It is called that because it can be implemented by QR decomposing $A_k$ as $Q_k R_k$ and then setting $A_{k+1}=R_k Q_k$ and iterating from there.
– Ian
Sep 20, 2016 at 11:23
• @7iat Why not test some of these questions? It is easy enough to construct a nondiagonal symmetric matrix with non-distinct eigenvalues. See what the QR algorithm does in this case.
– Ian
Sep 20, 2016 at 11:24
– tibL
Sep 20, 2016 at 11:25
• @7iat More specifically, you could try something like: r=randn(n,1); lam=[r;r]; D=diag(lam); Qproto=randn(2*n,2*n); [Q,~]=qr(Qproto); A=Q*D*Q'. Then run the QR algorithm on Q. See what happens.
– Ian
Sep 20, 2016 at 11:36

• $A^{(k)}$ converges to a triangular matrix: this is the result for general matrices. For symmetric matrices $A^{(k)}$ stays symmetric for all $k$, so that "triangular" translates to "diagonal".
• $\bar Q^{(k)}$ converges to a basis of eigenvectors of $A$: This is only true for diagonal matrices. For normal matrices, the complex eigenvalues result in $2×2$ diagonal blocks and the corresponding columns of the cumulative $\bar Q$ are real and imaginary parts of the pair of conjugate eigenvectors. In general where $A^{(k)}$ is increasingly triangular, the $\bar Q$ columns form a basis for an increasing sequence of invariant subspaces.