Skip to content

QR Decomposition

An exact matrix factorization into an orthogonal or unitary coordinate factor and an upper-triangular or trapezoidal coefficient factor.

Version
v1 · 2026-10-03 · History
Domain-specific #
13537
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Numerical Linear Algebra → Mathematics
Aliases
Qr Factorization

Core Idea

QR decomposition represents a matrix \(A\) as \(A=QR\), where \(Q\) has orthonormal columns (or is square orthogonal/unitary in the full form) and \(R\) is upper triangular or upper trapezoidal according to shape. For a real \(m\times n\) matrix with \(m\ge n\), the full convention is \(A=Q\begin{bmatrix}R\\0\end{bmatrix}\), with \(Q\) an \(m\times m\) orthogonal matrix and \(R\) an \(n\times n\) upper-triangular matrix; the economy form keeps the first \(n\) columns of \(Q\). The factors do two different jobs: \(Q\) supplies a norm-preserving coordinate frame, while \(R\) records how the original columns sit in that frame.[1][2]

The factorization is a formal representation, not a single construction algorithm. Gram–Schmidt, Householder transformations, and other methods can compute related QR forms, but their numerical behavior differs. The basic factorization can exist when \(A\) is rank deficient; the convenient nonsingular triangular solve and a positive-diagonal uniqueness convention need stronger full-rank assumptions. MIT's theorem explicitly states the square invertible positive-diagonal case, not an unconditional uniqueness result for every matrix.[3][4]

Structural Signature

Sig role-phrases: input matrix — orthogonal or unitary factor — upper-triangular factor — exact reconstruction — rank and convention qualifications.

  • Input matrix. \(A\) is the original linear map or column collection to be represented. Its dimensions and rank govern which QR convention and downstream solve can be used.[1]
  • Orthogonal or unitary factor. \(Q\) provides an orthonormal coordinate frame. Multiplication by square \(Q\) preserves Euclidean length in the real case, with the conjugate-transpose analogue for complex matrices.[1]
  • Upper-triangular or trapezoidal factor. \(R\) records coefficients of the original columns in the \(Q\) frame, imposing an order that permits triangular reasoning rather than an arbitrary dense second factor.[2]
  • Exact reconstruction. The product returns \(A\) in exact algebra; a floating-point implementation only approximates this equation up to its numerical error. Without reconstructability, the pair is not a QR factorization of that input.[1]
  • Rank and convention qualifications. Full column rank makes the square economy \(R\) nonsingular, enabling the standard backsolve. Positive diagonal signs can fix uniqueness in the stated full-rank setting; deficient rank and alternative full-basis completions need separate treatment.[1][4]

What It Is Not

QR is not any product of matrices. The orthogonality/unitarity and triangular restrictions are constitutive; a generic invertible \(Q\) or dense \(R\) loses the named structure. It is not simply Gram–Schmidt: that process is one possible derivation or computation, whereas QR is the factor relation that different algorithms can produce.[1][3]

It is not the QR eigenvalue algorithm. That algorithm repeatedly uses QR-related steps to transform a matrix toward Schur form. A single \(A=QR\) identity is one algebraic ingredient, not the iterative convergence procedure or its output theorem.[5]

It is not automatically a unique least-squares solution. A rank-deficient matrix may still be factored, while ordinary full-rank triangular back-substitution is not justified by the factorization alone. Pivoted QR or other rank-aware methods address that separate problem.[1][3]

Scope of Application

The factorization applies to real matrices and has a complex unitary counterpart. Full and economy conventions retain different extents of the orthonormal frame; QR may be used for square or rectangular matrices, with triangular/trapezoidal shape adjusted accordingly. In LAPACK's official real routine, the orthogonal factor is represented through elementary reflectors rather than always materialized as a dense \(Q\).[2][1]

For full-column-rank least squares, QR changes coordinates without changing the 2-norm of residuals, reducing the coefficient calculation to a triangular system. In eigenvalue computation, QR-based iteration works on a Hessenberg matrix toward Schur form. These are unlike downstream uses; neither is the definition of the factorization itself.[1][5]

Clarity

The representation separates where the column space points from how the original columns combine in that frame. \(Q\) makes orthonormal directions explicit; \(R\) keeps ordered coefficients. This prevents a common conflation of “orthogonalizing the data” with “solving the particular problem”: orthogonalization is a structural transform, while regression or eigensolving adds a separate goal.[1]

It also sharpens rank claims. An upper-triangular factor is not necessarily invertible. Saying “factorable by QR” does not entail “uniquely solvable by back-substitution,” and saying “orthogonal” does not identify whether one is using a thin \(m\times n\) frame or a full \(m\times m\) basis.[1][4]

