The generalised eigenvalue problem Ax=λBx and the QZ algorithm

Intuition Beginner

A standard eigenvalue question asks: in which directions does a matrix $A$ act by pure stretching, $Av=\lambda v$? The generalised question brings in a second matrix $B$ and asks instead: in which directions do $A$ and $B$ stretch in lockstep, so that $Av$ and $Bv$ point the same way? The number $\lambda$ that makes $Av=\lambda Bv$ is then a generalised eigenvalue. Set $B$ to the identity and you are back to the ordinary problem.

This shows up the moment a physical system has mass as well as stiffness. A vibrating structure obeys an equation where a stiffness matrix $K$ and a mass matrix $M$ both act, and the natural frequencies are exactly the numbers $\lambda$ with $Kv=\lambda Mv$. You cannot fold the mass into the stiffness without distorting the geometry, so the pair has to be handled together.

A tempting shortcut is to multiply through by the inverse of $B$ and solve the ordinary problem for $B^{-1}A$. That works on paper. On a computer it can be a trap: if $B$ is close to non-invertible, forming $B^{-1}A$ amplifies rounding error and corrupts the answer. The QZ algorithm is the careful alternative. It works on $A$ and $B$ side by side, never forming the inverse, and grinds the pair down to a shape where the generalised eigenvalues can be read straight off two diagonals.

Visual Beginner

The picture shows what the QZ algorithm produces. You start with a pair of full square matrices $A$ and $B$. The algorithm multiplies on the left by one rotation-like matrix $Q$ and on the right by another, $Z$, repeatedly, until both $A$ and $B$ have become upper-triangular staircases at the same time. Once they are both triangular, each generalised eigenvalue is the ratio of a diagonal entry of the transformed $A$ to the matching diagonal entry of the transformed $B$.

   Start: a PAIR                 QZ: shrink both together         Read the ratios
   (A , B) full                  Q on the left, Z on the right    lambda_i = a_ii / b_ii

   A = x x x x      B = x x x x        A' = a * * *     B' = b * * *
       x x x x          x x x x             . a * *          . b * *
       x x x x          x x x x   ===>      . . a *          . . b *
       x x x x          x x x x             . . . a          . . . b
                                          (both upper-triangular at once)

Two things are worth seeing. First, $A$ and $B$ are squeezed into triangular form simultaneously by the same pair of side multiplications, which is why two different matrices $Q$ and $Z$ are needed rather than one. Second, when a diagonal entry $b_{ii}$ of the transformed $B$ lands on zero, the ratio $a_{ii}/b_{ii}$ blows up: that direction is an infinite generalised eigenvalue, a perfectly real feature of pairs that the ordinary one-matrix picture has no room for.

Worked example Beginner

Take the small pair

$$A=\left(\begin{array}{cc}4& 0\\ 0& 6\end{array}\right),B=\left(\begin{array}{cc}2& 0\\ 0& 1\end{array}\right).$$

Both are already diagonal, so we can read the generalised eigenvalues directly. We want the numbers $\lambda$ and directions $v$ with $Av=\lambda Bv$.

Step 1. Try the first coordinate direction $v=(1,0)$. Then $Av=(4,0)$ and $Bv=(2,0)$. We need $(4,0)=\lambda (2,0)$, which gives $\lambda =4/2=2$.

Step 2. Try the second coordinate direction $v=(0,1)$. Then $Av=(0,6)$ and $Bv=(0,1)$. We need $(0,6)=\lambda (0,1)$, which gives $\lambda =6/1=6$.

Step 3. Collect the answers. The two generalised eigenvalues are $2$ and $6$, each the ratio of the matching diagonal entries of $A$ and $B$, and the eigendirections are the two coordinate axes.

What this tells us: when a pair is already triangular, every generalised eigenvalue is a diagonal-to-diagonal ratio $a_{ii}/b_{ii}$. The whole job of the QZ algorithm is to reach that triangular pair without ever dividing by $B$ as a whole matrix.

Check your understanding Beginner

Formal definition Intermediate+

