gram_schmidt

Gram-Schmidt Process

Statement

Given any basis $\{{\mathrm{v}}_1,\dots ,{\mathrm{v}}_n\}$ for an $n$-dimensional vector space, the Gram-Schmidt process produces an orthonormal basis $\{{\hat{\mathrm{u}}}_1,\dots ,{\hat{\mathrm{u}}}_n\}$ for the same space such that $\mathrm{span}\{{\hat{\mathrm{u}}}_1,\dots ,{\hat{\mathrm{u}}}_k\}=\mathrm{span}\{{\mathrm{v}}_1,\dots ,{\mathrm{v}}_k\}$ for all $k$.

Assumptions

• $\{{\mathrm{v}}_1,\dots ,{\mathrm{v}}_n\}$ is a basis (linearly independent spanning set) for a finite-dimensional inner product space over $\mathbb{R}$.
• No ${\mathrm{v}}_k$ is zero (guaranteed by linear independence).

Proof Sketch

At each step $k$, subtract from ${\mathrm{v}}_k$ its projections onto all previously constructed orthogonal vectors ${\mathrm{u}}_1,\dots ,{\mathrm{u}}_{k-1}$. The residual is nonzero (because ${\mathrm{v}}_k$ is not in $\mathrm{span}\{{\mathrm{v}}_1,\dots ,{\mathrm{v}}_{k-1}\}$) and orthogonal to all prior vectors by construction. Normalising gives a unit vector. Since each ${\mathrm{u}}_k$ is a linear combination of ${\mathrm{v}}_1,\dots ,{\mathrm{v}}_k$, the intermediate spans are preserved.

Full Proof

Algorithm. Set ${\mathrm{u}}_1={\mathrm{v}}_1$. For $k=2,\dots ,n$:

$${\mathrm{u}}_k={\mathrm{v}}_k-\sum _{j=1}^{k-1}\frac{{\mathrm{u}}_j^T{\mathrm{v}}_k}{{\mathrm{u}}_j^T{\mathrm{u}}_j}{\mathrm{u}}_j.$$

Normalize:

$${\hat{\mathrm{u}}}_k=\frac{{\mathrm{u}}_k}{({\mathrm{u}}_k^T{\mathrm{u}}_k{)}^{1/2}}.$$

Orthogonality. For $i<k$:

$${\mathrm{u}}_i^T{\mathrm{u}}_k={\mathrm{u}}_i^T{\mathrm{v}}_k-\frac{{\mathrm{u}}_i^T{\mathrm{v}}_k}{{\mathrm{u}}_i^T{\mathrm{u}}_i}({\mathrm{u}}_i^T{\mathrm{u}}_i)-\sum _{j\ne i}\frac{{\mathrm{u}}_j^T{\mathrm{v}}_k}{{\mathrm{u}}_j^T{\mathrm{u}}_j}({\mathrm{u}}_i^T{\mathrm{u}}_j)={\mathrm{u}}_i^T{\mathrm{v}}_k-{\mathrm{u}}_i^T{\mathrm{v}}_k=0,$$

where ${\mathrm{u}}_i^T{\mathrm{u}}_j=0$ for $j\ne i$ by induction.

Non-degeneracy. ${\mathrm{u}}_k\ne 0$ because ${\mathrm{v}}_k\notin \mathrm{span}\{{\mathrm{v}}_1,\dots ,{\mathrm{v}}_{k-1}\}=\mathrm{span}\{{\mathrm{u}}_1,\dots ,{\mathrm{u}}_{k-1}\}$; if ${\mathrm{u}}_k=0$ then ${\mathrm{v}}_k$ would be a linear combination of ${\mathrm{u}}_1,\dots ,{\mathrm{u}}_{k-1}$, contradicting linear independence.

Span preservation. Each ${\mathrm{u}}_k={\mathrm{v}}_k-{\sum }_{j<k}(\cdot ){\mathrm{u}}_j$ is a linear combination of ${\mathrm{v}}_1,\dots ,{\mathrm{v}}_k$, so $\mathrm{span}\{{\mathrm{u}}_1,\dots ,{\mathrm{u}}_k\}\subseteq \mathrm{span}\{{\mathrm{v}}_1,\dots ,{\mathrm{v}}_k\}$. Both sets have the same cardinality $k$ and are linearly independent (orthogonal vectors are independent), so the spans are equal.

Example. For the basis $\left\{\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)\right\}$:

$${\mathrm{u}}_1=\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),{\mathrm{u}}_2=\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)-\frac{2}{3}\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)=\frac{1}{3}\left(\begin{array}{c}-2\\ 1\\ 1\end{array}\right),$$

giving the orthonormal basis $\left\{\frac{1}{\sqrt{3}}\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\frac{1}{\sqrt{6}}\left(\begin{array}{c}-2\\ 1\\ 1\end{array}\right)\right\}$.

Notes / Intuition

Each step is a projection-and-subtract: we remove from ${\mathrm{v}}_k$ everything it “shares” with the already-built directions, leaving only a genuinely new orthogonal component. This is the constructive heart of the QR decomposition ($\mathrm{A}=\mathrm{QR}$, where $\mathrm{Q}$ has the ${\hat{\mathrm{u}}}_k$ as columns). Classical Gram-Schmidt is numerically unstable; the modified variant (subtracting projections one at a time) is preferred in practice.

Links

• Span, Basis and Dimension
• Orthogonal Projections
• Vector Space