Gram–Schmidt Process

Turn any basis into an orthonormal one by subtracting projections.

The idea

The Gram–Schmidt process is an algorithm that converts a list of linearly independent vectors $a_{1}, \dots, a_{n}$ into an orthonormal list $q_{1}, \dots, q_{n}$ — vectors mutually perpendicular, each of length $1$ — with the same span.

An orthonormal basis makes coordinates effortless. The component of a vector $x$ along $q_{j}$ is the single number $q_{j}^{\top}x$, with no system to solve, because the other basis vectors contribute nothing to that dot product.

The algorithm handles one vector at a time. The first needs only rescaling: $q_{1} = a_{1} / \lVert a_{1} \rVert$. Each later $a_{k}$ may lean partly along the directions already built, and the part of $a_{k}$ along a unit vector $q_{j}$ is the projection $(q_{j}^{\top}a_{k})\,q_{j}$. Subtracting all of these, $v_{k} = a_{k} - (q_{1}^{\top}a_{k})\,q_{1} - \cdots - (q_{k-1}^{\top}a_{k})\,q_{k-1},$ leaves a vector perpendicular to every earlier $q_{j}$: dot $v_{k}$ with any $q_{j}$ and the terms cancel. The figure shows the first such step, $v_{2} = a_{2} - (q_{1}^{\top}a_{2})\,q_{1}$. Normalizing, $q_{k} = v_{k} / \lVert v_{k} \rVert$, completes the step, and independence of the original list guarantees $v_{k} \neq 0$, so the algorithm never divides by zero.

Algorithm.

Algorithm: Gram–Schmidt Input: linearly independent vectors a_1, ..., a_n Output: orthonormal q_1, ..., q_n with the same span 1. q_1 = a_1 / ‖a_1‖ 2. k = 2 3. v_k = a_k - Σ_(j<k) (q_j·a_k) q_j // subtract the projections onto the q's built so far 4. q_k = v_k / ‖v_k‖ // independence guarantees v_k ≠ 0 5. k = k + 1; if k ≤ n, go to step 3 6. return q_1, ..., q_n

Ways to work on it

• Walkthrough. Normalize, project, subtract — build an orthonormal basis step by step.
• Practice. Subtract a projection to get the next orthogonal vector.
• Hardest. Full Gram–Schmidt on three vectors, removing two projections.

Not sure where to start? Take the ten-question placement test.