Let $A,B\in M_n(\mathbb{C})$. The matrix pencil generated by the ordered pair $(A,B)$ is the matrix-valued function $\lambda \mapsto A-\lambda B$, written $A-\lambda B$ and identified with the pair $(A,B)$. The pencil is regular when its determinant $\det (A-\lambda B)$ is not the identically-zero polynomial in $\lambda$, and singular otherwise. Throughout, the pencils considered are regular unless stated otherwise.

Definition (generalised eigenvalues and eigenvectors). A finite generalised eigenvalue of a regular pencil $(A,B)$ is a root $\lambda \in \mathbb{C}$ of the generalised characteristic polynomial $p(\lambda )=\det (A-\lambda B)$, following Golub-Van Loan §7.7 ^{[source pending]}. A non-zero vector $v$ with $(A-\lambda B)v=0$, equivalently $Av=\lambda Bv$, is an associated generalised eigenvector. To accommodate the degree drop of $p$ when $B$ is singular, generalised eigenvalues are recorded projectively as pairs $(\alpha ,\beta )\in {\mathbb{C}}^2\setminus \{(0,0)\}$, defined up to a common non-zero scaling, with the meaning $\beta Av=\alpha Bv$; the value $\lambda =\alpha /\beta$ when $\beta \ne 0$, and the pair with $\beta =0$, $\alpha \ne 0$ is the infinite eigenvalue. A regular $n\times n$ pencil has exactly $n$ generalised eigenvalues counted with multiplicity as pairs, of which $\mathrm{deg}p$ are finite and $n-\mathrm{deg}p$ are infinite.

Definition (equivalence of pencils). Two pencils $(A,B)$ and $(A^{\prime },B^{\prime })$ are equivalent when there exist invertible $Q,Z\in M_n(\mathbb{C})$ with $A^{\prime }=QAZ$ and $B^{\prime }=QBZ$. Equivalence preserves the generalised eigenvalues as projective pairs, since $\det (A^{\prime }-\lambda B^{\prime })=\det Q\det (A-\lambda B)\det Z$ differs from $\det (A-\lambda B)$ only by the non-zero constant $\det Q\det Z$. When $Q$ and $Z$ are required to be unitary, the relation is unitary equivalence, the numerically stable case: it leaves the two-norms of $A$ and $B$ unchanged and so does not amplify rounding error.

Definition (generalised Schur / QZ decomposition). A generalised Schur decomposition of $(A,B)$ is a unitary equivalence to a pair of upper-triangular matrices: unitary $Q,Z\in M_n(\mathbb{C})$ with

$$Q^{\mathsf{H}}AZ=T,Q^{\mathsf{H}}BZ=S$$

both upper-triangular. The generalised eigenvalues are then the pairs $(t_{ii},s_{ii})$ along the two diagonals, with finite values ${\lambda }_i=t_{ii}/s_{ii}$ when $s_{ii}\ne 0$ and an infinite eigenvalue at each index with $s_{ii}=0$. Over $\mathbb{R}$ one uses real orthogonal $Q,Z$ and accepts a generalised real Schur form in which $S$ is upper-triangular and $T$ is quasi-triangular with $1\times 1$ and $2\times 2$ diagonal blocks, the $2\times 2$ blocks carrying complex-conjugate eigenvalue pairs.

Definition (Hessenberg-triangular form). A pair $(H,R)$ is in Hessenberg-triangular form when $H$ is upper-Hessenberg (entries vanishing below the first subdiagonal, in the sense of 43.06.03) and $R$ is upper-triangular. This is the condensed starting form for the QZ iteration, the pencil analogue of the upper-Hessenberg starting form of the standard QR algorithm.

Notation: $A-\lambda B$ is the pencil of the pair $(A,B)$; $Q^{\mathsf{H}}$ is the conjugate transpose; $(\alpha :\beta )$ denotes a generalised eigenvalue as a projective pair; $T,S$ denote the upper-triangular generalised Schur factors of $A,B$; $H,R$ denote a Hessenberg-triangular pair. The symbol $\lambda$ ranges over finite generalised eigenvalues; the pencil is regular unless flagged singular.

Counterexamples to common slips

