[proofplan]
We show that the QR factorisation of a symmetric tridiagonal matrix $T \in \mathbb{R}^{n \times n}$ can be computed in $O(n)$ operations using $n-1$ Givens rotations. Each Givens rotation $G_i$ eliminates the single subdiagonal entry $t_{i+1,i}$ at a cost of $O(1)$ operations, and because $T$ has bandwidth 1, each rotation affects only two rows and at most three columns. The total work is therefore $O(n)$.
[/proofplan]
[step:Observe that the tridiagonal structure limits fill-in to a single extra diagonal]
Let $T \in \mathbb{R}^{n \times n}$ be symmetric tridiagonal, so $T_{ij} = 0$ whenever $|i - j| > 1$. The nonzero entries lie on the main diagonal $\{T_{ii}\}$, the subdiagonal $\{T_{i+1,i}\}$, and the superdiagonal $\{T_{i,i+1}\}$. To compute the QR factorisation $T = QR$, we reduce $T$ to upper triangular form by eliminating the $n - 1$ subdiagonal entries.
A Givens rotation $G_i$ in the $(i, i+1)$ plane zeroes out $T_{i+1,i}$ by mixing rows $i$ and $i+1$. After applying $G_i$, the only new nonzero entry that can be created (fill-in) lies in position $(i, i+2)$: since $T_{i+1,i+2} \neq 0$ in general, the rotation mixes this entry into row $i$. The resulting matrix after all rotations is upper triangular with bandwidth 2 (nonzeros on the diagonal, first superdiagonal, and second superdiagonal).
[guided]
Why does fill-in stay so limited? Consider the effect of $G_i$ on the matrix. The rotation $G_i$ acts on rows $i$ and $i+1$ only. Row $i$ of $T$ has nonzeros at columns $i-1, i, i+1$ (at most). Row $i+1$ has nonzeros at columns $i, i+1, i+2$ (at most). After mixing these two rows, row $i$ can have nonzeros at columns $i-1, i, i+1, i+2$ — the union of the nonzero positions — while row $i+1$ gains a zero at column $i$ (by construction). The entry at position $(i, i+2)$ is the only new fill-in.
Since we process the subdiagonal entries in order $i = 1, 2, \ldots, n-1$, the fill-in at $(i, i+2)$ is already above the diagonal and does not create any new subdiagonal entries for subsequent rotations. Each $G_{i+1}$ deals with position $(i+2, i+1)$, which was already present in the original matrix and is unaffected by $G_i$ (since $G_i$ only modifies rows $i$ and $i+1$, not row $i+2$). The process therefore runs cleanly in a single sweep.
[/guided]
[/step]
[step:Count the operations for each Givens rotation applied to a tridiagonal matrix]
To apply $G_i$ to rows $i$ and $i+1$, we must update every column $j$ where at least one of $(T_{i,j}, T_{i+1,j})$ is nonzero. Before the rotation, the nonzero entries in rows $i$ and $i+1$ span at most columns $i-1$ through $i+2$ (accounting for the original bandwidth and the fill-in from $G_{i-1}$). This is at most 4 columns.
For each such column, the Givens rotation performs a $2 \times 2$ rotation:
\begin{align*}
\begin{pmatrix} T'_{i,j} \\ T'_{i+1,j} \end{pmatrix} = \begin{pmatrix} c_i & s_i \\ -s_i & c_i \end{pmatrix} \begin{pmatrix} T_{i,j} \\ T_{i+1,j} \end{pmatrix},
\end{align*}
where $c_i = \cos\theta_i$ and $s_i = \sin\theta_i$ are chosen so that $T'_{i+1,i} = 0$. Computing $(c_i, s_i)$ from the entries $T_{i,i}$ and $T_{i+1,i}$ requires $O(1)$ operations (a square root and a division). Each column update requires 4 multiplications and 2 additions, giving $O(1)$ work per column and at most $O(1) \times 4 = O(1)$ work per rotation.
[/step]
[step:Sum over all $n-1$ rotations to obtain $O(n)$ total cost]
There are $n - 1$ subdiagonal entries to eliminate, one per Givens rotation $G_1, G_2, \ldots, G_{n-1}$. Each rotation costs $O(1)$ operations (a fixed number of multiplications and additions independent of $n$). The total cost of computing the upper triangular factor $R$ is:
\begin{align*}
\sum_{i=1}^{n-1} O(1) = O(n).
\end{align*}
The orthogonal factor is $Q = G_1^\top G_2^\top \cdots G_{n-1}^\top$. If $Q$ is needed explicitly, it can be accumulated by applying the same rotations to the identity matrix, again at $O(1)$ cost per rotation (since each $G_i^\top$ affects only two rows), giving $O(n)$ total for $Q$ as well. The complete QR factorisation $T = QR$ is therefore computed in $O(n)$ operations.
[guided]
To appreciate why this is remarkable, recall that a general $n \times n$ matrix requires $O(n^3)$ operations for its QR factorisation (via Householder reflections or Givens rotations). For a tridiagonal matrix, three structural properties combine to reduce the cost to $O(n)$:
1. **Only $n-1$ subdiagonal entries need elimination** (compared to $\frac{n(n-1)}{2}$ for a full matrix).
2. **Each Givens rotation affects only $O(1)$ entries** because the bandwidth is 1, so each row has at most 3-4 nonzero entries.
3. **Fill-in is limited to a single extra superdiagonal**, so the bandwidth grows from 1 to 2 but no further.
The same $O(n)$ cost extends to symmetric tridiagonal matrices specifically because the subdiagonal and superdiagonal are transposes of each other (only $n-1$ independent off-diagonal entries), but the operation count is dominated by the row operations, not the storage, so the symmetry is not the primary driver — it is the bandwidth that matters. Any matrix with bandwidth $O(1)$ would admit $O(n)$ QR factorisation by the same argument.
[/guided]
[/step]
