Gram-Schmidt Process

Dependencies:

1. Inner product space
2. Orthogonality and orthonormality
3. Span
4. Linear independence

$$ The Gram-Schmidt process takes a set of $n$ linearly independent vectors as input and outputs a set of $n$ orthogonal vectors which have the same span.

Let $W=\{w_1,w_2,\dots ,w_n\}$ be a linearly independent set of vectors from an inner product space. Then the Gram-Schmidt process outputs $V=\{v_1,v_2,\dots ,v_n\}$ where

$$v_i=w_i-\sum _{j=1}^{i-1}{c}_{i,j}{v}_j\text{where}{c}_{i,j}=\frac{⟨w_i,v_j⟩}{\Vert v_j{\Vert }^2}$$

Then:

• $\mathrm{span}(V)=\mathrm{span}(W)$.
• $\mathrm{\forall }i,v_i\ne 0$.
• $\mathrm{\forall }i\ne j,⟨v_i,v_j⟩=0$.

Also, scaling each $v_i$ by a (possibly different) non-zero scalar maintains orthogonality and does not change the span.

Proof by induction

Let $V_k=\{v_1,v_2,\dots ,v_k\}$ and $W_k=\{w_1,w_2,\dots ,w_k\}$.

Let the predicate $P(k)$ be the 'logical and' of the following statements:

1. $\mathrm{span}(V_k)=\mathrm{span}(W_k)$.
2. $\mathrm{\forall }i\le k,v_i\ne 0$.
3. $\mathrm{\forall }i<j\le k,⟨v_i,v_j⟩=⟨v_j,v_i⟩=0$.

Base case:

$v_1=w_1$.

1. $\mathrm{span}(V_1)=\mathrm{span}(\{v_1\})=\mathrm{span}(\{w_1\})=\mathrm{span}(W_1)$.
2. Since $W$ is linearly independent, $w_1\ne 0\Rightarrow v_1\ne 0$.
3. The third part of $P(1)$ is trivially true.

Therefore, $P(1)$ holds.

Inductive step:

Assume $P(k)$ is true (inductive hypothesis).

Part 1

$$\mathrm{\forall }i\le k,w_i\in \mathrm{span}(W_k)=\mathrm{span}(V_k)\subseteq \mathrm{span}(V_{k+1})$$

$$w_{k+1}=v_{k+1}+\sum _{j=1}^k{c}_{k+1,j}{v}_j\in \mathrm{span}(V_{k+1})$$

Since, each of $w_1,w_2,\dots ,w_{k+1}$ is a linear combination of $V_{k+1}$. Their linear combination is also a linear combination of $V_{k+1}$. Therefore, $\mathrm{span}(W_{k+1})\subseteq \mathrm{span}(V_{k+1})$.

$$\mathrm{\forall }i\le k,v_i\in \mathrm{span}(V_k)=\mathrm{span}(W_k)\subseteq \mathrm{span}(W_{k+1})$$

$$\begin{array}{rl}& \sum _{j=1}^k{c}_{k+1,j}{v}_j\in \mathrm{span}(V_k)=\mathrm{span}(W_k)\subseteq \mathrm{span}(W_{k+1})\\ & \Rightarrow v_{k+1}=w_{k+1}-\sum _{j=1}^k{c}_{k+1,j}{v}_j\in \mathrm{span}(W_{k+1})\end{array}$$

Since, each of $v_1,v_2,\dots ,v_{k+1}$ is a linear combination of $W_{k+1}$. Their linear combination is also a linear combination of $W_{k+1}$. Therefore, $\mathrm{span}(V_{k+1})\subseteq \mathrm{span}(W_{k+1})$.

Therefore, $\mathrm{span}(V_{k+1})=\mathrm{span}(W_{k+1})$, which is part 1 of $P(k+1)$.

Part 2

$$v_{k+1}=0⟹w_{k+1}=\sum _{i=1}^k{c}_{k+1,i}{v}_i\in \mathrm{span}(V_k)=\mathrm{span}(W_k)$$

$w_{k+1}\in \mathrm{span}(W_k)$ means $W_{k+1}$ is linearly dependent, which is a contradiction. Therefore, $v_{k+1}\ne 0$. Combining this fact with part 2 of $P(k)$, we get $\mathrm{\forall }i\le k+1,v_i\ne 0$, which is the part 2 of $P(k+1)$.

Part 3

Let $i\le k$.

$$\begin{array}{rl}⟨v_{k+1},v_i⟩& =⟨w_{k+1}-\sum _{j=1}^k\frac{⟨w_{k+1},v_j⟩}{\Vert v_j{\Vert }^2}{v}_j,v_i⟩\\ \text{(linearity in first argument)}& & =⟨w_{k+1},v_i⟩-\sum _{j=1}^k\frac{⟨w_{k+1},v_j⟩}{\Vert v_j{\Vert }^2}⟨v_j,v_i⟩\text{(}\because i\ne j\Rightarrow ⟨v_j,v_i⟩=0\text{)}& & =⟨w_{k+1},v_i⟩-\frac{⟨w_{k+1},v_i⟩}{\Vert v_i{\Vert }^2}⟨v_i,v_i⟩& =⟨w_{k+1},v_i⟩-⟨w_{k+1},v_i⟩=0\end{array}$$

$$\begin{array}{}\text{(by conjugate symmetry)}& ⟨v_i,v_{k+1}⟩=\overline{⟨v_{k+1},v_i⟩}=\bar{0}=0\end{array}$$

Combining the above fact with part 3 of $P(k)$, we get part 3 of $P(k+1)$.

Therefore, $P(n)$ is true by mathematical induction.

Dependency for:

1. Standard normal random vector on vector space
2. Symmetric operator iff hermitian
3. Symmetric operator on V has a basis of orthonormal eigenvectors
4. Joining orthogonal linindep sets

Info:

• Depth: 6
• Number of transitive dependencies: 8

Transitive dependencies:

1. Group
2. Ring
3. Field
4. Vector Space
5. Linear independence
6. Span
7. Inner product space
8. Orthogonality and orthonormality