[proofplan]
We show that one step of shifted QR iteration preserves the symmetric tridiagonal structure. The argument has two parts: (1) the orthogonal factor $Q$ from the QR factorisation of the tridiagonal matrix $A - sI$ is upper Hessenberg, because the Givens rotations used to triangularise a tridiagonal matrix produce a $Q$ with $Q_{ij} = 0$ for $i > j + 1$; (2) the product $A^+ = RQ + sI = Q^\top AQ$ is symmetric (by orthogonal similarity of a symmetric matrix), and a symmetric upper Hessenberg matrix is tridiagonal.
[/proofplan]
[step:Show that $A - sI$ is tridiagonal and its QR factor $Q$ is upper Hessenberg]
Since $A$ is tridiagonal and $sI$ is diagonal, $A - sI$ is tridiagonal: shifting the diagonal entries does not affect the off-diagonal structure.
The QR factorisation of the tridiagonal matrix $A - sI$ is computed using $n-1$ Givens rotations $G_1, G_2, \ldots, G_{n-1}$ (as established in the [QR Factorisation of Symmetric Tridiagonal Matrix](/theorems/1418) result), where each $G_i$ acts in the $(i, i+1)$ plane. The orthogonal factor is:
\begin{align*}
Q = G_1^\top G_2^\top \cdots G_{n-1}^\top.
\end{align*}
Each $G_i^\top$ is a rotation in the $(i, i+1)$ plane, so it differs from the identity only in the $2 \times 2$ block at rows and columns $(i, i+1)$. In particular, $(G_i^\top)_{jk} = \delta_{jk}$ whenever $j \notin \{i, i+1\}$ or $k \notin \{i, i+1\}$.
[guided]
We want to show that $Q_{ij} = 0$ whenever $i > j + 1$. To see why, consider how the product $Q = G_1^\top G_2^\top \cdots G_{n-1}^\top$ builds up column by column.
The $j$-th column of $Q$ is obtained by applying $G_1^\top G_2^\top \cdots G_{n-1}^\top$ to $e_j$. The rotation $G_k^\top$ can only mix components $k$ and $k+1$. Starting from $e_j$ (which has a single nonzero entry at position $j$):
- Rotations $G_k^\top$ with $k > j$ do not affect position $j$ and below, because they mix positions $k$ and $k+1$ where $k > j$.
- Rotation $G_j^\top$ mixes positions $j$ and $j+1$, creating a nonzero entry at position $j+1$.
- Rotation $G_{j-1}^\top$ (if it exists) has already been applied (since we multiply left to right in $G_1^\top G_2^\top \cdots$), but the ordering means rotations $G_k^\top$ with $k < j$ mix positions $k$ and $k+1 \leq j$, which cannot push nonzeros below position $j+1$.
More precisely, after multiplying by all rotations, column $j$ of $Q$ has nonzeros only at positions $1, 2, \ldots, j+1$. That is, $Q_{ij} = 0$ for $i > j + 1$, which is the definition of an upper Hessenberg matrix.
[/guided]
[/step]
[step:Express $A^+$ as an orthogonal similarity and conclude it is symmetric]
From $A - sI = QR$, we have $R = Q^\top(A - sI)$, so:
\begin{align*}
A^+ = RQ + sI = Q^\top(A - sI)Q + sI = Q^\top AQ - sQ^\top Q + sI = Q^\top AQ,
\end{align*}
where we used $Q^\top Q = I$ (since $Q$ is orthogonal). Therefore $A^+$ is an orthogonal similarity of $A$. Since $A$ is symmetric:
\begin{align*}
(A^+)^\top = (Q^\top AQ)^\top = Q^\top A^\top Q = Q^\top AQ = A^+,
\end{align*}
so $A^+$ is symmetric.
[/step]
[step:Show that $A^+$ is upper Hessenberg and conclude it is tridiagonal]
Since $R$ is upper triangular and $Q$ is upper Hessenberg, we show that $RQ$ is upper Hessenberg. The $(i,j)$ entry of $RQ$ is:
\begin{align*}
(RQ)_{ij} = \sum_{k=1}^n R_{ik} Q_{kj}.
\end{align*}
Since $R$ is upper triangular, $R_{ik} = 0$ for $k < i$, so the sum reduces to $k \geq i$. Since $Q$ is upper Hessenberg, $Q_{kj} = 0$ for $k > j + 1$, so the sum requires $k \leq j + 1$. For a nonzero contribution, we need $i \leq k \leq j + 1$, which requires $i \leq j + 1$, i.e., $i - j \leq 1$. Therefore $(RQ)_{ij} = 0$ when $i > j + 1$, confirming that $RQ$ is upper Hessenberg.
Adding $sI$ (a diagonal matrix) preserves the upper Hessenberg structure, so $A^+ = RQ + sI$ is upper Hessenberg.
A matrix that is both symmetric and upper Hessenberg is tridiagonal: if $A^+_{ij} = 0$ for $i > j + 1$, then by symmetry $A^+_{ji} = A^+_{ij} = 0$ for $j > i + 1$, which means $A^+_{ij} = 0$ whenever $|i - j| > 1$.
[guided]
The conclusion ties together three structural facts:
1. **$A^+$ is symmetric** because it is an orthogonal similarity of the symmetric matrix $A$.
2. **$A^+$ is upper Hessenberg** because it is the sum of the upper Hessenberg matrix $RQ$ and the diagonal matrix $sI$.
3. **Symmetric + upper Hessenberg = tridiagonal** because the symmetry constraint $A^+_{ij} = A^+_{ji}$ forces the lower Hessenberg structure as well.
The product $RQ$ deserves closer examination. The matrix $R$ is upper triangular with bandwidth 2 (since it comes from triangularising a tridiagonal matrix, the fill-in creates entries on the second superdiagonal). The matrix $Q$ is upper Hessenberg. When we multiply an upper triangular matrix by an upper Hessenberg matrix, each entry $(RQ)_{ij}$ involves a sum over indices $k$ with $i \leq k \leq j+1$. For $i > j + 1$, this range is empty, so $(RQ)_{ij} = 0$.
This is exactly why QR iteration is so efficient for tridiagonal matrices: not only is each QR factorisation $O(n)$ (by the [QR Factorisation of Symmetric Tridiagonal Matrix](/theorems/1418) result), but the tridiagonal structure regenerates at each step, so the cost remains $O(n)$ per iteration throughout the entire QR algorithm. This structural invariance is the foundation of the practical QR algorithm for symmetric eigenvalue problems.
[/guided]
[/step]
