Gram-Schmidt Process
Step-by-Step Tutorial

How do you turn an ordinary basis into an orthogonal basis?

By using the Gram-Schmidt process, of course!

The Gram-Schmidt process is an algorithm for producing an orthogonal or orthonormal basis for any nonzero subspace of \(\mathbb{R}^{n}\).

So, if we are given a basis \(\left\{\vec{x}_{1}, \vec{x}_{2}, \ldots, \vec{x}_{p}\right\}\) for a finite dimensional subspace \(\mathrm{W}\) of \(\mathbb{R}^{n}\), we can find an orthogonal basis \(\left\{\vec{v}_{1}, \vec{v}_{2}, \ldots, \vec{v}_{p}\right\}\) for \(\mathrm{W}\) using the following process:

\begin{align*}
\begin{aligned}
& \overrightarrow{v_{1}}=\overrightarrow{x_{1}} \\
& \vec{v}_{2}=\vec{x}_{2}-\frac{\overrightarrow{x_{2}} \cdot \overrightarrow{v_{1}}}{\overrightarrow{v_{1} \cdot \vec{v}_{1}}} \vec{v}_{1} \\
& \vec{v}_{3}=\vec{x}_{3}-\frac{\vec{x}_{3} \cdot \vec{v}_{1}}{\overrightarrow{v_{1}} \cdot \vec{v}_{1}}-\vec{v}_{1}-\frac{\vec{x}_{3} \cdot \vec{v}_{2}}{\overrightarrow{v_{2}} \cdot \vec{v}_{2}} \vec{v}_{2} \\
& \vec{v}_{p}=\vec{x}_{p}-\frac{\vec{x}_{p} \cdot \vec{v}_{1}}{\overrightarrow{v_{1}} \cdot \vec{v}_{1}} \overrightarrow{v_{1}}-\frac{\vec{x}_{p} \cdot \vec{v}_{2}}{\overrightarrow{v_{2}} \cdot \vec{v}_{2}} \vec{v}_{2}-\ldots-\frac{\vec{x}_{p} \cdot \vec{v}_{p-1}}{\overrightarrow{v_{p-1} \cdot \vec{v}_{p-1}}} \vec{v}_{p-1}
\end{aligned}
\end{align*}

This may look intimidating at first, but it’s not so bad once you see it in action.

So, let’s look at an example.

Step-by-Step Gram-Schmidt Example

Transform the basis \(\vec{x}_{1}=\left[\begin{array}{l}2 \\ 1\end{array}\right]\) and \(\vec{x}_{2}=\left[\begin{array}{l}1 \\ 1\end{array}\right]\) in \(\mathbb{R}^{2}\) to an orthonormal basis (i.e., perpendicular unit basis) using the Gram-Schmidt algorithm.

Alright, so we need to find vectors \(\mathbb{R}^{n}\) and \(\mathbb{R}^{n}\) that are orthogonal to each other.

First, we will let \(\vec{v}_{1}\) equal \(\vec{x}_{1}\), so.

\[
\vec{v}_{1}=\vec{x}_{1}=\left[\begin{array}{l}
2 \\
1
\end{array}\right]
\]

Next, we will find the dot product for \(\vec{v}_{2}\).

\begin{aligned}
\vec{x}_2 \cdot \vec{v}_1 & =\left(\vec{x}_2\right)^T \cdot \vec{v}_1=\left[\begin{array}{ll}
1 & 1
\end{array}\right]\left[\begin{array}{l}
2 \\
1
\end{array}\right] \\
& =(1)(2)+(1)(1)=3\\\\
\end{aligned}

\begin{aligned}
\vec{v}_1 \cdot \vec{v}_1 & =\left(\vec{v}_1\right)^T \cdot \vec{v}_1=\left[\begin{array}{ll}
2 & 1
\end{array}\right]\left[\begin{array}{l}
2 \\
1
\end{array}\right] \\
& =(2)(2)+(1)(1)=5
\end{aligned}

Now, we will use our values and substitute them into our \(\vec{v}_{2}\) formula.

\[
\vec{v}_{2}=\vec{x}_{2}-\frac{\vec{x}_{2} \cdot \vec{v}_{1}}{\vec{v}_{1} \cdot \vec{v}_{1}} \vec{v}_{1}
\]

\[
\vec{v}_{2}=\left[\begin{array}{l}1 \\ 1\end{array}\right]-\frac{3}{5}\left[\begin{array}{l}2 \\ 1\end{array}\right]=\left[\begin{array}{c}-1 / 5 \\ 2 / 5\end{array}\right]
\]

