11. The Gram-Schmidt Process

Gram-Schmidt Orthonormalization

We can orthonormalize a set of vectors $\{{\vec{a}}_1,{\vec{a}}_2,\dots ,{\vec{a}}_n\}$ into an orthonormal set $Q$ by executing the following algorithm:

1. Normalize ${\vec{a}}_1$ by setting ${\vec{q}}_1=\frac{{\vec{a}}_1}{\Vert {\vec{a}}_1{\Vert }_2}$.
2. For $i=2,\dots ,n$:

• Orthogonalize ${\vec{a}}_i$ with respect to the direction of each the previously computed vectors ${\vec{q}}_j,\dots ,{\vec{q}}_{i-1}$ by subtracting from ${\vec{a}}_i$ the projection of ${\vec{a}}_i$ onto the subspace of ${\vec{q}}_1,\dots ,{\vec{q}}_{i-1}$, such that ${\vec{z}}_i:={\vec{a}}_i-{\Pi }_{\mathrm{Span}({\vec{q}}_1,\dots ,{\vec{q}}_{i-1})}({\vec{a}}_i)={\vec{a}}_i-{\sum }_{k=1}^{i-1}⟨{\vec{a}}_i,{\vec{q}}_k⟩{\vec{q}}_k$.
• Normalize ${\vec{z}}_i$ by setting ${\vec{q}}_i:=\frac{{\vec{z}}_i}{||{\vec{z}}_i||}$.

Intuition

In short, Gram-Schmidt normalizes the first vector in the set and orthogonalizes all subsequent vectors by subtracting from them their orthogonal projections onto the span of all previously orthonormalized vectors, which leaves them orthogonal to that span. Then they are simply normalized and the process is repeated.

Example

We can illustrate the Gram-Schmidt process as follows. In this case, we limit our set to three vectors $\{{\vec{a}}_1=\left[\begin{array}{c}3\\ 1\end{array}\right],{\vec{a}}_2=\left[\begin{array}{c}2\\ 3\end{array}\right]\}\in {\mathbb{R}}^2$. We first set ${\vec{q}}_1:=\left[\begin{array}{c}\frac{3}{\sqrt{10}}\\ \frac{1}{\sqrt{10}}\end{array}\right]$ to normalize ${\vec{a}}_1$ (since $||{\vec{q}}_1||=1$). We can then illustrate the 3 vectors in as follows:

\usepackage{tikz}
 
\begin{document}
\begin{tikzpicture}
    % Vectors
    \draw[->, thick, green] (0,0) -- (2,3) node[midway, above left] {$\vec{a}_2$};
    \draw[->, thick, red] (0,0) -- (3,1) node[midway, above] {$\vec{a}_1$};
    \draw[->, thick, orange] (0,0) -- ({3 / sqrt(10)},{1 / sqrt(10)}) node[midway, below] {$\vec{q}_1$};
\end{tikzpicture}
\end{document}

Note that $\mathrm{Span}({\vec{q}}_1)=\mathrm{Span}({\vec{a}}_1)$. Now we start the second part of the process by setting $\vec{z}:=\left[\begin{array}{c}2\\ 3\end{array}\right]-⟨\left[\begin{array}{c}2\\ 3\end{array}\right],\left[\begin{array}{c}\frac{3}{\sqrt{10}}\\ \frac{1}{\sqrt{10}}\end{array}\right]⟩\left[\begin{array}{c}\frac{3}{\sqrt{10}}\\ \frac{1}{\sqrt{10}}\end{array}\right]=\left[\begin{array}{c}2\\ 3\end{array}\right]-\left[\begin{array}{c}\frac{27}{10}\\ \frac{9}{10}\end{array}\right]=\left[\begin{array}{c}-\frac{7}{10}\\ \frac{21}{10}\end{array}\right],$ illustrated as:

\usepackage{tikz}
 
