QR Decomposition

⚡ Key Takeaways

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 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.

DefinitionQR Decomposition

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

1

\quad A = QR

Derivation hint: 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^\top 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^\top Q = QQ^\top = I_m$ ) and $R$ is $m\times n$ upper triangular with $m-n$ zero rows at the bottom:

2

\quad A = \underbrace{\begin{bmatrix} Q_1 & Q_2 \end{bmatrix}}_{m\times m}\begin{bmatrix} R_1 \\ 0 \end{bmatrix},\qquad A = Q_1 R_1

Derivation hint: Append $m-n$ orthonormal vectors to the columns of the thin $Q$ to complete an orthonormal basis of $\mathbb{R}^m$ ; the extra columns multiply the zero block.

TheoremExistence and Uniqueness

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

3

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

Derivation hint: Uniqueness follows from the uniqueness of Gram–Schmidt with a fixed sign convention, or equivalently from the uniqueness of the Cholesky factor of $A^\top A$ .

ProofConstructive 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:

4

\quad u_1 = a_1,\qquad q_1 = \frac{u_1}{\lVert u_1\rVert}.

Derivation hint: $a_1\ne 0$ by full rank, so dividing by its norm is valid; $\lVert q_1\rVert=1$ .

Step 2. For $k = 2,\dots,n$ , subtract the components of $a_k$ along the already-built orthonormal vectors:

5

\quad u_k = a_k - \sum_{i=1}^{k-1}\big(q_i^\top a_k\big)\,q_i,\qquad q_k = \frac{u_k}{\lVert u_k\rVert}.

Derivation hint: Each term $q_i^\top a_k$ is the orthogonal projection coefficient onto $q_i$ ; removing them leaves $u_k\perp q_i$ for all $i<k$ . Full rank guarantees $u_k\ne 0$ .

Step 3. By construction $\{q_1,\dots,q_n\}$ is orthonormal, so $Q=[q_1\,\cdots\,q_n]$ satisfies $Q^\top Q = I_n$ . Solving the relations above for $a_k$ gives

6

\quad a_k = \lVert u_k\rVert\, q_k + \sum_{i=1}^{k-1}\big(q_i^\top a_k\big)\,q_i = \sum_{i=1}^{k}r_{ik}\,q_i,

with $r_{kk}=\lVert u_k\rVert>0$ and $r_{ik}=q_i^\top a_k$ for $i<k$ . Derivation hint: Rearrange equation [5]; the sum ranges only over $i\le 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. $\blacksquare$ Derivation hint: The $k$ -th column of $QR$ equals $\sum_{i}q_i r_{ik}$ , matching equation [6] column-by-column.

∎

ProofUniqueness

Suppose $A=Q_1R_1=Q_2R_2$ with both $R$ 's having positive diagonals. Then $Q_2^\top Q_1 = R_2R_1^{-1}=:M$ . The product of upper-triangular matrices is upper triangular, so $M$ is upper triangular; but $M=Q_2^\top Q_1$ is orthogonal. An orthogonal upper-triangular matrix is diagonal, and a diagonal orthogonal matrix has entries $\pm1$ . Positive diagonals of $R_1,R_2$ force $M=I$ , hence $Q_1=Q_2$ and $R_1=R_2$ . $\blacksquare$ Derivation hint: 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.

∎

ES

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.

🧠 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.

Figure

Gram–Schmidt: projecting out the parallel component to build

q_2

from

a_2

ExampleA 2×2 Decomposition by Hand

Given:

7

\quad A=\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix},\quad a_1=\begin{bmatrix}1\\1\end{bmatrix},\ a_2=\begin{bmatrix}1\\0\end{bmatrix}.

Derivation hint: We apply equations [4]–[6] directly.

Step 1 — first column. $\lVert a_1\rVert=\sqrt 2$ , so

8

\quad q_1=\frac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix},\qquad r_{11}=\sqrt2.

Derivation hint: $r_{11}=\lVert u_1\rVert=\sqrt{1^2+1^2}$ .

Step 2 — second column. Projection coefficient:

9

\quad r_{12}=q_1^\top a_2=\tfrac{1}{\sqrt2}(1\cdot1+1\cdot0)=\tfrac{1}{\sqrt2}.

Derivation hint: Dot product of $q_1$ with $a_2$ .

10

