QR Decomposition

QR Decomposition factors any matrix

A

into a product

A = QR

, where

Q

has orthonormal columns and

R

is upper triangular. It exists for every real or complex matrix, is the engine behind least-squares solvers and the QR algorithm for eigenvalues, and was developed through the work of Gram, Schmidt, Householder, and Givens in the late 19th and 20th centuries.

The QR decomposition expresses a matrix $A \in R^{m \times n}$ (with $m \geq n$ ) as $A = QR$ , where the columns of $Q$ form an orthonormal set and $R$ is upper (right) triangular. Geometrically, it performs Gram–Schmidt orthogonalization on the columns of $A$ , recording the projection coefficients in $R$ . It matters because orthonormal bases make numerical computation stable: solving least-squares problems, computing eigenvalues, and orthogonalizing data all reduce to QR. A surprising fact is that although the "textbook" Gram–Schmidt procedure that motivates QR is numerically unreliable, the same decomposition computed via Householder reflections is one of the most stable algorithms in all of numerical linear algebra.

The Core Insight

Any spanning set of vectors can be replaced by an orthonormal basis built one vector at a time, subtracting off the parts already accounted for. The orthonormal vectors become the columns of $Q$ ; the coefficients describing how each original column is reconstructed from the orthonormal ones form the upper-triangular $R$ . Triangularity is not imposed — it falls out automatically because the $k$ -th original column lies in the span of only the first $k$ orthonormal vectors.

Formal Statement

QR Decomposition

Let $A \in R^{m \times n}$ with $m \geq n$ . A QR decomposition of $A$ is a factorization

A = QR

⟳This is the defining equation; its existence is established constructively in the proof below.

where the symbols mean:

$A$ — the $m \times n$ input matrix whose columns are $a_{1}, \dots, a_{n}$ ;
$Q$ — an $m \times n$ matrix with orthonormal columns, i.e. $Q^{⊤} Q = I_{n}$ (in the reduced / thin form);
$R$ — an $n \times n$ upper-triangular matrix, with entries $r_{ij} = 0$ for $i > j$ .

In the full form, $Q$ is $m \times m$ orthogonal ( $Q^{⊤} Q = Q Q^{⊤} = I_{m}$ ) and $R$ is $m \times n$ upper triangular with $m - n$ zero rows at the bottom:

A = m \times m [Q_{1} Q_{2}] [R_{1} 0], A = Q_{1} R_{1}

⟳Append

m - n

orthonormal vectors to the columns of the thin

Q

to complete an orthonormal basis of

R^{m}

; the extra columns multiply the zero block.

Existence and Uniqueness

Every $A \in R^{m \times n}$ admits a QR decomposition. If $m \geq n$ and $A$ has full column rank ( $rank A = n$ ), then the thin decomposition $A = Q_{1} R_{1}$ is unique under the normalization that the diagonal entries of $R_{1}$ are positive:

r_{ii} > 0, i = 1, \dots, n .

⟳Uniqueness follows from the uniqueness of Gram–Schmidt with a fixed sign convention, or equivalently from the uniqueness of the Cholesky factor of

A^{⊤} A

Why It Holds / Derivation

Constructive Existence via Gram–Schmidt

Assume $A$ has full column rank with columns $a_{1}, \dots, a_{n}$ .

Step 1. Define the first orthogonal vector and normalize:

u_{1} = a_{1}, q_{1} = \frac{u _{1}}{∥ u _{1} ∥} .

⟳

a_{1} \neq = 0

by full rank, so dividing by its norm is valid;

∥ q_{1} ∥ = 1

Step 2. For

k = 2, \dots, n

, subtract the components of

a_{k}

along the already-built orthonormal vectors:

u_{k} = a_{k} - i = 1 \sum k - 1 (q_{i}^{⊤} a_{k}) q_{i}, q_{k} = \frac{u _{k}}{∥ u _{k} ∥} .

⟳Each term

q_{i}^{⊤} a_{k}

is the orthogonal projection coefficient onto

q_{i}

; removing them leaves

u_{k} ⊥ q_{i}

for all

i < k

. Full rank guarantees

u_{k} \neq = 0

Step 3. By construction

{q_{1}, \dots, q_{n}}