• A generalised eigenvalue need not be a ratio of an eigenvalue of $A$ to one of $B$. For A = \begin{psmallmatrix} 1 & 1 \\ 0 & 1 \end{psmallmatrix}, B = \begin{psmallmatrix} 1 & 0 \\ 1 & 1 \end{psmallmatrix}, the polynomial $\det (A-\lambda B)=(1-\lambda {)}^2+\lambda ={\lambda }^2-\lambda +1$ has roots that are not quotients of the eigenvalues of $A$ (both $1$) and $B$ (both $1$). The pencil mixes the two matrices and must be solved as a pair.

• The infinite eigenvalue is not an artefact to be discarded. For A = \begin{psmallmatrix} 1 & 0 \\ 0 & 1 \end{psmallmatrix}, B = \begin{psmallmatrix} 1 & 0 \\ 0 & 0 \end{psmallmatrix}, the polynomial $\det (A-\lambda B)=(1-\lambda )\cdot 1$ has degree one, so one finite eigenvalue $\lambda =1$ and one infinite eigenvalue; the second is a genuine solution direction of $0\cdot Av=1\cdot Bv$ recorded as the pair $(\alpha ,\beta )=(1,0)$.

• A singular pencil is not merely an ill-conditioned regular one. Take A = \begin{psmallmatrix} 1 & 0 \\ 0 & 0 \end{psmallmatrix}, B = \begin{psmallmatrix} 1 & 0 \\ 0 & 0 \end{psmallmatrix}: then A - \lambda B = (1-\lambda)\begin{psmallmatrix}1&0\\0&0\end{psmallmatrix} has determinant identically zero. Every $\lambda$ "solves" it, the eigenvalues are undefined, and QZ is not applicable without first extracting the Kronecker structure.

Key theorem with proof Intermediate+

Theorem (existence of the generalised Schur decomposition; Moler-Stewart 1973 ^{[source pending]}; Golub-Van Loan §7.7 ^{[source pending]}). Let $A,B\in M_n(\mathbb{C})$. There exist unitary matrices $Q,Z\in M_n(\mathbb{C})$ such that $T=Q^{\mathsf{H}}AZ$ and $S=Q^{\mathsf{H}}BZ$ are both upper-triangular. If the pencil $(A,B)$ is regular, its generalised eigenvalues are exactly the pairs $(t_{ii},s_{ii})$, and the diagonal entries can be made to appear in any prescribed order.

Proof. Argue by induction on $n$. The case $n=1$ is immediate, since a $1\times 1$ pair is already triangular. Assume the result for size $n-1$.

Two cases arise according to whether $B$ is invertible. Suppose first $B$ is invertible. Then $B^{-1}A\in M_n(\mathbb{C})$ has an eigenpair $(B^{-1}A)x=\lambda x$ with $x$ a unit vector, by the fundamental theorem of algebra applied to its characteristic polynomial 01.01.08. This $x$ satisfies $Ax=\lambda Bx$, so $\lambda$ is a generalised eigenvalue of the pencil with eigenvector $x$. Choose this $x$ as the last column $z_n$ of a unitary $Z$, extending to an orthonormal basis. The vector $Bx$ is non-zero because $B$ is invertible; normalise $w=Bx/\Vert Bx\Vert$ and choose this $w$ as the last column $q_n$ of a unitary $Q$, again extending to an orthonormal basis.

With these choices, consider the last columns of $Q^{\mathsf{H}}BZ$ and $Q^{\mathsf{H}}AZ$. The last column of $BZ$ is $B{z}_n=Bx=\Vert Bx\Vert q_n$, so $Q^{\mathsf{H}}BZ{e}_n=\Vert Bx\Vert Q^{\mathsf{H}}{q}_n=\Vert Bx\Vert e_n$, placing the only non-zero entry of that column on the diagonal. Likewise $A{z}_n=Ax=\lambda Bx=\lambda \Vert Bx\Vert q_n$, so $Q^{\mathsf{H}}AZ{e}_n=\lambda \Vert Bx\Vert e_n$. Both $Q^{\mathsf{H}}AZ$ and $Q^{\mathsf{H}}BZ$ therefore have a zero last row except in the bottom-right corner — equivalently, after the equivalence the pencil deflates into an $(n-1)\times (n-1)$ leading pencil and a $1\times 1$ trailing block. Apply the inductive hypothesis to the leading $(n-1)\times (n-1)$ pair, with its own unitary factors padded by a $1$ in the corner, to triangularise the rest. The composition of the two unitary equivalences is again a unitary equivalence, and the resulting $T,S$ are upper-triangular.

