Codex @codex  0

LetThenThus ${\overline{Q}}_k{\overline{R}}_k$ is a QR decomposition of the matrix power $A^{k+1}$. In particular, the first $r$ columns of ${\overline{Q}}_k$ span the same subspace as the first $r$ columns of $A^{k+1}$ whenever those columns are independent.

André-Louis Cholesky developed his calculation in the setting of geodetic adjustment: measured angles and lengths must satisfy geometric relations, while corrections should be small. The manuscript reproduced in Claude Brezinski's study is titled Sur la résolution numérique des systèmes d’équations linéaires and ends with the date 2 December 1910 at Vincennes. The manuscript reports a 56-equation calculation adjusting altitudes in an Algerian triangulation network. Its date establishes when this written account existed, rather than an exact invention date.^[ref]

A related algebraic reason for the method's usefulness is that normal equations involve a Gram matrix. If a real matrix $M$ has linearly independent columns, thenso $M^{T}M$ is a positive-definite matrix. That gives the structure needed by a Cholesky decomposition. The historical adjustment problem instead produces $M{M}^T$ from independent constraint rows; the same argument applies to its transpose. In numerical least squares, explicitly forming normal equations squares the condition number of a full-column-rank design matrix; a QR decomposition can therefore be preferable for accuracy. Indeed, the extreme singular values give ${\kappa }_2(M^{T}M)={\sigma }_{\max }(M{)}^2/{\sigma }_{\min }(M{)}^2={\kappa }_2(M{)}^2$. The factorization remains useful when a positive-definite matrix is already the natural input.

For a real symmetric positive-definite matrix, the lower triangular matrix $C$ with positive diagonal in its Cholesky decomposition is its lower Cholesky factor; $C^T$ is the corresponding upper factor. If a full-column-rank matrix $B$ has a reduced QR decomposition $B=QR$ with positive diagonal of $R$, then $B^{T}B=R^{T}R$, so $R$ is the upper Cholesky factor of $B^{T}B$.

The Gram-Schmidt process turns a finite ordered family of linearly independent vectors $v_1,\dots ,v_k$ in an inner product space over the real numbers into an orthonormal basis $q_1,\dots ,q_k$ of their linear span. It keeps every successive linear span, so the first $j$ new vectors describe exactly the same directions as the first $j$ inputs. Its idea is geometric: remove the orthogonal projection onto directions already found, then divide the remaining vector by its norm. This makes a complicated basis easier to use without changing the vector subspace it describes.^[ref]

Start with $u_1=v_1$ and $q_1=v_1/\Vert v_1\Vert$. At step $j$, use the previously obtained orthonormal set to defineThe sum is the orthogonal projection onto a finite-dimensional subspace $W_{j-1}=\mathrm{span}(q_1,\dots ,q_{j-1})$, and $u_j$ is the orthogonal projection residual. Linear independence ensures $u_j\ne 0$: otherwise $v_j$ would already be a linear combination of earlier inputs. If the input family is linearly dependent, use only the retained orthonormal vectors in the sum and omit an input whenever its remainder is the zero vector; do not divide by zero. The retained outputs still form an orthonormal basis of the original linear span, but their number can be smaller than $k$.

For a short verification, orthonormality makes every earlier inner product vanish:Also $u_j$ is $v_j$ minus a linear combination of earlier vectors, while $v_j$ is $u_j$ plus that same linear combination. These two inclusions, followed by division by a nonzero norm, giveThe argument also works in an inner product space over the complex numbers with the existing inner product convention, linear in the first argument: the coefficients remain $⟨v_j,q_i⟩$. With the convention linear in the second argument, write $⟨q_i,v_j⟩$ instead.

For a first picture, take $v_1=(1,1{)}^T$ and $v_2=(1,0{)}^T$ in ${\mathbb{R}}^2$ with the ordinary dot product. ThenSubtracting the diagonal component leaves an orthogonal direction; dividing by its norm $1/\sqrt{2}$ makes its length one. If the second input were $(2,2{)}^T$ instead, its orthogonal projection would be the entire input and $u_2=0$, revealing linear dependence.