Manages Complexity

Instead of treating \(A\) as an undifferentiated array, QR concentrates its geometry in \(Q\) and its ordered algebra in \(R\). This permits a least-squares residual to be viewed as coordinates parallel and orthogonal to the column space, while the coefficient part becomes a triangular solve. The factorization thus compresses a dense minimization into norm-preserving coordinate change plus a simpler system under the full-rank hypothesis.[1]

The compression does not erase every numerical issue. The method of forming factors matters in finite precision, and ill-conditioning or rank uncertainty can make a naive solve unreliable. Cornell's notes contrast backward-stable Householder QR with classical Gram–Schmidt and explain why normal equations square the condition number of \(A\); those are computational qualifications, not additional axioms of the exact factorization.[3]

Abstract Reasoning

Given \(A=Q\begin{bmatrix}R\\0\end{bmatrix}\) and a vector \(b\), orthogonality gives \(\lVert Ax-b\rVert_2=\lVert Q^T(Ax-b)\rVert_2\). Partitioning \(Q^Tb\) into coordinates along and orthogonal to the columns of \(A\) exposes which part can be fitted. If \(R\) is nonsingular, the coefficient part is obtained from a triangular equation. This inference depends on full column rank; otherwise the same factorization does not deliver a unique coefficient vector by that step.[1]

For a different question, ask what repeated orthogonality-preserving transformations can reveal about a square matrix's spectrum. LAPACK's Hessenberg QR iteration uses factorization within an eigenvalue pipeline toward Schur form. The exact QR identity supplies a legitimate step, but the later convergence analysis belongs to the iteration, not to \(A=QR\) by itself.[5]

Knowledge Transfer

The structural roles transfer literally from least-squares matrices to eigenvalue iterates: input matrix, orthogonal/unitary factor, triangular factor, and exact reconstruction. The downstream objective changes from minimizing a residual to revealing spectral structure. Thus the same algebraic object can serve distinct numerical methods without being identical to either.[1][5]

Beyond matrix settings, broad Decomposition captures the recoverable-whole/meaningful-parts skeleton. QR's specific \(Q\)/\(R\) relation does not become a prime abstraction merely because a non-matrix process also has “orthogonal” aspects metaphorically. The live Factorization prime is related but its same-type native-operation and irreducible-factor requirements are too restrictive for every rectangular QR product.[6][7]

Examples

Full-rank overdetermined least squares

LAPACK's guide considers \(m\ge n\) and full-column-rank \(A\). With \(A=Q\begin{bmatrix}R\\0\end{bmatrix}\), applying \(Q^T\) to \(b\) splits its coordinates; the fitted part requires solving the triangular \(Rx=c_1\), and the remaining coordinates account for the residual. This is an exact structural derivation, not a claim that every measured regression matrix is full rank.[1]

Mapped back: The input matrix is the design matrix \(A\); the orthogonal factor is \(Q\), which preserves residual norm; the upper-triangular factor is \(R\); exact reconstruction is \(A=Q[R;0]\) in block notation; and the rank qualification is full column rank, which makes \(R\) suitable for unique back-substitution. The output coefficients belong to the least-squares application, not to QR's definition.

Hessenberg eigenvalue iteration

LAPACK's eigenvalue machinery reduces a matrix to Hessenberg form and uses QR-based multishift iteration toward a Schur form. A current iterate can be factorized into orthogonal and triangular pieces; their use in further transformations is an algorithmic step beyond the one factorization. The setting is spectral computation, not a triangular solve for regression coefficients.[5]

Mapped back: The input matrix is the current Hessenberg or shifted iterate; its orthogonal factor and triangular factor are the \(Q\) and \(R\) of that step; exact reconstruction identifies the current matrix with their product in exact arithmetic; rank/convention qualifications differ from the full-rank least-squares requirement. QR supplies structure to the iteration without promising its convergence by itself.

Structural Tensions

T1 — Orthogonality preservation versus immediate computational economy. Orthogonal transformations avoid the normal-equation route's squared condition number, but can demand additional operations or storage compared with forming \(A^TA\). Pursuing only the cheaper apparent solve can lose numerical accuracy; pursuing a robust factorization for every tiny well-conditioned case can spend resources needlessly. Diagnostic: Is this matrix's conditioning and accuracy requirement such that the cheaper normal-equation route is unsafe relative to QR?[3]