When $B$ is singular, it has a kernel of positive dimension: pick a unit vector $x$ with $Bx=0$, and set $z_n=x$. Then the last column of $BZ$ vanishes, so the last column of $Q^{\mathsf{H}}BZ$ is zero for any unitary $Q$; choose $Q$ so that $Q^{\mathsf{H}}A{z}_n$ is a multiple of $e_n$ (take $q_n$ aligned with $A{z}_n$, which is non-zero because regularity forbids a common kernel vector). The pencil again deflates, contributing an infinite eigenvalue $(t_{nn},0)$, and the induction proceeds on the leading block. Reordering of the diagonal pairs is achieved by selecting which eigenpair is peeled off at each step, since the eigenpair chosen for $z_n$ is free. $\square$

Bridge. This existence theorem builds toward the QZ algorithm of the Advanced results, which computes the very decomposition just shown to exist, by the same orthogonal-equivalence mechanism but iteratively and in $O(n^3)$ rather than through an abstract induction. The construction here is exactly the generalised analogue of the static Schur form whose single-matrix version underwrites the QR algorithm of 43.06.03: setting $B=I$ collapses $Q^{\mathsf{H}}AZ$ with $Q=Z$ back to ordinary Schur triangularisation, so the QZ decomposition generalises that case while keeping two independent unitaries to handle the second matrix. The foundational reason two unitaries are unavoidable is that a pencil carries two matrices that cannot in general be triangularised by one common similarity; this is exactly the structural fact that the diagonal pairs $(t_{ii},s_{ii})$, not single numbers, are the invariants. The decomposition appears again in the symmetric-definite reduction and in the perturbation theory of the chordal metric, and putting these together, the bridge is the recognition that the existence proof's peel-one-eigenpair induction is precisely what the QZ iteration realises as a convergent, backward-stable sweep on the Hessenberg-triangular form.

Exercises Intermediate+

Advanced results Master

Theorem (the QZ algorithm; Moler-Stewart 1973 ^{[source pending]}; Golub-Van Loan §7.7 ^{[source pending]}). Let $(A,B)$ be a regular pencil with $A,B\in M_n(\mathbb{C})$ and $B$ invertible. The QZ algorithm computes the generalised Schur decomposition in two phases. First, a finite sequence of unitary equivalences reduces $(A,B)$ to Hessenberg-triangular form $(H,R)$ with $H$ upper-Hessenberg and $R$ upper-triangular. Second, an iterative phase applies implicit shifted QR sweeps to the matrix $H{R}^{-1}$ — represented only through $H$ and $R$, never by forming the product — driving the subdiagonal of $H$ to zero while preserving the triangularity of $R$, so that $(H,R)$ converges to a generalised Schur pair $(T,S)$. The unitary accumulators $Q$ and $Z$ are the products of the left and right transformations, and the computed pair satisfies $\Vert Q^{\mathsf{H}}AZ-T\Vert ,\Vert Q^{\mathsf{H}}BZ-S\Vert =O({ϵ}_{\mathrm{mach}}(\Vert A\Vert +\Vert B\Vert ))$.

The reduction to Hessenberg-triangular form first triangularises $B$ by a QR factorisation $B=Q_{0}R$, applying $Q_0^{\mathsf{H}}$ on the left of both matrices; then a sequence of Givens rotations annihilates the entries of $A$ below the first subdiagonal one at a time, each rotation applied on the left to a pair of rows of both $A$ and $B$ and immediately followed by a rotation on the right to a pair of columns of both, chosen to restore the upper-triangularity of $R$ that the left rotation disturbed. This left-then-right paired sweep is the structural signature of QZ: every transformation is a two-sided orthogonal equivalence, so the generalised eigenvalues are preserved at machine precision throughout, and the cost is $O(n^3)$.

