Notes - Numerical Analysis HT24, Tridiagonal matrices
Flashcards
Quickly describe an algorithm for converting a symmetric matrix $A \in \mathbb R^{n \times n}$ into a tridiagonal matrix via an orthogonal similarity transformation.
Suppose $A$ is of the form
\[A = \begin{pmatrix} \gamma & u^\top \\\\ u & B \end{pmatrix}\]where $u$ is a vector, $\gamma$ is a scalar, and $B$ is an $n-1 \times n -1$ symmetric matrix. Let $w = (0, \hat w)^\top$ be such that $H(\hat w) u = (\alpha, 0, \ldots, 0)$. Then
\[H(w)A = \begin{pmatrix} \gamma & u^\top & \cdots \\\\ \alpha & B' & \cdots\\\\ 0 & \vdots & \ddots \end{pmatrix}\]And also
\[H(w)AH(w)^\top = \begin{pmatrix} \gamma & \alpha & 0 \\\\ \alpha & B'' & \cdots\\\\ 0 & \vdots & \ddots \end{pmatrix}\]Then, repeating inductively, we can form a sequence of Householder reflectors such that
\[(H_{n-1} \cdots H_{1}) A (H_1 \cdots H_{n-1})\]such that the resulting matrix is tridiagonal.