Categories: Algorithms, Mathematics.

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:

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}\]

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.

Normalize the resulting ortho

*gonal*vector \(\ket*{n_j'}\) to make it ortho*normal*:\[\begin{aligned} \ket*{n_j} = \frac{\ket*{n_j'}}{\sqrt{\braket*{n_j'}{n_j'}}} \end{aligned}\]

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.

© "Prefetch". Licensed under CC BY-SA 4.0.