Linear Algebra II HT23, Gram-Schmidt process

Created: February 06, 2023 | About these notes | View in context | Study these flashcards

Flashcards

The Gram-Schmidt process takes in a basis $[u _ 1, \ldots u _ n]$ and outputs an orthonormal basis $[w _ 1, \ldots, w _ n]$. What additional property does this orthonormal basis have?
\[\text{span}(u_1, \ldots, u_j) = \text{span}(w_1, \ldots, w_j)\]

for all $j \le n$.

How could you prove every finite dimensional inner product space has an orthonormal basis?

Use the Gram-Schmidt process.

Say you’ve been given a basis $[u _ 1, \ldots, u _ n]$ to construct an orthonormal basis from and have made it as far as $[w _ 1, \ldots, w _ {j-1}]$ where $\text{span}(u _ 1, \ldots, u _ {j-1}) = \text{span} (v _ 1, \ldots, v _ {j-1})$. What is the expression for $w _ j$ (the unnormalised basis vector), and then $v _ j$ (the normalised one)?
\[w_j = u_j - \sum^{j-1}_{k=1} \langle u_j , v_k \rangle v_k\]

and

\[v_j = \frac{w_j}{||w_j||}\]

What’s the main proof technique behind proving the validity of the Gram-Schmidt process, i.e.

Given $v _ 1, \ldots, v _ k$ lineraly independent vectors, then there exists $w _ 1, \ldots, w _ k$ such that:

  1. $w _ i$ are mutually orthogonal
  2. $\text{span}(w _ 1, \ldots, w _ i) = \text{span}(v _ 1, \ldots, v _ i)$

for each $i \le k$.

?

Proof by induction.

When proving the validity of the Gram-Schmidt process, i.e. that

Given $v _ 1, \ldots, v _ k$ lineraly independent vectors, then there exists $w _ 1, \ldots, w _ k$ such that:

  1. $w _ i$ are mutually orthogonal
  2. $\text{span}(w _ 1, \ldots, w _ i) = \text{span}(v _ 1, \ldots, v _ i)$

for each $i \le k$.

you proceed by induction. At some stage in the proof, you have to show (assuming the inductive hypothesis) that

\[\text{span}(v_1, \ldots, v_{k-1}, v_k) = \text{span}(w_1, \ldots, w_{k-1}, w_k)\]

Can you justify this?
\[\begin{aligned} \text{span}(v_1, \ldots, v_{k-1}, v_k) &= \text{span}(v_1, \ldots, v_{k-1}, v_k) \\\\ &= \text{span}(w_1, \ldots, w_{k-1}, w_k) \end{aligned}\]

Step one by the inductive hypothesis, and step two by the Steinitz exchange lemma.

Proofs

Prove (via the Gram-Schmidt process) that given $v _ 1, \ldots, v _ k$ lineraly independent vectors, then there exists $w _ 1, \ldots, w _ k$ such that:

  1. $w _ i$ are mutually orthogonal
  2. $\text{span}(w _ 1, \ldots, w _ i) = \text{span}(v _ 1, \ldots, v _ i)$

for each $i \le k$.

Todo.



Related posts