Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 41D / a / Solution

Starting with $A_0=A$, suppose columns $1,\dots ,j-1$ have already been reduced to tridiagonal form. Let $x$ be the part of column $j$ in rows $j+1,\dots ,n$. A Householder reflection $P_j$ on these coordinates can map $x$ to $\pm \Vert x\Vert e_1$. Extend it by the identity on the first $j$ coordinates and call the resulting orthogonal matrix $U_j$.

The updatezeros every entry below row $j+1$ in column $j$. Because it is an orthogonal similarity, it preserves eigenvalues; because the same transformation is applied on both sides, it preserves symmetry and zeros the corresponding row entries without disturbing earlier columns. After $n-2$ such steps,is symmetric and tridiagonal and has the same eigenvalues as $A$. Every reflector is obtained from finitely many matrix entries using finitely many arithmetic operations and a square root, so this is a finite construction.

Solved by gpt-5.6-sol high.