Gram-Schmidt Algorithm

A process to make two vectors Orthogonal.

Procedure

• Let $\{{\beta }_1,\dots ,{\beta }_j\}$ be a Linearly Independent set of vectors
• Consider set of vectors $\{{\alpha }_1,\dots ,{\alpha }_n\}$

1. ${\alpha }_1={\beta }_1$
2. ${\alpha }_2={\beta }_2-\frac{⟨{\beta }_2|{\alpha }_1⟩}{⟨{\alpha }_1|{\alpha }_1⟩}{\alpha }_1$
3. …
4. ${\alpha }_j={\beta }_k-{\sum }_{i=1}^{k-1}\frac{⟨{\beta }_k|{\alpha }_i⟩}{⟨{\alpha }_i|{\alpha }_1⟩}{\alpha }_i$

Intuition

1. Pick a first vector to base everything off. This first vector is now a fundamental basis vector.
2. The second vector is projected down with the first vector, and that component is subtracted from the second vector. This second vector is now a fundamental basis vector
3. The third vector is projected down with second, that component is subtracted, projected down with first vector, that component is subtracted. Now the third vector is a fundamental basis vector
4. Repeat for all other vectors

Proof

Using Strong Induction

1. Firstly note that $||{\alpha }_i||\ne 0$
2. We can define $\beta$ as follows

Proving All Units are Unit Vector

1. First, we prove every vector is a Unit Vector
2. $⟨\frac{{\alpha }_i}{||{\alpha }_i||}|\frac{{\alpha }_i}{||{\alpha }_i||}⟩=\frac{1}{||{\alpha }_i||\cdot ||{\alpha }_i||}\cdot ⟨{\alpha }_i|{\alpha }_i⟩=\frac{||{\alpha }_i|{|}^2}{||{\alpha }_i|{|}^2}=1$

Proving $\beta$ is an Orthogonal Set

1. We show that $⟨\frac{{\alpha }_i}{||{\alpha }_i||}|\frac{{\alpha }_j}{||{\alpha }_j||}⟩=0⟺i\ne j$
2. Note that $⟨\frac{{\alpha }_i}{||{\alpha }_i||}|\frac{{\alpha }_j}{||{\alpha }_j||}⟩=\frac{1}{||{\alpha }_i||\ast ||{\alpha }_j||}⟨{\alpha }_i|{\alpha }_j⟩=0⟺⟨{\alpha }_i|{\alpha }_j⟩=0$
3. Now we show $⟨{\alpha }_i|{\alpha }_j⟩=0⟺i\ne j$
4. Proof with strong induction:

Base Case

1. Base case $n=2$
2. Then, $⟨{\alpha }_2|{\alpha }_1⟩=⟨{\beta }_2-\frac{⟨{\beta }_2-{\alpha }_1⟩}{⟨{\alpha }_1|{\alpha }_1⟩}\ast {\alpha }_1|{\alpha }_1⟩$
3. $=⟨{\beta }_2|{\alpha }_1⟩-\frac{⟨{\beta }_2|{\alpha }_1⟩}{⟨{\alpha }_1|{\alpha }_1⟩}\cdot ⟨{\alpha }_1|{\alpha }_1⟩$
4. $=0$

$n+1$ case

1. Assume the set $\{{\alpha }_1,\dots ,{\alpha }_n\}$ is Orthogonal Set
2. Then, this means $⟨{\alpha }_i|{\alpha }_j⟩=0,\forall i\ne j\in \{1,\dots ,n\}$
3. Consider $⟨{\alpha }_{n+1}|{\alpha }_k⟩$ where $k\in \{1,\dots ,n\}$
4. $⟨{\alpha }_{n+1}|{\alpha }_k⟩=⟨{\beta }_{n+1}-{\sum }_{i=1}^n\frac{⟨{\beta }_{n+1}|{\alpha }_i⟩}{⟨{\alpha }_i|{\alpha }_i⟩}\cdot {\alpha }_i|{\alpha }_k⟩$
5. $=⟨{\beta }_{n+1}|{\alpha }_k-⟩-{\sum }_{i=1}^n\frac{⟨{\beta }_{n+1}|{\alpha }_i⟩}{⟨{\alpha }_i|{\alpha }_k⟩}⟨{\alpha }_i|{\alpha }_k⟩-\frac{⟨{\beta }_{n+1}|{\alpha }_k}{⟨{\alpha }_k|{\alpha }_k⟩}⟨{\alpha }_k|{\alpha }_k⟩-{\sum }_{i=1}^n\frac{⟨{\beta }_{n+1}|{\alpha }_i⟩}{⟨{\alpha }_i|{\alpha }_i⟩}⟨{\alpha }_i|{\alpha }_k⟩$