\quad u_2=a_2-r_{12}\,q_1=\begin{bmatrix}1\\0\end{bmatrix}-\tfrac12\begin{bmatrix}1\\1\end{bmatrix}=\begin{bmatrix}\tfrac12\\-\tfrac12\end{bmatrix}.

Derivation hint: Subtract the parallel part; note $u_2\perp q_1$ since their dot product is $\tfrac14-\tfrac14=0$ .

11

\quad r_{22}=\lVert u_2\rVert=\tfrac{1}{\sqrt2},\qquad q_2=\frac{u_2}{r_{22}}=\frac{1}{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix}.

Derivation hint: $\lVert u_2\rVert=\sqrt{1/4+1/4}=1/\sqrt2$ .

Boxed answer:

12

\quad \boxed{\,Q=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix},\qquad R=\frac{1}{\sqrt2}\begin{bmatrix}2&1\\0&1\end{bmatrix}\,}

Derivation hint: Verify $QR=A$ : the $(1,1)$ entry is $\frac{1}{\sqrt2}\cdot\frac{1}{\sqrt2}(1\cdot2+1\cdot0)=1$ , etc. Quantities here are dimensionless.

ExampleSolving 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

13

\quad A=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix},\qquad b=\begin{bmatrix}1\\2\\2\end{bmatrix}.

Derivation hint: Each row encodes $c_0+c_1x_i=y_i$ .

Step 1 — QR of $A$ . Column 1: $\lVert a_1\rVert=\sqrt3$ , $q_1=\tfrac{1}{\sqrt3}(1,1,1)^\top$ , $r_{11}=\sqrt3$ . Column 2: $r_{12}=q_1^\top a_2=\tfrac{0+1+2}{\sqrt3}=\sqrt3$ . Then

14

\quad u_2=\begin{bmatrix}0\\1\\2\end{bmatrix}-\sqrt3\cdot\tfrac{1}{\sqrt3}\begin{bmatrix}1\\1\\1\end{bmatrix}=\begin{bmatrix}-1\\0\\1\end{bmatrix},\ \ r_{22}=\sqrt2,\ q_2=\tfrac{1}{\sqrt2}\begin{bmatrix}-1\\0\\1\end{bmatrix}.

Derivation hint: 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^\top b$ :

15

\quad Q^\top b=\begin{bmatrix}q_1^\top b\\ q_2^\top b\end{bmatrix}=\begin{bmatrix}\tfrac{1+2+2}{\sqrt3}\\ \tfrac{-1+0+2}{\sqrt2}\end{bmatrix}=\begin{bmatrix}\tfrac{5}{\sqrt3}\\ \tfrac{1}{\sqrt2}\end{bmatrix}.

Derivation hint: Multiply $b$ by each orthonormal column.

Step 3 — back-substitution in $R c = Q^\top b$ , with $R=\begin{bmatrix}\sqrt3&\sqrt3\\0&\sqrt2\end{bmatrix}$ :

16

\quad c_1=\frac{1/\sqrt2}{\sqrt2}=\tfrac12,\qquad c_0=\frac{5/\sqrt3-\sqrt3\cdot\tfrac12}{\sqrt3}=\frac{5}{3}-\frac12=\frac{7}{6}.

Derivation hint: Solve the bottom equation first, substitute upward.

Boxed answer:

17

\quad \boxed{\,y = \tfrac{7}{6} + \tfrac12 x\,}

Derivation hint: This is the same answer the normal equations $A^\top A c=A^\top b$ give, but obtained more stably. Variables $c_0,c_1$ carry the units of $y$ and $y/x$ respectively.

⚠️ Common mistake

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$ .

⚠️ Common mistake

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.

Counterexample

Consider $A=\begin{bmatrix}1&1\\ \varepsilon&0\\ 0&\varepsilon\end{bmatrix}$ with $\varepsilon=10^{-8}$ (a Läuchli-type matrix). Classical Gram–Schmidt computes $q_2$ whose inner product with $q_1$ is of order $\varepsilon$ in floating point — orthogonality $q_1^\top q_2\approx 10^{-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.

connection

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^\top A$ (since $A^\top A = R^\top Q^\top Q R = R^\top R$ ). It is the workhorse of Least Squares Problems, where solving $Rc=Q^\top b$ avoids forming the ill-conditioned $A^\top 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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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 ( $AP=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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also