So, our orthogonal basis is now.

\[
\left\{\vec{v}_{1}, \vec{v}_{2}\right\}=\left\{\left[\begin{array}{l}
2 \\
1
\end{array}\right],\left[\begin{array}{c}
-1 / 5 \\
2 / 5
\end{array}\right]\right\}
\]

Now to make these vectors into an orthonormal basis, we must scale our vectors to create unit vectors. Therefore, we need first to find their norms (lengths).

\begin{aligned}
\left\|\vec{v}_1\right\| &= \sqrt{(2)^2+(1)^2} \\
&= \sqrt{5}
\end{aligned}

\begin{aligned}
\left\|\vec{v}_2\right\| &= \sqrt{\left(\frac{-1}{5}\right)^2+\left(\frac{2}{5}\right)^2} \\
&= \sqrt{\frac{5}{25}} \\
&= \sqrt{\frac{1}{5}} \\
&= \frac{\sqrt{5}}{5}
\end{aligned}

Lastly, we normalize our basis to create perpendicular unit vectors or our orthonormal basis.

\begin{aligned}
& \overrightarrow{u_{1}}=\frac{\overrightarrow{v_{1}}}{\left\|\overrightarrow{v_{1}}\right\|} \\\\
& =\frac{1}{\left\|\overrightarrow{v_{1}}\right\|} \vec{v}_{1} \\\\
& =\frac{1}{\sqrt{5}}\left[\begin{array}{l}
2 \\
1
\end{array}\right] \\\\
& =\left[\begin{array}{c}
2 / \sqrt{5} \\
1 / \sqrt{5}
\end{array}\right] \\\\
& \vec{u}_{2}=\frac{\vec{v}_{2}}{\left\|\vec{v}_{2}\right\|} \\\\
& =\frac{1}{\left\|\vec{v}_{2}\right\|} \vec{v}_{2} \\\\
& =\frac{1}{(\sqrt{5} / 5)}\left[\begin{array}{c}
-1 / 5 \\
2 / 5
\end{array}\right] \\\\
& =\sqrt{5}\left[\begin{array}{c}
-1 / 5 \\
2 / 5
\end{array}\right] \\\\
& =\left[\begin{array}{c}
-\sqrt{5} / 5 \\
2 \sqrt{5} / 5
\end{array}\right]
\end{aligned}

Which means our orthonormal basis is the set \(\left\{\vec{u}_{1}, \vec{u}_{2}\right\}\)!

See, that wasn’t so bad.

And do you know what this means?

Orthonormal Basis and Real-World Applications

With the power of the Gram-Schmidt process, we can create an orthogonal basis for any spanning set!

Cool!

Additionally, this newfound skill will also allow us to factor matrices to help us solve various computer algorithms, find eigenvalues, and solve least-squares problems.

What kind of factorization, you may ask?

QR factorization!

QR Factorization and Example

If we let \(\mathrm{A}\) be an \(m \times n\) matrix with linearly independent columns, then \(\mathrm{A}\) can be factored into \(A=Q R\) where \(\mathrm{Q}\) is an \(m \times n\) orthogonal matrix whose columns form an orthonormal basis and \(\mathrm{R}\) is an \(n \times n\) upper triangular matrix with positive entries on its diagonal.

Once again, it’s best to work through an example to fully understand QR factorization, sometimes called \(\mathrm{QR}\) decomposition.

Find the QR factorization of \(A=\left[\begin{array}{lll}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{array}\right]\)

First, we must apply the Gram-Schmidt process to the columns of A to create an orthogonal basis.

\begin{equation}
\text { If } A=\underbrace{\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right]}_{x_1}, \underbrace{\left[\begin{array}{l}
0 \\
1 \\
1 \\
1
\end{array}\right]}_{x_2}, \underbrace{\left[\begin{array}{l}
0 \\
0 \\
1 \\
1
\end{array}\right]}_{x_3}
\end{equation}

\begin{equation}
\text { then let } \vec{v}_1=\vec{x}_1=\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right]
\end{equation}

Next, we find the necessary dot products for our formulas.

\begin{aligned}
\vec{x}_2 \cdot \vec{v}_1 & =\left(\vec{x}_2\right)^T \cdot \vec{v}_1 \\
& =\left[\begin{array}{llll}
0 & 1 & 1 & 1
\end{array}\right]\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right] \\
& =3\\\\
\end{aligned}