The iterative phase is the implicit shift. Conceptually one runs the shifted QR algorithm of 43.06.03 on $M=H{R}^{-1}$, which is upper-Hessenberg because $H$ is Hessenberg and $R^{-1}$ is upper-triangular. A QR step on $M-\mu I$ would compute $M-\mu I=\tilde{Q}\tilde{R}$ and form ${\tilde{Q}}^{\mathsf{H}}(M)\tilde{Q}$. The QZ realisation never forms $M$: it computes only the first column of $M-\mu I$, which depends on $H$ and on solving one triangular system with $R$, builds the Householder or Givens transformation that maps that column to a multiple of $e_1$, applies it on the left of $(H,R)$, and then chases the resulting bulge down the pencil with paired left-right rotations exactly as in the reduction phase, restoring Hessenberg-triangular form. By the implicit-Q theorem of 43.06.03, the result is the same pencil the explicit shifted step on $M$ would produce, because an unreduced Hessenberg-triangular pencil is determined up to diagonal scaling by the first column of the equivalent $M$. Avoiding the explicit product $H{R}^{-1}$ is what makes the method stable when $R$ (equivalently $B$) is ill-conditioned: the entries of $H{R}^{-1}$ would be polluted by a factor $\kappa (R)$, whereas the implicit scheme touches $R$ only through one well-posed triangular solve per sweep.

Theorem (the symmetric-definite generalised eigenproblem; Golub-Van Loan §8.7 ^{[source pending]}). Let $A$ be Hermitian and $B$ Hermitian positive-definite, with Cholesky factorisation $B=L{L}^{\mathsf{H}}$. Then $C=L^{-1}A{L}^{-\mathsf{H}}$ is Hermitian, its eigenvalues are the generalised eigenvalues of $(A,B)$ — all real and finite — and the symmetric QR algorithm applied to $C$ computes them with backward error $O({ϵ}_{\mathrm{mach}}\Vert C\Vert )$. The generalised eigenvectors are recovered by $v=L^{-\mathsf{H}}y$ from the eigenvectors $y$ of $C$.

This reduction is the constructive numerical counterpart of the simultaneous-diagonalisation theory of 01.01.19, which establishes that a symmetric pair with one definite member can be diagonalised by a single congruence; the Cholesky factor $L$ supplies that congruence explicitly and stably. The QZ algorithm applies to a general pencil and so does not exploit symmetry, but on the symmetric-definite class it is wasteful: the Cholesky reduction costs a third of the work and delivers a standard Hermitian eigenproblem whose conditioning is governed by $\kappa (B)$, acceptable when $B$ is well-conditioned. When $B$ is symmetric positive-definite but ill-conditioned, the QZ algorithm on the unsymmetrised pair is preferred for accuracy, trading the symmetry exploitation for the avoidance of the squared sensitivity that $L^{-1}A{L}^{-\mathsf{H}}$ inherits from $\kappa (B)$.

Theorem (perturbation and the chordal metric; Stewart-Sun 1990 ^{[source pending]}). The sensitivity of a simple finite generalised eigenvalue of a regular pencil is correctly measured not by the Euclidean distance on $\mathbb{C}$ but by the chordal metric on projective pairs,

$$\chi (({\alpha }_1,{\beta }_1),({\alpha }_2,{\beta }_2))=\frac{|{\alpha }_1{\beta }_2-{\alpha }_2{\beta }_1|}{\sqrt{|{\alpha }_1{|}^2+|{\beta }_1{|}^2}\sqrt{|{\alpha }_2{|}^2+|{\beta }_2{|}^2}},$$

under which a finite and an infinite eigenvalue sit at finite chordal distance, and the condition number of a generalised eigenvalue with left and right eigenvectors $y,x$ is $(|y^{\mathsf{H}}Ax{|}^2+|y^{\mathsf{H}}Bx{|}^2{)}^{1/2}/(\Vert x\Vert \Vert y\Vert |y^{\mathsf{H}}Bx|\cdots )$, finite even as $\lambda \to \infty$.

The chordal metric is the intrinsic distance on the projective line of eigenvalue pairs, and its appearance is forced by the existence of infinite eigenvalues: a perturbation that moves a large finite eigenvalue past infinity to a large negative one is small in the chordal sense though enormous in the ordinary one, which is the correct accounting for a pencil where $\lambda =\infty$ is an ordinary point. This is the perturbation-theoretic shadow of the projective bookkeeping that the generalised Schur form keeps in its diagonal pairs $(t_{ii},s_{ii})$.

