An orthogonal basis makes coordinates cheap: each coefficient is one dot product, with no system to solve. The catch is that the bases you actually meet (the columns of a matrix, the vectors row reduction hands you) are almost never orthogonal. Gram–Schmidt is the fix. It takes any basis and straightens it out, one vector at a time, without changing what it spans. Written with matrices, the same computation factors a matrix as $A = QR$, one of the workhorses of numerical computing: it solves systems without magnifying rounding errors, it's how least squares gets solved in practice, and repeated over and over it finds eigenvalues.
Two arrows at an awkward angle make a perfectly good basis for the plane, but measuring with them is a chore. Arrows at right angles are much nicer: to find how much of a vector points along each one, you just drop its shadow. This page turns any two arrows (or three, in space) into perpendicular ones. The trick is to knock off each arrow's shadow on the arrows before it. What's left stands at a right angle, and it still lives in the same plane.
On Inner Products, the coordinates of $y$ in an orthogonal basis came out as $\frac{y \cdot v_i}{\|v_i\|^2}$, one dot product each. That only works when the basis is orthogonal to begin with. This page makes it orthogonal.
The shadow of $v_2$ on $v_1$ is the part of $v_2$ that points along $v_1$. Take it away and what's left points straight off that line. That's the whole idea; the rest of the page is bookkeeping, and then a surprising amount of payoff.
The shadow is the projection from Dot & Cross Products, $\proj_u v = \frac{v \cdot u}{u \cdot u}\,u$, and that page already showed that what's left over, $v - \proj_u v$, is orthogonal to $u$. So one step of straightening is one subtraction. Here it is on Hefferon's first example.
Start from $v_1 = (4, 2)$ and $v_2 = (1, 3)$. Find an orthogonal basis of $\R^2$ from them, then an orthonormal one.
Keep the first vector: $u_1 = v_1 = (4, 2)$. The shadow of $v_2$ on it has $v_2 \cdot u_1 = 4 + 6 = 10$ and $u_1 \cdot u_1 = 16 + 4 = 20$, so
$$\proj_{u_1} v_2 = \tfrac{10}{20}(4, 2) = (2, 1), \qquad u_2 = v_2 - \proj_{u_1} v_2 = (1, 3) - (2, 1) = (-1, 2).$$Check: $u_1 \cdot u_2 = -4 + 4 = 0$. The lengths are $\|u_1\| = \sqrt{20} = 2\sqrt5$ and $\|u_2\| = \sqrt5$, so dividing gives the orthonormal basis $q_1 = \frac{1}{\sqrt5}(2, 1)$, $q_2 = \frac{1}{\sqrt5}(-1, 2)$.
Here's what the new basis buys. The slanted tiles of $v_1$ and $v_2$ become right-angled tiles of $u_1$ and $u_2$, covering the same plane, and finding the coordinates of a point like $(3, 4)$ takes two shadows instead of two equations: $\frac{(3, 4) \cdot (4, 2)}{20} = 1$ and $\frac{(3, 4) \cdot (-1, 2)}{5} = 1$, so $(3, 4) = u_1 + u_2$.
The one number in that computation is the $\frac{10}{20}$: how much of $v_1$ to subtract. Subtract too little and $v_2$ still leans along $v_1$; subtract too much and it leans the other way. Try finding it by hand.
Only one amount makes the dot product $0$, and it's always the shadow's coefficient $\frac{v_2 \cdot v_1}{v_1 \cdot v_1}$: negative when the two arrows make an obtuse angle, and the whole of $v_2$ when they lie on one line, which leaves nothing at all.
With more vectors, keep going: each new vector loses its shadow on every $u$ built so far. Because those $u$'s are already square to each other, their shadows don't get in each other's way, and what's left is square to all of them.
Let $v_1, \ldots, v_k$ be linearly independent vectors in $\R^n$. The Gram–Schmidt process builds $$\begin{aligned} u_1 &= v_1, \\ u_2 &= v_2 - \proj_{u_1} v_2, \\ u_3 &= v_3 - \proj_{u_1} v_3 - \proj_{u_2} v_3, \\ &\;\;\vdots \\ u_k &= v_k - \proj_{u_1} v_k - \cdots - \proj_{u_{k-1}} v_k, \end{aligned}$$ and then normalizes them: $q_i = \frac{1}{\|u_i\|}u_i$.
Start with two arrows $v_1, v_2$ in $\R^2$ or $\R^3$ that don't lie on one line, or three arrows $v_1, v_2, v_3$ in $\R^3$ that don't lie in one plane. The Gram–Schmidt process keeps the first arrow, $u_1 = v_1$; removes the second arrow's shadow on it, $u_2 = v_2 - \proj_{u_1} v_2$; and removes the third arrow's shadows on both, $u_3 = v_3 - \proj_{u_1} v_3 - \proj_{u_2} v_3$. Then it shrinks each one to length $1$: $q_i = \frac{1}{\|u_i\|}u_i$.
The shadows on $u_1, \ldots, u_{j-1}$ add up to the shadow on their whole span, the orthogonal projection onto it, and that adding-up works only because the $u$'s are orthogonal. So step $j$ subtracts from $v_j$ its projection onto everything built so far.
In space, the two shadows of $v_3$ add up to its shadow on the whole plane of $u_1$ and $u_2$ (the Orthogonal Projection page shows why, and why it needs $u_1$ and $u_2$ square to each other). So step three drops $v_3$ straight down onto that plane and keeps the part that sticks up.
Every step of Gram–Schmidt is just "stop leaning on the vectors that came before you." Honestly, solid life advice.
Here's Hefferon's three-vector example, where the fractions start to show up.
Run Gram–Schmidt on $v_1 = (1, 1, 1)$, $v_2 = (2, 0, 0)$, $v_3 = (1, 0, 3)$.
$u_1 = (1, 1, 1)$. Then $v_2 \cdot u_1 = 2$ and $u_1 \cdot u_1 = 3$, so $u_2 = (2, 0, 0) - \frac23(1, 1, 1) = \left(\frac43, -\frac23, -\frac23\right)$.
For $u_3$, two shadows: $v_3 \cdot u_1 = 4$, so $\proj_{u_1} v_3 = \frac43(1, 1, 1)$; and $v_3 \cdot u_2 = \frac43 - 2 = -\frac23$ with $u_2 \cdot u_2 = \frac{16}{9} + \frac49 + \frac49 = \frac83$, so $\proj_{u_2} v_3 = -\frac14 u_2 = \left(-\frac13, \frac16, \frac16\right)$. Then
$$u_3 = (1, 0, 3) - \left(\tfrac43, \tfrac43, \tfrac43\right) - \left(-\tfrac13, \tfrac16, \tfrac16\right) = \left(0, -\tfrac32, \tfrac32\right).$$Check all three pairs: $u_1 \cdot u_2 = \frac43 - \frac23 - \frac23 = 0$, $u_1 \cdot u_3 = 0 - \frac32 + \frac32 = 0$, $u_2 \cdot u_3 = 0 + 1 - 1 = 0$. Normalizing gives $q_1 = \frac{1}{\sqrt3}(1, 1, 1)$, $q_2 = \frac{1}{\sqrt6}(2, -1, -1)$, $q_3 = \frac{1}{\sqrt2}(0, -1, 1)$.
In space: $v_2$ slides along the line of $v_1$ until it stands square to it, and then $v_3$ slides parallel to the plane of $u_1$ and $u_2$ until it stands straight up off that plane.
Those fractions were optional, though.
Rescale any $u$ before you use it. Replace $u_2 = \left(\frac43, -\frac23, -\frac23\right)$ by $(2, -1, -1)$ and the next step gives the same $u_3$: the shadow $\frac{v \cdot u}{u \cdot u}\,u$ doesn't care how long $u$ is (double $u$, and the $2$ on top and the $2$ in front cancel the $4$ below). Here $v_3 \cdot (2, -1, -1) = -1$ over $(2, -1, -1) \cdot (2, -1, -1) = 6$ gives the same shadow $\left(-\frac13, \frac16, \frac16\right)$. Only the final normalizing cares about lengths, and it divides them out anyway.
Why does the process always work? Each step slides a vector without leaving the span of the vectors so far, and a vector that wasn't in the earlier span can't slide all the way to $0$.
If $v_1, \ldots, v_k$ in $\R^n$ are linearly independent, then the vectors $u_1, \ldots, u_k$ built by the Gram–Schmidt process are nonzero and mutually orthogonal, and for every $j$,
$$\span\{u_1, \ldots, u_j\} = \span\{v_1, \ldots, v_j\}.$$So the $u$'s are an orthogonal basis and the $q$'s an orthonormal basis of $\span\{v_1, \ldots, v_k\}$.
By induction on $j$. For $j = 1$: $u_1 = v_1 \neq 0$, since independent vectors are nonzero, and the spans agree. Now suppose $u_1, \ldots, u_{j-1}$ are nonzero and mutually orthogonal with the same span as $v_1, \ldots, v_{j-1}$. Write $c_i = \frac{v_j \cdot u_i}{u_i \cdot u_i}$ (defined, as $u_i \neq 0$), so $u_j = v_j - \sum_{i < j} c_iu_i$.
Orthogonal. For $m < j$, $u_j \cdot u_m = v_j \cdot u_m - \sum_{i < j} c_i (u_i \cdot u_m) = v_j \cdot u_m - c_m(u_m \cdot u_m) = 0$, since $u_i \cdot u_m = 0$ for $i \neq m$.
Nonzero. If $u_j = 0$, then $v_j = \sum_{i < j} c_iu_i$ lies in $\span\{u_1, \ldots, u_{j-1}\} = \span\{v_1, \ldots, v_{j-1}\}$, which contradicts the independence of $v_1, \ldots, v_j$.
Same span. $u_j$ is $v_j$ minus a combination of $u_1, \ldots, u_{j-1}$, which lie in $\span\{v_1, \ldots, v_{j-1}\}$, so $u_j \in \span\{v_1, \ldots, v_j\}$. Conversely $v_j = u_j + \sum_{i < j} c_iu_i \in \span\{u_1, \ldots, u_j\}$. Both spans contain each other's spanning vectors, so they're equal.
Finally, nonzero orthogonal vectors are linearly independent, so the $u$'s are a basis of the span, and dividing each by its length keeps them orthogonal and makes them unit vectors. $\blacksquare$
Run Gram–Schmidt on two arrows that don't lie on one line, or on three arrows in $\R^3$ that don't lie in one plane. Then the $u$'s are nonzero and square to each other. Also $u_1$ lies along $v_1$; $u_1$ and $u_2$ lie in the same plane as $v_1$ and $v_2$; and with three arrows, $u_1, u_2, u_3$ reach all of space, just as $v_1, v_2, v_3$ do. So the $q$'s are perpendicular unit arrows covering the same line, plane, or space as the $v$'s.
This is a visual argument, not a formal proof. Step two slides $v_2$ along the direction of $v_1$. Sliding parallel to $v_1$ never leaves the plane of $v_1$ and $v_2$, and the slide stops exactly when the shadow is gone, which is exactly when the arrow stands square to $v_1$. It can't slide all the way to $0$, because $v_2$ isn't on $v_1$'s line. Step three is the same idea one dimension up: $v_3$ slides parallel to the plane of $u_1$ and $u_2$ until its shadow on that plane is gone, so it stands straight up, square to both. It can't reach $0$ either, because $v_3$ isn't in that plane. And sliding an arrow along directions you already have never changes which plane or space the arrows reach.
The full proof is in the n version.
Your turn. In free response, type the entries separated by commas, like -1, 2; fractions like 4/3 are fine.
Loading practice engine...
What if the input isn't independent? Then some $v_j$ already lies in the span of the vectors before it, its shadow on that span is all of it, and Gram–Schmidt gives $u_j = 0$. That's a report, not a breakdown: drop that vector, carry on, and you still end with an orthogonal basis of the span. Gram–Schmidt doubles as a test for dependence.
Every subspace has some basis. Feed it to Gram–Schmidt and an orthonormal one comes out, so orthonormal bases are always available, never a lucky accident.
Every subspace $\W \neq \{0\}$ of $\R^n$ has an orthonormal basis.
$\W$ has a finite basis $v_1, \ldots, v_k$ (Bases & Dimension), with $k \geq 1$ since $\W \neq \{0\}$. By the Gram–Schmidt theorem, the $q$'s it produces are an orthonormal basis of $\span\{v_1, \ldots, v_k\} = \W$. $\blacksquare$
Every line through $0$ has an orthonormal basis (one unit arrow along it), every plane through $0$ has one (two perpendicular unit arrows in it), and so do $\R^2$ and $\R^3$ themselves.
These are all the subspaces there are, besides $\{0\}$. For a line, shrink any arrow on it to length $1$. For a plane, pick two arrows in it that don't lie on one line and run Gram–Schmidt; the theorem above says the two $q$'s are perpendicular unit arrows in the same plane. For all of space, do the same with three arrows. The full proof is in the n version.
Here's a plane through $0$ that doesn't come with a nice basis, from Hefferon's exercises.
Find an orthonormal basis for the plane $x - y + z = 0$ in $\R^3$.
First, any basis. Solving gives $x = y - z$ with $y$ and $z$ free; $y = 1, z = 0$ gives $v_1 = (1, 1, 0)$, and $y = 0, z = 1$ gives $v_2 = (-1, 0, 1)$. These aren't orthogonal ($v_1 \cdot v_2 = -1$), so straighten them: $u_1 = (1, 1, 0)$ and
$$u_2 = (-1, 0, 1) - \tfrac{-1}{2}(1, 1, 0) = \left(-\tfrac12, \tfrac12, 1\right), \text{ rescaled to } (-1, 1, 2).$$Check: $(-1, 1, 2)$ is in the plane ($-1 - 1 + 2 = 0$) and square to $u_1$ ($-1 + 1 + 0 = 0$). Normalizing: $q_1 = \frac{1}{\sqrt2}(1, 1, 0)$, $q_2 = \frac{1}{\sqrt6}(-1, 1, 2)$.
Picture the tilted plane with its normal $(1, -1, 1)$ sticking out. Both $v$'s lie flat in it, $u_2$ swings within the plane to a right angle, and the two unit arrows mark out a unit square lying in the plane.
For a plane in $\R^3$, there's also a shortcut.
In $\R^3$, the second vector has to be square to both $v_1$ and the plane's normal $n$, and the cross product makes exactly such a vector: $n \times v_1$. Here $(1, -1, 1) \times (1, 1, 0) = (0 - 1, \ 1 - 0, \ 1 + 1) = (-1, 1, 2)$, the same line Gram–Schmidt found. The shortcut only exists in $\R^3$; Gram–Schmidt works in every dimension.
Your turn. The answer is a direction, so in free response any nonzero multiple counts; type the entries separated by commas, like -1, 1, 2.
Loading practice engine...
Stand orthonormal vectors side by side as the columns of a matrix $Q$. Then $Q^tQ$ computes every dot product among the columns at once, and being orthonormal becomes a single matrix equation.
Let $Q$ be an $m \times k$ matrix with columns $q_1, \ldots, q_k$. The columns are orthonormal exactly when $Q^tQ = I_k$.
Entry $(i, j)$ of $Q^tQ$ is row $i$ of $Q^t$ times column $j$ of $Q$. Row $i$ of $Q^t$ is column $i$ of $Q$, so the entry is $q_i \cdot q_j$. So $Q^tQ = I_k$ says exactly that $q_i \cdot q_i = 1$ for every $i$ (unit vectors) and $q_i \cdot q_j = 0$ for $i \neq j$ (orthogonal). $\blacksquare$
This is a visual argument, not a formal proof. $Q^tQ$ is a table of dot products: the row of $Q^t$ that holds $q_i$ meets the column of $Q$ that holds $q_j$, and their product is $q_i \cdot q_j$. Each arrow against itself gives its length squared, which is $1$ for a unit arrow. Each arrow against a different one gives $0$ when they're perpendicular. Ones down the diagonal and zeros everywhere else: that's $I$.
The full proof is in the n version.
The order of the product matters, and the plane's basis from Example 3 shows how much.
Let $Q$ have the columns $q_1 = \frac{1}{\sqrt2}(1, 1, 0)$ and $q_2 = \frac{1}{\sqrt6}(-1, 1, 2)$ from Example 3. Compute $Q^tQ$ and $QQ^t$.
$Q^tQ$ is $2 \times 2$, with entries $q_1 \cdot q_1 = \frac{1 + 1}{2} = 1$, $q_2 \cdot q_2 = \frac{1 + 1 + 4}{6} = 1$, and $q_1 \cdot q_2 = \frac{-1 + 1 + 0}{\sqrt{12}} = 0$. So $Q^tQ = I_2$.
$QQ^t$ is $3 \times 3$: it's $q_1q_1^t + q_2q_2^t$, which works out to
$$QQ^t = \frac13\begin{pmatrix} 2 & 1 & -1 \\ 1 & 2 & 1 \\ -1 & 1 & 2 \end{pmatrix} \neq I_3.$$It isn't even invertible: it sends the normal $(1, -1, 1)$ to $\frac13(2 - 1 - 1, \ 1 - 2 + 1, \ -1 - 1 + 2) = 0$. In fact $QQ^t$ drops every vector onto the plane, the orthogonal projection onto it.
So a tall $Q$ with orthonormal columns has $Q^tQ = I$ but not $QQ^t = I$. When $Q$ is square, the story changes.
A square $Q$ with orthonormal columns gets $Q^tQ = I$ on the nose, so $Q^t$ undoes $Q$. These matrices turn out to be exactly the rotations and reflections, and they get their own page next: Orthogonal Matrices.
Now read Gram–Schmidt backward. Run it on the columns $a_1, \ldots, a_n$ of a matrix $A$. Each $u_j$ was $a_j$ minus multiples of $u_1, \ldots, u_{j-1}$, so $a_j$ is $u_j$ plus those multiples: a combination of $q_1, \ldots, q_j$ and nothing later. Its coefficients are dot products, because coordinates in an orthonormal basis are:
$$a_j = (q_1 \cdot a_j)\,q_1 + (q_2 \cdot a_j)\,q_2 + \cdots + (q_j \cdot a_j)\,q_j.$$Write those recipes as the columns of a matrix and Gram–Schmidt becomes a factorization.
A QR factorization of an $m \times n$ matrix $A$ is $A = QR$, where $Q$ is an $m \times n$ matrix with orthonormal columns and $R$ is an $n \times n$ upper triangular matrix whose diagonal entries are positive.
A QR factorization of a $2 \times 2$, $3 \times 2$, or $3 \times 3$ matrix $A$ is $A = QR$, where the columns of $Q$ are perpendicular unit arrows and $R$ is a square matrix with zeros below its diagonal (upper triangular) and positive numbers on its diagonal.
Gram–Schmidt says such a factorization exists whenever the columns are independent, and the positive diagonal makes it the only one.
If the columns of $A$ are linearly independent, then $A$ has exactly one QR factorization. The columns of $Q$ are the vectors $q_1, \ldots, q_n$ that Gram–Schmidt makes from $a_1, \ldots, a_n$, and $R = Q^tA$, so $R_{ij} = q_i \cdot a_j$, with $R_{jj} = \|u_j\|$.
Existence. By the Gram–Schmidt theorem, $a_j \in \span\{a_1, \ldots, a_j\} = \span\{q_1, \ldots, q_j\}$, so by coordinates in an orthonormal basis, $a_j = \sum_{i \leq j} (q_i \cdot a_j)\,q_i$. Column by column, that says $A = QR$ with $R_{ij} = q_i \cdot a_j$ for $i \leq j$ and $R_{ij} = 0$ for $i > j$: upper triangular. Since $(q_i \cdot a_j)\,q_i = \proj_{u_i} a_j$, the last term is $R_{jj}q_j = a_j - \sum_{i < j}\proj_{u_i} a_j = u_j$, so $R_{jj} = \|u_j\| > 0$. And $Q^tA = Q^tQR = R$ by the orthonormal columns theorem.
Uniqueness. Suppose also $A = Q'R'$ with $Q'$ having orthonormal columns $q_1', \ldots, q_n'$ and $R'$ upper triangular with positive diagonal. Column $1$ reads $a_1 = R'_{11}q_1'$; a positive multiple of a unit vector equal to $a_1$ forces $R'_{11} = \|a_1\|$ and $q_1' = a_1/\|a_1\| = q_1$. Suppose $q_i' = q_i$ for all $i < j$. Column $j$ reads $a_j = \sum_{i < j} R'_{ij}q_i + R'_{jj}q_j'$. Dotting with $q_i$ for $i < j$ (orthonormal columns, so $q_j' \cdot q_i = q_j' \cdot q_i' = 0$) gives $R'_{ij} = q_i \cdot a_j = R_{ij}$. Then $R'_{jj}q_j' = a_j - \sum_{i < j} R_{ij}q_i = u_j$, and as before a positive multiple of a unit vector forces $R'_{jj} = \|u_j\|$ and $q_j' = q_j$. By induction, $Q' = Q$ and $R' = R$. $\blacksquare$
If the columns of a $2 \times 2$, $3 \times 2$, or $3 \times 3$ matrix $A$ don't lie on one line (or, for three columns, in one plane), then $A = QR$, where the columns of $Q$ are the unit arrows $q_1, q_2, \ldots$ from Gram–Schmidt and $R = Q^tA$. Column $j$ of $R$ lists how far $a_j$ reaches along $q_1, q_2, \ldots$: $R_{ij} = q_i \cdot a_j$. It never reaches along a later $q$, which is why $R$ has zeros below its diagonal. There's only one such factorization.
This is a visual argument, not a formal proof. Build each column of $A$ as a staircase of steps along the perpendicular unit arrows. Column $a_1$ points along $q_1$, so it's one step. Column $a_2$ lies in the plane of $q_1$ and $q_2$, so it's a step along $q_1$ and a step along $q_2$. Only $a_3$ needs $q_3$. The step lengths are shadows, so they're dot products $q_i \cdot a_j$, and writing them down column by column fills $R$ in, with nothing below the diagonal. The diagonal steps are the leftover heights $\|u_j\|$, which are positive.
The full proof, including why there's only one, is in the n version.
Example 1's arrows, stood up as the columns of a matrix, factor right away.
Find the QR factorization of $A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}$.
The columns are Example 1's $v_1$ and $v_2$, so $q_1 = \frac{1}{\sqrt5}(2, 1)$ and $q_2 = \frac{1}{\sqrt5}(-1, 2)$. Then $R = Q^tA$ has $R_{11} = q_1 \cdot a_1 = \frac{10}{\sqrt5} = 2\sqrt5$, $R_{12} = q_1 \cdot a_2 = \frac{5}{\sqrt5} = \sqrt5$, and $R_{22} = q_2 \cdot a_2 = \frac{5}{\sqrt5} = \sqrt5$:
$$\begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} = \frac{1}{\sqrt5}\begin{pmatrix} 2 & -1 \\ 1 & 2 \end{pmatrix}\begin{pmatrix} 2\sqrt5 & \sqrt5 \\ 0 & \sqrt5 \end{pmatrix}.$$Each entry of $R$ is a length from the opening figure: $R_{11} = \|v_1\|$, $R_{12} = \|(2, 1)\|$, the length of the shadow, and $R_{22} = \|u_2\|$. (And $q_2 \cdot a_1 = \frac{-4 + 2 \cdot 2}{\sqrt5} = 0$, as the zero below the diagonal promises.)
Square roots are the usual price of normalizing. A $3 \times 3$ chosen so every length comes out whole shows the structure without them.
Find the QR factorization of $A = \begin{pmatrix} 2 & 2 & -1 \\ 1 & 4 & 7 \\ 2 & 5 & 2 \end{pmatrix}$.
$a_1 = (2, 1, 2)$ has length $3$, so $q_1 = \frac13(2, 1, 2)$.
$q_1 \cdot a_2 = \frac{4 + 4 + 10}{3} = 6$, so $u_2 = (2, 4, 5) - 6q_1 = (2, 4, 5) - (4, 2, 4) = (-2, 2, 1)$, of length $3$: $q_2 = \frac13(-2, 2, 1)$.
$q_1 \cdot a_3 = \frac{-2 + 7 + 4}{3} = 3$ and $q_2 \cdot a_3 = \frac{2 + 14 + 2}{3} = 6$, so $u_3 = (-1, 7, 2) - 3q_1 - 6q_2 = (-1, 7, 2) - (2, 1, 2) - (-4, 4, 2) = (1, 2, -2)$, of length $3$: $q_3 = \frac13(1, 2, -2)$.
Every number we multiplied a $q$ by goes above the diagonal of $R$, and every length goes on it:
$$A = \frac13\begin{pmatrix} 2 & -2 & 1 \\ 1 & 2 & 2 \\ 2 & 1 & -2 \end{pmatrix}\begin{pmatrix} 3 & 6 & 3 \\ 0 & 3 & 6 \\ 0 & 0 & 3 \end{pmatrix}.$$That last example never multiplied $Q^t$ by $A$, and it didn't need to.
You never have to multiply out $Q^tA$: every entry of $R$ already showed up while you ran Gram–Schmidt. $R_{ij}$ above the diagonal is the number you multiplied $q_i$ by before subtracting it from $a_j$, and $R_{jj}$ is the length you divided by to normalize. One catch: that's with the $q$'s. If you subtracted $\frac{a_j \cdot u_i}{u_i \cdot u_i}\,u_i$ instead, multiply that coefficient by $\|u_i\|$ to get $R_{ij}$.
Drag two columns around and watch $R$ change: each entry is a length you can see.
The top-left entry is the length of the first column, the top-right is the second column's shadow on the first, and the bottom-right is its height off the first column's line. Flatten that height to $0$ and the columns are dependent, and there's no QR factorization to be had.
Your turn. In free response, type the column's entries separated by commas, like 6, 3, 0.
Loading practice engine...
For a square $A$ with independent columns, $Ax = b$ becomes $QRx = b$. Multiply both sides by $Q^t$, and $Q^tQ = I$ leaves
$$Rx = Q^tb.$$$R$ is triangular, so back substitution finishes the job, just like the second half of LU. And $Q^tb$ is nothing but dot products: the coordinates of $b$ along the $q$'s. Is the solution of $Rx = Q^tb$ really the solution of $Ax = b$? Yes: $Ax = b$ has exactly one solution (its columns are independent and it's square, so it's invertible), that solution satisfies $Rx = Q^tb$, and $Rx = Q^tb$ has only one solution since $R$ is triangular with nonzero diagonal.
Solve $Ax = (-1, 4, -1)$ for the $3 \times 3$ matrix $A$ of Example 6.
First $Q^tb$: $q_1 \cdot b = \frac{-2 + 4 - 2}{3} = 0$, $q_2 \cdot b = \frac{2 + 8 - 1}{3} = 3$, $q_3 \cdot b = \frac{-1 + 8 + 2}{3} = 3$. Then back substitution on $Rx = (0, 3, 3)$, bottom row first:
$$3x_3 = 3 \implies x_3 = 1, \qquad 3x_2 + 6x_3 = 3 \implies x_2 = -1, \qquad 3x_1 + 6x_2 + 3x_3 = 0 \implies x_1 = 1.$$So $x = (1, -1, 1)$. Check: $A(1, -1, 1) = (2 - 2 - 1, \ 1 - 4 + 7, \ 2 - 5 + 2) = (-1, 4, -1)$.
In pictures: the three numbers in $Q^tb$ are the shadows of $b$ on the three perpendicular unit arrows, and back substitution peels the answer off one row at a time, starting from the row with a single unknown.
Why bother, when elimination solves it too? Because multiplying by $Q^t$ never stretches anything (that's a fact about orthogonal matrices), so the rounding errors already in $b$ stay the size they were, while elimination can magnify them. And for a tall $A$ with more rows than columns, where $Ax = b$ usually has no solution at all, $Rx = Q^tb$ gives the best approximate one: that's how computers do least squares.
There's one more thing a computer cares about: the order of the subtractions.
Classical Gram–Schmidt, as defined above, computes every shadow of $v_j$ from the original $v_j$. Modified Gram–Schmidt removes the shadow on $q_1$ from every later vector as soon as $q_1$ is known, then the shadow on $q_2$ from the updated vectors, and so on. In exact arithmetic the two give identical results. In floating point they don't. Take $\varepsilon = 10^{-8}$, small enough that $1 + \varepsilon^2$ rounds to $1$ in double precision, and $v_1 = (1, \varepsilon, 0, 0)$, $v_2 = (1, 0, \varepsilon, 0)$, $v_3 = (1, 0, 0, \varepsilon)$. Both versions find $q_1 = v_1$ (its length rounds to $1$) and $q_2 = \frac{1}{\sqrt2}(0, -1, 1, 0)$. Classical then gets $q_3 = \frac{1}{\sqrt2}(0, -1, 0, 1)$, with $q_2 \cdot q_3 = \frac12$: a $60^\circ$ angle where there should be $90^\circ$. Modified first removes the shadow on $q_1$, leaving $(0, -\varepsilon, 0, \varepsilon)$, whose shadow on $q_2$ it can now see, and gets $q_3 = \frac{1}{\sqrt6}(0, -1, -1, 2)$, square to $q_2$ as it should be.
Modified Gram–Schmidt removes each shadow from all the later arrows as soon as it's known, instead of computing every shadow from the original arrow. With exact numbers the two versions agree. With rounded numbers, the modified version stays much closer to perpendicular. The difference only shows up with more arrows than this page can draw, so the example lives in the n version.
Your turn. In free response, type the entries of $x$ separated by commas, like 1, -1, 1.
Loading practice engine...
Here's the job that made QR famous. Factor $A = QR$, multiply the factors back together in the other order, and repeat:
$$A_0 = A, \qquad A_k = Q_kR_k, \qquad A_{k+1} = R_kQ_k.$$This is the QR algorithm, and with a few refinements on top it's how computers find all the eigenvalues of a matrix. Two facts make it work. First, every $A_k$ has the same eigenvalues as $A$: since $R_k = Q_k^tA_k$, we get $A_{k+1} = Q_k^tA_kQ_k$, and a square $Q_k$ with orthonormal columns has $Q_k^t = Q_k^{-1}$ (Orthogonal Matrices), so $\det(A_{k+1} - tI) = \det\!\big(Q_k^{-1}(A_k - tI)Q_k\big) = \det(A_k - tI)$. Second, when the eigenvalues have different sizes, the $A_k$ drift toward upper triangular, with the eigenvalues collecting on the diagonal, largest first (a theorem beyond this page). So the diagonal reads off the eigenvalues.
Run the QR algorithm on $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$.
The first column $(2, 1)$ points the same way as Example 1's $v_1$, so $q_1 = \frac{1}{\sqrt5}(2, 1)$, $q_2 = \frac{1}{\sqrt5}(-1, 2)$, and $R_0 = Q_0^tA = \frac{1}{\sqrt5}\begin{pmatrix} 5 & 4 \\ 0 & 3 \end{pmatrix}$. Multiplying in the other order,
$$A_1 = R_0Q_0 = \frac15\begin{pmatrix} 5 & 4 \\ 0 & 3 \end{pmatrix}\begin{pmatrix} 2 & -1 \\ 1 & 2 \end{pmatrix} = \frac15\begin{pmatrix} 14 & 3 \\ 3 & 6 \end{pmatrix} = \begin{pmatrix} 2.8 & 0.6 \\ 0.6 & 1.2 \end{pmatrix}.$$Repeating gives $A_2 \approx \begin{pmatrix} 2.976 & 0.220 \\ 0.220 & 1.024 \end{pmatrix}$ and $A_3 \approx \begin{pmatrix} 2.997 & 0.074 \\ 0.074 & 1.003 \end{pmatrix}$. The diagonal closes in on $3$ and $1$, the eigenvalues, and the corners shrink by about a third each step. (The trace stays $4$ and the determinant stays $3$ the whole way, as similar matrices must.)
Here are six steps of it, with the diagonal entries and the corner plotted as they settle.
Those diagonal numbers look familiar. $2.8$, $2.976$, $2.997$ are exactly the Rayleigh quotients $\frac{14}{5}$, $\frac{122}{41}$, $\frac{1094}{365}$ from the Power Method page's example on this same matrix. That's no coincidence: the first column of $Q_0Q_1 \cdots Q_k$ is the power method's iterate $A^{k+1}e_1$, made unit length, so the QR algorithm runs the power method in its first column for free, and the third-a-step shrinking is the same $\left|\frac{\lambda_2}{\lambda_1}\right| = \frac13$.
The toolkit for this page: remove each vector's shadows on the $u$'s before it, $u_j = v_j - \proj_{u_1} v_j - \cdots - \proj_{u_{j-1}} v_j$, then normalize. The span never changes and the output is orthogonal, so every subspace has an orthonormal basis. Orthonormal columns mean $Q^tQ = I$. Gram–Schmidt on the columns of $A$ is $A = QR$ with $R = Q^tA$ upper triangular, and $Ax = b$ becomes $Rx = Q^tb$. Repeating $A \to RQ$ finds eigenvalues.
Every question so far came right after its idea, which is a hint a quiz never gives you. Down here the hint is gone. First, true or false: a claim from anywhere on this page, and you decide whether it holds.
Loading practice engine...
Next, a mixed set: every question type on this page, shuffled. Type the entries separated by commas when it asks for a vector.
Loading practice engine...
Made it this far? Time for something with a little heat: one full step of the QR algorithm by hand. In free response, type a number.
Loading practice engine...