The Gram-Schmidt Process

The Gram–Schmidt process is the theoretical proof, and a practical algorithm, behind the QR factorization of a matrix: writing $A = QR$ with $Q$ orthogonal (or unitary) and $R$ upper triangular, used to solve least-squares problems, compute eigenvalues via the QR algorithm, and stabilize numerical linear algebra computations. In statistics, orthogonalizing regressors via Gram–Schmidt underlies sequential (Type I) sums of squares and the construction of orthogonal polynomial regression bases. In numerical analysis and approximation theory, applying the process to the monomials $1,x,x^2,\dots$ on an interval with a weighted inner product produces classical families of orthogonal polynomials, such as Legendre and Chebyshev polynomials. In quantum mechanics and more broadly in the theory of Hilbert spaces, Gram–Schmidt constructs orthonormal bases of state spaces from convenient but non-orthogonal spanning sets. In signal processing and coding theory, orthogonalizing a set of basis signals or codewords (as in some lattice reduction and precoding schemes) relies on the same recursive projection-and-subtract idea, and modified variants of the algorithm are used for numerically stable orthogonalization in large-scale linear algebra software.

Ask the tutor: How does the Gram-Schmidt process change if I only need an orthogonal (not orthonormal) list, and why might I prefer to skip normalization until the end?

Picture building an orthonormal list one vector at a time, always working inside the growing subspace spanned by the vectors processed so far. The first vector $v_1$ only needs rescaling: divide by its length to make it a unit vector $e_1$. This changes nothing about direction. The second vector $v_2$ is not generally orthogonal to $e_1$. But we can decompose $v_2$ into a piece parallel to $e_1$ and a piece orthogonal to it: the parallel piece is the orthogonal projection $\langle v_2, e_1\rangle e_1$, and subtracting it off leaves the orthogonal remainder $u_2 = v_2 - \langle v_2,e_1\rangle e_1$. Normalizing $u_2$ gives $e_2$, a unit vector orthogonal to $e_1$ and lying in $\mathrm{span}(v_1,v_2)$. The pattern repeats: at stage $k$, subtract from $v_k$ its projection onto the entire subspace spanned by the previously constructed orthonormal vectors $e_1,\dots,e_{k-1}$. What remains, $u_k$, is orthogonal to all of $e_1,\dots,e_{k-1}$ by construction, and it is nonzero precisely because $v_k$ was not already in $\mathrm{span}(v_1,\dots,v_{k-1})$ — this is exactly where linear independence is used. Normalizing produces $e_k$. The crucial invariant, illustrated below, is that no information about the span is ever lost: $\mathrm{span}(e_1,\dots,e_k)$ always equals $\mathrm{span}(v_1,\dots,v_k)$, so the new orthonormal list "sits inside" the old flag of subspaces at every stage.

Example 1: an asymmetric list in $\mathbb{R}^3$. Let $V = \mathbb{R}^3$ with the standard inner product, and let

First check linear independence: the matrix with these as rows,

has determinant $1(0\cdot1 - 1\cdot3) - 1(2\cdot1-1\cdot0) + 0 = 1(-3) - 1(2) + 0 = -5 \ne 0$, so $(v_1,v_2,v_3)$ is linearly independent.

Step 1. $\|v_1\| = \sqrt{1^2+1^2+0^2} = \sqrt2$, so

Step 2. Compute $\langle v_2, e_1\rangle = \frac{1}{\sqrt2}(2\cdot1 + 0\cdot1 + 1\cdot0) = \frac{2}{\sqrt2} = \sqrt2$. Then

Check orthogonality directly: $\langle u_2, v_1\rangle = 1\cdot1 + (-1)\cdot1 + 1\cdot0 = 0$. Good. Now $\|u_2\| = \sqrt{1+1+1} = \sqrt3$, so

Step 3. Compute $\langle v_3,e_1\rangle = \frac{1}{\sqrt2}(0\cdot1 + 3\cdot1 + 1\cdot0) = \frac{3}{\sqrt2}$, and $\langle v_3, e_2\rangle = \frac{1}{\sqrt3}(0\cdot1 + 3\cdot(-1) + 1\cdot1) = \frac{-2}{\sqrt3}$. Then

