In Quantum Computation and Quantum Information by Nielson and Chaung, the Gram-Schmidt procedure is defined as: given that we have basis $w_1,...,w_d$ for some vector space $V$, we can construct an orthonormal basis set $v_1,...,v_d$ for V by inductively defining
$$ v_{k+1} = \frac{w_{k+1} - \sum^k_{i=1}\langle w_{k+1}, v_i\rangle \cdot v_i}{||w_{k+1} - \sum^k_{i=1}\langle w_{k+1}, v_i\rangle \cdot v_i||} $$
To further understand why this works, I found a proof online which can be found here. It uses proof by induction. Assuming that we have shown that the base case works, if we have $j > 1$, then we can define a set of vectors basis $w_1,...,w_{j-1}$ and $v_1,...,v_{j-1}$. We hence define $v_j$, then
$$ v_{j} = \frac{w_{j} - \langle w_j, v_1\rangle \cdot v_1 - \langle w_j, v_2\rangle \cdot w_2...\langle w_j, v_{j-1}\rangle \cdot v_{j-1}}{||w_{j} - \langle w_j, v_1\rangle \cdot v_1 - \langle w_j, v_2\rangle \cdot w_2...\langle w_j, v_{j-1}\rangle \cdot v_{j-1} ||} $$
Let $N = ||w_{j} - \langle w_j, v_1\rangle \cdot v_1 - \langle w_j, v_2\rangle \cdot w_2...\langle w_j, v_{j-1}\rangle \cdot v_{j-1} ||$ and $k$ be some integer less than $j$ but greater than or equal to 1. If we take the inner product of $v_j$ and $v_k$, we get:
$$ \langle v_{j}, v_{k} \rangle = \frac{1}{N}\langle w_{j} - \langle w_j, v_1\rangle \cdot v_1 - \langle w_j, v_2\rangle \cdot v_2...\langle w_j, v_{j-1}\rangle \cdot v_{j-1} , v_k \rangle \tag 1 $$
Hence, we get: $$ \langle v_{j}, v_{k} \rangle = \frac{1}{N}(\langle w_j, v_k \rangle - \langle w_j, v_k \rangle) = 0 \tag 2 $$
My questions are the following:
- Why does (1) reduce down to (2)? Maybe there exists a better proof to help me to understand this...?
- This is probably indirectly answered by the above question, but why does the subtraction $\langle w_{j}, v_i\rangle \cdot v_i$ from $w_j$ for $i \in [1,...j-1]$ produce an orthogonal vector? Is there some theorem that I am missing which explains this?
Thank you!