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

As written, the assertion needs a nonzero-vector assumption: the singleton set containing the zero vector is mutually orthogonal but is linearly dependent. For the linear independence of nonzero orthogonal vectors, suppose ${\sum }_{i=1}^k{\alpha }_i{q}_i=0$. Taking the inner product with $q_j$ givesSince $q_j\ne 0$, positive definiteness gives $\Vert q_j{\Vert }^2>0$, hence ${\alpha }_j=0$. This holds for every $j$, proving linear independence under the necessary assumption.

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.

In the column convention used for QR factorization, an $m\times k$ real matrix has orthonormal columns when $Q^{T}Q=I_k$. This says that each column has unit norm and distinct columns have zero inner product. If $Q$ is square, then $Q^{T}Q=I$ provides a left inverse; a square matrix with a left inverse is invertible, so $Q^{-1}=Q^T$, and also $Q{Q}^T=I$. Such a square matrix is an orthogonal matrix. A rectangular matrix with orthonormal columns generally has no two-sided inverse.

The first two columns are already orthogonal and have norms 15 and 5. Their normalized versions are $q_1=(3,4,0,0{)}^T/5$ and $q_2=(0,0,4,-3{)}^T/5$. Their inner products with the third column are 10 and 5. Subtracting these projections leaves $(20,-15,0,0{)}^T$, whose norm is 25. Thus an economy-size QR factorization isDirect multiplication gives $Q^{T}Q=I_3$ and $QR=A$. If a full square $Q$ is required, append $q_4=(0,0,3,4{)}^T/5$ and append a zero fourth row to $R$; the product is unchanged and the completed $Q$ is an orthogonal matrix.