Categories: Algorithms, Mathematics.

Gram-Schmidt method

Given a set of NN linearly independent vectors V1,V2,...\ket{V_1}, \ket{V_2}, ... from a Hilbert space, the Gram-Schmidt method is an algorithm that turns them into an orthonormal set n1,n2,...\ket{n_1}, \ket{n_2}, ... as follows (in Dirac notation):

  1. Take the first vector V1\ket{V_1} and normalize it to get n1\ket{n_1}:

    n1=V1V1V1\begin{aligned} \ket{n_1} = \frac{\ket{V_1}}{\sqrt{\inprod{V_1}{V_1}}} \end{aligned}
  2. Begin loop. Take the next input vector Vj\ket{V_j}, and subtract from it its projection onto every already-processed vector:

    gj=Vjn1n1Vjn2n2Vj...nj1nj1Vj\begin{aligned} \ket{g_j} = \ket{V_j} - \ket{n_1} \inprod{n_1}{V_j} - \ket{n_2} \inprod{n_2}{V_j} - ... - \ket{n_{j-1}} \inprod{n_{j-1}}{V_j} \end{aligned}

    This leaves only the part of Vj\ket{V_j} that is orthogonal to all previous nk\ket{n_k}. This why the input vectors must be linearly independent; otherwise gj\ket{g_j} could become zero.

    On a computer, the resulting gj\ket{g_j} will not be perfectly orthogonal due to rounding errors. The above description of step #2 is particularly bad. A better approach is:

    gj(1)=Vjn1n1Vjgj(2)=gj(1)n2n2gj(1)gj=gj(j1)=gj(j2)nj2nj2gj(j2)\begin{aligned} \ket{g_j^{(1)}} &= \ket{V_j} - \ket{n_1} \inprod{n_1}{V_j} \\ \ket{g_j^{(2)}} &= \ket{g_j^{(1)}} - \ket{n_2} \inprod{n_2}{g_j^{(1)}} \\ \vdots \\ \ket{g_j} = \ket{g_j^{(j-1)}} &= \ket{g_j^{(j-2)}} - \ket{n_{j-2}} \inprod{n_{j-2}}{g_j^{(j-2)}} \end{aligned}

    In other words, instead of projecting Vj\ket{V_j} directly onto all nk\ket{n_k}, we instead project only the part of Vj\ket{V_j} that has already been made orthogonal to all previous nm\ket{n_m} with m<km < k. This is known as the modified Gram-Schmidt method.

  3. Normalize the resulting orthogonal vector gj\ket{g_j} to make it orthonormal:

    nj=gjgjgj\begin{aligned} \ket{n_j} = \frac{\ket{g_j}}{\sqrt{\inprod{g_j}{g_j}}} \end{aligned}
  4. Loop back to step 2, taking the next vector Vj+1\ket{V_{j+1}}, until all NN have been processed.


  1. R. Shankar, Principles of quantum mechanics, 2nd edition, Springer.