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.
Write the symmetric $A$ in $2 \times 2$ block form (block sizes $1$ and $n-1$):
\[A = \begin{pmatrix} \gamma & u^\top \\\\ u & B \end{pmatrix}\]with $\gamma \in \mathbb R$, $u \in \mathbb R^{n-1}$, and $B \in \mathbb R^{(n-1) \times (n-1)}$ symmetric.
Choose $\hat w \in \mathbb R^{n-1}$ so the $(n-1) \times (n-1)$ Householder reflector $\hat H := H(\hat w)$ satisfies $\hat H u = \alpha e _ 1 = (\alpha, 0, \ldots, 0)^\top$, with $\alpha = \pm \|u\| _ 2$. Embed it as the $n \times n$ reflector
\[H = \begin{pmatrix} 1 & 0 \\\\ 0 & \hat H \end{pmatrix}\]which fixes the first coordinate (so it does not touch $\gamma$ or the first row/column).
Left multiply (acts on rows $2, \ldots, n$ only):
\[H A = \begin{pmatrix} 1 & 0 \\\\ 0 & \hat H \end{pmatrix} \begin{pmatrix} \gamma & u^\top \\\\ u & B \end{pmatrix} = \begin{pmatrix} \gamma & u^\top \\\\ \hat H u & \hat H B \end{pmatrix} = \begin{pmatrix} \gamma & u^\top \\\\ \alpha e _ 1 & B' \end{pmatrix}\]The $(2,1)$ block is the explicit column $\hat H u = (\alpha, 0, \ldots, 0)^\top$, and $B' := \hat H B$ is the whole $(n-1) \times (n-1)$ trailing block (no special structure, and not yet symmetric). The first row $(\gamma, u^\top)$ is unchanged.
Then right multiply by $H^\top = H$ (Householder reflectors are symmetric; acts on columns $2, \ldots, n$ only):
\[H A H^\top = \begin{pmatrix} \gamma & u^\top \\\\ \alpha e _ 1 & B' \end{pmatrix} \begin{pmatrix} 1 & 0 \\\\ 0 & \hat H \end{pmatrix} = \begin{pmatrix} \gamma & (\hat H u)^\top \\\\ \alpha e _ 1 & \hat H B \hat H \end{pmatrix} = \begin{pmatrix} \gamma & \alpha e _ 1^\top \\\\ \alpha e _ 1 & B'' \end{pmatrix}\]using $u^\top \hat H = (\hat H u)^\top = \alpha e _ 1^\top$. Now the first column and first row are both $(\gamma, \alpha, 0, \ldots, 0)$, the tridiagonal pattern in row/column $1$, and $B'' := \hat H B \hat H$ is symmetric and occupies the entire bottom-right $(n-1) \times (n-1)$ block.
Recurse on the trailing symmetric block $B''$, embedding each successive reflector as $\begin{pmatrix} I & 0 \\\\ 0 & \hat H _ k \end{pmatrix}$ so it fixes the already-tridiagonalised leading rows and columns. After $n-2$ two-sided steps,
\[(H _ {n-2} \cdots H _ 1)\, A \,(H _ 1 \cdots H _ {n-2}) = T\]is symmetric tridiagonal. Only $n-2$ reflectors are needed (the final trailing $2 \times 2$ block is already tridiagonal), and the transformation is an orthogonal similarity, so $\text{eig}(T) = \text{eig}(A)$.
Bite-sized
Why is tridiagonal form so valuable as preprocessing for the QR algorithm?
Once $A$ is tridiagonal, each QR step costs $O(n)$ via Givens (vs $O(n^2)$ for general Hessenberg, $O(n^3)$ for dense). Combined with the empirical $O(n)$ iterations of shifted QR per eigenvalue, total cost drops from a hypothetical $O(n^4)$ to $\tfrac{4}{3} n^3$ — the symmetric eigenvalue problem becomes genuinely $O(n^3)$.
Two-sided Householder similarity for symmetric $A$: apply $H _ k$ as $A \mapsto $ $H _ k A H _ k$, preserving symmetry and eigenvalues. The two-sided form is the key trick — one-sided $H _ k A$ would only zero column $k$ but break symmetry.