Download original notes
PAGE 1

6.4 The Gram-Schmidt Process

\[ \left\{ \vec{u}_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \vec{u}_2 = \begin{bmatrix} 3 \\ 4 \end{bmatrix} \right\} \]

\( \vec{u}_1 \) and \( \vec{u}_2 \) are linearly independent but not orthogonal.

Modify this into an orthogonal set?

Subtract from \( \vec{u}_2 \) the component along \( \vec{u}_1 \). Then \( \vec{u}_1 = \vec{v}_1 \) and \( \vec{v}_2 \) are orthogonal.

\[ \hat{u}_2 = \frac{\vec{u}_2 \cdot \vec{u}_1}{\vec{u}_1 \cdot \vec{u}_1} \vec{u}_1 \]
Vector diagram showing u1 and u2, with the projection of u2 onto u1 labeled as u2-hat and the orthogonal component v2.
\[ \hat{u}_2 = \frac{11}{5} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 11/5 \\ 22/5 \end{bmatrix} \]
\[ \vec{v}_2 = \vec{u}_2 - \hat{u}_2 = \begin{bmatrix} 3 \\ 4 \end{bmatrix} - \begin{bmatrix} 11/5 \\ 22/5 \end{bmatrix} = \begin{bmatrix} 4/5 \\ -2/5 \end{bmatrix} \]
PAGE 2

now \( \{ \vec{v}_1, \vec{v}_2 \} = \left\{ \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \begin{bmatrix} 4/5 \\ -2/5 \end{bmatrix} \right\} \) is orthogonal

Example

\[ \left\{ \vec{x}_1 = \begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix}, \vec{x}_2 = \begin{bmatrix} -2 \\ -1 \\ 0 \end{bmatrix}, \vec{x}_3 = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} \right\} \text{ not mutually orthogonal} \]
\[ \vec{v}_1 = \vec{x}_1 = \begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix} \]
\[ \vec{v}_2 = \vec{x}_2 - \frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1} \vec{v}_1 = \begin{bmatrix} -2 \\ -1 \\ 0 \end{bmatrix} - \frac{-5}{6} \begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix} = \begin{bmatrix} -1 \\ -1/2 \\ -5/6 \end{bmatrix} \]

Note: Component of \( \vec{x}_2 \) along \( \vec{v}_1 \). To make fractions disappear for convenience, we can scale the vector.

\[ \vec{v}_2 = \begin{bmatrix} -2 \\ 3 \\ -1 \end{bmatrix} \]
\[ \vec{v}_3 = \vec{x}_3 - \frac{\vec{x}_3 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1} \vec{v}_1 - \frac{\vec{x}_3 \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2} \vec{v}_2 \]
  • First subtraction gets rid of component of \( \vec{x}_3 \parallel \vec{v}_1 \)
  • Second subtraction gets rid of component of \( \vec{x}_3 \parallel \vec{v}_2 \)
PAGE 3
\[ = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} - \frac{1}{6} \begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix} - \frac{1}{14} \begin{bmatrix} -2 \\ 3 \\ -1 \end{bmatrix} \]\[ = \begin{bmatrix} 17/21 \\ 34/21 \\ 68/21 \end{bmatrix} = \begin{bmatrix} 17 \\ 34 \\ 68 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 4 \end{bmatrix} \]

now \( \left\{ \begin{bmatrix} 2 \\ 1 \\ -1 \end{bmatrix}, \begin{bmatrix} -2 \\ 3 \\ -1 \end{bmatrix}, \begin{bmatrix} 1 \\ 2 \\ 4 \end{bmatrix} \right\} \) is orthogonal

Gram-Schmidt Process

in general, given \( \{ \vec{x}_1, \dots, \vec{x}_p \} \), Gram-Schmidt process is

\[ \vec{v}_1 = \vec{x}_1 \]\[ \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}_3 = \vec{x}_3 - \frac{\vec{x}_3 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1} \vec{v}_1 - \frac{\vec{x}_3 \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2} \vec{v}_2 \]\[ \vec{v}_4 = \vec{x}_4 - \frac{\vec{x}_4 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1} \vec{v}_1 - \frac{\vec{x}_4 \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2} \vec{v}_2 - \frac{\vec{x}_4 \cdot \vec{v}_3}{\vec{v}_3 \cdot \vec{v}_3} \vec{v}_3 \]\[ \vdots \]
PAGE 4

