 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/digital-systems-linear-algebra-introduction-to-formal-proof/6/a/i/solution

For independent columns

a_{1}, \dots, a_{k}

u_{j} = a_{j} - \sum_{i < j} ⟨ q_{i}, a_{j} ⟩ q_{i}, q_{j} = \frac{u _{j}}{∥ u _{j} ∥} .

Each

u_{j}

subtracts the orthogonal projections onto earlier normalized vectors. Their independence ensures

u_{j} \neq = 0

. The resulting

q_{i}

are orthonormal and preserve the span of every initial column set. Putting

Q = (q_{1} \dots q_{k})

and

r_{ij} = ⟨ q_{i}, a_{j} ⟩

for

i \leq j

, with zeros below the diagonal, gives a QR decomposition

A = QR

with

Q^{T} Q = I

. Dependent input columns require omitting a zero residual or treating rank deficiency separately.

 New to topics? Read the docs here!