---
title: The Gram-Schmidt Process and QR Factorization
module: Orthogonality and Least Squares
moduleNumber: 6
lessonNumber: 3
order: 603
summary: >
  Gram-Schmidt turns any basis into an orthogonal one by repeatedly subtracting
  off projections onto the span already built. Normalizing the result and
  recording the coefficients factors the matrix as A = QR, with Q orthonormal
  and R upper triangular, the factorization behind stable least-squares and
  eigenvalue algorithms.
topics: [Orthogonality and Least Squares]
sources:
  - book: Lay
    ref: "§6.4 The Gram-Schmidt Process"
---

An orthogonal basis makes coordinates and projections trivial, but a subspace
usually arrives with an arbitrary basis instead. The Gram–Schmidt process converts
one into the other: given any basis for a subspace, it produces an orthogonal basis
for the same subspace, one vector at a time. Recording the arithmetic as a matrix
product yields the QR factorization, the numerically preferred route to
least-squares solutions and eigenvalues.

## Subtracting the projection

Start with a basis $\{\mathbf{x}_1, \dots, \mathbf{x}_p\}$ of a subspace $W$. Keep
the first vector, $\mathbf{v}_1 = \mathbf{x}_1$. To make the second vector
orthogonal to the first, subtract from $\mathbf{x}_2$ its projection onto the line
$W_1 = \operatorname{Span}\{\mathbf{v}_1\}$:
$$
\mathbf{v}_2 = \mathbf{x}_2 - \operatorname{proj}_{W_1}\mathbf{x}_2
  = \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{v}_1}
  {\mathbf{v}_1 \cdot \mathbf{v}_1}\, \mathbf{v}_1.
$$
By the orthogonal decomposition theorem, $\mathbf{v}_2$ is the component of
$\mathbf{x}_2$ orthogonal to $\mathbf{v}_1$, and it stays in $W$ because it is a
combination of $\mathbf{x}_2$ and $\mathbf{x}_1$. Each later vector subtracts its
projection onto the span of _all_ the orthogonal vectors already built.

$$
% caption: One Gram-Schmidt step in R^3: v2 is x2 minus its projection p onto the
% line through x1, leaving the part of x2 perpendicular to x1 while staying in the
% plane W.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\fill[acc!10] (-0.4,-0.4) -- (5.0,-0.4) -- (5.6,1.4) -- (0.2,1.4) -- cycle;
\draw[acc, thick] (-0.4,-0.4) -- (5.0,-0.4) -- (5.6,1.4) -- (0.2,1.4) -- cycle;
\node[acc] at (5.15,-0.15) {$W$};
\coordinate (o) at (0.6,0.0);
\coordinate (x1) at (3.6,0.0);
\coordinate (p) at (2.4,0.0);
\coordinate (x2) at (2.4,1.9);
\draw[->, acc, very thick] (o) -- (x1) node[below right] {$\mathbf{x}_1=\mathbf{v}_1$};
\draw[->, black, very thick] (o) -- (x2) node[above] {$\mathbf{x}_2$};
\draw[->, acc, thick] (o) -- (p) node[below] {$\mathbf{p}$};
\draw[->, black, very thick] (p) -- (x2) node[midway, right] {$\mathbf{v}_2$};
\draw[black] (2.4,0.22) -- (2.18,0.22) -- (2.18,0);
\fill[black] (o) circle (1.6pt);
\end{tikzpicture}
$$

## The general process