is orthonormal, so

Q = [q_{1} \dots q_{n}]

satisfies

Q^{⊤} Q = I_{n}

. Solving the relations above for

a_{k}

gives

a_{k} = ∥ u_{k} ∥ q_{k} + i = 1 \sum k - 1 (q_{i}^{⊤} a_{k}) q_{i} = i = 1 \sum k r_{ik} q_{i},

with

r_{k k} = ∥ u_{k} ∥ > 0

and

r_{ik} = q_{i}^{⊤} a_{k}

for

i < k

⟳Rearrange equation [5]; the sum ranges only over

i \leq k

, which is exactly the upper-triangular pattern.

Step 4. Collecting these relations into matrix form yields

A = QR

where

R = (r_{ik})

is upper triangular with positive diagonal.

■

⟳The

k

-th column of

QR

equals

\sum_{i} q_{i} r_{ik}

, matching equation [6] column-by-column.

Uniqueness

Suppose $A = Q_{1} R_{1} = Q_{2} R_{2}$ with both $R$ 's having positive diagonals. Then $Q_{2}^{⊤} Q_{1} = R_{2} R_{1}^{- 1} =: M$ . The product of upper-triangular matrices is upper triangular, so $M$ is upper triangular; but $M = Q_{2}^{⊤} Q_{1}$ is orthogonal. An orthogonal upper-triangular matrix is diagonal, and a diagonal orthogonal matrix has entries $\pm 1$ . Positive diagonals of $R_{1}, R_{2}$ force $M = I$ , hence $Q_{1} = Q_{2}$ and $R_{1} = R_{2}$ . $■$

⟳Key facts — (i) inverse of upper triangular is upper triangular; (ii) an orthogonal matrix whose entries vanish below the diagonal must be diagonal because its columns are unit-length and mutually orthogonal.

Erhard Schmidt | 1876–1959

Erhard Schmidt, a student of David Hilbert, formalized the orthogonalization procedure in 1907 while developing the theory of integral equations and Hilbert spaces — the abstract setting where "orthonormal basis" became a precise concept. Jørgen Pedersen Gram had introduced essentially the same idea in 1883 in the context of least squares. Although neither wrote " $A = QR$ ," their procedure is the conceptual heart of the decomposition. The numerically robust matrix algorithms (Householder, Givens) arrived only with the computer era in the 1950s–60s.

Building Intuition

Think of the columns of $A$ as a skewed, non-perpendicular set of axes. Gram–Schmidt straightens them: $q_{1}$ points along $a_{1}$ ; $q_{2}$ keeps only the part of $a_{2}$ perpendicular to $q_{1}$ ; $q_{3}$ keeps only the part of $a_{3}$ perpendicular to the plane spanned by $q_{1}, q_{2}$ ; and so on. The matrix $R$ is the "translation dictionary" telling you how to rebuild the original skewed columns from the clean perpendicular ones. Because $a_{k}$ only ever involves $q_{1}, \dots, q_{k}$ , the dictionary is upper triangular. Multiplying by an orthogonal $Q$ is a rotation/reflection — it preserves lengths and angles — so QR says: every set of vectors is a rigid rotation of a "stretched-and-sheared" triangular set.

Gram–Schmidt: projecting out the parallel component to build $q_2$ from $a_2$

Worked Examples

A 2×2 Decomposition by Hand

Given:

A = [1110], a_{1} = [11], a_{2} = [10] .

⟳We apply equations [4]–[6] directly.

Step 1 — first column.

∥ a_{1} ∥ = 2

, so

q_{1} = \frac{1}{2} [11], r_{11} = 2 .

⟳

r_{11} = ∥ u_{1} ∥ = 1^{2} + 1^{2}

Step 2 — second column. Projection coefficient:

r_{12} = q_{1}^{⊤} a_{2} = \frac{1}{2} (1 \cdot 1 + 1 \cdot 0) = \frac{1}{2} .

⟳Dot product of

q_{1}

with

a_{2}

u_{2} = a_{2} - r_{12} q_{1} = [10] - \frac{1}{2} [11] = [\frac{1}{2} - \frac{1}{2}] .

⟳Subtract the parallel part; note

u_{2} ⊥ q_{1}