T2 — Thin compactness versus full ambient geometry. Thin QR retains the column-space frame and economizes representation; full \(Q\) also exposes complementary directions useful for residual or transform reasoning. Retaining the full basis when unnecessary costs storage, while discarding it when needed obscures the orthogonal complement. Diagnostic: Does the downstream task need only \(Q_1\) and \(R\), or also explicit coordinates in the complement of the column space?[1][2]

Structural–Framed Character

QR decomposition lies at the structural end within a mathematical domain: its product equation and orthogonality constraints are exact, while “matrix,” “unitary,” and “triangular” are not optional vocabulary. Its evaluative weight is low in definition; a QR factorization is neither good nor bad simply by existing, though numerical algorithms can be compared. Its human-practice dependence is low for the algebraic identity and higher for selecting a computational form. Its institutional origin is numerical linear algebra, expressed here by official LAPACK documentation, not a social norm. Its vocabulary travels between least-squares and eigenvalue computation while retaining literal matrix roles. For import versus recognition, finding a broad decomposition pattern in another discipline does not import the exact QR conditions there. Its character: a precise domain-specific factorization that instantiates the live Decomposition prime but does not itself become substrate-independent.[1][5][6]

Structural Core vs. Domain Accent

The portable skeleton is one whole represented by recoverable, separately useful components. Live Decomposition supplies that genus. The domain-bound mechanism is sharper: an orthogonal/unitary coordinate factor multiplied by an upper-triangular factor, preserving norms while exposing ordered coefficients. A system without matrices, an inner-product geometry, and triangular algebra cannot literally instantiate QR even if it can be decomposed.[1][6]

The nearby live Factorization prime is not asserted as a second parent. Its current signature demands same-type factors under a closed native operation and an irreducible endpoint. A rectangular \(A\), square/full or thin \(Q\), and triangular \(R\) need not share one type or bottom out in irreducibles. The named QR identity therefore remains domain-specific rather than inheriting a false universal factorization signature.[7][2]

This entry is a kind of Decomposition.

DAG parent — Decomposition (Decomposition). \(A\) is exactly reconstructed from two meaningful components: norm-preserving coordinate frame and triangular coefficients. The broader abstraction explicitly includes matrix decompositions and remains broader than this particular form. This edge awaits independent review.[6][1]

Related, not strict parent — Factorization (Factorization). Its product language resembles QR, but its live same-type/irreducible conditions fail as a universal description of rectangular QR. The relationship is lexical and conceptual, not an asserted whole-identity subsumption.[7]

Relationships to Other Abstractions

Local relationship map for QR DecompositionParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.QR DecompositionDOMAINPrime abstraction: Decomposition — is a kind ofDecompositionPRIME

Current abstraction QR Decomposition Domain-specific

Parents (1) — more general patterns this builds on

  • QR Decomposition is a kind of Decomposition Prime

    QR decomposes a matrix into exactly recombinable orthogonal/unitary and triangular factors.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

QR Decomposition sits in a sparse region of the domain-specific corpus (60th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Codes, Matrices & Combinatorial Problems (30 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • QR algorithm: an iterative eigenvalue procedure using QR-based steps, not a synonym for one factorization.[5]
  • Classical Gram–Schmidt: one way to derive/compute QR with numerical limitations, not the factor relation itself.[3]
  • Normal equations: a different least-squares reduction involving \(A^TA\); the condition number can be squared, unlike the QR route's orthogonal transform.[3]
  • Automatic rank resolution: rank-deficient matrices can be factored, but ordinary triangular backsolve and positive-diagonal uniqueness need explicit conditions.[1][4]

References

[1] E. Anderson et al., LAPACK Users' Guide, 3rd ed. (1999), “QR Factorization”, official Netlib edition, especially factorization and least-squares equations. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t

[2] LAPACK project, DGEQRF reference documentation, Purpose and output parameters, inspected 2026-10-01. registry ↩a ↩b ↩c ↩d ↩e

[3] Cornell University CS 4220/5223 numerical methods lecture review, §5.3 and adjacent normal-equations paragraph, PDF p. 26. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[4] MIT 18.700 Lesson Plan 19, Theorem 10, square full-rank QR uniqueness under positive-diagonal convention. registry ↩a ↩b ↩c ↩d

[5] E. Anderson et al., LAPACK Users' Guide, “Eigenvalue Problems”, multishift QR iteration and Schur form. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[6] Encyclopedia of Abstractions, live prime_abstractions/v2/decomposition.md, Core Idea and Broad Use, inspected 2026-10-01. registry ↩a ↩b ↩c ↩d

[7] Encyclopedia of Abstractions, live prime_abstractions/v2/factorization.md, Core Idea and Structural Signature, inspected 2026-10-01. registry ↩a ↩b ↩c