QR decomposition

So chances are, if you've taken a first course in linear algebra you know about the Gram-Schmidt procedure (GS): it's an algorithm to produce, starting from one finite set of linearly independent vectors in any inner product space, a second set of vectors with the same linear span as the first one, but orthonormal. Particularly, the algorithm produces vectors such that the ith vector in the new set is in the linear span of the i first vectors of the original set (and vice versa). Quickly in formulas: given linearly independent vectors p₁ through p_n, the algorithm produces vectors q₁ through q_n, such that for all 1 ≤ i ≤ j ≤ n

span(q₁, ... q_n) = span(p₁, ... p_n),

q_i ∈ span(p₁, ... p_i),

p_i ∈ span(q₁, ... q_i),

<q_i,q_j> = δ_ij.

Thus, GS is a type of QR decomposition algorithm. That's because if you stack the vectors p₁ through p_n horizontally as columns of a matrix P, then the algorithm produces a decomposition of P into the product of a matrix Q with orthonormal columns, and an upper triangular matrix R. The matrix Q consists of the vectors q₁ through q_n as its columns, and the ith column of the matrix R gives the representation of p_i in the new orthonormal basis (its inverse, also upper triangular, gives the representations of the q-vectors in the p-basis). R is upper triangular because the representation of p_i in terms of the vectors q₁ through q_n involves non-zero coefficients in only the i first terms.

The QR decomposition (the result) should be distinguished from GS (the algorithm). QR decompositions are very useful in various numerical applications, but it turns out that the algorithm you want to use in these applications to compute the decomposition is never GS, because of GS's numerical instability issues. Instead, any standard linear algebra numerical library (such as LAPACK) should provide an optimized QR procedure which uses some combination of Givens rotations and Householder reflections. Still, GS is a great tool when writing proofs.