The Gram-Schmidt Process

Math 303: Section 30

Dr. Janssen

Intro

\[ \def\R{{\mathbb R}} \def\P{{\mathbb P}} \def\B{{\mathcal B}} \def\C{{\mathcal C}} \def\S{{\mathcal S}} \def\b{{\mathbf{b}}} \def\a{{\mathbf{a}}} \def\c{{\mathbf{c}}} \def\x{{\mathbf{x}}} \def\y{{\mathbf{y}}} \def\u{{\mathbf{u}}} \def\v{{\mathbf{v}}} \def\w{{\mathbf{w}}} \def\z{{\mathbf{z}}} \def\e{{\mathbf{e}}} \def\r{{\mathbf{r}}} \def\M{{\mathcal{M}}} \DeclareMathOperator{\null}{Nul} \DeclareMathOperator{\span}{Span} \DeclareMathOperator{\dim}{dim} \DeclareMathOperator{\proj}{proj} \DeclareMathOperator{\row}{Row} \DeclareMathOperator{\col}{Col} \DeclareMathOperator{\trace}{trace} \newcommand{\set}[1]{\left\{ {#1} \right\}} \newcommand{\setof}[2]{{\left\{#1\,\colon\,#2\right\}}} \newcommand{\norm}[1]{{\left|\! \left| #1 \right| \! \right|}} \newcommand{\ip}[1]{{\left\langle #1 \right\rangle}} \]

Big Question: given a basis for \(\R^n\), how do we make an orthogonal basis?

Preview Activity 30.1

In step 3, we can know it’s a basis since it’s got 3 orthogonal (hence LI) vectors in a 3-dimensional space.

Idea: given a subspace \(W\) and a basis, start by finding a vector \(\w_1\) in \(W\) orthogonal to the first basis vector. Then find a vector \(\w_2\) in \(W\) orthogonal to \(W_1 = \span\set{\w_1}\). The find a vector orthogonal to \(\span\set{\w_1, \w_2}\). Iterate.

Go through the derivation on pp. 532–533.

Theorem 30.1: Gram-Schmidt

Let \(\set{\v_1, \v_2, \ldots, \v_m}\) be a basis for a subspace \(W\) of an inner product space \(V\). The set \(\set{\w_1, \w_2, \ldots, \w_m}\) defined by:

• \(\w_1 = \v_1\),
• \(\w_2 = \v_2 - \frac{\ip{\v_2, \w_1}}{\ip{\w_1, \w_1}} \w_1\),
• \(\w_3 = \v_3 - \frac{\ip{\v_3, \w_1}}{\ip{\w_1, \w_1}} \w_1 - \frac{\ip{\v_3, \w_2}}{\ip{\w_2, \w_2}} \w_2\),
• \(\vdots\)
• \(\w_m = \v_m - \frac{\ip{\v_m, \w_1}}{\ip{\w_1, \w_1}} \w_1 - \frac{\ip{\v_m, \w_2}}{\ip{\w_2, \w_2}} \w_2 - \cdots - \frac{\ip{\v_m, \w_{m-1}}}{\ip{\w_{m-1}, \w_{m-1}}} \w_{m-1}\)

is an orthogonal basis for \(W\). Moreover, for each \(k\) satisfying \(1\le k \le m\),

\[ \span \set{\w_1, \w_2, \ldots, \w_k} = \span \set{\v_1, \v_2, \ldots, \v_k}. \]

Note that we can make it orthonormal by normalizing each vector.

Activity 30.1

Use the Gram-Schmidt process to find an orthogonal basis for each space \(W\) below.

• \(W = \span \set{\left[\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}\right], \left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right]}\).
• \(W = \span \set{1, t, t^2}\) in \(\P_2\) using the inner product \(\ip{p(t), q(t)} = \int_0^1 p(t) q(t)\, dt\).

The QR Factorization of a Matrix

multiple ways to factor a matrix: LU (upper/lower triangular), EVD (eigenvectors and diagonal matrices)

QR factorization: orthogonal matrix and upper triangular matrix

The QR factorization has applications to solving least squares problems and approximating eigenvalues of matrices.

Activity 30.2

Let \(A = \left[\begin{matrix} 1 & 0 \\ 0 & 0 \\ 0 & 2 \end{matrix}\right]\).

• Find an orthonormal basis for \(\col A\). Let \(\mathcal{B}\) be the basis formed by these vectors and \(Q\) the matrix whose columns are these orthonormal basis vectors.
• Write the columns of \(A\) as linear combinations of the columns of \(Q\). That is, if \(A = [ \mathbf{a}_1 \ \mathbf{a}_2]\), find \([\mathbf{a}_1]_\B\) and \([\mathbf{a}_2]_\B\). Let \(R = [[\mathbf{a}_1]_\B \ [\mathbf{a}_2]_\B]\).
• Find the product \(QR\) and compare it to \(A\).

The idea

Let \(A = [\a_1 \ \a_2 \ \a_3 \ \cdot \ \a_n]\) be \(m\times n\) with rank \(n\).

• Use Gram-Schimdt to find an orthonormal basis \(\set{\u_1, \u_2, \ldots, \u_n}\) for \(\col A\). Recall that \(\span \set{\u_1, \ldots, \u_k} = \span \set{\a_1, \ldots, \a_k}\) for all \(k\) between 1 and \(n\).
• Let \(Q = [\u_1 \ \u_2 \ \cdots \u_n]\). If \(1\le k\le n\), then \(\a_k \in \span\set{\u_1, \u_2, \ldots, \u_k}\) and \(\a_k = r_{k1} \u_1 + \r_{k2} \u_2 + \cdots + r_{kk}\u_k\).
• That is: \(Q [r_{k1} \ r_{k2} \ \cdots \ r_{kk} \ 0 \ \cdots 0]^\textsf{T} = \a_{k}\).
• Set \(\r_k = [r_{k1} \ r_{k2} \ \cdots \ r_{kk} \ 0 \ \cdots 0]^\textsf{T}\) for all \(k\) from 1 to \(n\).
• Then:

\[ A = [Q \r_1 \ Q \r_2 \ \cdots \ Q \r_n] = Q R, \]

where

\[ R = \left[\begin{matrix} r_{11} & r_{12} & r_{13} & \cdots & r_{1n-1} r_{1n} \\ 0 & r_{22} & r_{23} & \cdots & r_{2n-1} & r_{2n}\\ 0 & 0 & r_{33} & \cdots & r_{3n-1} & r_{3n} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & r_{nn} \end{matrix}\right] \]

note that \(Q\) is $m\(n\) with orthogonal columns, and \(R\) is \(n\times n\) and upper triangular.

Activity 30.3

Let \(A = \left[\begin{matrix} 1 & 0 & 2 \\ 0 & 2 & 0 \end{matrix}\right]\). Find the \(QR\) factorization, or explain why it does not have one.

The \(QR\) factorization can be used to approximate all eigenvalues of a matrix. Details omitted.