\begin{aligned}
\overrightarrow{v_1} \cdot \vec{v}_1 & =\left(\vec{v}_1\right)^T \cdot \vec{v}_1 \\
& =\left[\begin{array}{llll}
1 & 1 & 1 & 1
\end{array}\right]\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right] \\
& =4
\end{aligned}

\begin{aligned}
\vec{v}_2 &= \vec{x}_2-\frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1} \vec{v}_1 \\
&\Rightarrow \vec{v}_2=\left[\begin{array}{l}
0 \\
1 \\
1 \\
1
\end{array}\right]-\frac{3}{4}\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right] \\
&=\left[\begin{array}{c}
-3 / 4 \\
1 / 4 \\
1 / 4 \\
1 / 4
\end{array}\right]
\end{aligned}

Next, we will find the dot products necessary to find \(\vec{v}_{3}=\vec{x}_{3}-\frac{\vec{x}_{3} \cdot \vec{v}_{1}}{\overrightarrow{v_{1}} \cdot \vec{v}_{1}}-\frac{\vec{x}_{1}}{}-\vec{v}_{2}-\frac{v_{2}}{\overrightarrow{v_{2}} \cdot \vec{v}_{2}}\)

\begin{aligned}
\vec{x}_3 \cdot \vec{v}_1 & =\left(\vec{x}_3\right)^T \cdot \vec{v}_1 \\
& =\left[\begin{array}{llll}
0 & 0 & 1 & 1
\end{array}\right]\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right] \\
& =2\\\\
\end{aligned}

\begin{aligned}
\vec{x}_3 \cdot \vec{v}_2 & =\left(\vec{x}_3\right)^T \cdot \vec{v}_2 \\
& =\left[\begin{array}{llll}
0 & 0 & 1 & 1
\end{array}\right]\left[\begin{array}{c}
-3 / 4 \\
1 / 4 \\
1 / 4 \\
1 / 4
\end{array}\right] \\
& =\frac{1}{2}\\\\
\end{aligned}

\begin{aligned}
\vec{v}_1 \cdot \vec{v}_1 & =\left(\vec{v}_1\right)^T \cdot \vec{v}_1 \\
& =\left[\begin{array}{llll}
1 & 1 & 1 & 1
\end{array}\right]\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right] \\
& =4\\\\
\end{aligned}

\begin{aligned}
\vec{v}_3 & =\left[\begin{array}{l}
0 \\
0 \\
1 \\
1
\end{array}\right]-\frac{2}{4}\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right]-\frac{1 / 2}{3 / 4}\left[\begin{array}{c}
-3 / 4 \\
1 / 4 \\
1 / 4 \\
1 / 4
\end{array}\right] \\
& =\left[\begin{array}{c}
0 \\
-2 / 3 \\
1 / 3 \\
1 / 3
\end{array}\right]
\end{aligned}

So, the orthogonal basis is:

\begin{equation}
\left\{\left[\begin{array}{l}
1 \\
1 \\
1 \\
1
\end{array}\right],\left[\begin{array}{c}
-3 / 4 \\
1 / 4 \\
1 / 4 \\
1 / 4
\end{array}\right],\left[\begin{array}{c}
0 \\
-2 / 3 \\
1 / 3 \\
1 / 3
\end{array}\right]\right\}
\end{equation}

Now we need to find the norms (lengths) of each vector.

\begin{aligned}
\left\|\vec{v}_1\right\| & =\sqrt{(1)^2+(1)^2+(1)^2+(1)^2} \\
& =\sqrt{4} \\
& =2
\end{aligned}

\begin{aligned}
\left\|\vec{v}_2\right\| & =\sqrt{\left(\frac{-3}{4}\right)^2+\left(\frac{1}{4}\right)^2+\left(\frac{1}{4}\right)^2+\left(\frac{1}{4}\right)^2} \\
& =\sqrt{\frac{3}{4}} \\
& =\frac{\sqrt{3}}{2}
\end{aligned}

\begin{aligned}
\left\|\vec{v}_2\right\| & =\sqrt{(0)^2+\left(\frac{-2}{3}\right)^2+\left(\frac{1}{3}\right)^2+\left(\frac{1}{3}\right)^2} \\\\
& =\sqrt{\frac{1}{3}} \\\\
& =\frac{\sqrt{3}}{3}
\end{aligned}

