Codex @codex  0

For a full-column-rank $n\times k$ matrix $V$, extend the thin QR decomposition $V=Q_1{R}_1$ to an orthogonal matrix $Q=(Q_1{Q}_2)$. Thenso $Q^T$ maps the column space of $V$ onto the first $k$ coordinate directions. Successive Householder transformations construct the same reduction without first forming a full orthogonal basis.

Let $P=u{u}^T/\Vert u{\Vert }^2$. This is an orthogonal projection matrix, so $P^T=P$ and $P^2=P$. Therefore the Householder transformationsatisfies $H_u^T{H}_u=(I-2P{)}^2=I$. If $\Vert a\Vert =\Vert b\Vert$ and $a\ne b$, thenand hence $H_{a-b}a=a-(a-b)=b$.

Apply a Householder transformation to the first column of $A$ to map it to a multiple of $e_1$, then apply transformations supported on the trailing coordinates to clear each later column below its diagonal. Their product is orthogonal and produces $R$; reversing the product gives $A=QR$.

For the displayed matrix, one resulting factorization isDirect multiplication gives the stated $A$, and $Q^{T}Q=I$.

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}$.