Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 40E (Numerical Analysis)

Since $S\mathbf{w}=c{\mathbf{e}}^{(1)}$ and $A\mathbf{w}={\lambda }_1\mathbf{w}$,Thus the first column of $\hat{A}$ is $({\lambda }_1,0,\dots ,0{)}^T$, and $\hat{A}$ is a block upper triangular matrix:where $B$ is its bottom-right $(n-1)\times (n-1)$ submatrix. ThereforeA similarity transformation preserves the characteristic polynomial, sowith algebraic multiplicities included.

To construct $S$, use a Householder transformation. With $\alpha =\Vert \mathbf{w}{\Vert }_2$, choose the sign of $\alpha$ to avoid cancellation and setThen $S$ is an orthogonal matrix and maps $\mathbf{w}$ to $\alpha {\mathbf{e}}^{(1)}$ up to the chosen sign. If $\mathbf{w}$ already lies on the first coordinate axis, take a suitable diagonal sign matrix. This is the one-vector case of orthogonal coordinate reduction of a subspace.

Let $W=\mathrm{span}\{\mathbf{v},\mathbf{w}\}=\mathrm{col}V$. Since the two columns are linearly independent, the leading $2\times 2$ block $R_1$ inis invertible. Hence $S(W)=\mathrm{span}\{{\mathbf{e}}^{(1)},{\mathbf{e}}^{(2)}\}$. The hypothesis that $W$ is an invariant subspace of $A$ implies that this coordinate plane is invariant under $\hat{A}=SA{S}^{-1}$. Consequently the first two columns of $\hat{A}$ have no entries below row two, andwhere $B$ is the top-left $2\times 2$ block and $D$ is the bottom-right $(n-2)\times (n-2)$ block. Eigenvalue deflation by an invariant subspace now givessoagain counting algebraic multiplicities.

For the required orthogonal reduction, take a thin QR decomposition $V=Q_1{R}_1$, extend the two orthonormal columns of $Q_1$ to an orthogonal matrix $Q$, and set $S=Q^T$. ThenEquivalently, apply one Householder transformation to annihilate entries $2,\dots ,n$ of $\mathbf{v}$, followed by a second Householder transformation acting only on coordinates $2,\dots ,n$ to annihilate entries $3,\dots ,n$ of the transformed $\mathbf{w}$.