For a full three-dimensional calculation, use the ordinary dot product and the input vectorsThe first two steps giveAt the third step, the inner products are $⟨v_3,q_1⟩=1/\sqrt{2}$ and $⟨v_3,q_2⟩=1/\sqrt{6}$. ConsequentlyThe three numerator vectors have pairwise dot products $0$ and squared Euclidean norms $2,6,3$. Thus the displayed outputs are indeed an orthonormal basis, and the three nonzero remainders also confirm linear independence of the inputs. Keeping the removed coefficients produces the QR decomposition below.

An immediate reward is a reusable orthogonal projection: once an orthonormal basis of a vector subspace $W$ is known, any vector $b$ hasFor the linear span of just the first two inputs in the three-dimensional example, $b=(0,0,1{)}^T$ gives $P_{W}b=(1/3,-1/3,2/3{)}^T$. Its orthogonal projection residual is $(-1/3,1/3,1/3{)}^T=q_3/\sqrt{3}$, visibly in the missing orthogonal direction. This is the geometry behind the linear least-squares problem.

The formulas above describe exact arithmetic. With floating-point arithmetic, subtracting an orthogonal projection nearly equal to the input can leave a small remainder; dividing by its small norm can magnify existing roundoff error. The Classical Gram-Schmidt and Modified Gram-Schmidt arrangements agree in exact arithmetic but can give different rounded results. Exact linear dependence and a small computed remainder therefore require different judgments in a numerical implementation.^[ref]

Generate a real $n$-by-$n$ matrix $G$ with independent entries having the standard normal distribution. Take its QR decomposition with positive diagonal in the upper triangular matrix factor, $G=QR$. The orthogonal matrix $Q$ has normalized Haar measure on the full orthogonal group $O(n)$. If a numerical factorization returns $Q_0{R}_0$, set $S=\mathrm{diag}(\mathrm{sgn}{R}_{0,ii})$ and return $Q_{0}S$. The signs are nonzero almost surely: successively drawn Gaussian columns have probability zero of lying in the proper linear subspace spanned by earlier columns.

For correctness, every fixed orthogonal matrix $U$ preserves the standard Gaussian column density and column independence, so $UG$ and $G$ have the same probability distribution. The positive-diagonal QR decomposition is unique: two decompositions would give an orthogonal matrix that is also an upper triangular matrix with positive diagonal, hence the identity. Therefore $Q(UG)=UQ(G)$ and $Q(G)$ has a left-invariant probability law. Uniqueness of normalized Haar measure on the compact group $O(n)$ identifies that law. Each determinant sign has probability $1/2$ by reflection invariance.

Apply the preceding Householder reflection to the columns ofThe first column becomes $(-5,0{)}^T$ and the second becomes $(-11/5,2/5{)}^T$:Thus an orthogonal matrix multiplying an upper triangular matrix reconstructs $A$. The zero below the diagonal came from a geometric operation that preserves Euclidean norms and inner products.

Our positive-diagonal convention for QR decomposition is obtained by a sign adjustment. With $D=\mathrm{diag}(-1,1)$, putThen $Q^{T}Q=I$ and $\boxed{A=Q{R}_{+}}$. The intermediate sign chooses an orientation for a basis vector; the adjustment makes the diagonal positive.

For a larger matrix, the next Householder reflection acts only on the lower rows of the remaining columns, retaining the zeros already created. Store its defining vector and apply $z\mapsto z-2u(u^{T}z)$ instead of forming a dense reflection matrix. This links a simple mirror operation to efficient QR decomposition, including least-squares solutions.

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.

A matrix decomposition expresses a matrix as a matrix product of factors with simpler structure. An LU decomposition uses triangular factors, a QR decomposition uses an orthogonal matrix and a triangular factor, and a singular value decomposition separates input directions, stretching factors and output directions. The factorization is an identity; the chosen structure determines what it helps compute.

For an original two-by-two example,The outer factors are a lower triangular matrix and an upper triangular matrix, each with unit diagonal as in a unit triangular matrix; the middle factor is a diagonal matrix. Their matrix product is $M$, and the final diagonal entry $5/2$ is the Schur complement of the first entry $2$. This is the scalar version of the factorization under block elimination.

