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 Notation
Notation
QR Notation
The same two letters appear on this page with three different jobs, and the shapes behind them are never written down. Five marks decide which reading applies.
The contract A=QR itself — what each factor carries and why R comes out upper triangular — is set out at the Gram-Schmidt process. The reserved letter Q and the equation QTQ=I belong to orthogonal sets, the normal equations and the hat on x^ to least squares.
A = Q_1R_1 \qquad \text{versus} \qquad A = QR
A equals Q one R one — the thin factorisation — against A equals Q R, the full one
The letters match and the matrices do not. Thin: Q1 is m×n with orthonormal columns and R1 is n×n. Full: Q is square m×m and R is m×n, carrying m−n rows of zeros underneath. The line A=QR records neither shape, so which version is meant has to come from the surrounding sentence.
CasesThe subscript 1 marks the thin factors only when both versions are in play; on their own the thin factors are usually written Q and R as well. Gram-Schmidt produces the thin version, and the full one is reached by appending m−n columns that span the orthogonal complement of the column space.
Also writtenReduced and economy are the same thing as thin. Numerical libraries select between them with an argument rather than a symbol, which is why code and page can disagree about what Q names.
Do not confuseAssuming Q is square. That assumption is harmless for the full version and is exactly where the identity in the next entry stops holding.
Q^{T}Q = I_n, \qquad QQ^{T} \neq I_m
Q transpose Q is the n by n identity; Q Q transpose is not the identity
For a thin Q the order of the product decides whether the statement is true. Orthonormal columns give QTQ=In directly. Reversing the factors gives QQT, the projection onto the column space of A — equal to the identity only when Q is square and there is nothing left over to project away.
CasesIn the full factorisation Q is square and both products give Im, which is the case set out at orthogonal sets. This page needs the other one, and that is why QQT appears here as a projection matrix rather than as a way of writing I.
Also writtenThe thin case is sometimes flagged in words as orthonormal columns rather than by the equation, precisely to avoid claiming more than holds.
Do not confuseCalling a thin Q an orthogonal matrix. That name requires a square matrix, and a thin Q has no inverse at all. The practical version of the error is cancelling QQT inside a longer expression as though it were I.
R_{jj} = \|\mathbf{u}_j\| > 0
the j-th diagonal entry of R is the norm of the j-th orthogonal vector, and it is positive
Positivity buys uniqueness and is a convention, not something the factorisation forces. Multiplying a column of Q by −1 and the matching row of R by −1 leaves the product untouched, so without the sign rule an n-column matrix has 2n different QR factorisations. The line A=QR records none of that.
CasesGram-Schmidt gets the positive diagonal for free, since each Rjj is a norm. Householder reflections do not, and numerical libraries generally do not enforce the convention — two correct computed factorisations of one matrix can differ by a column of sign flips with nothing wrong in either.
Also writtenStated as a condition on R rather than built into the notation: with the diagonal ofRkept positive, appended to the factorisation whenever uniqueness is being claimed.
Do not confuseReading the QR factorisation as though the article were earned. It is earned only once the sign convention is stated, in the same way that the diagonal of ones earns uniqueness at LU.
A_k = Q_kR_k, \qquad A_{k+1} = R_kQ_k
factor A sub k into Q sub k times R sub k, then multiply those same factors back in the opposite order
The letters Q and R name a factorisation everywhere else on this page and an iteration here. The whole method sits in the reversal: the second line multiplies the factors just produced in swapped order, which amounts to Ak+1=QkTAkQk — a similarity transformation, so the eigenvalues survive while the sub-diagonal shrinks.
CasesThe subscript k counts iteration steps. It is the only subscript on the page that indexes time rather than a column, a row or an entry, and Qk is a different matrix at every step.
Also writtenThe shifted form factors Ak−σkI and adds σkI back afterwards, keeping the same two-line shape with a scalar moved in and out.
Do not confuseReading RkQk as a second factorisation, or expecting the reversal to undo the first line. Swapping the order changes the matrix, and repeating the swap is what drives Ak toward upper triangular form with the eigenvalues on its diagonal.
H = I - \frac{2\mathbf{v}\mathbf{v}^{T}}{\mathbf{v}^{T}\mathbf{v}}
H equals the identity minus two times v v transpose, over v transpose v
One vector appears four times in two products that are not the same operation. vvT is an m×m matrix of rank one; vTv is a single number, the squared length. Only the position of the transpose separates them, and it determines the shape of the result.
CasesThe numerator is a matrix and the denominator a scalar, so the fraction is ordinary scaling of a matrix and the subtraction from I is well formed. Writing v as a unit vector makes the denominator 1 and shortens the formula to I−2vvT, the form most texts quote — the same reflection either way.
Also writtenThe rank-one term is sometimes written v⊗v to name the outer product explicitly instead of leaving it to the transpose position.
Do not confuseReading the two products as interchangeable. Swapping them makes the subtraction ill-formed in one direction and the division ill-formed in the other, which is a useful check when the formula is being recalled rather than copied.
The diagonal 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.
The projection removed from a column
The part of this column lying along the directions already fixed is being subtracted away, leaving only what is genuinely new. The coefficients removed are not discarded — they are exactly the entries of R, which is why R comes out upper triangular without anyone arranging it. Watch both factors emerge on the QR decomposition visualizer.
Classical Gram-Schmidt is the clearest route to QR and the least stable one, which is why Householder reflections follow in the next section.
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.
The two variants compare cleanly on the dimensions of their factors and what each one captures.
Both reconstruct A exactly. The full form keeps m−n extra columns of Q that multiply against rows of zeros — useless for the product, and the only route to a basis for the left null space.
The extra columns are not redundant so much as unused. They complete Q into a genuine orthogonal matrix, which is what makes QQT=I hold as well as QTQ=I — and that second identity is what any argument about the left null space needs.
The difference is m−n columns of Q paired against m−n rows of zeros in R, so they contribute nothing to the product and A comes back identically either way. What they do contribute is a basis for everything A cannot reach — the left null space — and the squareness that makes Q orthogonal in both directions rather than only one.
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, starting from A0=A and at each step factoring and reassembling the product in reversed order:
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.
The leftover normalised to length one
What remained after the projections was a direction with an arbitrary length; dividing by that length makes it a unit vector and the next column of Q. Gram-Schmidt and QR are not two procedures but one, read as a geometric construction or as a factorisation. Step through the orthogonalisation on the Gram-Schmidt visualizer.
Seeing them as one procedure explains why improving the stability of Gram-Schmidt improves QR at the same time.
Summary: Four Routes to the Same Factorization
The QR factorization is unique (with the positive-diagonal convention), but the algorithms that produce it are not. Classical Gram-Schmidt, modified Gram-Schmidt, Householder reflections, and Givens rotations all yield the same A=QR in exact arithmetic, but they differ sharply in numerical stability and in the kinds of matrices they handle most efficiently. The table below collects each method alongside how it operates, its stability behavior, and the setting in which it is the right choice.
The four methods divide cleanly by strategy. The first two build Q directly, orthogonalizing the columns of A one at a time; the second two leave Q implicit and instead apply orthogonal operations to A until what remains is triangular. That difference is what decides the stability, so the grouping below is also the ranking.
All four produce A=QR and none is a variant of the others in output — they differ only in how they get there and how much accuracy survives the trip. The split below is by numerical standing, which is the column that decides in practice.
Each column is orthogonalized against the original earlier columns. In exact arithmetic this is correct; in floating point the accumulated rounding means QTQ drifts measurably from I, and badly when the columns are nearly dependent. Worth knowing as the definition, not as a method.
The same arithmetic reassociated: update the remaining columns in place after each subtraction rather than accumulating. Substantially more accurate than the classical form for no extra cost, which is why it is the version to use if Gram–Schmidt is used at all.
One reflection per column zeros everything below the pivot at once. Q arrives as a product of reflections rather than being built directly, which is what keeps it orthogonal to machine precision. This is what a numerical library calls unless told otherwise.
Zeros one entry at a time instead of a whole column. Slower on a dense matrix, but each rotation touches only two rows — so a sparse matrix stays sparse, and the work can be parallelised. The reason to choose it is structure, not speed.
Two of these are used and two are taught. Gram–Schmidt makes the connection between orthogonalization and QR visible, which is why it appears in every course; Householder and Givens are what libraries actually call, because backward stability is the property that matters once the matrix is anything other than well behaved.
Why the second group wins is worth stating plainly. Building Q by orthogonalization means every column inherits the rounding error of the columns before it, so orthogonality degrades as the computation proceeds — and degrades fastest exactly when the columns are nearly dependent, which is when the factorization was most needed. Householder and Givens never construct Q from the data at all: each step is an orthogonal matrix by construction, and a product of orthogonal matrices is orthogonal whatever the arithmetic did.
In practice the choice is narrow. Householder is the default for dense matrices and is what least squares routines call. Givens is chosen when the matrix is sparse or when entries arrive one at a time, since a rotation acts on two rows and leaves the rest untouched. Modified Gram–Schmidt survives where the columns of Q are wanted explicitly and progressively — and classical Gram–Schmidt survives as an explanation.
QR Decomposition FAQ
Is a thin Q an orthogonal matrix?
+
No, that name requires a square matrix, and a thin Q has none of the properties it implies, including an inverse. The practical form of the error is cancelling QQT inside a longer expression as though it were the identity. For a thin Q only QTQ=I holds, while QQT is a projection matrix.Read more →
Is the QR factorisation unique?
+
Only once a sign convention is fixed, usually requiring the diagonal of R to be positive. Gram-Schmidt satisfies that automatically since each diagonal entry is a norm, but Householder reflections do not, and numerical libraries rarely enforce it. Two correct factorisations of one matrix can therefore differ by a column of sign flips.Read more →
In the QR algorithm, is RkQk a second factorisation?
+
No, it is a deliberate reversal of the factors just computed, and reversing them changes the matrix rather than undoing anything. Repeating that swap is exactly what drives the sequence toward upper triangular form with the eigenvalues along the diagonal. The subscript k counts iterations rather than rows or columns.Read more →