Synthesis. The QZ algorithm is the orthogonal-equivalence descendant of the QR algorithm, and the generalised Schur decomposition is the foundational reason it computes the entire pencil spectrum at once: where QR drives a single matrix to triangular form by one-sided similarity, QZ drives the pair $(A,B)$ to a triangular pair by two-sided equivalence, reading every generalised eigenvalue as a diagonal ratio $t_{ii}/s_{ii}$. This is exactly the structure that setting $B=I$ collapses back to the standard Schur form of 43.06.03, so QZ generalises that algorithm while keeping two unitaries $Q\ne Z$ to absorb the second matrix; the central insight is that the implicit shift runs the shifted QR iteration on $H{R}^{-1}$ without ever forming it, touching $R$ only through one triangular solve per sweep, which is precisely how the method stays backward stable when $B$ is ill-conditioned and forming $B^{-1}A$ would not.

The symmetric-definite case is dual to the general one: there the Cholesky congruence of 01.01.19 reduces the pencil to a single Hermitian matrix, trading the two-sided machinery for the cheaper one-sided symmetric QR whenever $B$ is well-conditioned. Putting these together, the perturbation theory closes the loop — the chordal metric on projective pairs $(\alpha ,\beta )$ is the intrinsic geometry the diagonal pairs live in, making a finite and an infinite eigenvalue near neighbours — and the bridge is the recognition that the static existence of a common triangularising equivalence becomes, through Hessenberg-triangular reduction plus implicit bulge-chasing, a constructive backward-stable algorithm whose every step is the pencil analogue of one orthogonal QR sweep.

Full proof set Master

Proposition (equivalence preserves the generalised spectrum). If $Q,Z$ are invertible and $(A^{\prime },B^{\prime })=(QAZ,QBZ)$, then $\det (A^{\prime }-\lambda B^{\prime })=\det (Q)\det (Z)\det (A-\lambda B)$, so the finite generalised eigenvalues and their multiplicities, the degree of the characteristic polynomial, and hence the count of infinite eigenvalues are all preserved.

Proof. Compute $A^{\prime }-\lambda B^{\prime }=QAZ-\lambda QBZ=Q(A-\lambda B)Z$ by linearity in $\lambda$. Taking determinants, $\det (A^{\prime }-\lambda B^{\prime })=\det (Q)\det (A-\lambda B)\det (Z)$, with $\det (Q)\det (Z)$ a non-zero constant independent of $\lambda$. The two polynomials in $\lambda$ therefore have the same roots with the same multiplicities and the same degree. Since a regular $n\times n$ pencil has $n$ eigenvalue pairs of which the degree counts the finite ones, the infinite count $n-\mathrm{deg}$ is preserved as well. $\square$

Proposition (HR⁻¹ is upper-Hessenberg). If $H$ is upper-Hessenberg and $R$ is invertible upper-triangular, then $M=H{R}^{-1}$ is upper-Hessenberg.

Proof. The inverse $R^{-1}$ of an invertible upper-triangular matrix is upper-triangular. The product of an upper-Hessenberg matrix $H$ and an upper-triangular matrix $T=R^{-1}$ has $(i,j)$ entry ${\sum }_m{h}_{im}{t}_{mj}$, where $h_{im}=0$ for $i>m+1$ and $t_{mj}=0$ for $m>j$. A non-zero term needs $i-1\le m\le j$, which is impossible when $i>j+1$. So $M_{ij}=0$ for $i>j+1$, that is $M$ is upper-Hessenberg. $\square$

Proposition (one QZ sweep preserves Hessenberg-triangular form). Let $(H,R)$ be Hessenberg-triangular with $R$ invertible, and let a QZ sweep consist of a left transformation $Q_1$ determined by the first column of $M-\mu I$ (with $M=H{R}^{-1}$) followed by bulge-chasing left-right paired rotations restoring triangularity of $R$. The resulting pair $(H^{\prime },R^{\prime })=(Q_s^{\mathsf{H}}\cdots Q_1^{\mathsf{H}}H{Z}_1\cdots Z_s,Q_s^{\mathsf{H}}\cdots Q_1^{\mathsf{H}}R{Z}_1\cdots Z_s)$ is again Hessenberg-triangular, and $M^{\prime }=H^{\prime }{R}^{\prime -1}$ equals the explicit shifted-QR iterate of $M$.

