# 9.5: The Gram-Schmidt Orthogonalization procedure

We now come to a fundamentally important algorithm, which is called the **Gram-Schmidt orthogonalization procedure**. This algorithm makes it possible to construct, for each list of linearly independent vectors (resp. basis), a corresponding orthonormal list (resp. orthonormal basis).

Theorem 9.5.1

*If* \((v_1,\ldots,v_m) \) *is a list of linearly independent vectors in* \(V\), *then there exists an orthonormal list* \((e_1,\ldots,e_m) \) *such that*

\[ \Span(v_1,\ldots,v_k) = \Span(e_1,\ldots,e_k), \quad \text{for all \(k=1,\ldots,m\).} \label{9.5.1} \]

Proof

The proof is constructive, that is, we will actually construct vectors \(e_1,\ldots,e_m \) having the desired properties. Since \((v_1,\ldots,v_m) \) is linearly independent, \(v_k\neq 0 \) for each \(k=1,2,\ldots,m\). Set \(e_1=\frac{v_1}{\norm{v_1}}\). Then \(e_{1} \) is a vector of norm 1 and satisfies Equation (9.5.1) for \(k=1\). Next, set

\[\begin{equation*}

e_2 = \frac{v_2 - \inner{v_2}{e_1} e_1}{\norm{v_2 - \inner{v_2}{e_1} e_1}}.

\end{equation*} \]

This is, in fact, the normalized version of the orthogonal decomposition Equation(9.3.1)~\eqref{eq:orthogonal decomp}. I.e.,

\[\begin{equation*}

w = v_2 - \inner{v_2}{e_1}e_1,

\end{equation*} \]

where \(w\bot e_1\). Note that \(\norm{e_2}=1 \) and \(\Span(e_1,e_2)=\Span(v_1,v_2)\).

Now, suppose that \(e_1,\ldots,e_{k-1} \) have been constructed such that \((e_1,\ldots,e_{k-1})\) is an orthonormal list and \(\Span(v_1,\ldots,v_{k-1}) = \Span(e_1,\ldots,e_{k-1})\). Then define

\[\begin{equation*}

e_k = \frac{v_k - \inner{v_k}{e_1}e_1 - \inner{v_k}{e_2} e_2 - \cdots -\inner{v_k}{e_{k-1}} e_{k-1}}

{\norm{v_k - \inner{v_k}{e_1}e_1 - \inner{v_k}{e_2} e_2 - \cdots -\inner{v_k}{e_{k-1}} e_{k-1}}}.

\end{equation*} \]

Since \((v_1,\ldots,v_k) \) is linearly independent, we know that \(v_k\not\in \Span(v_1,\ldots,v_{k-1})\). Hence, we also know that \(v_k\not\in \Span(e_1,\ldots,e_{k-1})\). It follows that the norm in the definition of \(e_k \) is not zero, and so \(e_k \) is well-defined (i.e., we are not dividing by zero). Note that a vector divided by its norm has norm 1 so that \(\norm{e_k}=1\). Furthermore,

\[\begin{equation*}

\begin{split}

\inner{e_k}{e_i} &= \left\langle \frac{v_k - \inner{v_k}{e_1}e_1 - \inner{v_k}{e_2} e_2 - \cdots

-\inner{v_k}{e_{k-1}} e_{k-1}}

{\norm{v_k - \inner{v_k}{e_1}e_1 - \inner{v_k}{e_2} e_2 - \cdots -\inner{v_k}{e_{k-1}} e_{k-1}}},

e_i \right\rangle \\

&= \frac{\inner{v_k}{e_i} - \inner{v_k}{e_i}}

{\norm{v_k - \inner{v_k}{e_1}e_1 - \inner{v_k}{e_2} e_2 - \cdots -\inner{v_k}{e_{k-1}} e_{k-1}}}=0,

\end{split}

\end{equation*} \]

for each \(1\le i<k\). Hence, \((e_1,\ldots,e_k) \) is orthonormal.

\(\square\)

From the definition of \(e_k\), we see that \(v_k\in \Span(e_1,\ldots,e_k) \) so that \(\Span(v_1,\ldots,v_k) \subset \Span(e_1,\ldots,e_k)\). Since both lists \((e_1,\ldots,e_k) \) and \((v_1,\ldots,v_k) \) are linearly independent, they must span subspaces of the same dimension and therefore are the same subspace. Hence Equation (9.5.1) holds.

Example \(\PageIndex{2}\)

