Back to the on-screen lesson ·
Turning any basis into an orthonormal one by subtracting projections, why the span is unchanged at every stage, the factorisation $A = QR$ that records the coefficients, and why the classical process is fragile in floating point.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run the Gram-Schmidt process on a list of independent vectors, explain in one line why each new vector is orthogonal to all the earlier ones and why the span is unchanged at every stage, normalise at the right moment, read the entries of $R$ off the coefficients and lengths the process already computed, say why $R$ is upper triangular for a structural reason rather than by accident, and run the same process under an inner product that is not the dot product.
The projection onto a subspace was $\operatorname{proj}_W b = (b \cdot q_1)q_1 + \dots + (b \cdot q_k)q_k$, and it was true only for an orthonormal $q_1, \dots, q_k$. A subspace usually arrives as the span of a basis that is nothing of the kind. This lesson is the missing step: given any basis, manufacture an orthonormal one for the same subspace.
The Gram-Schmidt process turns a list of independent vectors into an orthonormal list with the same span. Normalising a non-zero vector means dividing it by its own length, leaving a unit vector in the same direction. The QR factorisation of an $m \times n$ matrix $A$ of independent columns is $A = QR$ with $Q$ of orthonormal columns and $R$ upper triangular with positive diagonal; it is the process, written as a product.
Take independent $v_1, \dots, v_n$. Build orthogonal $w_1, \dots, w_n$ one at a time:
$$w_1 = v_1, \qquad w_k = v_k - \sum_{j<k} \frac{w_j \cdot v_k}{w_j \cdot w_j}\,w_j.$$
In words: take the next vector and remove from it every component lying along a direction you have already made orthogonal. What is left points in a direction none of them reaches.
Why $w_k$ is orthogonal to each earlier $w_i$. Dot the formula with $w_i$. The sum has one surviving term — the $j = i$ one, since the others contain $w_j \cdot w_i = 0$ — and it contributes exactly $\dfrac{w_i \cdot v_k}{w_i \cdot w_i}(w_i \cdot w_i) = w_i \cdot v_k$, which cancels the $w_i \cdot v_k$ coming from $v_k$. Zero. That single cancellation is the whole proof, and it is the reason for the denominator.
Why the span never changes. At every stage $w_k$ is $v_k$ plus a combination of earlier vectors, and $v_k$ is $w_k$ plus a combination of earlier vectors. Each list is built from the other, so at every $k$,
$$\operatorname{span}\{w_1, \dots, w_k\} = \operatorname{span}\{v_1, \dots, v_k\}.$$
The equality holds stage by stage, not merely at the end, and that nested version is what the triangular shape of $R$ records.
Normalising. Finally set $q_k = w_k / |w_k|$. Dividing by a positive number does not turn a vector, so the orthogonality and the spans are untouched, and every $q_k$ now has length one.
None of the $w_k$ can come out zero, because a zero $w_k$ would put $v_k$ in the span of the earlier vectors and the list was independent. A zero does appear if the input is dependent, and that is how the process detects it.
Another way: picture
Two vectors leaning together in the plane. Keep the first. To fix the second, drop its shadow onto the first and slide the shadow away — what remains stands at a right angle. In three dimensions the third vector has two shadows to lose, one on each direction already fixed, and what survives points out of their plane. At no point does the room change: only the set of arrows describing it.
Another way: steps
Normalise as you go and read the process backwards. Each $v_k$ was built from $q_1, \dots, q_k$ and nothing later, so
$$v_1 = r_{11}q_1, \quad v_2 = r_{12}q_1 + r_{22}q_2, \quad v_3 = r_{13}q_1 + r_{23}q_2 + r_{33}q_3, \ \dots$$
Stacking those as columns is exactly $A = QR$, with $Q$ holding the $q_k$ and $R$ holding the coefficients. $R$ is upper triangular for a structural reason: $v_k$ cannot contain a $q_j$ for $j > k$, because $q_j$ had not been invented when $v_k$ was expanded.
The entries are the numbers the process already computed: $r_{jk} = q_j \cdot v_k$ above the diagonal, and $r_{kk} = |w_k|$ on it, the length of what survived the subtractions. The diagonal is positive by construction, which makes the factorisation unique.
Two payoffs. Solving $Ax = b$ becomes $Rx = Q^{T}b$ — a triangular system, solved by back-substitution, because $Q^{-1} = Q^{T}$ costs nothing. And $A^{T}A = R^{T}Q^{T}QR = R^{T}R$, which is the next lesson's normal-equations matrix arriving already factorised.
On paper Gram-Schmidt is exact. In floating-point arithmetic it is not, and the failure is worth knowing about because it is the standard example of a correct algorithm that should not be used as written.
When two input vectors are nearly parallel, $w_2 = v_2 - c\,v_1$ is the difference of two nearly equal vectors. Almost all the leading digits cancel, and what survives is dominated by the rounding error in $c$. The computed $q_2$ then fails to be orthogonal to $q_1$ by an amount that grows with how nearly parallel the inputs were — and the error propagates, because $q_3$ is corrected against a $q_2$ that is already wrong.
Modified Gram-Schmidt fixes most of it by reordering the arithmetic: instead of computing all the projections of $v_k$ against the original $v_k$ and subtracting them together, subtract each one and use the updated vector for the next projection. The two are identical in exact arithmetic and behave quite differently in practice. Serious software uses Householder reflections instead, which build $Q$ from reflections and never form a small difference at all.
The lesson to carry forward: identical formulas can have different numerical fates, and the deciding factor is usually whether the algorithm ever subtracts two nearly equal quantities.
Projecting onto the original vectors instead of the new ones. From the third vector onward, the subtraction must use $w_1, w_2, \dots$ — the vectors already made orthogonal — not $v_1, v_2, \dots$. Using the originals gives a $w_3$ that is perpendicular to nothing in particular.
Forgetting the denominator. $v_k - (w_j \cdot v_k)w_j$ is only right when $w_j$ is already of unit length. With unnormalised $w_j$ the coefficient must be divided by $w_j \cdot w_j$, and omitting it overshoots by exactly that factor.
Normalising too early, by hand. It is legitimate but it fills every later subtraction with square roots. Orthogonalise first with whole numbers where you can, and normalise at the end.
Expecting the output to be unique. Change the order of the input vectors and you get a different orthonormal basis for the same subspace. The process depends on the order, and only the span it produces at each stage is forced.
Assuming an orthogonal output means an orthonormal one. The $w_k$ are orthogonal; only the $q_k$ are orthonormal. The projection formula with no denominators needs the latter.
$v_1 = (3, 0)$, $v_2 = (2, 5)$. Keep $w_1 = (3, 0)$; the coefficient is $\dfrac{w_1 \cdot v_2}{w_1 \cdot w_1} = \dfrac{6}{9} = \dfrac{2}{3}$.
Dot product over squared length.
$w_2 = (2, 5) - \tfrac{2}{3}(3, 0) = (0, 5)$. Check: $(3,0) \cdot (0,5) = 0$.
Always check before normalising.
Normalise: $q_1 = (1, 0)$, $q_2 = (0, 1)$. And $R = \begin{pmatrix} 3 & 2 \\ 0 & 5\end{pmatrix}$, whose entries are the lengths $3$ and $5$ and the coefficient $q_1 \cdot v_2 = 2$.
The numbers were all computed already.
$w_1 = (1,1,0)$ and $w_2 = (1,-1,0)$ are already orthogonal; take $v_3 = (2, 0, 7)$.
A head start on the first two.
$\dfrac{w_1 \cdot v_3}{w_1 \cdot w_1} = \dfrac{2}{2} = 1$ and $\dfrac{w_2 \cdot v_3}{w_2 \cdot w_2} = \dfrac{2}{2} = 1$.
One coefficient per earlier direction.
$w_3 = (2,0,7) - (1,1,0) - (1,-1,0) = (0,0,7)$, orthogonal to both. Subtracting only the first correction would have left $(1,-1,7)$, which is not orthogonal to $w_2$.
Both, or neither works.
$v_1 \cdot v_2 = 4 + 6 = 10$ and $v_1 \cdot v_1 = 1 + 4 = 5$, so the coefficient is $2$.
Both dot products first.
$w_2 = (4,3) - 2(1,2) = (2, -1)$.
Subtract that multiple of $v_1$.
Check: $(1,2) \cdot (2,-1) = 2 - 2 = 0$. Normalising would divide each by $\sqrt5$, and $R = \begin{pmatrix} \sqrt5 & 2\sqrt5 \\ 0 & \sqrt5 \end{pmatrix}$.
$v_1 = (1, 1)$ and $v_2 = (6, 4)$. Write $w_2 = v_2 - \operatorname{proj}_{v_1}v_2$ as a column.
This task has no paper form; do it on a device.
$v_1 = (1, 1, 1)$ and $v_2 = (4, 4, 1)$. Gram-Schmidt forms $v_2 - c\,v_1$. What is $c$?
Answer:
$A$ has columns $v_1 = (3, 4)$ and $v_2 = (45, 5)$. In $A = QR$ with orthonormal $Q$ and upper triangular $R$ of positive diagonal, write $R$.
This task has no paper form; do it on a device.
Independent vectors $v_1, v_2, v_3$ in $\mathbb{R}^{5}$ are to be replaced by an orthonormal basis of their span. Put the steps in order.
Number the steps in order (write the number in the box):
$w_2 = v_2 - c\,v_1$ with $c = \dfrac{v_1 \cdot v_2}{v_1 \cdot v_1}$. What is true of $\{v_1, w_2\}$?
Use $\langle u, v \rangle = u_1v_1 + 3\,u_2v_2$ in place of the dot product, with $v_1 = (1, 1)$ and $v_2 = (2, 2)$. Fill in the three quantities a Gram-Schmidt step needs.
| Value | |
|---|---|
| $\langle v_1, v_2 \rangle$ | |
| $\langle v_1, v_1 \rangle$ | |
| $c$ |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
$v_1 = (1, 1)$ and $v_2 = (8, 6)$. Write $w_2 = v_2 - \operatorname{proj}_{v_1}v_2$ as a column.
This task has no paper form; do it on a device.
You can orthogonalise a basis, normalise it, and write the QR factorisation whose entries the process produced. Say in your own words why the span is the same after every step. Next: what an orthonormal basis of a column space does for a system that has no solution at all.
10. Your turn: orthogonalise $v_1 = (1, 2)$ and $v_2 = (4, 3)$, step 3
The check costs one line.