Gram-Schmidt Orthogonalization

Section 6.2 Gram-Schmidt Orthogonalization

In this section, we look at how to construct an orthogonal basis of \(\R^n\) from a basis.

Let \(\{v_1,\ldots, v_n\}\) be a basis of \(\R^n\text{.}\) Define

\begin{align*} u_1: =\amp v_1\\ u_2: =\amp v_2 -\frac{u_2\cdot u_1}{\norm{u_1}^2}u_1\\ u_3: =\amp v_3 -\frac{v_3\cdot u_1}{\norm{u_1}^2}u_1-\frac{v_3\cdot u_2}{\norm{u_2}^2}u_2\\ \amp \vdots\\ u_n: =\amp v_n -\frac{v_n\cdot u_1}{\norm{u_1}^2}u_1-\cdots -\frac{v_n\cdot u_{n-1}}{\norm{u_{n-1}}^2}u_{n-1} \end{align*}

🔗

In view of Ex. Checkpoint 6.1.4, it is easy to see that \(\{u_1,\ldots, u_n\}\) is an orthogonal basis of \(\R^n\text{.}\) Now we normalize \(u_i's\text{.}\) Define \(q_i=\frac{u_i}{\norm{u_i}}\text{.}\) Then \(\{q_1,\cdots, q_n\}\) is an orthononal basis of \(\R^n\text{.}\) Note that we could have defined \(q_i\) immediately after defining \(u_i\text{.}\)

🔗

This process is called the Gram-Schmidt orthogonalization process.

🔗

Geometrically \(u_2\text{,}\) constructed by subtracting the orthogonal projection of \(v_2\) on to \(u_1\text{.}\) In order to construct \(u_3\text{,}\) we take sum of orthogonal projections of \(v_3\) onto \(u_1\) and \(u_2\text{,}\) which is the orthogonal projection of the plane spanned by \(u_1\) and \(u_2\) and subtract this from \(v_3\text{.}\) Readers are encouraged to draw figures. Also explore the Sage interact applet by changing the basis vectors.

🔗

Figure 6.2.1. Goemetry of Linear Tranformation

🔗

Example 6.2.2.

Consider a linearly independ set of vectors \(v_1=(2,1)\) and \(v_2=(2,4)\text{.}\) Refer to Figure 6.2.3 to see the geometric meaning of the Gram-Schmidt orthogonalization in \(\R^2\text{.}\)

Figure 6.2.3. Gram-Schmidt Orthogonalization in \(\R^2\text{.}\)
🔗

🔗

Example 6.2.4.

Use the Gram-Schmidt orthogonalization process to find an orthonormal basis of \(\R^3\) starting with a basis \(\{(0,1,1), (1,1,1), (1,-2,2)\}\text{.}\) Let \(v_1 = (0, 1, 1), v_2=(1, 1, 1), v_3=(1, -2, 2)\text{.}\) Then we have

\begin{align*} u_1: = \amp (0, 1, 1)\\ u_2: = \amp v_2 -\frac{u_2\cdot u_1}{\norm{u_1}^2}u_1=(1, 1, 1)-\frac{2}{2}(0,1,1)=(1,0,0)\\ u_3:= \amp v_3 -\frac{u_3\cdot u_1}{\norm{u_1}^2}u_1-\frac{u_3\cdot u_2}{\norm{u_2}^2}u_2\\ = \amp (1, -2, 2)-\frac{0}{2}(0,1,1)-\frac{1}{1}(1,0,0)=(0,-2,2) \end{align*}

🔗

Thus the orthonormal basis obtained from the given basis is

\begin{equation*} \left\{q_1 = \left(0, \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right), q_2=(1,0,0), q_3 =\left(0,\frac{-1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right)\right\}\text{.} \end{equation*}

🔗

Example 6.2.5.

Consider the matrix \(A=\left(\begin{array}{rrrr} -1 \amp 1 \amp 0 \amp 1 \\ 1 \amp -1 \amp 0 \amp 1 \\ -1 \amp 0 \amp 2 \amp 1 \end{array} \right)\text{.}\) Find an orthogonal basis of the row space of \(A\text{.}\) It is easy to check that rank of \(A\) is 3. Hence row are linearly independent vectors in \(\R^4\text{.}\)

🔗

Let \(v_1=(-1,1,0,1), v_2 = (1,-1,0,1), v_3=(-1,0,2,1) \text{.}\)

\begin{align*} u_1: = \amp (-1,1,0,1)\\ u_2: = \amp v_2 -\frac{u_2\cdot u_1}{\norm{u_1}^2}u_1\\ =\amp (1,-1,0,1)-\frac{-1}{3}(-1,1,0,1)=(2/3, -2/3, 0, 4/3)\\ u_3: = \amp v_3 -\frac{u_3\cdot u_1}{\norm{u_1}^2}u_1-\frac{u_3\cdot u_2}{\norm{u_2}^2}u_2\\ = \amp (-1,0,2,1)-\frac{2}{3}(-1,1,0,1)-\frac{2/3}{9/2}(2/3, -2/3, 0, 4/3)\\ =\amp (-1/2, -1/2, 2, 0) \end{align*}

🔗

Hence

\begin{equation*} \{(-1, 1, 0, 1), (2/3, -2/3, 0, 4/3), (-1/2, -1/2, 2, 0)\} \end{equation*}

is an orthogonal basis of the row space of \(A\text{.}\)

🔗

Sage also has an inbuilt method for Gramm-Schmidt orthogonalization process. For example, A.gram_schmidt() performs Gram-Schmidt orthogonalization on the rows of the matrix, \(A\) returning a new matrix and a matrix accomplishing the transformation.

🔗

Here \(Q\) is the matrix whose rows are nothing but orthogonal vectors obtained by Gram-Schmidt and \(R\) is an upper triangular matrix. We shall see meaning of \(R\) and how it is obtained in later sections.

🔗

Checkpoint 6.2.6.

Use the Gram-Schmidt orthogonalization process to find an orthonormal basis of \(\R^3\) starting with a basis \(\beta=\{(1,1,1),(-1,1,1),(-1,0,1)\}\text{.}\)

🔗

Checkpoint 6.2.7.

Use the Gram-Schmidt orthogonalization process to find an orthonormal basis of the subspace \(W\subset \R^4\) with basis

\begin{equation*} \beta = \{ (-1,1,1,0),(-1,0,1,0),(1,0,0,1)\}\text{.} \end{equation*}

🔗

Activity 6.2.1. Sage Routine for Gram-Schmidt Orthogonalizatio.

Let us create a Sage routine to find an orthogonal basis from a set of linearly independent set of vecrors \(S=\{v_1,\ldots,v_k\}\text{.}\)

🔗

Now let us call the above function.

🔗

We can check if the set of vectors thus orbtained is orthonormal?

🔗

Prev Top Next