QR Factorization of Matrices

If \( A \) is an \( m \times n \) matrix with linearly independent columns, then \( A = QR \) where \( Q \) is an \( m \times n \) matrix whose columns form an orthonormal basis for \( \text{Col } A \) and \( R \) is an \( n \times n \) upper triangular matrix w/ positive entries on the main diagonal.

Example

\[ A = \begin{bmatrix} 0 & 4 \\ 8 & 6 \\ 4 & -7 \end{bmatrix} \]

independent but not orthogonal

first, apply Gram-Schmidt process

\[ \vec{v}_1 = \vec{x}_1 = \begin{bmatrix} 0 \\ 8 \\ 4 \end{bmatrix} \]\[ \vec{v}_2 = \vec{x}_2 - \frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1} \vec{v}_1 = \begin{bmatrix} 4 \\ 6 \\ -7 \end{bmatrix} - \frac{20}{80} \begin{bmatrix} 0 \\ 8 \\ 4 \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \\ -8 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} \]
PAGE 5

QR Decomposition: Normalizing Vectors

Given the initial vectors:

\[ \vec{v}_1 = \begin{bmatrix} 0 \\ 8 \\ 4 \end{bmatrix} = \begin{bmatrix} 0 \\ 2 \\ 1 \end{bmatrix}, \quad \vec{v}_2 = \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} \]

are not orthonormal yet

Normalizing to Unit Vectors

We calculate the unit vectors \( \vec{u}_1 \) and \( \vec{u}_2 \) by dividing each vector by its magnitude:

\[ \vec{u}_1 = \frac{\vec{v}_1}{\|\vec{v}_1\|} = \begin{bmatrix} 0 \\ 2/\sqrt{5} \\ 1/\sqrt{5} \end{bmatrix}, \quad \vec{u}_2 = \frac{\vec{v}_2}{\|\vec{v}_2\|} = \begin{bmatrix} 1/\sqrt{6} \\ 1/\sqrt{6} \\ -2/\sqrt{6} \end{bmatrix} \]

Constructing Matrix Q

The matrix \( Q \) is formed by using the orthonormal vectors as columns:

\[ Q = \begin{bmatrix} 0 & 1/\sqrt{6} \\ 2/\sqrt{5} & 1/\sqrt{6} \\ 1/\sqrt{5} & -2/\sqrt{6} \end{bmatrix} \]

The QR Factorization Form

We express the original matrix \( A \) as the product of \( Q \) and \( R \):

\[ A = QR \]
\[ \underbrace{\begin{bmatrix} 0 & 4 \\ 8 & 6 \\ 4 & -7 \end{bmatrix}}_{3 \times 2} = \underbrace{\begin{bmatrix} 0 & 1/\sqrt{6} \\ 2/\sqrt{5} & 1/\sqrt{6} \\ 1/\sqrt{5} & -2/\sqrt{6} \end{bmatrix}}_{3 \times 2} \underbrace{R}_{2 \times 2} \]
PAGE 6

QR Decomposition: Solving for R

Matrices Q and QT

\[ Q = \begin{bmatrix} 0 & 1/\sqrt{6} \\ 2/\sqrt{5} & 1/\sqrt{6} \\ 1/\sqrt{5} & -2/\sqrt{6} \end{bmatrix}, \quad Q^T = \begin{bmatrix} 0 & 2/\sqrt{5} & 1/\sqrt{5} \\ 1/\sqrt{6} & 1/\sqrt{6} & -2/\sqrt{6} \end{bmatrix} \]

Orthogonality Property

Since the columns of \( Q \) are orthonormal, \( Q^T Q \) results in the identity matrix \( I \):

\[ Q^T Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I \]

Calculating Matrix R

To find \( R \), we multiply both sides of \( A = QR \) by \( Q^T \):

\[ A = QR \]\[ Q^T A = Q^T Q R = R \]

Performing the matrix multiplication:

\[ R = \begin{bmatrix} 0 & 2/\sqrt{5} & 1/\sqrt{5} \\ 1/\sqrt{6} & 1/\sqrt{6} & -2/\sqrt{6} \end{bmatrix} \begin{bmatrix} 0 & 4 \\ 8 & 6 \\ 4 & -7 \end{bmatrix} = \begin{bmatrix} 20/\sqrt{5} & 5/\sqrt{5} \\ 0 & 24/\sqrt{6} \end{bmatrix} \]