The QR decomposition factors a matrix into an orthogonal factor Q and an upper triangular factor R. It is the matrix form of the Gram-Schmidt process, the standard method for least-squares computation, and the foundation of the most widely used eigenvalue algorithm. The orthogonal factor preserves lengths and condition numbers, making QR the numerically safest of the triangular factorizations.
where Q is m×n with orthonormal columns and R is n×n upper triangular with positive diagonal entries.
The columns of Q form an orthonormal basis for the column space of A. The matrix R stores the coefficients: each column of A is a linear combination of the columns of Q with weights given by the corresponding column of R. The upper triangular structure of R reflects the sequential nature of the orthogonalization — each column depends only on the columns that came before it.
QR via Gram-Schmidt
Applying the Gram-Schmidt process to the columns a1,…,an of A produces orthonormal vectors q1,…,qn. These become the columns of Q.
The entries of R are the dot products computed during Gram-Schmidt: Rij=qi⋅aj for i≤j, and Rij=0 for i>j. Each column of A decomposes as
aj=R1jq1+R2jq2+⋯+Rjjqj
The entry Rjj=∥uj∥ (the norm of the j-th orthogonal vector before normalization) is always positive, which makes R unique.
Worked Example
For A=101110: Gram-Schmidt on the two columns gives q1=21(1,0,1)T and q2=61(1,2,−1)T. Then R=(201/23/6) and A=QR.
QR via Householder Reflections
A Householder reflection is an orthogonal matrix H=I−2vvT/(vTv) that reflects Rm across the hyperplane perpendicular to v. By choosing v appropriately, a single Householder reflection zeros out all entries below the pivot in one column.
Applying Householder reflections sequentially — one per column — produces Hn⋯H2H1A=R. Since each Hi is orthogonal, Q=H1H2⋯Hn is orthogonal, giving A=QR.
Householder QR is more numerically stable than Gram-Schmidt. It achieves backward stability — the computed factors Q and R satisfy QR=A+E where ∥E∥ is on the order of machine precision times ∥A∥. This makes Householder QR the standard algorithm in numerical libraries.
Thin QR vs. Full QR
The thin (reduced) QR factorization has Q1 of size m×n with orthonormal columns and R1 of size n×n upper triangular: A=Q1R1. This is the version produced by Gram-Schmidt and is sufficient for most applications.
The full QR factorization extends Q1 to a square m×m orthogonal matrix Q by appending m−n columns forming an orthonormal basis for Col(A)⊥. The factor R is extended to m×n by appending m−n rows of zeros: A=QR.
The full version is needed when the orthogonal complement of the column space is required — for instance, when extracting a basis for the left null space. The thin version is more economical for system solving and least squares.
Existence and Uniqueness
Every m×n matrix with m≥n and linearly independent columns has a thin QR factorization. Every m×n matrix (regardless of rank) has a full QR factorization.
The thin QR factorization with positive diagonal entries on R is unique. If negative diagonal entries are permitted, the factorization is not unique — signs can be redistributed between Q and R (multiplying a column of Q by −1 and the corresponding row of R by −1 preserves the product). The convention of positive diagonal entries on R resolves this ambiguity.
Solving Least Squares with QR
The normal equationsATAx^=ATb transform under A=QR. Since ATA=RTQTQR=RTR and ATb=RTQTb, the normal equations become RTRx^=RTQTb. Canceling RT (invertible because R has positive diagonal):
Rx^=QTb
The right-hand side QTb is computed by ndot products. The system Rx^=QTb is upper triangular, solved by back substitution in O(n2) operations.
The critical advantage over the normal equations is numerical. Forming ATA squares the condition number: κ(ATA)=κ(A)2. If A has condition number 106, the normal equations work with condition number 1012, losing 12 digits of accuracy in double precision. QR avoids this squaring and works with the original condition number 106.
The QR Algorithm for Eigenvalues
The QR algorithm is the standard method for computing eigenvalues of general (non-symmetric) matrices. It proceeds iteratively:
Set A0=A. At each step, compute the QR factorization Ak=QkRk, then form Ak+1=RkQk.
Under mild conditions, Ak converges to an upper triangular matrix with the eigenvalues on the diagonal. The convergence is driven by the fact that Ak+1=QkTAkQk — each iteration is a similarity transformation that preserves the eigenvalues while driving the sub-diagonal entries toward zero.
With shifts (replacing Ak by Ak−σkI before factoring and adding σkI back), convergence accelerates dramatically — cubic convergence for symmetric matrices with the Wilkinson shift. The QR algorithm computes eigenvalues without ever forming the characteristic polynomial, avoiding the severe numerical instability of polynomial root-finding.
Properties of the Factors
The orthonormality of Q's columns (QTQ=In) has several immediate consequences.
The matrix QQT is the projection matrix onto Col(A). For any b, QQTb is the orthogonal projection of b onto the column space.
Orthogonal multiplication preserves norms: ∥Ax∥=∥QRx∥=∥Rx∥, since ∥Qy∥=∥y∥ for any y. This means R captures all the "size" information of A — the orthogonal factor contributes nothing to stretching or compressing.
R is invertible when A has full column rank (the diagonal entries are the norms of the Gram-Schmidt vectors, all positive). The singular values of A equal the singular values of R, since the orthogonal factor does not affect them.
Gram-Schmidt vs. Householder
Classical Gram-Schmidt can lose orthogonality in floating-point arithmetic when the columns of A are nearly dependent. The computed qi's may fail to be perpendicular to machine precision, and the errors accumulate with each step.
Modified Gram-Schmidt improves stability by updating the remaining vectors in place after each projection subtraction, rather than using the original columns throughout. The mathematical result is identical in exact arithmetic, but the numerical behavior is significantly better.
Householder reflections provide the strongest stability guarantee. Each reflection zeros an entire column below the diagonal in a single, orthogonally-implemented step. The resulting QR factorization is backward stable — the gold standard in numerical linear algebra.
Givens rotations offer a third option, zeroing entries one at a time via plane rotations. They are preferred for sparse matrices, where surgically placed zeros can be introduced without disturbing the existing sparsity structure.
In practice, Householder is the default for dense matrices, Givens for sparse ones, and Gram-Schmidt (modified) for situations where the orthogonal factor Q is needed explicitly rather than implicitly.
QR and Gram-Schmidt: The Connection
The Gram-Schmidt process and the QR decomposition are two descriptions of the same computation.
Gram-Schmidt takes the columns of A and produces orthonormal vectors q1,…,qn while recording the coefficients Rij=qi⋅aj along the way. Assembling these into matrices gives A=QR.
Conversely, given A=QR, the columns of Q are exactly what Gram-Schmidt would produce, and R stores exactly the dot products Gram-Schmidt would compute. The factorization is the matrix-level summary of the vector-level algorithm.
This duality means every theorem about QR has an interpretation in terms of Gram-Schmidt, and vice versa. The QR decomposition is Gram-Schmidt made systematic, portable, and computable in a single matrix equation.