Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 4 / b / Solution

The Gram-Schmidt process constructs the vectors in order:The empty sum at $j=1$ is zero. Each subtraction removes the projection onto one previous unit vector, so $v_j$ is orthogonal to their span. Linear independence of the inputs ensures $v_j\ne 0$ in exact arithmetic, and normalization gives unit length.

In floating-point arithmetic, subtracting nearly equal projections can amplify roundoff and cause loss of orthogonality, especially for nearly dependent columns. Modified Gram-Schmidt, reorthogonalization, or Householder QR factorization can improve numerical behaviour; no implementation can remove the underlying sensitivity of nearly dependent input data.