\begin{document}
\begin{tikzpicture}
    % Vectors
    \draw[->, thick, green] (0,0) -- (2,3) node[midway, above left] {$\vec{a}_2$};
    \draw[->, thick, red] (0,0) -- (3,1) node[below right] {$\vec{a}_1$};
    \draw[->, thick, dashed, pink] (0,0) -- (27/10,9/10) node[midway, below right] {$\mathrm{proj}_{\mathrm{Span}(\vec{q}_1)}(\vec{a}_2)$};
    \draw[->, thick, orange] (0,0) -- ({3 / sqrt(10)},{1 / sqrt(10)}) node[midway, below] {$\vec{q}_1$};
    \draw[->, thick, magenta] (0,0) -- (-7/10,21/10) node[midway, left] {$\vec{z}_2$};
    \draw[->, thick, dashed, purple] (2,3) -- (27/10,9/10) node[midway, right] {$\vec{a}_2-\mathrm{proj}_{\mathrm{Span}(\vec{q}_1)}(\vec{a}_2)$};
\end{tikzpicture}
\end{document}

Let’s take a second to deconstruct what’s happening. Essentially, we are calculating ${\vec{z}}_2$ as a vector that is orthogonal to the span of ${\vec{q}}_1$ (and in higher dimensions simultaneously to the span of ${\vec{q}}_2,\dots ,{\vec{q}}_n$). We do this by subtracting from ${\vec{a}}_2$ the orthonormal projection of ${\vec{a}}_2$ onto the span. This is because ${\mathrm{proj}}_{\mathrm{Span}({\vec{q}}_1)}({\vec{a}}_2)$ captures all the components of ${\vec{a}}_2$ in the direction of $\mathrm{Span}({\vec{q}}_1)$, so subtracting it from ${\vec{a}}_2$ leaves it only the components of the vector that are orthogonal to the span. The actual dimensions of $\vec{z}$ do not matter as long as it’s orthogonal to ${\vec{q}}_1$.

We now continue with the second part of the final step of our algorithm, where we calculate the normalized ${\vec{q}}_2=\left[\begin{array}{c}-\frac{\sqrt{10}}{10}\\ \frac{3\sqrt{10}}{10}\end{array}\right]$. We can illustrate our space as:

\usepackage{tikz}
 
\begin{document}
\begin{tikzpicture}
    % Vectors
    \draw[->, thick, green] (0,0) -- (2,3) node[midway, above left] {$\vec{a}_2$};
    \draw[->, thick, red] (0,0) -- (3,1) node[right] {$\vec{a}_1$};
    \draw[->, thick, dashed, pink] (0,0) -- (27/10,9/10) node[midway, below right] {$\mathrm{proj}_{\mathrm{Span}(\vec{q}_1)}(\vec{a}_2)$};
    \draw[->, thick, orange] (0,0) -- ({3 / sqrt(10)},{1 / sqrt(10)}) node[midway, below] {$\vec{q}_1$};
    \draw[->, thick, magenta] (0,0) -- (-7/10,21/10) node[left] {$\vec{z}_2$};
    \draw[->, thick, dashed, purple] (2,3) -- (27/10,9/10) node[midway, right] {$\vec{a}_2-\mathrm{proj}_{\mathrm{Span}(\vec{q}_1)}(\vec{a}_2)$};
    \draw[->, thick, yellow] (0,0) -- ({-sqrt(10) / 10},{3 * sqrt(10) / 10}) node[midway, left] {$\vec{q}_2$};
\end{tikzpicture}
\end{document}

