Gram-Schmidt Process

The Gram-Schmidt process converts any set of independent vectors into an orthogonal basis for the same space.

Algorithm

Given vectors $\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n$:

1. $\mathbf{q}_1 = \frac{\mathbf{a}_1}{\|\mathbf{a}_1\|}$

2. $\mathbf{q}_2 = \frac{\mathbf{a}_2 - (\mathbf{a}_2 \cdot \mathbf{q}_1)\mathbf{q}_1}{\|\cdots\|}$

3. $\mathbf{q}_3 = \frac{\mathbf{a}_3 - (\mathbf{a}_3 \cdot \mathbf{q}_1)\mathbf{q}_1 - (\mathbf{a}_3 \cdot \mathbf{q}_2)\mathbf{q}_2}{\|\cdots\|}$

Each step: subtract the projections onto all previous $\mathbf{q}$'s, then normalize.

QR Factorization

Gram-Schmidt produces:

$$A = QR$$

Where:

• $Q$ — orthogonal matrix (columns are orthonormal)
• $R$ — upper triangular matrix

Why QR Is Better Than $A$

• $Q^TQ = I$ (easy to invert)
• Solving $Ax = b$ becomes $Rx = Q^Tb$ (no need for $A^TA$)