Compute each piece: $\frac{3}{\sqrt2}\cdot\frac{1}{\sqrt2}(1,1,0) = \frac{3}{2}(1,1,0) = (1.5, 1.5, 0)$, and $\frac{2}{\sqrt3}\cdot\frac{1}{\sqrt3}(1,-1,1) = \frac{2}{3}(1,-1,1) = (2/3, -2/3, 2/3)$. So

Converting to thirds: $-1.5 = -3/2 = -9/6$, $2/3 = 4/6$, sum $= -5/6$. Similarly $1.5 - 2/3 = 9/6 - 4/6 = 5/6$. And $1+2/3 = 5/3 = 10/6$. So

Sanity check: $\langle u_3, e_1\rangle$ should be $0$: $\frac{1}{\sqrt2}(-\tfrac56 + \tfrac56) = 0$. ✓. And $\langle u_3,e_2\rangle = \frac{1}{\sqrt3}\left(-\tfrac56\cdot1 + \tfrac56\cdot(-1) + \tfrac{5}{3}\cdot1\right) = \frac{1}{\sqrt3}\left(-\tfrac56-\tfrac56+\tfrac{10}{6}\right) = \frac{1}{\sqrt3}(0) = 0$. ✓ Now $\|u_3\| = \tfrac56\sqrt{1+1+4} = \tfrac56\sqrt6$, so

Final answer:

One can verify $\mathrm{span}(e_1,e_2) = \mathrm{span}(v_1,v_2)$ by checking both $v_1,v_2 \in \mathrm{span}(e_1,e_2)$ (immediate from the recursion) and vice versa.

Example 2: a complex inner product space, $\mathbb{C}^2$. Let $V=\mathbb{C}^2$ with $\langle x,y\rangle = x_1\overline{y_1} + x_2\overline{y_2}$ (linear in the first slot, conjugate-linear in the second). Take

Check independence: if $c_1 v_1 + c_2 v_2 = 0$ then $c_1 + 2c_2 = 0$ and $c_1 i + c_2(1-i) = 0$; substituting $c_1=-2c_2$ into the second gives $-2ic_2 + c_2(1-i) = c_2(1-3i) = 0$, forcing $c_2=0$ (since $1-3i\ne0$) and then $c_1=0$. So the list is independent.

Step 1. $\|v_1\|^2 = 1\cdot\overline1 + i\overline i = 1 + i(-i) = 1+1 = 2$, so $\|v_1\|=\sqrt2$ and

Step 2. Compute $\langle v_2, e_1\rangle = \frac{1}{\sqrt2}\left(2\cdot\overline{1} + (1-i)\cdot\overline{i}\right) = \frac{1}{\sqrt2}\left(2 + (1-i)(-i)\right)$. Compute $(1-i)(-i) = -i + i^2 = -i - 1$. So the bracket is $2 + (-1-i) = 1 - i$. Thus

Then

Compute $\frac{1-i}{2}(1,i) = \left(\frac{1-i}{2},\ \frac{i(1-i)}{2}\right) = \left(\frac{1-i}{2},\ \frac{i+1}{2}\right)$ (since $i(1-i) = i - i^2 = i+1$). So

Check orthogonality: $\langle u_2, e_1\rangle$ should vanish. Using linearity in the first slot and conjugate-linearity in the second, since we already engineered this, we trust the algebra but verify numerically:

Compute $\frac{1-3i}{2}\cdot(-i) = \frac{-i + 3i^2}{2} = \frac{-i-3}{2}$. Sum: $\frac{3+i}{2} + \frac{-3-i}{2} = 0$. ✓ Now compute $\|u_2\|^2 = \left|\frac{3+i}{2}\right|^2 + \left|\frac{1-3i}{2}\right|^2 = \frac{9+1}{4} + \frac{1+9}{4} = \frac{10}{4}+\frac{10}{4} = 5$. So $\|u_2\| = \sqrt5$ and

This example illustrates the extra bookkeeping care required with the conjugate: the inner product $\langle v_2,e_1\rangle$ is generally a complex number, and one must remember which slot is conjugate-linear when computing both the projection coefficient and its conjugate appearing in later verifications.