Past exam of the Probability, statistics and options II course of the University of Oxford / 2008 / P / 4

A real square QR factorization is $A=QR$ with $Q^{\mathsf{T}}Q=I$ and $R$ upper triangular. For an invertible matrix it can be made unique by requiring positive diagonal entries of $R$.

If $A$ is orthogonal, then $R=Q^{\mathsf{T}}A$ is orthogonal as well. An orthogonal upper triangular matrix is diagonal with entries $\pm 1$: its first column has just its first entry, which must have modulus one, and orthogonality then zeros the rest of the first row; repeat inductively on the lower block. Thusand under the positive-diagonal convention $\boxed{R=I}$, $Q=A$.

The first column is five times $(4,0,3,0{)}^{\mathsf{T}}/5$. Its orthogonal companion in the first-and-third-coordinate plane is $(3,0,-4,0{)}^{\mathsf{T}}/5$, and the second column has positive residual seven times that vector. The remaining coordinate directions can therefore be read off immediately rather than performing a general four-dimensional orthogonalization. One obtainsThe columns of $Q$ are visibly orthonormal. Taking their inner products with each column of the given matrix gives the displayed $R$, which also verifies $QR=A$ and positive diagonal entries.

At step $k$, choose a real shift ${\mu }_k$, factor $A_k-{\mu }_{k}I=Q_k{R}_k$, and setThe last equality proves orthogonal similarity at every step. Thus all iterates have the same eigenvalues; if $A_k$ is symmetric, the last expression is symmetric, proving symmetry by induction.

For the specified matrix, let $e=(1,\dots ,1{)}^{\mathsf{T}}$. Then $A=I-2e{e}^{\mathsf{T}}/n$ and $e^{\mathsf{T}}e=n$, so $A^{\mathsf{T}}=A$ and $A^2=I$. It is a Householder reflection, hence orthogonal. With the standard positive-diagonal QR convention, part (a) gives $Q=A$, $R=I$ at the first unshifted step, and therefore $A_1=RQ=A$. The same repeats forever: the unshifted algorithm is stationary.

If arbitrary diagonal signs in QR are allowed, $R=D$, $Q=AD$ for a sign matrix $D$, and the next iterate is $DAD$. Its off-diagonal magnitudes are unchanged, so even then only sign changes occur, not progress toward a diagonal form. This explains the role of the usual convention in the literal stationary-iterate statement.