43.06.02 · numerical-analysis / 06-eigenvalue-algorithms

Reduction to Hessenberg/tridiagonal form

shipped3 tiersLean: none

Anchor (Master): Trefethen-Bau *Numerical Linear Algebra* Lectures 26–28; Golub-Van Loan *Matrix Computations* (4th ed.) §7.4.3 (Householder reduction to Hessenberg form), §8.3 (the symmetric tridiagonal reduction); Wilkinson *The Algebraic Eigenvalue Problem* (Oxford, 1965) Ch. 6 (Householder's method); Parlett *The Symmetric Eigenvalue Problem* (SIAM Classics, 1998) §7.3 (the Householder tridiagonalisation)

Intuition Beginner

Finding the eigenvalues of a full square matrix is hard work, and the machine that does it, the QR algorithm, has to grind through many rounds. Each round costs roughly the cube of the matrix size, so for a dense matrix the whole job is expensive. There is a cheaper way to set things up first.

The idea is to comb the matrix into a tidier shape before the eigenvalue machine ever runs. We squeeze almost all of its entries down to zero, leaving only a narrow band near the diagonal. A general matrix gets combed into a shape where everything below the first slot under the diagonal is zero; this is called Hessenberg form. A symmetric matrix combs down even further, to a thin three-stripe band called tridiagonal form.

The combing has to be done carefully, because we are not allowed to change the eigenvalues. We use a special kind of rotation, a reflection, applied on both sides of the matrix at once. Applying the same reflection on the left and on the right is a change of viewpoint that leaves every eigenvalue exactly where it was. So we get a matrix with the same eigenvalues but a far simpler shape, and the eigenvalue machine then races through it.

Visual Beginner

The picture shows a five-by-five matrix before and after combing. On the left every cell can be nonzero, a full block of numbers. On the right almost the whole lower triangle has been zeroed out, leaving a staircase: the diagonal, the one stripe just below it, and everything above. That staircase is the Hessenberg shape.

   Full matrix            Upper-Hessenberg form
  x x x x x                x x x x x
  x x x x x                x x x x x
  x x x x x      ===>      0 x x x x
  x x x x x                0 0 x x x
  x x x x x                0 0 0 x x

   Symmetric matrix        Tridiagonal form
  x x x x x                x x 0 0 0
  x x x x x                x x x 0 0
  x x x x x      ===>      0 x x x 0
  x x x x x                0 0 x x x
  x x x x x                0 0 0 x x

Two things are worth seeing. First, the combed matrix keeps the same eigenvalues as the full one, because each combing step is a balanced two-sided reflection. Second, the symmetric case lands on the thinnest band of all, a single stripe on each side of the diagonal, because zeroing a column of a symmetric matrix zeroes the matching row for free.

Worked example Beginner

Take the symmetric three-by-three matrix

A = 412130205 .

We want to clear the entry $2$ in the bottom-left corner, the one that sits below the first subdiagonal in column one. We will use a reflection acting on the last two coordinates to fold the vector $(1, 2)$ formed by the two below-diagonal entries of column one onto a single axis.

Step 1. Look at the part of column one below the diagonal: the numbers $1$ and $2$ . Their combined length is $1^{2} + 2^{2} = 5 \approx 2.236$ . A reflection on these two coordinates can rotate $(1, 2)$ onto $(2.236, 0)$ , putting all the weight into the first of the two slots and clearing the second.

Step 2. Build the reflection $H$ that does this, and form the new matrix $H A H$ . Applying $H$ on the left clears the bottom-left entry; applying the same $H$ on the right keeps the eigenvalues unchanged and, because $A$ is symmetric, clears the top-right entry to match.

Step 3. The result is the tridiagonal matrix

4 2.236 0 2.236 4.6 1.2 0 1.2 3.4,

where the corner entries are now zero and only the diagonal and its two neighbouring stripes survive.

What this tells us: one reflection turned a full symmetric matrix into a three-stripe band, and the eigenvalues are unchanged because we reflected on both sides. A larger matrix needs a handful more reflections, one per column, but the principle is the same.

Check your understanding Beginner

Exercise (easy, multiple choice).

Why do we reduce a matrix to Hessenberg or tridiagonal form before running the eigenvalue algorithm?

A. To change the eigenvalues into rounder numbers. B. To make the later iterative steps far cheaper while keeping the same eigenvalues. C. To make the matrix bigger. D. To turn the matrix into the identity.

Hint

The reduction is a setup phase: a tidier shape means each later round of the eigenvalue machine does much less work, and the two-sided reflections leave the eigenvalues alone.

Answer

B. To make the later iterative steps far cheaper while keeping the same eigenvalues. The narrow band shape lets each round of the QR algorithm run in far fewer operations, and the two-sided reflections preserve the spectrum. Feedback-correct: the reduction is a cheap one-time setup that speeds up everything after it. Feedback-wrong: the eigenvalues are deliberately left unchanged, the matrix size is unchanged, and the goal is not the identity.

Formal definition Intermediate+

Let $A \in M_{n} (F)$ with $F \in {R, C}$ . A matrix $H = (h_{ij})$ is upper-Hessenberg when $h_{ij} = 0$ for all $i > j + 1$ ; that is, the only possibly-nonzero entries below the main diagonal lie on the first subdiagonal. A matrix $T$ is tridiagonal when $t_{ij} = 0$ for $∣ i - j ∣ > 1$ , so it is upper-Hessenberg and lower-Hessenberg at once. A Hessenberg matrix is unreduced when every subdiagonal entry is nonzero, $h_{i + 1, i} \neq = 0$ for $1 \leq i \leq n - 1$ .

A Householder reflector is a unitary matrix of the form $H = I - 2 v v^{*} / (v^{*} v)$ for a nonzero vector $v$ , in the sense of 01.01.09; it is Hermitian and unitary, $H = H^{*} = H^{- 1}$ , and it reflects across the hyperplane $v^{⊥}$ . Given any vector $x$ , a Householder reflector can be chosen so that $H x = α e_{1}$ with $∣ α ∣ = ∥ x ∥$ , collapsing all but the first coordinate of $x$ onto a single axis.

Two matrices $A$ and $B$ are similar when $B = S^{- 1} A S$ for an invertible $S$ ; they share the same characteristic polynomial and hence the same eigenvalues with the same algebraic multiplicities. When $S = Q$ is unitary, $B = Q^{*} A Q$ is a unitary (orthogonal, in the real case) similarity, and it preserves not only the spectrum but the Hermitian structure: if $A = A^{*}$ then $(Q^{*} A Q)^{*} = Q^{*} A Q$ .

Definition (Hessenberg reduction). The Hessenberg reduction of $A$ is a unitary $Q$ with $Q^{*} A Q = H$ upper-Hessenberg. It is built as a product $Q = Q_{1} Q_{2} \dots Q_{n - 2}$ of Householder reflectors: $Q_{k}$ acts as the identity on the first $k$ coordinates and, applied as the two-sided similarity $A \mapsto Q_{k}^{*} A Q_{k}$ , zeroes the entries of column $k$ below row $k + 1$ . When $A = A^{*}$ the same construction yields $Q^{*} A Q = T$ tridiagonal, because each reflector preserves symmetry and the cleared subcolumn forces a cleared superrow.

Notation: $e_{1}$ is the first standard basis vector; $fl (\cdot)$ denotes the computed (floating-point) result of an operation; $∥ \cdot ∥$ without subscript is the Euclidean / spectral norm; $ϵ_{mach}$ is the unit roundoff. The reflector $Q_{k}$ is identified with the embedded $(n - k) \times (n - k)$ reflection $diag (I_{k}, \tilde{H}_{k})$ acting on coordinates $k + 1, \dots, n$ .

Counterexamples to common slips

The reflector must act as a two-sided similarity $Q_{k}^{*} A Q_{k}$ , not a one-sided multiplication. A one-sided $Q_{k}^{*} A$ would zero the subcolumn but change the eigenvalues; the right multiplication by $Q_{k}$ restores the spectrum and is why the cleared region is below the first subdiagonal, not below the diagonal — the right multiply refills the entries in row $k + 1$ that a triangularising left-only sweep would have cleared.
One cannot zero the entry $h_{k + 1, k}$ on the first subdiagonal: the reflector $Q_{k}$ is built to act on coordinates $k + 1$ through $n$ , so it can collapse the subcolumn $(a_{k + 1, k}, \dots, a_{n, k})$ onto its first slot $a_{k + 1, k}$ but cannot remove that slot. This is the structural reason finite Householder reduction stops at Hessenberg, not at triangular form.
Tridiagonal form requires $A = A^{*}$ . For a non-symmetric $A$ , clearing the subcolumn does not clear the matching superrow, so the upper triangle stays full and the result is only Hessenberg.

Key theorem with proof Intermediate+

Theorem (orthogonal reduction to Hessenberg/tridiagonal form; Trefethen-Bau Lecture 26 ^{[source pending]}; Golub-Van Loan §7.4.3 ^{[source pending]}). Every $A \in M_{n} (F)$ admits a unitary $Q$ , a product of at most $n - 2$ Householder reflectors, with $Q^ A Q = H $u pp er - H esse nb er g . I f$ A = A^ $t h e n$ Q^ A Q = T $i s t r i d ia g o na l . T h er e d u c t i o n u ses$ O(n^3) $a r i t hm e t i co p er a t i o n s —$ \tfrac{10}{3}n^3 $f or t h e g e n er a l c a se an d$ \tfrac{4}{3}n^3 $f or t h esy mm e t r i cc a se — an d$ A $,$ H $,$ T$ all share the same spectrum.*

Proof. Construct $Q$ one column at a time. Suppose after $k - 1$ steps the matrix $A_{k - 1} = Q_{k - 1}^{*} \dots Q_{1}^{*} A Q_{1} \dots Q_{k - 1}$ is upper-Hessenberg in its first $k - 1$ columns. Write the $k$ -th column below the diagonal as $x = (a_{k + 1, k}, \dots, a_{n, k})^{⊤} \in F^{n - k}$ . Choose a Householder reflector $\tilde{H}_{k}$ on $F^{n - k}$ with $\tilde{H}_{k} x = α e_{1}$ , $∣ α ∣ = ∥ x ∥$ , and set $Q_{k} = diag (I_{k}, \tilde{H}_{k})$ , the identity on the first $k$ coordinates.

Left-multiplication $Q_{k}^{*} A_{k - 1}$ replaces the subcolumn $x$ by $α e_{1}$ , zeroing rows $k + 2, \dots, n$ of column $k$ while leaving the diagonal and subdiagonal entries in rows $1, \dots, k + 1$ intact. Right-multiplication by $Q_{k}$ acts only on columns $k + 1, \dots, n$ — because $Q_{k}$ fixes the first $k$ coordinates — so it does not disturb columns $1, \dots, k$ and in particular preserves the zeros just created in column $k$ . Thus $A_{k} = Q_{k}^{*} A_{k - 1} Q_{k}$ is upper-Hessenberg in its first $k$ columns. After $k = n - 2$ steps every column below the first subdiagonal is zero, so $A_{n - 2} = H$ is upper-Hessenberg, with $Q = Q_{1} \dots Q_{n - 2}$ .

When $A = A^{*}$ , each $A_{k} = Q_{k}^{*} A_{k - 1} Q_{k}$ is again Hermitian, since the $Q_{k}$ are unitary and Hermitian conjugation commutes with the similarity. A Hermitian upper-Hessenberg matrix is tridiagonal: $h_{ij} = 0$ for $i > j + 1$ forces $h_{j i} = \overline{h_{ij}} = 0$ for $j > i + 1$ , so both bands vanish beyond the first off-diagonals. Hence $H = T$ is tridiagonal.

The operation count: step $k$ applies $\tilde{H}_{k}$ to an $(n - k) \times (n - k)$ trailing block from both sides, costing $O ((n - k)^{2})$ per side; summing $\sum_{k = 1}^{n - 2} 4 (n - k)^{2} = \frac{4}{3} n^{3} + O (n^{2})$ in the symmetric case (only the lower band is touched) and $\frac{10}{3} n^{3}$ in the general case where both the trailing rows and columns are updated. Each $A_{k}$ is unitarily similar to $A$ , so the characteristic polynomials agree and the spectra coincide. $□$

Bridge. This construction builds toward the QR algorithm of 43.06.03, where the Hessenberg form produced here is the standing input that makes each QR sweep cost $O (n^{2})$ instead of $O (n^{3})$ ; the band structure appears again in the Arnoldi iteration of 43.07.02, whose orthonormal Krylov basis produces exactly a Hessenberg matrix $H_{m} = Q_{m}^{*} A Q_{m}$ , the same object reached here by direct reflectors rather than by iteration. The foundational reason the reduction stops at Hessenberg and not at triangular form is the Abel/Galois obstruction: a finite rational-plus-root algorithm cannot in general expose the eigenvalues, so the best a finite orthogonal procedure can do is the cheapest non-triangular band, and this is exactly the division of labour between a finite direct phase and an infinite iterative phase. The two-sided similarity that preserves the spectrum here generalises the change-of-basis invariance of eigenvalues, and putting these together, the reduction is the bridge from the static spectral theory of 01.01.08 to the production eigensolvers: it converts a dense problem into a banded one at one-time $O (n^{3})$ cost, after which the iteration is nearly free.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Explain precisely why the Householder reflector $Q_{k}$ used at step $k$ must act as the identity on the first $k$ coordinates. What goes wrong if it acts on coordinate $k$ as well?

Hint

The right-multiplication by $Q_{k}$ touches exactly the columns on which $Q_{k}$ acts nontrivially. Which previously-cleared zeros would be disturbed if $Q_{k}$ acted on column $k$ ?

Answer

Right-multiplication $A_{k - 1} Q_{k}$ forms linear combinations of exactly those columns on which $Q_{k}$ acts nontrivially. If $Q_{k}$ acted on coordinate $k$ , the right-multiply would mix column $k$ into the others, refilling the subdiagonal zeros already placed in columns $1, \dots, k - 1$ , and the reduction would not progress. By fixing the first $k$ coordinates, $Q_{k}$ leaves columns $1, \dots, k$ untouched on the right while its left action clears rows $k + 2, \dots, n$ of column $k$ . The price of this restriction is that $Q_{k}$ can only collapse the subcolumn onto row $k + 1$ , not row $k$ , so the entry $h_{k + 1, k}$ survives — this is why the reduction halts at Hessenberg rather than triangular form. Rubric: full credit for identifying the refill problem and connecting the coordinate restriction to the Hessenberg stopping point.

Exercise 7 (hard, short-answer).

Prove that the upper-Hessenberg structure is preserved by one step of the QR algorithm: if $H$ is upper-Hessenberg with QR factorisation $H = QR$ , then $\hat{H} = R Q$ is again upper-Hessenberg.

Hint

$Q = H R^{- 1}$ , and $R^{- 1}$ is upper-triangular. An upper-Hessenberg matrix times an upper-triangular matrix is upper-Hessenberg; so is upper-triangular times upper-Hessenberg.

Answer

From $H = QR$ with $R$ invertible upper-triangular, $Q = H R^{- 1}$ . The product of an upper-Hessenberg matrix $H$ with an upper-triangular matrix $R^{- 1}$ is upper-Hessenberg: entry $(i, j)$ of $H R^{- 1}$ is $\sum_{m} h_{im} (R^{- 1})_{mj}$ , and $(R^{- 1})_{mj} = 0$ for $m > j$ while $h_{im} = 0$ for $i > m + 1$ , so a nonzero term needs $i \leq m + 1 \leq j + 1$ , giving zero whenever $i > j + 1$ . Hence $Q$ is upper-Hessenberg. Then $\hat{H} = R Q$ is upper-triangular times upper-Hessenberg: entry $(i, j)$ is $\sum_{m} r_{im} q_{mj}$ with $r_{im} = 0$ for $m < i$ and $q_{mj} = 0$ for $m > j + 1$ , so nonzero terms need $i \leq m \leq j + 1$ , again forcing the entry to vanish for $i > j + 1$ . Therefore $\hat{H}$ is upper-Hessenberg, and the band structure is invariant across the iteration. Rubric: full credit for both products and the index bookkeeping.

Exercise 8 (hard, symbolic).

Show that an unreduced Hessenberg matrix $H$ (every subdiagonal entry nonzero) has geometric multiplicity exactly $1$ for each eigenvalue — that is, $H$ is non-derogatory.

Hint

For any scalar $λ$ , examine the rank of $H - λ I$ by looking at its first $n - 1$ columns and the nonzero subdiagonal entries.

Answer

Fix any $λ$ and consider $M = H - λ I$ , still upper-Hessenberg with the same (nonzero) subdiagonal entries $h_{i + 1, i}$ . Delete the first row and the last column of $M$ to obtain an $(n - 1) \times (n - 1)$ matrix whose main diagonal consists of the subdiagonal entries $h_{2, 1}, h_{3, 2}, \dots, h_{n, n - 1}$ , and which is upper-triangular (every entry strictly below this diagonal came from below the first subdiagonal of $M$ , hence is zero). Its determinant is $\prod_{i = 1}^{n - 1} h_{i + 1, i} \neq = 0$ , so this submatrix is invertible and $rank (M) \geq n - 1$ . Therefore $dim ker (H - λ I) = n - rank (M) \leq 1$ for every $λ$ , so each eigenvalue has geometric multiplicity exactly $1$ . Rubric: full credit for the deleted-submatrix triangularity argument and the rank conclusion.

Advanced results Master

Theorem (backward stability of the orthogonal reduction; Wilkinson Ch. 6 ^{[source pending]}). Let $A \in M_{n} (F)$ and let $\hat{H}$ be the upper-Hessenberg matrix computed by Householder reduction in floating-point arithmetic with unit roundoff $ϵ_{mach}$ . There is a unitary $\hat{Q}$ , and a perturbation $E$ , such that

\hat{Q}^{*} (A + E) \hat{Q} = \hat{H}, ∥ E ∥ = O (n^{2} ϵ_{mach} ∥ A ∥) .

The computed reduction is the exact reduction of a nearby matrix. The mechanism is that each Householder reflector, applied in floating point, equals an exactly-unitary reflector applied to a slightly perturbed operand, with the perturbation bounded by a low-degree polynomial in $n$ times $ϵ_{mach} ∥ A ∥$ ; composing $n - 2$ such steps multiplies the bound by the number of steps and keeps the accumulated $\hat{Q}$ exactly unitary to working precision. Because the backward error $E$ is of the order of the unavoidable rounding of the input, the reduction adds no instability of its own: the eigenvalues of $\hat{H}$ are the eigenvalues of a matrix within $O (n^{2} ϵ_{mach} ∥ A ∥)$ of $A$ , and by the perturbation theory of 43.01.02 they are accurate to the conditioning of the eigenproblem. This is the precise sense in which orthogonal similarities are the right tool: a non-orthogonal reduction with a large condition number $κ (S)$ would magnify $E$ by $κ (S)$ , whereas a unitary $\hat{Q}$ has $κ (\hat{Q}) = 1$ .

Theorem (the implicit-Q / uniqueness theorem; Golub-Van Loan §7.4.5 ^{[source pending]}). Let $A \in M_{n} (F)$ and let $Q$ , $V$ be unitary with $Q^ A Q = H $an d$ V^* A V = G $b o t h u n r e d u ce d u pp er - H esse nb er g . I f t h e f i r s t co l u mn s a g r ee,$ Q e_1 = V e_1 $, t h e n$ Q $an d$ V $a g r ee u pt o a d ia g o na l u ni t a r y s i g nma t r i x, an d cor r es p o n d in g l y$ H $an d$ G $a g r ee u pt o t ha t d ia g o na l s imi l a r i t y . * T h e u n r e d u ce d H esse nb er g f or mi s t h er e f or eesse n t ia l l y d e t er min e d b y i t s f i r s t co l u mn . T hi s i s t h es t r u c t u r a l f a c tt h e im pl i c i t (b u l g e - c ha s in g) QR a l g or i t hm r es t so n : a s hi f t e d QR s w ee p n ee d n o t f or m$ H - \mu I$ explicitly; it suffices to apply the correct first transformation and then restore Hessenberg form by chasing the resulting bulge down the band, because the uniqueness theorem guarantees the result equals the explicit sweep.

Theorem (band reduction and the operation-count hierarchy). For a banded Hermitian $A$ with bandwidth $b$ , the Householder tridiagonalisation can be organised to cost $O (n^{2} b)$ rather than $O (n^{3})$ by chasing fill-in within the band; for a full Hermitian $A$ the cost is $\frac{4}{3} n^{3}$ , half the general $\frac{10}{3} n^{3}$ because only one triangle is updated. The symmetric case is cheaper at every level because the two-sided similarity acts on a self-conjugate object, so the work and the storage halve; the band-chasing organisation is the lever that turns an already-sparse input into a tridiagonal output at sub-cubic cost, and it is the same fill-control idea that governs sparse-direct factorisation.

Synthesis. The reduction to Hessenberg/tridiagonal form is the hinge of the two-phase eigenvalue computation, and the foundational reason it exists is the Abel/Galois obstruction: no finite rational-and-radical procedure exposes the eigenvalues of a general matrix, so the computation must split into a finite direct phase and an infinite iterative phase. This is exactly the division this unit constructs — Householder reflectors collapse the matrix onto the cheapest band a finite orthogonal procedure can reach, and the band is preserved by every QR sweep, so the iterative phase inherits a permanent $O (n^{2})$ -per-step (or $O (n)$ tridiagonal) cost. The two-sided unitary similarity is the central insight that makes the scheme stable: it preserves the spectrum exactly, preserves Hermitian structure, and has unit condition number, so the reduction's backward-error bound generalises the $κ (S)$ -free stability of the Householder QR of 01.01.09. Putting these together, the Hessenberg form is at once the output of a finite direct algorithm and the standing input of the iterative one, and the implicit-Q theorem shows the form is rigid enough — fixed by its first column — that the iteration can be driven implicitly; the bridge to the Krylov methods of chapter $43.07$ is that the same Hessenberg object arises there as $Q_{m}^{*} A Q_{m}$ from the Arnoldi process, so the direct reduction and the iterative projection are two routes to one structure.

Full proof set Master

Proposition (existence and finiteness of the Hessenberg reduction). For every $A \in M_{n} (F)$ there is a unitary $Q$ , a product of at most $n - 2$ Householder reflectors, with $Q^ A Q$ upper-Hessenberg.*

Proof. Induct on the column index $k$ , with the invariant that $A_{k} = Q_{k}^{*} \dots Q_{1}^{*} A Q_{1} \dots Q_{k}$ is upper-Hessenberg in columns $1, \dots, k$ . The base case $k = 0$ is vacuous. Assume $A_{k - 1}$ is Hessenberg in its first $k - 1$ columns. Let $x = (a_{k + 1, k}, \dots, a_{n, k})^{⊤}$ be the part of column $k$ below the subdiagonal. If $x = 0$ take $Q_{k} = I$ ; otherwise choose a Householder reflector $\tilde{H}_{k}$ on $F^{n - k}$ with $\tilde{H}_{k} x = - sgn (x_{1}) ∥ x ∥ e_{1}$ — the sign chosen to avoid cancellation — and embed $Q_{k} = diag (I_{k}, \tilde{H}_{k})$ .

Left-multiplication by $Q_{k}^{*}$ acts only on rows $k + 1, \dots, n$ , replacing $x$ by a multiple of $e_{1}$ and so zeroing rows $k + 2, \dots, n$ of column $k$ ; rows and columns $1, \dots, k$ are fixed, preserving the earlier Hessenberg columns. Right-multiplication by $Q_{k}$ acts only on columns $k + 1, \dots, n$ , hence does not touch columns $1, \dots, k$ and preserves the new zeros in column $k$ . So $A_{k}$ is Hessenberg in columns $1, \dots, k$ . At $k = n - 2$ the matrix is fully upper-Hessenberg, and $Q = Q_{1} \dots Q_{n - 2}$ is unitary as a product of unitaries. $□$

Proposition (preservation of Hermitian structure; tridiagonal output). If $A = A^ $t h e n t h er e d u c t i o nab o v ey i e l d s$ Q^* A Q$ tridiagonal.*

Proof. Each $A_{k} = Q_{k}^{*} A_{k - 1} Q_{k}$ is Hermitian whenever $A_{k - 1}$ is, since $(Q_{k}^{*} A_{k - 1} Q_{k})^{*} = Q_{k}^{*} A_{k - 1}^{*} Q_{k} = Q_{k}^{*} A_{k - 1} Q_{k}$ , and $A_{0} = A$ is Hermitian by hypothesis; by induction $H = A_{n - 2}$ is Hermitian. By the previous proposition $H$ is upper-Hessenberg, so $h_{ij} = 0$ for $i > j + 1$ . Hermitian symmetry gives $h_{j i} = \overline{h_{ij}}$ , so $h_{j i} = 0$ for $j > i + 1$ as well. Both bands beyond the first off-diagonals vanish, so $∣ i - j ∣ > 1 \Rightarrow h_{ij} = 0$ , which is tridiagonality. $□$

Proposition (spectral invariance and the operation count). The reduction preserves the spectrum and uses $O (n^{3})$ operations, with leading term $\frac{4}{3} n^{3}$ in the Hermitian case.

Proof. Spectral invariance is similarity invariance: $Q^{*} A Q = Q^{- 1} A Q$ for unitary $Q$ , so $det (Q^{*} A Q - λ I) = det (Q^{- 1} (A - λ I) Q) = det (A - λ I)$ , and the characteristic polynomials, hence the spectra with multiplicities, coincide. For the count, step $k$ applies $\tilde{H}_{k} = I - 2 v v^{*} / (v^{*} v)$ to a trailing block: a Householder application $B \mapsto \tilde{H}_{k} B = B - v (2 v^{*} B / v^{*} v)$ on an $(n - k) \times m$ block costs $4 (n - k) m$ operations (one matrix-vector product and one rank-one update). In the Hermitian case only the lower triangle is stored and each step updates an $(n - k) \times (n - k)$ symmetric trailing block at cost $\approx 4 (n - k)^{2}$ halved by symmetry to $\approx 2 (n - k)^{2}$ for the two-sided update plus the symmetric rank-two correction; summing $\sum_{k = 1}^{n - 2}$ gives leading term $\frac{4}{3} n^{3}$ . The general (non-Hermitian) case updates both the trailing rows and the trailing columns, doubling the symmetric work to leading term $\frac{10}{3} n^{3}$ . $□$

Proposition (QR-step invariance of the Hessenberg band). If $H$ is upper-Hessenberg with QR factorisation $H = QR$ ( $Q$ unitary, $R$ upper-triangular invertible), then $\hat{H} = R Q$ is upper-Hessenberg.

Proof. Write $Q = H R^{- 1}$ . For an upper-Hessenberg $H$ and an upper-triangular $T$ , the product $H T$ is upper-Hessenberg: $(H T)_{ij} = \sum_{m} h_{im} t_{mj}$ , with $t_{mj} = 0$ for $m > j$ and $h_{im} = 0$ for $m < i - 1$ , so a surviving term needs $i - 1 \leq m \leq j$ , impossible when $i > j + 1$ . Thus $Q = H R^{- 1}$ is upper-Hessenberg. Likewise for upper-triangular $T$ and upper-Hessenberg $K$ , the product $T K$ is upper-Hessenberg: $(T K)_{ij} = \sum_{m} t_{im} k_{mj}$ with $t_{im} = 0$ for $m < i$ and $k_{mj} = 0$ for $m > j + 1$ , so a surviving term needs $i \leq m \leq j + 1$ , impossible when $i > j + 1$ . Applying this with $T = R$ , $K = Q$ gives $\hat{H} = R Q$ upper-Hessenberg. The same argument with the conjugate-symmetric band shows a symmetric tridiagonal $H$ stays tridiagonal under a QR step. $□$

Connections Master

The Hessenberg/tridiagonal reduction is the direct first phase of the QR algorithm of 43.06.03: the QR algorithm is run not on the dense $A$ but on its Hessenberg reduction, where the band-invariance proposition proved here guarantees that every QR sweep returns another Hessenberg matrix, dropping the per-sweep cost from $O (n^{3})$ to $O (n^{2})$ and, in the symmetric tridiagonal case, to $O (n)$ ; without this reduction the QR algorithm would be impractical.

The Householder reflectors that perform the reduction are the same orthogonal triangularisation tool built and analysed in 01.01.09, reused here as two-sided similarities rather than one-sided factors; the backward-stability bound $∥ E ∥ = O (ϵ_{mach} ∥ A ∥)$ of the reduction is the $κ$ -independent stability of Householder transformations transplanted from the QR factorisation to the eigenvalue setting.

The inverse-iteration step of 43.06.01 solves a linear system $(A - μ I) y = x$ at every iteration, and reducing $A$ to Hessenberg or tridiagonal form first makes each of those solves cheap — a tridiagonal solve is $O (n)$ — which is why the practical eigenvalue pipeline reduces once and then iterates, sharing the reduction across the iteration just as the QR algorithm does.

The Arnoldi iteration of 43.07.02 produces the Hessenberg matrix $H_{m} = Q_{m}^{*} A Q_{m}$ as the projection of $A$ onto a Krylov subspace, and its Hermitian specialisation, the Lanczos iteration, produces a tridiagonal $T_{m}$ ; these are the same band structures reached here by direct reflectors, so the present unit is the finite-dimensional, full-spectrum counterpart of the Krylov-subspace projection that underlies GMRES and conjugate gradients.

Historical & philosophical context Master

The reduction of a matrix to Hessenberg form by orthogonal similarities is due to Alston Householder, whose 1958 introduction of the elementary reflector $I - 2 v v^{*} / (v^{*} v)$ gave numerical linear algebra its sharpest tool for selectively zeroing entries while preserving norms, and whose subsequent treatise The Theory of Matrices in Numerical Analysis (1964) systematised the reduction as the standard preprocessing step ^{[Householder 1958]}. Wilkinson, in The Algebraic Eigenvalue Problem (1965), supplied the rounding-error analysis showing that Householder's reduction is backward stable: the computed band matrix is the exact reduction of a matrix within $O (ϵ_{mach} ∥ A ∥)$ of the original, which is what made the two-phase eigenvalue computation trustworthy in finite precision ^{[Wilkinson 1965]}.

The strategic role of the reduction — a finite direct phase followed by an infinite iterative phase — reflects the Abel-Ruffini theorem and Galois's resolution of solvability by radicals: because the eigenvalues of a general matrix of size $\geq 5$ are the roots of an arbitrary polynomial, no finite sequence of arithmetic and root operations can produce them, so the eigenvalue problem is necessarily iterative ^{[Abel 1826]}. The reduction does the maximal finite work — banding the matrix as far as a finite orthogonal procedure allows — and hands the irreducibly iterative remainder to the QR algorithm of Francis and Kublanovskaya (1961). The tridiagonal specialisation for symmetric matrices, and its exploitation by the symmetric QR and divide-and-conquer eigensolvers, was developed extensively by Parlett, whose The Symmetric Eigenvalue Problem is the standard account ^{[Parlett 1998]}.

Bibliography Master

@article{Householder1958,
  author  = {Householder, Alston S.},
  title   = {Unitary Triangularization of a Nonsymmetric Matrix},
  journal = {Journal of the ACM},
  volume  = {5},
  number  = {4},
  year    = {1958},
  pages   = {339--342}
}

@book{Householder1964,
  author    = {Householder, Alston S.},
  title     = {The Theory of Matrices in Numerical Analysis},
  publisher = {Blaisdell},
  address   = {New York},
  year      = {1964}
}

@book{Wilkinson1965,
  author    = {Wilkinson, James H.},
  title     = {The Algebraic Eigenvalue Problem},
  publisher = {Oxford University Press},
  address   = {Oxford},
  year      = {1965}
}

@article{Francis1961,
  author  = {Francis, John G. F.},
  title   = {The QR Transformation, I},
  journal = {The Computer Journal},
  volume  = {4},
  number  = {3},
  year    = {1961},
  pages   = {265--271}
}

@article{Abel1826,
  author  = {Abel, Niels Henrik},
  title   = {Beweis der Unm{\"o}glichkeit, algebraische Gleichungen von h{\"o}heren Graden als dem vierten allgemein aufzul{\"o}sen},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume  = {1},
  year    = {1826},
  pages   = {65--84}
}

@book{Parlett1998,
  author    = {Parlett, Beresford N.},
  title     = {The Symmetric Eigenvalue Problem},
  publisher = {SIAM},
  series    = {Classics in Applied Mathematics},
  year      = {1998}
}

@book{TrefethenBau1997,
  author    = {Trefethen, Lloyd N. and Bau, David},
  title     = {Numerical Linear Algebra},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {1997}
}

@book{GolubVanLoan2013,
  author    = {Golub, Gene H. and Van Loan, Charles F.},
  title     = {Matrix Computations},
  edition   = {4th},
  publisher = {Johns Hopkins University Press},
  address   = {Baltimore},
  year      = {2013}
}

Prerequisites

01.01.09
43.06.01

Tier anchors

beginner: Trimming a matrix down to a near-triangular shape so the later eigenvalue machine has almost no work to do — Strang *Introduction to Linear Algebra* Ch. 6 (eigenvalues and similar matrices); 3Blue1Brown *Essence of Linear Algebra* Ch. 13–14 (change of basis and eigenvectors)
intermediate: Trefethen-Bau *Numerical Linear Algebra* Lecture 26 (introduction to the eigenvalue problem) and Lecture 26's reduction to Hessenberg form; Golub-Van Loan *Matrix Computations* (4th ed.) §7.4 (the Hessenberg and tridiagonal reduction) and §5.1 (Householder transformations)
master: Trefethen-Bau *Numerical Linear Algebra* Lectures 26–28; Golub-Van Loan *Matrix Computations* (4th ed.) §7.4.3 (Householder reduction to Hessenberg form), §8.3 (the symmetric tridiagonal reduction); Wilkinson *The Algebraic Eigenvalue Problem* (Oxford, 1965) Ch. 6 (Householder's method); Parlett *The Symmetric Eigenvalue Problem* (SIAM Classics, 1998) §7.3 (the Householder tridiagonalisation)

References

images/Shilov-Linear-Algebra__4cbdee00cc.jpg · Shilov *Linear Algebra* — Fast Track archive cover; Ch. 6 linear operators and the invariance of the spectrum under a change of basis (similarity), the static fact this unit turns into a constructive orthogonal reduction
Trefethen, L. N. & Bau, D. — Numerical Linear Algebra (SIAM, 1997) · Lecture 26 — the two-phase eigenvalue computation: a direct orthogonal reduction to Hessenberg (tridiagonal in the symmetric case) followed by the iterative QR algorithm; the Abel/Galois obstruction forcing the second phase to be iterative
Golub, G. H. & Van Loan, C. F. — Matrix Computations (4th ed., Johns Hopkins, 2013) · §7.4.3 and §8.3 — Householder reduction to upper-Hessenberg form ($\tfrac{10}{3}n^3$ flops, $\tfrac{14}{3}n^3$ with the transformations accumulated) and the symmetric tridiagonal reduction ($\tfrac{4}{3}n^3$ flops)
Wilkinson, J. H. — The Algebraic Eigenvalue Problem (Oxford, 1965) · Ch. 6 — Householder's method and the backward-error analysis of an orthogonal similarity, $\mathrm{fl}(Q^*AQ) = Q^*(A+E)Q$ with $\|E\| = O(\epsilon_{\mathrm{mach}}\|A\|)$
Parlett, B. N. — The Symmetric Eigenvalue Problem (SIAM Classics, 1998) · §7.3 — Householder tridiagonalisation of a symmetric matrix and the preservation of symmetry under the two-sided similarity

Estimated time

beginner: 16m
intermediate: 42m
master: 85m