since their dot product is

\frac{1}{4} - \frac{1}{4} = 0

r_{22} = ∥ u_{2} ∥ = \frac{1}{2}, q_{2} = \frac{u _{2}}{r _{22}} = \frac{1}{2} [1 - 1] .

⟳

∥ u_{2} ∥ = 1/4 + 1/4 = 1/ 2

Boxed answer:

Q = \frac{1}{2} [11 1 - 1], R = \frac{1}{2} [2011]

⟳Verify

QR = A

: the

(1, 1)

entry is

\frac{1}{2} \cdot \frac{1}{2} (1 \cdot 2 + 1 \cdot 0) = 1

, etc. Quantities here are dimensionless.

Solving a Least-Squares Problem with QR

Given: Fit a line

y = c_{0} + c_{1} x

through the data points

(0, 1), (1, 2), (2, 2)

. The overdetermined system is

A c = b

with

A = 111012, b = 122 .

⟳Each row encodes

c_{0} + c_{1} x_{i} = y_{i}

Step 1 — QR of $A$ . Column 1:

∥ a_{1} ∥ = 3

q_{1} = \frac{1}{3} (1, 1, 1)^{⊤}

r_{11} = 3

. Column 2:

r_{12} = q_{1}^{⊤} a_{2} = \frac{0 + 1 + 2}{3} = 3

. Then

u_{2} = 012 - 3 \cdot \frac{1}{3} 111 = - 1 01, r_{22} = 2, q_{2} = \frac{1}{2} - 1 01 .