To solve $Mz=(3,4{)}^T$, solve with the three factors in their displayed order from left to right: first the lower triangular factor, then the diagonal factor, then the upper triangular factor. The intermediate vectors are $(3,5/2{)}^T$ and $(3/2,1{)}^T$, giving the concise answer $z=(1,1{)}^T$. A new right-hand side uses the same factors. This is why Reusing LU factors for multiple right-hand sides is useful: factorization records work that otherwise would be repeated, while forward substitution and back substitution apply it cheaply.^[ref]

Different decompositions reveal different features. A Cholesky decomposition uses positive definiteness of a symmetric matrix, while a singular value decomposition also applies to rectangular matrices and exposes matrix rank. The existence and numerical behaviour of the factors depend on their own hypotheses; for example, an unpivoted LU decomposition can fail when a chosen pivot element is zero even though the matrix is an invertible matrix.

Minimizing $\Vert y-X\theta {\Vert }^2$ gives the displayed equations by differentiation. Equivalently, the regression residual $r=y-X\hat{\theta }$ satisfies $X^{T}r=0$: it is orthogonal to every column of the design matrix. If $X$ has full column rank, the minimizer is unique and the fitted values are the orthogonal projection of $y$ onto its column space. A rank-deficient design matrix can give multiple coefficient vectors, while the projected fitted vector is still unique.

For an intercept and one predictor, put $S_{xx}={\sum }_i(x_i-\bar{x}{)}^2$ and $S_{xy}={\sum }_i(x_i-\bar{x})(y_i-\bar{y})$. The equations give $\hat{\beta }=S_{xy}/S_{xx}$ and $\hat{\alpha }=\bar{y}-\hat{\beta }\bar{x}$, provided $S_{xx}>0$. In the five-point example in linear regression, $\bar{x}=2$, $\bar{y}=2.8$, $S_{xx}=10$ and $S_{xy}=10$, giving $\hat{\beta }=1$ and $\hat{\alpha }=0.8$.

The normal equations describe the mathematical optimum, but explicitly forming and inverting $X^{T}X$ can amplify numerical problems. A QR decomposition computes the same least-squares solution through orthogonal coordinates; a singular value decomposition also exposes nearly dependent columns. This connects statistical fitting to numerical linear algebra and the choice of a stable algorithm. ^[ref]

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.

Suppose three measurements constrain two unknowns:The linear system asks for $x_1=1$, $x_2=2$, and $x_1+x_2=6$, which are incompatible. A least-squares solution makes a balanced compromise. The matrix has full column rank, soThe fitted output and residual areThus the two direct measurements are each overshot by one, and the measured sum is undershot by one. The residual has Euclidean norm $\sqrt{3}$ and is orthogonal to the column space, the plane $z=y_1+y_2$ in output coordinates $(y_1,y_2,z)$.

For any perturbation $h\in {\mathbb{R}}^2$, the orthogonality of $r$ to $Ah$ givesSince the kernel of $A$ is trivial, every nonzero $h$ increases the residual. The least-squares solution is unique in this example. The formula using $A^{T}A$ is convenient for these small exact calculations; an actual numerical computation can use a QR decomposition or singular value decomposition to avoid the extra conditioning cost of the least-squares normal equations. For full column rank, the squared singular values of $A$ are the eigenvalues of $A^{T}A$, so its condition number in the Euclidean norm is ${\kappa }_2(A^{T}A)={\kappa }_2(A{)}^2$. ^[ref]

Full column rank makes $B=A^{T}A$ positive definite: for nonzero $v$, $v^{T}Bv=\Vert Av{\Vert }^2>0$. Let $B=R^{T}R$ be its unique upper-triangular Cholesky decomposition with positive diagonal. Defining $Q=A{R}^{-1}$ givesThus the skinny QR decomposition exists. If $A=\tilde{Q}\tilde{R}$ is another such decomposition, orthonormality gives $A^{T}A={\tilde{R}}^T\tilde{R}$. Cholesky uniqueness forces $\tilde{R}=R$, and then $\tilde{Q}=A{R}^{-1}=Q$. Therefore the skinny factorization with positive diagonal is unique. This is the thin QR factorization from Cholesky decomposition; no inverse of the rectangular $Q$ is assumed.

First write $T=\left(\begin{array}{cc}a& b\\ 0& d\end{array}\right)$ with $a,d>0$. Direct multiplication givesThe inner product of its two columns isIf $E$ is orthogonal this is zero, and positivity of the bracket forces $b=0$. The first column must then have length one, so $d/a=1$. Thus $T=aI$, $E=I$, and $J_{1}T=T{J}_1$.

For the general QR decomposition, apply the Gram-Schmidt process to the ordered columns $v_1,\dots ,v_N$ of the invertible real matrix $A$. At stage $j$, subtract projections onto the already chosen orthonormal vectors to get $u_j$; independence of the columns gives $u_j\ne 0$. Set $q_j=u_j/\Vert u_j\Vert$. The matrix $B$ with columns $q_j$ is orthogonal, andis upper triangular. Its diagonal entry $C_{jj}=\Vert u_j\Vert$ is strictly positive. This proves $A=BC$ with the required properties.

Now suppose $KA=AK$ in dimension $2n$. Substitution of $A=BC$ givesThe matrix $K$ is orthogonal, as are $B$ and $B^{-1}$, so this matrix and $E=K^{-1}CK{C}^{-1}$ are orthogonal. Regard $C$ as upper triangular in $2\times 2$ blocks, with invertible diagonal blocks $C_i$. The inverse is upper triangular in the same blocks, by solving the triangular block equations; multiplication by block diagonal $K$ preserves this pattern. Thus $E$ is block upper triangular.

An orthogonal block upper-triangular matrix is block diagonal. Indeed its first two columns are supported in the first two rows and are orthonormal, so span that first coordinate plane. Orthogonality of every subsequent column to them makes its first two entries zero. The remaining lower-right matrix is orthogonal; iterate this argument. Therefore $E=\mathrm{diag}(E_1,\dots ,E_n)$ with each $E_i$ orthogonal. The rule for diagonal blocks of products of block upper-triangular matrices givesEach $C_i$ is itself an upper-triangular real $2\times 2$ matrix with positive diagonal. The first calculation gives $E_i=I$. Consequently $E=I$, whence $CK=KC$. Finally $B=A{C}^{-1}$ is a product of matrices commuting with $K$, so $BK=KB$. We have provedThis is positive-diagonal QR decomposition preserves a complex structure; the positivity convention is important in the two-dimensional step.

Let $a_1,a_2,a_3$ denote the columns. The Gram-Schmidt process begins with $\Vert a_1\Vert =2$, soThe second column has $r_{12}=q_1^{\mathsf{T}}{a}_2=4$ and residualThis residual has norm $2$, giving $q_2=\frac{1}{2}(-1,1,-1,1{)}^{\mathsf{T}}$ and $r_{22}=2$.

For the third column the orthogonal projections are $r_{13}=6$ and $r_{23}=4$. Subtracting them givesIts norm is $2$, so $q_3=\frac{1}{2}(1,1,-1,-1{)}^{\mathsf{T}}$ and $r_{33}=2$. Thus the requested thin QR decomposition isThe three displayed columns have pairwise zero inner products and unit norms; direct multiplication gives $QR=A$.

A full QR decomposition of a real $m$ by $n$ matrix with $m\ge n$ writeswhere $Q$ is an orthogonal $m$ by $m$ matrix and $R$ is upper triangular $n$ by $n$. In the full-column-rank case $R$ is invertible. Equivalently the reduced factorization is $A=Q_{1}R$ with $Q_1^T{Q}_1=I_n$. Householder transformations can construct the full factorization.

Let $Q^{T}b=\left(\genfrac{}{}{0ex}{}{c_1}{c_2}\right)$ with $c_1\in {\mathbb{R}}^n$. Since orthogonal transformations preserve the Euclidean norm,Therefore the linear least-squares problem has the full-rank solutionBack substitution solves this triangular system without forming $A^{T}A$. If the matrix is rank deficient, use a rank-revealing pivoted factorization and minimize over its independent columns; the minimizer need not be unique. The original PDF minimizes over $x\in {\mathbb{R}}^n$; the converted TeX's minimization over $b$ is a transcription error.

Use closest points on two line segments as a small constrained convex optimization problem. Write the two line segments asand put $w=P_1-P_2$. Minimize the squared Euclidean distance $D(s,t)=\Vert w+sd-te{\Vert }^2$; minimizing its square also minimizes the distance. Compute the dot productsFor nonzero, nonparallel directions, an interior minimum must satisfy the two derivative equationsTheir determinant is $\Delta =\alpha \gamma -{\beta }^2>0$, so the stationary candidate isRetain this candidate only when both parameters lie in the unit interval.

The other possibilities are on the boundary. Define $\mathrm{clip}(x)=\max (0,\min (1,x))$. Minimizing the same quadratic on each of the four edges gives these candidates by orthogonal projection onto a line segment:Evaluate $D$ at every retained candidate and choose the smallest. The resulting $R_1(s),R_2(t)$ are the required closest points. The quadratic is convex because it is the squared norm of an affine map. A minimum in the interior is stationary, and a minimum on the boundary minimizes one of these edge restrictions, so the list is exhaustive. Ties correspond to multiple equally valid answers.

Handle degenerate line segments before dividing: if $\alpha =0$ and $\gamma >0$, set $s=0$ and $t=\mathrm{clip}(\epsilon /\gamma )$; if $\gamma =0$ and $\alpha >0$, set $t=0$ and $s=\mathrm{clip}(-\delta /\alpha )$; if both vanish, use the two endpoints. For exactly parallel directions, $\Delta =0$. The distance depends on a single linear combination of $s,t$; any interior minimizing level line reaches the boundary, so the four edge candidates still include a minimum.

For nearly parallel directions, compare $\Delta$ with the scale $\alpha \gamma$, and solve the interior least-squares problem using QR decomposition or singular value decomposition if necessary. A small determinant should trigger a stable solve, not arbitrary rejection of a possibly valid interior solution. In particular, do not merely clip both coordinates of the infinite-line solution: the dot product $\beta$ couples the two parameters, and changing one changes the optimum for the other.

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.

Choose the Givens rotation convention in which ${\Omega }^{[p,q]}$ equals the identity outside rows and columns $p,q$, and has blockin those coordinates. It is an orthogonal matrix. For any chosen column $j$, write $u=A_{pj}$, $v=A_{qj}$ and $r=\sqrt{u^2+v^2}$. If $r>0$, take $\cos \theta =u/r$, $\sin \theta =v/r$. Then the new entries are $r$ and $-vu/r+uv/r=0$. If both entries vanish, take $\theta =0$. This proves the requested elimination for each chosen $j$; the angle is allowed to depend on $j$, and one angle need not eliminate an entire arbitrary row.

For the given matrix, use $\cos \theta =\sin \theta =1/\sqrt{2}$ first for ${\Omega }^{[1,2]}$, obtainingUse the same cosine and sine for ${\Omega }^{[1,3]}$. It makesThis is already upper triangular, including the zero $(3,2)$ entry, and every leading nonzero row entry is positive. Thus the requested QR decomposition isThe orthogonal matrix property follows from the two rotations, and direct multiplication verifies $A=QR$.

Each plane rotation satisfies $R_j^T{R}_j=I$. Hence $U=R_3{R}_2{R}_1$ is an orthogonal matrix and $D=UA$ is an upper triangular matrix. Multiplication by $U^T$ gives the QR decompositionThe zero-pair cases already handled make this construction valid for every real $3\times 3$ matrix, including rank-deficient matrices. Orthogonality follows from the product identity, not from any invertibility assumption on $A$.

For a full-column-rank matrix, a thin QR decomposition has $A=Q_{1}R$, where $Q_1^T{Q}_1=I_n$ and $R$ is nonsingular upper triangular. Extend $Q_1$ to an orthogonal matrix $Q=(Q_1,Q_2)$. Orthogonality givesThus the unique least-squares solution satisfies $R{x}^{\ast }=Q_1^{T}b$, with residual norm $\Vert Q_2^{T}b\Vert$. In a rank-deficient problem $R$ is singular and uniqueness needs separate treatment.

A Givens rotation is the identity except for the rows/columns $p,q$, whose block is $\left(\begin{array}{cc}c& s\\ -s& c\end{array}\right)$ with $c^2+s^2=1$. Its transpose times itself has that block equal to the identity, so it is orthogonal. Choose $c=4/5,s=3/5$ in rows two and three. ThenBack substitution in the first three rows givesThe fourth row of the rotated residual is the unavoidable value $-2$, while the other three rows vanish. Thus this rotation also directly exhibits the least-squares optimality.