Proof. Each paired step applies a left rotation $Q_k^{\mathsf{H}}$ and a right rotation $Z_k$. The right rotations are chosen at each stage to annihilate the single entry that the preceding left rotation introduced below the diagonal of $R$, so $R^{\prime }=Q_s^{\mathsf{H}}\cdots Q_1^{\mathsf{H}}R{Z}_1\cdots Z_s$ is upper-triangular by construction. The left rotation $Q_1$ is built so that $Q_1^{\mathsf{H}}(M-\mu I)e_1$ is a multiple of $e_1$; the bulge-chasing restores $H^{\prime }$ to upper-Hessenberg form one subdiagonal position at a time, the standard bulge-chase of 43.06.03 adapted so each left rotation is paired with a right rotation keeping $R$ triangular. Let $Q=Q_1\cdots Q_s$ and $Z=Z_1\cdots Z_s$. Then $M^{\prime }=H^{\prime }{R}^{\prime -1}=(Q^{\mathsf{H}}HZ)(Q^{\mathsf{H}}RZ{)}^{-1}=Q^{\mathsf{H}}HZ{Z}^{-1}{R}^{-1}Q=Q^{\mathsf{H}}(H{R}^{-1})Q=Q^{\mathsf{H}}MQ$, so $M^{\prime }$ is a unitary similarity of $M$ by $Q$. Since $Q{e}_1\propto (M-\mu I)e_1$ — because $Q_1{e}_1\propto (M-\mu I)e_1$ and each subsequent $Q_k$ fixes the first coordinate — and both $M^{\prime }$ and the explicit iterate ${\tilde{Q}}^{\mathsf{H}}M\tilde{Q}$ from $M-\mu I=\tilde{Q}\tilde{R}$ are unreduced upper-Hessenberg with transforming first columns agreeing up to scale, the implicit-Q uniqueness theorem of 43.06.03 gives $Q=\tilde{Q}D$ for a diagonal unitary $D$, so $M^{\prime }=D^{\mathsf{H}}({\tilde{Q}}^{\mathsf{H}}M\tilde{Q})D$ equals the explicit shifted-QR iterate up to diagonal scaling. $\square$

Proposition (deflation at a zero subdiagonal). If during the QZ iteration a subdiagonal entry $h_{k+1,k}$ of $H$ falls below a tolerance proportional to ${ϵ}_{\mathrm{mach}}(|h_{kk}|+|h_{k+1,k+1}|)$, setting it to zero splits the pencil into a leading $(k)\times (k)$ Hessenberg-triangular pencil and a trailing $(n-k)\times (n-k)$ one, whose generalised eigenvalues are the union of the two subpencils'.

Proof. Setting $h_{k+1,k}=0$ makes $H$ block upper-triangular with diagonal blocks $H_{11}$ (size $k$) and $H_{22}$ (size $n-k$); $R$ is already upper-triangular, hence block upper-triangular with the same partition into $R_{11},R_{22}$. For a block upper-triangular pencil, $\det (H-\lambda R)=\det (H_{11}-\lambda R_{11})\det (H_{22}-\lambda R_{22})$ by the block-triangular determinant formula, so the generalised characteristic polynomial factors and the eigenvalue set is the union of the two subpencils' eigenvalue sets, with multiplicities adding. The QZ iteration then continues independently on each block. When instead a diagonal entry $r_{kk}$ of $R$ becomes negligible, a left rotation moves the resulting zero to the bottom-right, deflating an infinite eigenvalue $(t_{nn},0)$. $\square$

Connections Master

The QZ algorithm is the direct generalisation of the QR algorithm of 43.06.03: setting $B=I$ and constraining $Q=Z$ recovers ordinary Schur triangularisation, the implicit shift on $H{R}^{-1}$ reduces to the implicit shift on $H$, and the bulge-chasing machinery, the implicit-Q theorem, the shift strategies, and the backward-stability argument all specialise verbatim; the present unit is the standard eigenproblem lifted from one matrix to a pencil by replacing one-sided similarity with two-sided orthogonal equivalence.

