= Solution
A <QR decomposition> is a factorization $A=QR$ with $Q^TQ=I$ and $R$ upper triangular. An orthogonal transformation preserves the Euclidean <norm> because
$$
\boxed{\|Qx\|^2=x^TQ^TQx=x^Tx=\|x\|^2.}
$$
For the basic <QR algorithm>, start with $A_0=A$ and repeatedly form
$$
A_k=Q_kR_k,\qquad A_{k+1}=R_kQ_k.
$$
In a convergent diagonal form, the diagonal entries give the eigenvalues; practical symmetric-<matrix> implementations use shifts and deflation to obtain and isolate such convergence. The basic unshifted iteration alone need not converge diagonally for every symmetric input.
At every step, however,
$$
\boxed{A_{k+1}=R_kQ_k=Q_k^TA_kQ_k.}
$$
Thus each iterate is orthogonally similar to its predecessor. Similar matrices have the same <characteristic polynomial> and eigenvalues, including multiplicities, so induction proves that every iterate has exactly the original eigenvalues. <Orthogonal similarity> also preserves symmetry.
Back to article page
