Orthogonal bases are easy to work with: as shown on the
Orthogonal Bases and Projections page, the coordinates of a vector with respect to an orthogonal basis are just projections. The \textbf{Gram–Schmidt} orthogonalization process allows one to start from a non-orthogonal basis $\beta$ of a subspace $W$, and construct an \emph{orthogonal} basis $\gamma$ that spans the same subspace $W$. Let $\beta$ be a basis for a subspace $W \subseteq \R^n$:
$$\beta = \{\mathbf{v}_1, \ldots, \mathbf{v}_p\} \xrightarrow{\text{Gram–Schmidt}} \gamma = \{\mathbf{u}_1, \ldots, \mathbf{u}_p\}.$$
The interactive graph above runs through this process. I invite you to play around and visualize this procedure, as it is algebraically quite dense.
Throughout, recall that the projection of $\mathbf{v}$ onto a nonzero vector $\mathbf{u}$ is computed as
$$\frac{\mathbf{u}^\mathsf{T}\mathbf{v}}{\|\mathbf{u}\|^2}\,\mathbf{u}.$$
\subsection*{1st step}
We need to start somewhere, with a vector that is orthogonal to all the rest. But "all the rest" is nothing when we only have one vector. For sake of easy, just choose
$$\boxed{\mathbf{u}_1 = \mathbf{v}_1}.$$
\subsection*{2nd step}
We now define the following two vectors:
- $\mathbf{v}_2^\parallel$, called the "parallel component of $\mathbf{v}_2$ with respect to $\mathbf{u}_1$", which is just the \emph{projection} of $\mathbf{v}_2$ onto $\mathbf{u}_1$;
- $\mathbf{v}_2^\perp$, called the "perpendicular component of $\mathbf{v}_2$ with respect to $\mathbf{u}_1$", which is the other component of $\mathbf{v}_2$, i.e. the vector such that $\mathbf{v}_2 = \mathbf{v}_2^\parallel + \mathbf{v}_2^\perp$. Notably this is perpendicular to both $\mathbf{v}_2^\parallel$ and $\mathbf{u}_1$.
Thus, we have $\mathbf{v}_2^\perp = \mathbf{v}_2 - \mathbf{v}_2^\parallel$, and $\mathbf{v}_2^\parallel$ and $\mathbf{v}_2^\perp$ are orthogonal to one another.
We then choose $\mathbf{u}_2 = \mathbf{v}_2^\perp$. With this choice, $\operatorname{span}\{\mathbf{u}_1, \mathbf{u}_2\} = \operatorname{span}\{\mathbf{v}_1, \mathbf{v}_2\}$ (the spanned set is the plane that contains both pairs of vectors). Since $\mathbf{v}_2^\parallel$ is the projection of $\mathbf{v}_2$ onto $\mathbf{u}_1$,
$$\mathbf{v}_2 = \mathbf{v}_2^\parallel + \mathbf{v}_2^\perp \implies \mathbf{v}_2^\perp = \mathbf{v}_2 - \mathbf{v}_2^\parallel \implies \mathbf{v}_2^\perp = \mathbf{v}_2 - \frac{\mathbf{u}_1^\mathsf{T}\mathbf{v}_2}{\|\mathbf{u}_1\|^2}\,\mathbf{u}_1.$$
In conclusion,
$$\boxed{\mathbf{u}_2 = \mathbf{v}_2 - \frac{\mathbf{u}_1^\mathsf{T}\mathbf{v}_2}{\|\mathbf{u}_1\|^2}\,\mathbf{u}_1}.$$
To reiterate: $\mathbf{u}_2$ is obtained by subtracting from $\mathbf{v}_2$ its parallel component to $\mathbf{u}_1$. The subsequent steps keep this pattern going.
\subsection*{3rd step}
At this point, $\mathbf{u}_1$ and $\mathbf{u}_2$ are known. How do we "straighten" $\mathbf{v}_3$ so that (i) it becomes a vector $\mathbf{u}_3$ orthogonal to both $\mathbf{u}_1$ and $\mathbf{u}_2$, and (ii) $\operatorname{span}\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\} = \operatorname{span}\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$? Similarly to the 2nd step, we define the parallel components of $\mathbf{v}_3$ with respect to $\mathbf{u}_1$ and $\mathbf{u}_2$, i.e. its projections onto each:
$$\mathbf{v}_{3,1} = \frac{\mathbf{u}_1^\mathsf{T}\mathbf{v}_3}{\|\mathbf{u}_1\|^2}\,\mathbf{u}_1, \qquad \mathbf{v}_{3,2} = \frac{\mathbf{u}_2^\mathsf{T}\mathbf{v}_3}{\|\mathbf{u}_2\|^2}\,\mathbf{u}_2.$$
The vector $\mathbf{u}_3$, simply by how projections work, is such that $\mathbf{u}_3 + \mathbf{v}_{3,1} + \mathbf{v}_{3,2} = \mathbf{v}_3$, so it is obtained by subtracting from $\mathbf{v}_3$ its components with respect to both $\mathbf{u}_1$ and $\mathbf{u}_2$:
$$\boxed{\mathbf{u}_3 = \mathbf{v}_3 - \frac{\mathbf{u}_1^\mathsf{T}\mathbf{v}_3}{\|\mathbf{u}_1\|^2}\,\mathbf{u}_1 - \frac{\mathbf{u}_2^\mathsf{T}\mathbf{v}_3}{\|\mathbf{u}_2\|^2}\,\mathbf{u}_2}.$$
It is easy to verify that $\mathbf{u}_3^\mathsf{T}\mathbf{u}_1 = 0$ and $\mathbf{u}_3^\mathsf{T}\mathbf{u}_2 = 0$, so $\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}$ is an orthogonal set.
\subsection*{$k$
th step}
In general, once $\mathbf{u}_1, \ldots, \mathbf{u}_{k-1}$ are known, the vector $\mathbf{u}_k$ is obtained by subtracting from $\mathbf{v}_k$ its components in the directions of $\mathbf{u}_1, \ldots, \mathbf{u}_{k-1}$:
$$\mathbf{u}_k = \mathbf{v}_k - \frac{\mathbf{u}_1^\mathsf{T}\mathbf{v}_k}{\|\mathbf{u}_1\|^2}\,\mathbf{u}_1 - \frac{\mathbf{u}_2^\mathsf{T}\mathbf{v}_k}{\|\mathbf{u}_2\|^2}\,\mathbf{u}_2 - \cdots - \frac{\mathbf{u}_{k-1}^\mathsf{T}\mathbf{v}_k}{\|\mathbf{u}_{k-1}\|^2}\,\mathbf{u}_{k-1},$$
or, in a more compact form,
$$\boxed{\mathbf{u}_k = \mathbf{v}_k - \sum_{i=1}^{k-1} \frac{\mathbf{u}_i^\mathsf{T}\mathbf{v}_k}{\|\mathbf{u}_i\|^2}\,\mathbf{u}_i}.$$
\begin{remark}
Once you have computed an orthogonal basis $\gamma = \{\mathbf{u}_1, \ldots, \mathbf{u}_p\}$, you can make it orthonormal by dividing each vector by its own length:
$$\delta = \left\{ \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|}, \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|}, \ldots, \frac{\mathbf{u}_p}{\|\mathbf{u}_p\|} \right\}$$
is an orthonormal basis of $W$.
\end{remark}
\begin{remark}
If you start from a different ordering of the vectors of $\beta$, you get a different orthogonal basis. In other words, the result of the Gram–Schmidt process depends on the initial ordering of the vectors in $\beta$. (In the graph, $\mathbf{u}_1$ always lies along $\mathbf{v}_1$, whichever basis you start from.)
\end{remark}
\begin{example}
Take the default basis in the graph, $\beta = \{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\} \subseteq \R^3$ with
$$\mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \qquad \mathbf{v}_2 = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix}, \qquad \mathbf{v}_3 = \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}.$$
First,
$$\mathbf{u}_1 = \mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}.$$
To compute $\mathbf{u}_2$, we subtract from $\mathbf{v}_2$ its projection onto $\mathbf{u}_1$. Since $\mathbf{u}_1^\mathsf{T}\mathbf{v}_2 = 1 + 0 + 3 = 4$ and $\|\mathbf{u}_1\|^2 = 3$,
$$\mathbf{u}_2 = \mathbf{v}_2 - \frac{\mathbf{u}_1^\mathsf{T}\mathbf{v}_2}{\|\mathbf{u}_1\|^2}\,\mathbf{u}_1 = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} - \frac{4}{3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -1/3 \\ -4/3 \\ \phantom{-}5/3 \end{bmatrix}.$$
To compute $\mathbf{u}_3$, we subtract from $\mathbf{v}_3$ its projections onto $\mathbf{u}_1$ and $\mathbf{u}_2$. We have $\mathbf{u}_1^\mathsf{T}\mathbf{v}_3 = 0 + 1 + 2 = 3$, $\mathbf{u}_2^\mathsf{T}\mathbf{v}_3 = 0 - \frac{4}{3} + \frac{10}{3} = 2$, and $\|\mathbf{u}_2\|^2 = \frac{1}{9} + \frac{16}{9} + \frac{25}{9} = \frac{14}{3}$, so
$$\mathbf{u}_3 = \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} - \frac{3}{3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - \frac{2}{14/3}\begin{bmatrix} -1/3 \\ -4/3 \\ \phantom{-}5/3 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - \begin{bmatrix} -1/7 \\ -4/7 \\ \phantom{-}5/7 \end{bmatrix} = \begin{bmatrix} -6/7 \\ \phantom{-}4/7 \\ \phantom{-}2/7 \end{bmatrix}.$$
As a check, $\mathbf{u}_3^\mathsf{T}\mathbf{u}_1 = \frac{-6 + 4 + 2}{7} = 0$ and $\mathbf{u}_3^\mathsf{T}\mathbf{u}_2 = \frac{6 - 16 + 10}{21} = 0$. In conclusion, the resulting orthogonal basis $\gamma = \{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}$ is comprised of the vectors
$$\boxed{\mathbf{u}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{u}_2 = \begin{bmatrix} -1/3 \\ -4/3 \\ \phantom{-}5/3 \end{bmatrix}, \quad \mathbf{u}_3 = \begin{bmatrix} -6/7 \\ \phantom{-}4/7 \\ \phantom{-}2/7 \end{bmatrix}}.$$
\end{example}