The symmetric-definite reduction realises numerically the simultaneous-diagonalisation theorem of 01.01.19: that unit proves a symmetric pencil with one definite member admits a single congruence diagonalising both forms, and the Cholesky factor $L$ of $B$ together with the spectral theorem of 01.01.13 applied to $C=L^{-1}A{L}^{-\mathsf{H}}$ is exactly that congruence made constructive and stable, turning the existence statement into the computed eigenvalues that vibration analysis and quadratic-form optimisation consume.

The generalised eigenvalue structure rests on the ordinary eigenvalue and characteristic-polynomial theory of 01.01.08: the generalised characteristic polynomial $\det (A-\lambda B)$ is the pencil analogue of $\det (A-\lambda I)$, its degree drop below $n$ encodes the infinite eigenvalues that the projective pair $(\alpha ,\beta )$ records, and the existence proof peels off one ordinary eigenpair of $B^{-1}A$ at a time exactly as the Schur induction of the single-matrix case peels off one eigenvector.

Historical & philosophical context Master

The QZ algorithm was introduced by Cleve Moler and G. W. Stewart in their 1973 paper in the SIAM Journal on Numerical Analysis, which gave the name QZ and established the two-phase structure — reduction to Hessenberg-triangular form followed by an implicit shifted iteration on the pencil — together with the backward-stability analysis ^{[Moler 1973]}. Their central design decision was to refuse the obvious route of forming $B^{-1}A$ and running the existing QR algorithm: when $B$ is ill-conditioned that product is computed inaccurately, and the resulting eigenvalues inherit the conditioning of $B$ rather than the conditioning of the pencil. By manipulating $A$ and $B$ only through unitary equivalences and a single triangular solve per sweep, QZ achieves the backward error $O({ϵ}_{\mathrm{mach}}(\Vert A\Vert +\Vert B\Vert ))$ that the explicit-inverse route forfeits.

The generalised eigenvalue problem itself is older, arising in the nineteenth-century theory of pairs of quadratic forms studied by Weierstrass, whose elementary-divisor theory and the Kronecker theory of singular pencils classify the canonical forms that QZ computes in the regular case ^{[Stewart 1990]}. The recognition that generalised eigenvalues should be carried as projective pairs $(\alpha ,\beta )$, and that their perturbation is governed by the chordal metric under which infinity is an ordinary point, was developed in the perturbation theory of Stewart and Sun, completing the numerical picture by giving the condition number of a generalised eigenvalue a form that remains finite as the eigenvalue tends to infinity. The QZ algorithm remains the method underlying the generalised eigenvalue routines of LAPACK and is the standard back end for polynomial root-finding through the companion pencil.

Bibliography Master

@article{MolerStewart1973,
  author  = {Moler, Cleve B. and Stewart, G. W.},
  title   = {An Algorithm for Generalized Matrix Eigenvalue Problems},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {10},
  number  = {2},
  year    = {1973},
  pages   = {241--256}
}

@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}
}

@book{StewartSun1990,
  author    = {Stewart, G. W. and Sun, Ji-Guang},
  title     = {Matrix Perturbation Theory},
  publisher = {Academic Press},
  address   = {Boston},
  year      = {1990}
}

@book{Stewart2001,
  author    = {Stewart, G. W.},
  title     = {Matrix Algorithms, Volume II: Eigensystems},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {2001}
}

@book{Watkins2007,
  author    = {Watkins, David S.},
  title     = {The Matrix Eigenvalue Problem: {GR} and {K}rylov Subspace Methods},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {2007}
}

@article{Weierstrass1868,
  author  = {Weierstrass, Karl},
  title   = {Zur Theorie der bilinearen und quadratischen Formen},
  journal = {Monatsberichte der K\"oniglich Preussischen Akademie der Wissenschaften zu Berlin},
  year    = {1868},
  pages   = {310--338}
}

@article{Kronecker1890,
  author  = {Kronecker, Leopold},
  title   = {Algebraische Reduction der Schaaren bilinearer Formen},
  journal = {Sitzungsberichte der K\"oniglich Preussischen Akademie der Wissenschaften zu Berlin},
  year    = {1890},
  pages   = {1225--1237}
}