As such, $\{{\vec{q}}_1,{\vec{q}}_2\}$ form an orthonormal basis for ${\mathbb{R}}^2$ where $\mathrm{Span}(\{{\vec{q}}_1,{\vec{q}}_2\}=\{{\vec{a}}_1,{\vec{a}}_2\}=$.

Case $l>n$

What if there was another vector ${\vec{a}}_3=\left[\begin{array}{c}-3\\ 1\end{array}\right]$ in our set such that our set is now $\{{\vec{a}}_1=\left[\begin{array}{c}3\\ 1\end{array}\right],{\vec{a}}_2=\left[\begin{array}{c}2\\ 3\end{array}\right],{\vec{a}}_3=\left[\begin{array}{c}-3\\ 1\end{array}\right]\}\in {\mathbb{R}}^2$? This step requires some more calculation in our algorithm. We can continue with how we left our algorithm above so that we calculate ${\vec{z}}_3:=\left[\begin{array}{c}-3\\ 1\end{array}\right]-\left(\left[\begin{array}{c}-\frac{3}{8}\\ -\frac{1}{8}\end{array}\right]+\left[\begin{array}{c}-\frac{1}{6}\\ \frac{1}{2}\end{array}\right]\right)=\left[\begin{array}{c}-\frac{59}{24}\\ \frac{5}{8}\end{array}\right]$. Note that the two vectors in the brackets (illustrated in pink in the plot below) represent ${\mathrm{proj}}_{\mathrm{Span}({\vec{q}}_1)}({\vec{a}}_3)$ and ${\mathrm{proj}}_{\mathrm{Span}({\vec{q}}_2)}({\vec{a}}_3)$ respectively. Check out the plot below for an illustration:

\usepackage{tikz}
 
\begin{document}
\begin{tikzpicture}
    % Vectors
    \draw[->, thick, green] (0,0) -- (2,3) node[midway, above left] {$\vec{a}_2$};
    \draw[->, thick, red] (0,0) -- (3,1) node[right] {$\vec{a}_1$};
    \draw[->, thick, teal] (0,0) -- (-3,1) node[midway, above left] {$\vec{a}_3$};
    \draw[->, thick, orange] (0,0) -- ({3 / sqrt(10)},{1 / sqrt(10)}) node[midway, below] {$\vec{q}_1$};
    \draw[->, thick, yellow] (0,0) -- ({-sqrt(10) / 10},{3 * sqrt(10) / 10}) node[midway, left] {$\vec{q}_2$};
    \draw[->, thick, pink] (0,0) -- (-3/8,-1/8) node[midway, above left]{};
    \draw[->, thick, pink] (0,0) -- (-1/6,1/2) node[midway, above left]{};
    \draw[->, thick, magenta] (0,0) -- (-59/24, 5/8) node[midway, below]{$\vec{z}_3$};
\end{tikzpicture}
\end{document}

Then, we can calculate the normalized version of ${\vec{z}}_3$ as ${\vec{q}}_3=\left[\begin{array}{c}-\frac{59}{\sqrt{3706}}\\ \frac{15}{\sqrt{3706}}\end{array}\right]$, represented below:

\usepackage{tikz}
 
\begin{document}
\begin{tikzpicture}
    % Vectors
    \draw[->, thick, green] (0,0) -- (2,3) node[midway, above left] {$\vec{a}_2$};
    \draw[->, thick, red] (0,0) -- (3,1) node[right] {$\vec{a}_1$};
    \draw[->, thick, teal] (0,0) -- (-3,1) node[midway, above left] {$\vec{a}_3$};
    \draw[->, thick, orange] (0,0) -- ({3 / sqrt(10)},{1 / sqrt(10)}) node[midway, below] {$\vec{q}_1$};
    \draw[->, thick, yellow] (0,0) -- ({-sqrt(10) / 10},{3 * sqrt(10) / 10}) node[midway, left] {$\vec{q}_2$};
    \draw[->, thick, pink] (0,0) -- (-3/8,-1/8) node[midway, above left]{};
    \draw[->, thick, pink] (0,0) -- (-1/6,1/2) node[midway, above left]{};
    \draw[->, thick, magenta] (0,0) -- (-59/24, 5/8) node[midway, below]{$\vec{z}_3$};
    \draw[->, thick, brown] (0,0) -- ({-59/sqrt(3706)}, {15 / sqrt(3706)}) node[midway, below]{$\vec{q}_3$};
\end{tikzpicture}
\end{document}

As such, the Gram-Schmidt process is inapplicable for $l>n$, where $n$ is the dimension of the vectors. This stems from the simple fact that in $n$-space, you cannot have more than $n$ linearly independent vectors.

Example

Extending Basis