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.

The first column already has zeros below the top entry. In the last three rows of the second column, reflect $w=(4,2,4{)}^T$ to $(-6,0,0{)}^T$ using $u=w+6e_1=(10,2,4{)}^T$. Since $u^{T}u=120$, the Householder reflection isWith $Q=\mathrm{diag}(1,H)$, direct multiplication givesThe transformed least-squares objective is $(x_1+2x_2-1{)}^2+(-6x_2+2/3{)}^2+50/9$. Its first two squares can both vanish, so the unique answer isUniqueness follows because the triangular leading block is invertible; this calculation implements Householder QR decomposition without squaring the condition number through normal equations.

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.

The linear least-squares problem is to minimize $\Vert Ax-b{\Vert }_2^2$ over $x\in {\mathbb{R}}^n$, allowing an overdetermined system to have a nonzero residual. For a full QR decomposition, $Q$ is $m\times m$ orthogonal and $R$ is $m\times n$ with an upper-triangular top block. Orthogonal transformations preserve the Euclidean norm, soIf $A$ has full column rank, the top triangular block is nonsingular; setting its residual to zero gives the unique minimizer, while the remaining residual is independent of $x$. Without full column rank, minimizers still exist but need not be unique.

For the specified matrix, one Householder reflection already produces an upper-triangular matrix. Take $v=(-1,1,1,1{)}^T$, the difference between the first column and $2e_1$, and setThe formula gives $H^T=H$, $H^2=I$. Direct multiplication yields the Householder QR decompositionAll subdiagonal entries in the remaining columns are already zero, so no further reflection is needed. For the supplied right-hand side, $Q^{T}b=(2,0,2,-2{)}^T$. Back substitution gives $x_3=1$, $x_2=-1$, $x_1=2$, henceThe residual $A{x}^{\ast }-b=(1,-1,-1,1{)}^T$ is orthogonal to every column of $A$, independently confirming the normal equations $A^T(A{x}^{\ast }-b)=0$.

Apply part (b) to the first column of $A$, using the identity if it is already the zero vector. This gives an orthogonal matrix $H_1$ for which $H_{1}A$ has zeros below its first diagonal entry. At stage $j$, apply a Householder transformation to rows $j,\dots ,n$ of column $j$, and extend it by the identity on the first $j-1$ coordinates. If that trailing column is zero, again use the identity. The transformation preserves zeros in earlier columns, since their trailing entries already vanish.

After at most $n-1$ stages,is an upper triangular matrix. Each $H_j$ is symmetric and orthogonal, so withwe have $Q^{T}Q=I$ andNo invertibility assumption was used, so the Householder QR decomposition also exists for singular matrices.