⟳Subtract the mean (here

r_{12} q_{1}

removes the average value

1

from each entry of

a_{2}

Step 2 — transform the right side. The least-squares solution solves

R c = Q^{⊤} b

Q^{⊤} b = [q_{1}^{⊤} b q_{2}^{⊤} b] = [\frac{1 + 2 + 2}{3} \frac{- 1 + 0 + 2}{2}] = [\frac{5}{3} \frac{1}{2}] .

⟳Multiply

b

by each orthonormal column.

Step 3 — back-substitution in

R c = Q^{⊤} b

, with

R = [3032]

c_{1} = \frac{1/ 2}{2} = \frac{1}{2}, c_{0} = \frac{5/ 3 - 3 \cdot \frac{1}{2}}{3} = \frac{5}{3} - \frac{1}{2} = \frac{7}{6} .

⟳Solve the bottom equation first, substitute upward.

Boxed answer:

y = \frac{7}{6} + \frac{1}{2} x

⟳This is the same answer the normal equations

A^{⊤} A c = A^{⊤} b

give, but obtained more stably. Variables

c_{0}, c_{1}

carry the units of

y

and

y / x

respectively.

Common Misconceptions

The decomposition is not unique without a sign convention. If you negate a column of

Q

and the corresponding row of

R

, you get another valid QR. Software packages (LAPACK, NumPy) do not generally return positive diagonal

R

; comparing your hand result to numpy.linalg.qr may show sign flips that are entirely legitimate. Uniqueness in Theorem [3] holds only after fixing

r_{ii} > 0

. Classical Gram–Schmidt is numerically dangerous. Although equations [4]–[6] are mathematically exact, in floating point the computed columns of

Q

lose orthogonality catastrophically when the columns of

A

are nearly dependent. Never implement classical Gram–Schmidt for serious numerical work — use Modified Gram–Schmidt, Householder reflections, or Givens rotations instead, all of which compute the same

QR

but with vastly better stability.

Consider $A = 1 ε 0 10 ε$ with $ε = 1 0^{- 8}$ (a Läuchli-type matrix). Classical Gram–Schmidt computes $q_{2}$ whose inner product with $q_{1}$ is of order $ε$ in floating point — orthogonality $q_{1}^{⊤} q_{2} \approx 1 0^{- 8}$ instead of $0$ . Modified Gram–Schmidt cuts this error to machine precision, and Householder QR delivers orthogonality to full machine precision regardless of conditioning. This is the classic demonstration that the same exact decomposition can be computed well or badly.

Connections

QR sits at the crossroads of several pillars of linear algebra. It is the matrix encoding of Gram-Schmidt Process, and its $R$ factor is precisely the Cholesky Decomposition factor of the normal matrix $A^{⊤} A$ (since $A^{⊤} A = R^{⊤} Q^{⊤} QR = R^{⊤} R$ ). It is the workhorse of Least Squares Problems, where solving $R c = Q^{⊤} b$ avoids forming the ill-conditioned $A^{⊤} A$ . Iterated QR is the QR Algorithm for Eigenvalues, the standard method for computing the Eigenvalues and Eigenvectors of dense matrices. It complements the Singular Value Decomposition (rank-revealing but costlier) and the LU Decomposition (for square solves), and the orthogonal $Q$ embodies Orthogonal Matrices.

Real-World Applications

Least-squares regression & data fitting — every linear regression in statistics software (R's lm, MATLAB's backslash) factors the design matrix via QR to find best-fit coefficients stably.
Eigenvalue computation (QR algorithm) — LAPACK's dgeev/dsyev repeatedly apply shifted QR steps; this underlies eigenvalue routines in essentially all scientific software.
Signal processing & adaptive filters — recursive least-squares (RLS) filters use QR updates (via Givens rotations) for real-time channel equalization and noise cancellation.
Computer graphics / robotics — orthogonalizing a drifting rotation matrix back to a proper rotation uses the $Q$ from QR (polar/QR re-orthonormalization).
Krylov subspace methods — GMRES builds an orthonormal Arnoldi basis whose Hessenberg least-squares subproblem is solved with Givens-based QR each iteration.
Geodesy and surveying — overdetermined coordinate networks are adjusted by QR-based least squares to control numerical error in large sparse systems.
Machine learning — QR-based orthogonalization stabilizes solving linear models, computing pseudoinverses, and whitening features.

Historical Development

1883 — Jørgen Pedersen Gram introduces an orthogonalization procedure in his study of least squares and series expansions.
1907 — Erhard Schmidt, working in Hilbert's circle on integral equations, presents the procedure in the abstract Hilbert-space setting; it becomes "Gram–Schmidt."
1909 — Issai Schur and others develop triangular factorizations of matrices, foreshadowing matrix forms of orthogonalization.
1948 — Alan Turing's analysis of rounding errors in matrix computations launches modern numerical stability theory, motivating better factorizations.
1951–1954 — Cornelius Lanczos and Walter Arnoldi develop iterative orthogonalization (Krylov) methods that rely on QR-type steps.
1958 — Alston Householder introduces elementary reflectors (Householder transformations), giving a backward-stable way to compute QR.
1958–1961 — John G. F. Francis (and independently Vera Kublanovskaya) invent the QR algorithm for eigenvalues, one of the top algorithms of the 20th century.
1958 — Wallace Givens formalizes plane-rotation ("Givens") QR, ideal for sparse and streaming updates.
1965–1971 — Gene Golub and collaborators establish QR as the standard reliable method for least squares and codify it in what becomes LINPACK/LAPACK.

Subtleties & Limits

Rank-deficiency and rank-revealing QR. When

A

does not have full column rank, the plain QR can place tiny or zero pivots anywhere, masking the true rank. Rank-revealing QR (RRQR) uses column pivoting (

A P = QR

with permutation

P

) to push the "small" directions to the trailing columns, but no pivoting strategy is provably optimal for all matrices — constructing a strong rank-revealing factorization that is both cheap and guaranteed accurate remains an active area. Relatedly, communication-avoiding QR (TSQR/CAQR) for tall-skinny matrices on parallel hardware trades classical pivoting for blocked orthogonalization, and balancing stability against minimal data movement on modern GPUs/exascale machines is an ongoing engineering and analysis challenge. For the complex case,

Q

becomes unitary (

Q^{*} Q = I

) and the same theory carries over, but high-performance complex QR with careful rounding analysis still attracts research.

QR Decomposition

The Core Insight

Formal Statement

QR Decomposition

Existence and Uniqueness

Why It Holds / Derivation

Constructive Existence via Gram–Schmidt

Uniqueness

Erhard Schmidt | 1876–1959

Building Intuition

Gram–Schmidt: projecting out the parallel component to build $q_2$ from $a_2$

Worked Examples

A 2×2 Decomposition by Hand

Solving a Least-Squares Problem with QR

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads