Categories: Algorithms, Mathematics.

Gram-Schmidt method

Given a set of linearly independent non-orthonormal vectors \(\ket*{V_1}, \ket*{V_2}, ...\) from a Hilbert space, the Gram-Schmidt method turns them into an orthonormal set \(\ket*{n_1}, \ket*{n_2}, ...\) as follows:

1. Take the first vector \(\ket*{V_1}\) and normalize it to get \(\ket*{n_1}\):

   \[\begin{aligned} \ket*{n_1} = \frac{\ket*{V_1}}{\sqrt{\braket*{V_1}{V_1}}} \end{aligned}\]

2. Begin loop. Take the next non-orthonormal vector \(\ket*{V_j}\), and subtract from it its projection onto every already-processed vector:

   \[\begin{aligned} \ket*{n_j'} = \ket*{V_j} - \ket*{n_1} \braket*{n_1}{V_j} - \ket*{n_2} \braket*{n_2}{V_j} - ... - \ket*{n_{j-1}} \braket*{n_{j-1}}{V_{j-1}} \end{aligned}\]

   This leaves only the part of \(\ket*{V_j}\) which is orthogonal to \(\ket*{n_1}\), \(\ket*{n_2}\), etc. This why the input vectors must be linearly independent; otherwise \(\ket{n_j'}\) may become zero at some point.

3. Normalize the resulting orthogonal vector \(\ket*{n_j'}\) to make it orthonormal:

   \[\begin{aligned} \ket*{n_j} = \frac{\ket*{n_j'}}{\sqrt{\braket*{n_j'}{n_j'}}} \end{aligned}\]

4. Loop back to step 2, taking the next vector \(\ket*{V_{j+1}}\).

If you are unfamiliar with this notation, take a look at Dirac notation.