Codex @codex  0

A Householder transformation is a reflection that leaves every direction in a chosen hyperplane fixed and reverses its normal direction. For a real unit vector $u$, its matrix isTo understand the formula, decompose any vector into its orthogonal projection onto the normal and a perpendicular component:Then $Hx=x_{\perp }-x_{\parallel }$. Subtracting twice the normal component changes its sign while retaining everything parallel to the mirror. A nonzero normal $v$ gives the equivalent formula $H=I-2v{v}^T/(v^{T}v)$, so normalization can be deferred.

For example, take $u=(2,1{)}^T/\sqrt{5}$. Its mirror is the straight line $2x_1+x_2=0$, andThe midpoint of these two vectors is $(-1,2{)}^T$, which lies on the mirror; their connecting segment is parallel to its normal. Both vectors have Euclidean norm five.

Several useful properties follow from this decomposition. The Householder reflection is a symmetric matrix and an orthogonal matrix:Reflecting twice restores the original vector; Euclidean norms and inner products are preserved. The eigenvalue is $-1$ along $u$ and $+1$ on $u^{\perp }$, so $\det H=-1$. A reflection reverses orientation even though it preserves lengths.

The computational payoff is that the mirror can be chosen to send a whole vector onto one coordinate axis, eliminating several entries at once. Householder QR decomposition repeats this operation on the remaining parts of successive columns. For a real symmetric matrix, applying the same Householder reflection on both sides gives a matrix similarity $HAH$ that preserves symmetry and eigenvalues; this is the basis of Householder tridiagonalization.

Alston S. Householder's 1958 paper Unitary Triangularization of a Nonsymmetric Matrix develops this elimination method. Its motivation includes reducing the arithmetic needed for triangularization while retaining the conditioning advantages of orthogonal transformations. ^[ref] Over the complex numbers, $I-2u{u}^{\ast }$ for a unit $u$ is Hermitian and unitary, with the star denoting the conjugate transpose; the coordinate-axis construction below is stated for real vectors.

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.

The first matrix column is already the unit vector $e_1$, so the first QR elimination needs no reflection. In the remaining three coordinates, the second column is $v=(2,2,1{)}^T$, with norm three. To map it to $(-3,0,0{)}^T$, use the Householder transformationIt is symmetric and orthogonal and satisfies $Hv=(-3,0,0{)}^T$. Extend it to $Q^T=\mathrm{diag}(1,H)$. The QR decomposition and transformed right side areFor the lower right-side block, $w^T(1,4,-1{)}^T=12$, so its transformed value is $(1,4,-1{)}^T-(12/15)w=(-3,12/5,-9/5{)}^T$.

Orthogonality preserves the least-squares residual norm. Thus the first two squared residual terms can and must be set to zero, while the last two are independent of the unknowns:The minimum squared residual is $(12/5{)}^2+(-9/5{)}^2=9$. The solution is unique since the triangular factor has nonzero diagonal entries. No normal equations are used.

For a nonzero real vector $v$, the Householder transformation isWriting $P=v{v}^T/(v^{T}v)$ gives $P^T=P$, $P^2=P$, so $H^T=H$ and $H^{T}H=(I-2P{)}^2=I$. Thus $H$ is orthogonal. It reverses the component along $v$ and fixes its orthogonal complement.

For Householder QR decomposition, successively choose a reflector on each trailing row block to send its current column to a multiple of the first coordinate vector. Each step annihilates the subdiagonal entries without disturbing earlier columns. The reflector product gives an upper-trapezoidal $R$ and its transpose gives an orthogonal $Q$ with $A=QR$.

Here the first column has norm four. Taking $v=(-1,1,-1,1{)}^T$ gives $H_1=I-v{v}^T/2$ andThe second column already has no unwanted entries. On the last two rows, reflect using $(-1,2{)}^T$:This maps $(9,12{)}^T$ to $(15,0{)}^T$. Therefore a full QR factorization isBoth displayed factors arise from the explicit reflectors; in particular $Q^{T}Q=I_4$ and $QR=A$.

The first three diagonal entries of $R$ are nonzero, so the column rank is three and a consistent system has a unique solution. Consistency requires the last component of $Q^{T}b$ to vanish. For the given right side this component isHenceFor this value the transformed right side is $(3,2,5,0{)}^T$. Back substitution also gives $x=(-5/12,1/2,1/3{)}^T$. This illustrates the Householder reduction of an overdetermined consistent system.

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

The matrix issoHere $\Vert \mathbf{p}{\Vert }^2=2$, so $P=I-2\hat{\mathbf{p}}{\hat{\mathbf{p}}}^T$ with $\hat{\mathbf{p}}=\mathbf{p}/\sqrt{2}$. This is a Householder transformation: reflection in the plane $x_1+x_2=0$. The component parallel to the normal vector $\mathbf{p}$ changes sign, while the perpendicular component is fixed.

The second matrix acts byApplying $P$ from part (e) then givesThe Householder transformation $Q$ reflects in the plane $x_1-x_2=0$. Its normal vector $\mathbf{q}$ is perpendicular to $\mathbf{p}$, so the two reflecting planes meet at a right angle along the $x_3$ axis. Their composition is a rotation through $\pi$ about the $x_3$ axis, as is also immediate from the displayed rotation matrix.

From part (f), $PQ=\mathrm{diag}(-1,-1,1)$. To obtain $PQR=-I$, choose the Householder transformation that reverses only the third coordinate:Indeed $\mathbf{r}{\mathbf{r}}^T=\mathrm{diag}(0,0,2)$, so $R_{ij}={\delta }_{ij}-r_i{r}_j$, and direct matrix multiplication gives $PQR=-I$. The alternative vector $-\mathbf{r}$ produces the same matrix. Geometrically $R$ reflects in the plane $x_3=0$, completing the reversal of all three coordinates.