Take \(v_1=(1,1,0) \) and \(v_2=(2,1,1) \) in \(\mathbb{R}^3\). The list \((v_1,v_2) \) is linearly independent (as you should verify!). To illustrate the Gram-Schmidt procedure, we begin by setting

\[\begin{equation*}

e_1 = \frac{v_1}{\norm{v_1}} = \frac{1}{\sqrt{2}} (1,1,0).

\end{equation*} \]

Next, set

\[\begin{equation*}

e_2 = \frac{v_2 - \inner{v_2}{e_1}e_1}{\norm{v_2 - \inner{v_2}{e_1}e_1}}.

\end{equation*} \]

The inner product \(\inner{v_2}{e_1}=\frac{1}{\sqrt{2}}\inner{(1,1,0)}{(2,1,1)}=\frac{3}{\sqrt{2}}\),

so

\[\begin{equation*}

u_2 = v_2 - \inner{v_2}{e_1}e_1 = (2,1,1) - \frac{3}{2}(1,1,0) = \frac{1}{2}(1,-1,2).

\end{equation*} \]

Calculating the norm of \(u_2\), we obtain \(\norm{u_2}=\sqrt{\frac{1}{4}(1+1+4)} = \frac{\sqrt{6}}{2}\).

Hence, normalizing this vector, we obtain

\[\begin{equation*}

e_2 = \frac{u_2}{\norm{u_2}} = \frac{1}{\sqrt{6}}(1,-1,2).

\end{equation*} \]

The list \((e_1,e_2) \) is therefore orthonormal and has the same span as \((v_1,v_2)\).

Corollary 9.5.3.

Every finite-dimensional inner product space has an orthonormal basis.

Proof

Let \((v_1,\ldots,v_n) \) be any basis for \(V\). This list is linearly independent and spans \(V\). Apply the Gram-Schmidt procedure to this list to obtain an orthonormal list \((e_1,\ldots,e_n)\), which still spans \(V \) by construction. By Proposition9.4.2~\ref{prop:orth li}, this list is linearly independent and hence a basis of \(V\).

Corollary 9.5.4.

Every orthonormal list of vectors in \(V \) can be extended to an orthonormal basis of \(V\).

Proof

Let \((e_1,\ldots,e_m) \) be an orthonormal list of vectors in \(V\). By Proposition9.4.2~\ref{prop:orth li}, this list is linearly independent and hence can be extended to a basis \((e_1,\ldots,e_m,v_1,\ldots,v_k) \) of \(V \) by the **Basis Extension Theorem**. Now apply the Gram-Schmidt procedure to obtain a new orthonormal basis \((e_1,\ldots,e_m,f_1,\ldots,f_k)\). The first \(m \) vectors do not change since they already are orthonormal. The list still spans \(V \) and is linearly independent by Proposition9.4.2~\ref{prop:orth li} and therefore forms a basis.

Recall Theorem7.5.3~\ref{thm:ComplexLinearMapsUpperTriangularWrtSomeBasis}: given an operator \(T \in \mathcal{L}(V, V) \) on a complex vector space \(V\), there exists a basis \(B \) for \(V\) such that the matrix \(M(T)\) of \(T\) with respect to \(B \) is upper triangular. We would like to extend this result to require the additional property of orthonormality.

Corollary 9.5.5

Let \(V \) be an inner product space over \(\mathbb{F} \) and \(T\in\mathcal{L}(V,V)\). If \(T \) is upper-triangular with respect to some basis, then \(T \) is upper-triangular with respect to some orthonormal basis.

Proof

Let \((v_1,\ldots,v_n) \) be a basis of \(V \) with respect to which \(T \) is upper-triangular. Apply the Gram-Schmidt procedure to obtain an orthonormal basis \((e_1,\ldots,e_n)\), and note that

\[ \Span(e_1,\ldots,e_k) = \Span(v_1,\ldots,v_k), \quad \text{for all \(1\le k\le n\).} \]

We proved before that \(T \) is upper-triangular with respect to a basis \((v_1,\ldots,v_n) \) if and only if \(\Span(v_1,\ldots,v_k) \) is invariant under \(T \) for each \(1\le k\le n\). Since these spans are unchanged by the Gram-Schmidt procedure, \(T \) is still upper triangular for the corresponding orthonormal basis.

### Contributors

- Isaiah Lankham, Mathematics Department at UC Davis
- Bruno Nachtergaele, Mathematics Department at UC Davis
- Anne Schilling, Mathematics Department at UC Davis

Both hardbound and softbound versions of this textbook are available online at WorldScientific.com.