GramSchmidt

GramSchmidt is an algorithm in linear algebra used to convert a finite sequence of vectors into an orthogonal (or orthonormal) sequence that spans the same subspace. Given a linearly independent set {v1, v2, ..., vk} in an inner product space such as R^n, the GramSchmidt process constructs vectors {u1, u2, ..., uk} satisfying u_i · u_j = 0 for i ≠ j and ||u_i|| > 0. In real spaces the inner product is the dot product; in complex spaces it is the Hermitian inner product.

The procedure proceeds sequentially. Start with u1 = v1. For i from 2 to k, compute w_i = v_i minus the sum of projections of v_i onto each previously computed u_j: w_i = v_i - sum_{j=1}^{i-1} proj_{u_j}(v_i). The vector is then normalized: u_i = w_i / ||w_i||. The projection onto u_j is proj_{u_j}(v_i) = (v_i · u_j) / (u_j · u_j) u_j in the real case, and proj_{u_j}(v_i) = (v_i^H u_j) / (u_j^H u_j) u_j in the complex case.

If none of the w_i is zero, the resulting set {u1, ..., uk} is orthonormal and spans the same subspace as {v1, ..., vk}. The GramSchmidt process is closely connected to the QR decomposition A = QR, where Q has orthonormal columns and R is upper triangular. Classical GramSchmidt can be numerically unstable with floating-point arithmetic, particularly for nearly dependent vectors; the modified Gram-Schmidt variant improves numerical stability. Variants and related methods, such as Householder reflections, are also used in numerical linear algebra.