> **Theorem (Gram–Schmidt process).** Given a basis
> $\{\mathbf{x}_1, \dots, \mathbf{x}_p\}$ for a nonzero subspace $W$ of
> $\mathbb{R}^n$, define
> $$
> \begin{aligned}
> \mathbf{v}_1 &= \mathbf{x}_1, \\
> \mathbf{v}_2 &= \mathbf{x}_2
>   - \frac{\mathbf{x}_2\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\mathbf{v}_1, \\
> &\ \ \vdots \\
> \mathbf{v}_p &= \mathbf{x}_p
>   - \frac{\mathbf{x}_p\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\mathbf{v}_1
>   - \cdots
>   - \frac{\mathbf{x}_p\cdot\mathbf{v}_{p-1}}{\mathbf{v}_{p-1}\cdot\mathbf{v}_{p-1}}\mathbf{v}_{p-1}.
> \end{aligned}
> $$
> Then $\{\mathbf{v}_1, \dots, \mathbf{v}_p\}$ is an orthogonal basis for $W$, and
> $\operatorname{Span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\}
> = \operatorname{Span}\{\mathbf{x}_1, \dots, \mathbf{x}_k\}$ for each $k$.

The span condition is the point of the construction: the orthogonal set built from
the first $k$ inputs spans exactly the same subspace $W_k$ as those inputs. The
proof is induction. Suppose $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is an
orthogonal basis for $W_k = \operatorname{Span}\{\mathbf{x}_1, \dots,
\mathbf{x}_k\}$. Define $\mathbf{v}_{k+1} = \mathbf{x}_{k+1} -
\operatorname{proj}_{W_k}\mathbf{x}_{k+1}$. By the orthogonal decomposition theorem it is orthogonal to
$W_k$; it lies in $W_{k+1}$; and it is nonzero because $\mathbf{x}_{k+1}$ is not
in $W_k$. So $\{\mathbf{v}_1, \dots, \mathbf{v}_{k+1}\}$ is an orthogonal basis of
the $(k+1)$-dimensional space $W_{k+1}$.

$$
% caption: Gram-Schmidt builds a nested chain of subspaces: v1 spans a line, v2
% completes the plane W2, and v3 rises out of it, each new vector orthogonal to
% every one already built.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\fill[acc!10] (-0.3,-0.6) -- (4.6,-0.6) -- (5.4,0.8) -- (0.5,0.8) -- cycle;
\draw[acc, thick] (-0.3,-0.6) -- (4.6,-0.6) -- (5.4,0.8) -- (0.5,0.8) -- cycle;
\node[acc] at (5.05,-0.25) {$W_2$};
\coordinate (o) at (1.2,0.0);
\coordinate (v1) at (3.8,0.0);
\coordinate (v2) at (2.0,0.5);
\coordinate (v3) at (1.2,2.4);
\draw[->, acc, very thick] (o) -- (v1) node[right] {$\mathbf{v}_1$};
\draw[->, acc, very thick] (o) -- (v2) node[right] {$\mathbf{v}_2$};
\draw[->, black, very thick] (o) -- (v3) node[left] {$\mathbf{v}_3$};
\draw[black] (1.2,0.28) -- (1.45,0.28) -- (1.45,0.0);
\fill[black] (o) circle (1.6pt);
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Gram-Schmidt}(\mathbf{x}_1, \dots, \mathbf{x}_p)$ — orthogonal basis for the span
$\mathbf{v}_1 \gets \mathbf{x}_1$
for $k = 2$ to $p$ do
  $\mathbf{v}_k \gets \mathbf{x}_k$
  for $j = 1$ to $k-1$ do
    $\mathbf{v}_k \gets \mathbf{v}_k - \dfrac{\mathbf{x}_k \cdot \mathbf{v}_j}{\mathbf{v}_j \cdot \mathbf{v}_j}\, \mathbf{v}_j$ // remove the component along $\mathbf{v}_j$
return $\{\mathbf{v}_1, \dots, \mathbf{v}_p\}$
```

An orthonormal basis follows by normalizing each $\mathbf{v}_k$ at the end. Doing
so only after the orthogonal set is complete avoids writing square roots at every
step of a hand calculation.

## Orthogonalizing a basis

> **Worked example.** Orthogonalize the basis $\mathbf{x}_1 = (1, 1, 1, 1)$,
> $\mathbf{x}_2 = (0, 1, 1, 1)$, $\mathbf{x}_3 = (0, 0, 1, 1)$ of a subspace $W$ of
> $\mathbb{R}^4$.
>
> _Step 1._ $\mathbf{v}_1 = \mathbf{x}_1 = (1, 1, 1, 1)$.
>
> _Step 2._ With $\mathbf{x}_2 \cdot \mathbf{v}_1 = 3$ and
> $\mathbf{v}_1 \cdot \mathbf{v}_1 = 4$,
> $$
> \mathbf{v}_2 = \mathbf{x}_2 - \tfrac{3}{4}\mathbf{v}_1
>   = \left(-\tfrac{3}{4}, \tfrac{1}{4}, \tfrac{1}{4}, \tfrac{1}{4}\right).
> $$
> Scaling by $4$ gives the cleaner $\mathbf{v}_2' = (-3, 1, 1, 1)$, still
> orthogonal to $\mathbf{v}_1$.
>
> _Step 3._ Project $\mathbf{x}_3$ onto $W_2 = \operatorname{Span}\{\mathbf{v}_1,
> \mathbf{v}_2'\}$ using $\mathbf{x}_3 \cdot \mathbf{v}_1 = 2$,
> $\mathbf{x}_3 \cdot \mathbf{v}_2' = 2$, and
> $\mathbf{v}_2' \cdot \mathbf{v}_2' = 12$:
> $$
> \operatorname{proj}_{W_2}\mathbf{x}_3
>   = \tfrac{2}{4}\mathbf{v}_1 + \tfrac{2}{12}\mathbf{v}_2'
>   = \left(0, \tfrac{2}{3}, \tfrac{2}{3}, \tfrac{2}{3}\right),
> \qquad
> \mathbf{v}_3 = \mathbf{x}_3 - \operatorname{proj}_{W_2}\mathbf{x}_3
>   = \left(0, -\tfrac{2}{3}, \tfrac{1}{3}, \tfrac{1}{3}\right).
> $$
> Then $\{\mathbf{v}_1, \mathbf{v}_2', \mathbf{v}_3\}$ is an orthogonal basis for
> $W$. Normalizing each vector produces an orthonormal basis
> $\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}$.

## The QR factorization

Apply Gram–Schmidt with normalization to the _columns_ of a matrix. Each original
column $\mathbf{x}_k$ lies in $\operatorname{Span}\{\mathbf{u}_1, \dots,
\mathbf{u}_k\}$, so it is a combination of the first $k$ orthonormal vectors only.
Collecting those combinations as columns records the factorization.

> **Theorem (QR factorization).** If $A$ is an $m \times n$ matrix with
> linearly independent columns, then $A = QR$, where $Q$ is $m \times n$ with
> orthonormal columns forming a basis for $\operatorname{Col} A$, and $R$ is
> $n \times n$ upper triangular with positive diagonal entries.

Let $Q = [\,\mathbf{u}_1\ \cdots\ \mathbf{u}_n\,]$ be the orthonormal basis from
Gram–Schmidt. Because $\mathbf{x}_k \in \operatorname{Span}\{\mathbf{u}_1, \dots,
\mathbf{u}_k\}$, there are scalars with
$$
\mathbf{x}_k = r_{1k}\mathbf{u}_1 + \cdots + r_{kk}\mathbf{u}_k
  + 0\,\mathbf{u}_{k+1} + \cdots + 0\,\mathbf{u}_n,
$$
and the entries below the diagonal are zero, making $R = [r_{jk}]$ upper
triangular. Choosing $r_{kk} \ge 0$ (flip the sign of $\mathbf{u}_k$ if needed)
makes the diagonal positive. Then $\mathbf{x}_k = Q\mathbf{r}_k$ for each $k$, so
$A = QR$.

$$
% caption: A = QR splits an m-by-n matrix with independent columns into an
% orthonormal Q of the same shape and a small upper-triangular R; the shaded
% lower part of R is all zeros.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
% A
\draw[black, thick] (0,0) rectangle (1.5,3.0);
\node at (0.75,-0.4) {$A$};
\node[black] at (0.75,1.5) {$m$ by $n$};
\node at (2.05,1.5) {$=$};
% Q
\draw[acc, thick] (2.6,0) rectangle (4.1,3.0);
\foreach \x in {3.0,3.4,3.75} \draw[acc!55] (\x,0) -- (\x,3.0);
\node at (3.35,-0.4) {$Q$};
\node[black] at (3.35,1.5) {orthonormal};
% R
\draw[black, thick] (4.5,1.5) rectangle (6.0,3.0);
\fill[acc!12] (4.5,1.5) -- (6.0,1.5) -- (6.0,3.0) -- cycle;
\draw[black] (4.5,3.0) -- (6.0,1.5);
\node at (5.25,-0.4) {$R$};
\node[black] at (5.55,1.72) {$0$};
\node[black] at (5.25,3.35) {upper triangular};
\end{tikzpicture}
$$

Once $Q$ is known, $R$ is a single product. Since $Q^\top Q = I$,
$$
Q^\top A = Q^\top (QR) = R,
$$
so $R = Q^\top A$.

> **Worked example.** Assemble $A = QR$ from the columns
> $\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3$ orthogonalized above:
> $$
> A = \begin{bmatrix}
> 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1
> \end{bmatrix}.
> $$
> Normalizing the orthogonal basis $\{\mathbf{v}_1, \mathbf{v}_2', \mathbf{v}_3'\}$
> (with $\mathbf{v}_3' = 3\mathbf{v}_3$) gives
> $$
> Q = \begin{bmatrix}
>  1/2 & -3/\sqrt{12} & 0 \\
>  1/2 & 1/\sqrt{12} & -2/\sqrt{6} \\
>  1/2 & 1/\sqrt{12} & 1/\sqrt{6} \\
>  1/2 & 1/\sqrt{12} & 1/\sqrt{6}
> \end{bmatrix},
> \qquad
> R = Q^\top A = \begin{bmatrix}
>  2 & 3/2 & 1 \\
>  0 & 3/\sqrt{12} & 2/\sqrt{12} \\
>  0 & 0 & 2/\sqrt{6}
> \end{bmatrix}.
> $$
> The diagonal of $R$ is positive, and each column of $A$ is $Q$ times the
> corresponding column of $R$: $\mathbf{x}_1 = 2\mathbf{u}_1$ reads off
> $r_{11} = 2$, and the zeros below the diagonal record that $\mathbf{x}_1$ uses
> none of $\mathbf{u}_2$ or $\mathbf{u}_3$.

## Numerical stability of QR

The invertibility of $R$ is immediate: if $R\mathbf{x} = \mathbf{0}$, then
$A\mathbf{x} = QR\mathbf{x} = \mathbf{0}$, and the independent columns of $A$
force $\mathbf{x} = \mathbf{0}$. So $R^{-1}$ exists, and $A$ and $Q$ share the same
column space.

In floating point, the classical Gram–Schmidt recurrence loses orthogonality:
rounding makes the computed $\mathbf{u}_j$ drift out of perpendicularity as $j$
grows. Reordering the subtractions (the _modified_ Gram–Schmidt variant) helps,
but production QR routines instead left-multiply $A$ by a sequence of orthogonal
reflectors until it becomes upper triangular. That approach parallels the
elementary-matrix reduction behind the
[LU factorization](/linear-algebra/matrix-algebra/partitioned-matrices-and-lu) and
yields a more accurate $Q$; the details belong to the
[numerical least-squares](/linear-algebra/numerical-linear-algebra/qr-and-numerical-least-squares)
lesson.

$$
% caption: In floating point the classical Gram-Schmidt recurrence loses
% orthogonality as the step index grows, while the reordered (modified) variant
% stays far closer to orthonormal.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\draw[->, black] (0,0) -- (5.6,0) node[right] {step $j$};
\draw[->, black] (0,0) -- (0,3.4) node[above, black] {drift};
\draw[black, very thick] (0.3,0.2) .. controls (2.6,0.4) and (3.6,1.9) .. (5.0,3.0);
\node[black] at (4.1,2.75) {classical};
\draw[acc, very thick] (0.3,0.2) .. controls (2.6,0.3) and (4.0,0.5) .. (5.0,0.9);
\node[acc] at (4.1,0.55) {reordered};
\end{tikzpicture}
$$

| Method | Output | Cost | Numerical behavior |
| --- | --- | --- | --- |
| Classical Gram–Schmidt | $\{\mathbf{v}_k\}$ then normalize | low | orthogonality degrades for large $j$ |
| Modified Gram–Schmidt | same, reordered updates | low | markedly better, still imperfect |
| Reflector-based QR | $A = QR$ | about twice | most accurate $Q$ |

## Summary

- **Gram–Schmidt** converts a basis into an orthogonal basis by subtracting, from
  each vector, its projection onto the span of the vectors already orthogonalized,
  preserving the span at every step.
- **Normalization** at the end gives an orthonormal basis, the columns of $Q$.
- **QR factorization** $A = QR$ records the process as a matrix product: $Q$ has
  orthonormal columns spanning $\operatorname{Col} A$, and $R = Q^\top A$ is upper
  triangular and invertible.

The QR factorization gives a stable route to the
[least-squares solution](/linear-algebra/orthogonality-least-squares/least-squares-problems)
$\hat{\mathbf{x}} = R^{-1}Q^\top\mathbf{b}$ of an inconsistent system.[^lay-64]

[^lay-64]: Lay, §6.4 — The Gram–Schmidt Process: Theorem 11 (orthogonalization with the span property), the orthonormal variant, and Theorem 12 (the QR factorization $A = QR$ with $R = Q^\top A$), including the numerical notes on loss of orthogonality.