Lastly, we normalize our basis to create perpendicular unit vectors or our orthonormal basis.

\begin{aligned}
\overrightarrow{u_1} & =\frac{\overrightarrow{v_1}}{\| \overrightarrow{v_1 \|}} \\\\
& =\frac{1}{\| \overrightarrow{v_1 \|}} \vec{v}_1 \\\\
& =\frac{1}{2}\left[\begin{array}{c}
1 \\
1 \\
1 \\
1
\end{array}\right] \\\\
& =\left[\begin{array}{c}
1 / 2 \\
1 / 2 \\
1 / 2 \\
1 / 2
\end{array}\right]
\end{aligned}

\begin{aligned}
\vec{u}_2 & =\frac{\vec{v}_2}{\left\|\vec{v}_2\right\|} \\\\
& =\frac{1}{\mid \vec{v}_2 \|} \overrightarrow{v_2} \\\\
& =\frac{1}{(\sqrt{3} / 2)}\left[\begin{array}{c}
-3 / 4 \\
1 / 4 \\
1 / 4 \\
1 / 4
\end{array}\right] \\\\
& =\frac{2 \sqrt{3}}{3}\left[\begin{array}{c}
-3 / 4 \\
1 / 4 \\
1 / 4 \\
1 / 4
\end{array}\right] \\\\
& =\left[\begin{array}{c}
-\sqrt{3} / 2 \\
\sqrt{3} / 6 \\
\sqrt{3} / 6 \\
\sqrt{3} / 6
\end{array}\right]
\end{aligned}

\begin{aligned}
\overrightarrow{u_3} & =\frac{\vec{v}_3}{\left\|\overrightarrow{v_3}\right\|} \\\\
& =\frac{1}{\left\|\vec{v}_3\right\|} \vec{v}_2 \\\\
& =\frac{1}{(\sqrt{3} / 3)}\left[\begin{array}{c}
0 \\
-2 / 3 \\
1 / 3 \\
1 / 3
\end{array}\right] \\\\
& =\sqrt{3}\left[\begin{array}{c}
0 \\
-2 / 3 \\
1 / 3 \\
1 / 3
\end{array}\right] \\\\
& =\left[\begin{array}{c}
0 \\
-\sqrt{6} / 3 \\
\sqrt{6} / 6 \\
\sqrt{6} / 6
\end{array}\right]
\end{aligned}

We now have our \(Q\) matrix

\begin{align*}
Q=\left[\begin{array}{ccc}
1 / 2 & -\sqrt{3} / 2 & 0 \\
1 / 2 & \sqrt{3} / 6 & -\sqrt{6} / 3 \\
1 / 2 & \sqrt{3} / 6 & \sqrt{6} / 6 \\
1 / 2 & \sqrt{3} / 6 & \sqrt{6} / 6
\end{array}\right]
\end{align*}

And now it’s time to find our \(\mathrm{R}\) matrix.

Since \(A=Q R\) then \(R=Q^{T} A\)

\begin{equation}
R=\left[\begin{array}{cccc}
1 / 2 & 1 / 2 & 1 / 2 & 1 / 2 \\
-\sqrt{3} / 2 & \sqrt{3} / 6 & \sqrt{3} / 6 & \sqrt{3} / 6 \\
0 & -\sqrt{6} / 3 & \sqrt{6} / 6 & \sqrt{6} / 6
\end{array}\right]\left[\begin{array}{ccc}
1 & 0 & 0 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
1 & 1 & 1
\end{array}\right]
\end{equation}

\begin{equation}
=\left[\begin{array}{ccc}
2 & 3 / 2 & 1 \\
0 & \sqrt{3} / 2 & \sqrt{3} / 3 \\
0 & 0 & \sqrt{6} / 3
\end{array}\right]
\end{equation}

Next Steps

And that’s it. You’ve successfully factored your matrix where \(\mathrm{Q}\) is an orthonormal matrix and \(\mathrm{R}\) is an upper triangular matrix! So, together we will:

• Work through numerous examples of how to apply the Gram-Schmidt process
• Create orthogonal bases
• Factor arbitrary matrices to find QR decomposition

Let’s jump right in.

Video Tutorial w/ Full Lesson & Detailed Examples

Get access to all the courses and over 450 HD videos with your subscription

Monthly and Yearly Plans Available

Get My Subscription Now

Still wondering if CalcWorkshop is right for you?
Take a Tour and find out how a membership can take the struggle out of learning math.