3.6: Gram-Schmidt Process
- Page ID
- 96156
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)View Gram-Schmidt Process on YouTube
View Gram-Schmidt Process Example on YouTube
Given any basis for a vector space, we can use an algorithm called the Gram-Schmidt process to construct an orthonormal basis for that space. Let the vectors \(\text{v}_1,\: \text{v}_2,\cdots , \text{v}_n\) be a basis for some \(n\)-dimensional vector space. We will assume here that these vectors are column matrices, but this process also applies more generally.
We will construct an orthogonal basis \(\text{u}_1,\: \text{u}_2,\cdots , \text{u}_n\), and then normalize each vector to obtain an orthonormal basis. First, define \(\text{u}_1 = \text{v}_1\). To find the next orthogonal basis vector, define
\[\text{u}_2=\text{v}_2-\frac{(\text{u}_1^{\text{T}}\text{v}_2)\text{u}_1}{\text{u}_1^{\text{T}}\text{u}_1}.\nonumber \]
Observe that \(\text{u}_2\) is equal to \(\text{v}_2\) minus the component of \(\text{v}_2\) that is parallel to \(\text{u}_1\). By multiplying both sides of this equation with \(\text{u}_1^{\text{T}}\), it is easy to see that \(u_1^{\text{T}}\text{u}_2 = 0\) so that these two vectors are orthogonal.
The next orthogonal vector in the new basis can be found from
\[\text{u}_3=\text{v}_3-\frac{(\text{u}_1^{\text{T}}\text{v}_3)\text{u}_1}{\text{u}_1^{\text{T}}\text{u}_1}-\frac{(\text{u}_2^{\text{T}}\text{v}_3)\text{u}_2}{\text{u}_2^{\text{T}}\text{u}_2}.\nonumber \]
Here, \(\text{u}_3\) is equal to \(\text{v}_3\) minus the components of \(\text{v}_3\) that are parallel to \(\text{u}_1\) and \(\text{u}_2\). We can continue in this fashion to construct n orthogonal basis vectors. These vectors can then be normalized via
\[\hat{\text{u}}_1=\frac{\text{u}_1}{(\text{u}_1^{\text{T}}\text{u}_1)^{1/2}},\quad\text{etc.}\nonumber \]
Since \(\text{u}_k\) is a linear combination of \(\text{v}_1,\: \text{v}_2,\cdots , \text{v}_k\), the vector subspace spanned by the first \(k\) basis vectors of the original vector space is the same as the subspace spanned by the first \(k\) orthonormal vectors generated through the Gram-Schmidt process. We can write this result as
\[\text{span}\{\text{u}_1,\:\text{u}_2,\cdots ,\text{u}_k\}=\text{span}\{\text{v}_1,\:\text{v}_2,\cdots ,\text{v}_k\}.\nonumber \]
To give an example of the Gram-Schmidt process, consider a subspace of \(\mathbb{R}^4\) with the following basis:
\[W=\left\{\left(\begin{array}{c}1\\1\\1\\1\end{array}\right),\quad\left(\begin{array}{c}0\\1\\1\\1\end{array}\right),\quad\left(\begin{array}{c}0\\0\\1\\1\end{array}\right)\right\}=\{\text{v}_1,\:\text{v}_2,\:\text{v}_3\}.\nonumber \]
We use the Gram-Schmidt process to construct an orthonormal basis for this subspace. Let \(\text{u}_1 = \text{v}_1\). Then \(\text{u}_2\) is found from
\[\begin{aligned}\text{u}_2&=\text{v}_2-\frac{(\text{u}_1^{\text{T}}\text{v}_2)\text{u}_1}{\text{u}_1^{\text{T}}\text{u}_1} \\ &=\left(\begin{array}{c}0\\1\\1\\1\end{array}\right)-\frac{3}{4}\left(\begin{array}{c}1\\1\\1\\1\end{array}\right)=\frac{1}{4}\left(\begin{array}{r}-3\\1\\1\\1\end{array}\right).\end{aligned} \nonumber \]
Finally, we compute \(\text{u}_3\):
\[\begin{aligned}\text{u}_3&=\text{v}_3-\frac{(\text{u}_1^{\text{T}}\text{v}_3)\text{u}_1}{\text{u}_1^{\text{T}}\text{u}_1}-\frac{(\text{u}_2^{\text{T}}\text{v}_3)\text{u}_2}{\text{u}_2^{\text{T}}\text{u}_2} \\ &=\left(\begin{array}{c}0\\0\\1\\1\end{array}\right)-\frac{1}{2}\left(\begin{array}{c}1\\1\\1\\1\end{array}\right)-\frac{1}{6}\left(\begin{array}{r}-3\\1\\1\\1\end{array}\right)=\frac{1}{3}\left(\begin{array}{r}0\\-2\\1\\1\end{array}\right).\end{aligned} \nonumber \]
Normalizing the three vectors, we obtain the orthonormal basis
\[W'=\left\{\frac{1}{2}\left(\begin{array}{c}1\\1\\1\\1\end{array}\right),\quad\frac{1}{2\sqrt{3}}\left(\begin{array}{r}-3\\1\\1\\1\end{array}\right),\quad\frac{1}{\sqrt{6}}\left(\begin{array}{r}0\\-2\\1\\1\end{array}\right)\right\}.\nonumber \]