Codex @codex  0

Alternating right and left Householder transformations reduce a real square matrix to a bidiagonal matrix. For a lower-bidiagonal result, first clear row $j$ beyond column $j$ using a right transformation on trailing columns. Then clear column $j$ below row $j+1$ using a left transformation on trailing rows. Previously completed rows and columns are preserved. Since $B^{T}B=Q^T{A}^{T}AQ$ is a symmetric tridiagonal matrix, its eigenvalues are the squares of the singular values of $A$. This explains the reduction structurally; explicitly forming $A^{T}A$ is unnecessary and can worsen numerical conditioning.

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.

An LQ decomposition factors a real $m\times n$ matrix into a lower trapezoidal $m\times n$ matrix $L$ and an orthogonal $n\times n$ matrix $Q$. Transposing a QR decomposition of $A^T$ proves existence. Equivalently, right Householder transformations clear the part of each row beyond its diagonal while preserving earlier zeros. This factorization is useful for underdetermined systems, complementing the role of QR decomposition in overdetermined systems.

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.

An orthogonal matrix similarity changes coordinates by an orthogonal matrix. It preserves eigenvalues, singular values and Euclidean geometry; it also preserves symmetry when applied to a symmetric matrix. A sequence of Householder transformations can use this freedom to produce a Hessenberg reduction, while a symmetric matrix can be reduced further to tridiagonal form.

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.

A generic lower triangular matrix has a dense first column. The first left Householder transformation in its QR decomposition mixes those rows, usually creating entries throughout the rows to the right. Subsequent eliminations impose upper triangularity but no further systematic zeros; thus $R$ is generically a full upper triangular matrix.

For Householder bidiagonalization use two-sided operations instead. At stage $j$, a right Householder transformation acting on columns $j,\dots ,n$ clears the current row $j$ beyond its diagonal. Then a left Householder transformation acting on rows $j+1,\dots ,n$ clears column $j$ below its first subdiagonal. The left operation leaves row $j$ unchanged; both operations preserve the already completed lower-bidiagonal rows and columns. Continue for $j=1,\dots ,n-1$, omitting a final unnecessary left operation. The result isIt follows that $B^{T}B=Q^T{A}^{T}AQ$. Hence the two symmetric matrices are orthogonally similar and have the same eigenvalues. By part (c), compute the eigenvalues of the symmetric tridiagonal matrix $B^{T}B$ and take their nonnegative square roots to obtain all singular values of $A$.

For $w\ne 0$, the Householder transformation isLet $P=w{w}^T/(w^{T}w)$. Then $P^T=P$ and $P^2=P$, since $P$ is the orthogonal projection matrix onto the span of $w$. Hence $H^T=H$ andThus $H$ is a symmetric matrix and an orthogonal matrix. Geometrically it reverses the component parallel to $w$ and fixes the perpendicular hyperplane.

Let $r=\Vert u{\Vert }_2>0$, and choose $s=1$ if $u_1\ge 0$ and $s=-1$ otherwise. SetThis vector is nonzero, because $w_1$ has magnitude $|u_1|+r$. Direct computation givesso the Householder transformation satisfiesThe first entry is nonzero and every other entry is zero. The sign choice also avoids cancellation when forming the first entry of $w$, which is useful in numerical computation.

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.

Multiply $Ax=b$ by $Q^T$ to get the equivalent triangular systemFor nonsingular $A$, compute $c=Q^{T}b$ and use back substitution:Orthogonal transformations preserve the Euclidean norm, making this a numerically stable reduction. The factors can be applied as stored Householder transformations without explicitly forming $Q$.

Since $Q$ is invertible, $A$ is singular exactly when $R$ is singular. For an upper triangular matrix,Thus a singular $A$ forces at least one zero diagonal entry in $R$. In that case, ordinary division-based back substitution must be replaced by a consistency/rank analysis: the system may have no solution or infinitely many solutions, and a rank-revealing factorization can identify the free parameters.

For nonzero $w$, the Householder transformation isThe rank-one matrix $P=w{w}^T/(w^{T}w)$ is symmetric and satisfies $P^2=P$. Consequently $H^T=H$ and $H^{T}H=(I-2P{)}^2=I-4P+4P^2=I$. Thus the matrix is symmetric and orthogonal; geometrically it reflects the component along $w$ and fixes its perpendicular hyperplane.