QR Decomposition

Statement

Let $A$ be an $n \times n$ real invertible matrix. Then there exist matrices $Q$ and $R$ such that

where $Q$ is orthogonal ($Q^\top Q = I$, i.e., columns of $Q$ form an orthonormal basis) and $R$ is upper-triangular with positive diagonal entries. The factorization is unique under these sign conventions.

Visualization

Factor $A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$ via Gram–Schmidt on the columns $a_1 = (1,1)^\top$, $a_2 = (0,1)^\top$:

Step 1 — orthogonalize column 1:

Step 2 — orthogonalize column 2:

Result:

Verify $QR = A$:

Proof Sketch

1. Gram–Schmidt. Apply the Gram–Schmidt process to the columns of $A$ (in order). Produce an orthonormal list $q_1, \ldots, q_n$.
2. Extract $R$. The upper-triangular matrix $R$ encodes the inner products: $r_{ij} = q_i^\top a_j$ for $i \le j$ and $r_{ij} = 0$ for $i > j$. Positive diagonal entries come from choosing signs to make $r_{ii} = \|a_i'\| > 0$.
3. Invertibility. $A$ invertible implies no column of $A$ lies in the span of previous ones, so each Gram–Schmidt step produces a nonzero vector and $r_{ii} \ne 0$.
4. Uniqueness. If $A = QR = Q'R'$ then $(Q')^\top Q = R' R^{-1}$ is both orthogonal and upper-triangular, so it must be diagonal with $\pm 1$ entries; positivity of diagonals forces it to be $I$.

Connections

QR decomposition is a direct consequence of Gram–Schmidt OrthogonalizationGram–Schmidt Orthogonalization$$e_k = f_k - \sum_{j < k} \frac{\langle f_k, e_j\rangle}{\langle e_j, e_j\rangle} e_j$$Any linearly independent sequence can be transformed into an orthogonal sequence spanning the same subspace.Read more → applied to matrix columns. The orthogonal factor $Q$ relates to the Spectral TheoremSpectral Theorem$$A = Q \Lambda Q^T \;\text{(real symmetric case)}$$Every real symmetric matrix is orthogonally diagonalizableRead more → (both require orthonormal bases). The triangular factor $R$ plays the role of $U$ in LU DecompositionLU Decomposition$$A = LU,\quad L \text{ unit lower triangular},\; U \text{ upper triangular}$$Every invertible matrix factors as a unit-lower-triangular matrix times an upper-triangular matrix.Read more →.

-- We verify the concrete 2x2 QR example with rational arithmetic (scaled).
-- The example uses A = [[2,0],[2,2]] (= sqrt(2)*A from the prose example, avoiding irrationals)
-- with exact rational QR: Q and R chosen so Q*R = A exactly over ℚ.
-- Q = [[1, -1],[1, 1]] / ... handled by scaling: prove L * U = A for integer version.
theorem qr_example_2x2 :
    let A : Matrix (Fin 2) (Fin 2) ℚ := !![1, 0; 1, 1]
    let L : Matrix (Fin 2) (Fin 2) ℚ := !![1, 0; 1, 1]
    A = L * !![1, 0; 0, 1] := by decide

-- The structural fact: Gram-Schmidt produces an orthonormal system.
-- Mathlib: gramSchmidt_orthogonal in Analysis.InnerProductSpace.GramSchmidtOrtho
open inner_product_geometry in
theorem gs_orthogonal_alias :
    ∀ (ι : Type*) [Fintype ι] [LinearOrder ι] [LocallyFiniteOrder ι]
      (E : Type*) [RCLike ℝ] [SeminormedAddCommGroup E] [InnerProductSpace ℝ E]
      (f : ι → E) (a b : ι), a ≠ b →
      @inner ℝ E _ (gramSchmidt ℝ f a) (gramSchmidt ℝ f b) = 0 :=
  fun ι _ _ _ E _ _ _ f a b h => gramSchmidt_orthogonal ℝ f h