Generalized eigenvalue pencils and QZ methods

Let $n\ge 1$, let $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, and let $A,B\in {\mathbb{F}}^{n\times n}$. The matrix pencil determined by $(A,B)$ is $A-\lambda B$. Its determinant polynomial is $f(\lambda )=\det (A-\lambda B)$, with real coefficients viewed as complex coefficients when $\mathbb{F}=\mathbb{R}$. The pencil is regular if $f$ is not the zero polynomial; otherwise it is singular.

For $\alpha ,\beta \in \mathbb{C}$ not both zero, put $p(\alpha ,\beta )=\det (\beta A-\alpha B)\mathrm{.}$ A homogeneous generalized eigenvalue pair is an equivalence class of such pairs satisfying $p(\alpha ,\beta )=0$, where $(\alpha ,\beta )$ and $(c\alpha ,c\beta )$ represent the same pair for every $c\in \mathbb{C}\setminus \{0\}$. If $\beta \mathrm{\ne }0$, the associated finite generalized eigenvalue is $\lambda =\alpha \mathrm{/}\beta$; if $\beta =0$, the pair is an infinite generalized eigenvalue. The pair $(0,0)$ is never an eigenvalue pair. Write $\sigma (A,B)$ for the set of finite ratios $\alpha \mathrm{/}\beta$ among these homogeneous eigenvalue pairs.

The QZ results on this page assume a regular pencil. They make no assertion about Kronecker structure or eigenvalues of a singular pencil.

Let $n_1,n_2\ge 1$, $n=n_1+n_2$, and let $A,B\in {\mathbb{C}}^{n\times n}$ be block upper triangular with the same two-block partition of sizes $n_1,n_2$, with diagonal blocks $A_{11},A_{22}$ and $B_{11},B_{22}$. For every $\alpha ,\beta \in \mathbb{C}$, $\det (\beta A-\alpha B)=\det (\beta A_{11}-\alpha B_{11})\det (\beta A_{22}-\alpha B_{22})\mathrm{.}$

If $M\in {\mathbb{F}}^{n\times n}$, $n\ge 1$, $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, and $\det M=0$, then there is a nonzero vector $v\in {\mathbb{F}}^n$ with $Mv=0$.

Let $B\in {\mathbb{F}}^{n\times n}$, $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, be Hermitian positive definite, with Cholesky factor $B=L{L}^{\ast }$ and $L$ lower triangular with positive diagonal. This factor exists and is unique by A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique. Define the linear-first B-inner product by $⟨x,y{⟩}_B:=y^{\ast }Bx,$ the B-norm by $\mathrm{\parallel }x{\mathrm{\parallel }}_B:=\mathrm{\parallel }{L}^{\ast }x{\mathrm{\parallel }}_2=\sqrt{x^{\ast }Bx},$ and the B-dual residual norm by $\mathrm{\parallel }r{\mathrm{\parallel }}_{B^{-1}}:=\mathrm{\parallel }{L}^{-1}r{\mathrm{\parallel }}_2=\sqrt{r^{\ast }{B}^{-1}r}\mathrm{.}$ The B-orthogonality condition is $x^{\ast }By=0$; since $B=B^{\ast }$ it is equivalent to $⟨x,y{⟩}_B=0$.

Input $A,B\in {\mathbb{F}}^{n\times n}$, $n\ge 1$, with $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. All transformations here are exact. Use zero-based matrix indices $0,\dots ,n-1$, as in Real Givens rotations and complex Givens transformations. Let $Q=Z=I_n$.

For a target pair $(a,b)$, define the left factor $L(a,b)$ deterministically. Use $I_2$ if $a=b=0$. Otherwise put $r=(\mathrm{\mid }a{\mathrm{\mid }}^2+\mathrm{\mid }b{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$ and $L=\left(\begin{array}{cc}c& s\\ -\bar{s}& c\end{array}\right)$. Over $\mathbb{R}$, take $c=a\mathrm{/}r$, $s=b\mathrm{/}r$. Over $\mathbb{C}$, if $a=0$ take $c=0$, $s=\bar{b}\mathrm{/}\mathrm{\mid }b\mathrm{\mid }$; otherwise take $\varphi =a\mathrm{/}\mathrm{\mid }a\mathrm{\mid }$, $c=\mathrm{\mid }a\mathrm{\mid }\mathrm{/}r$, $s=\varphi \bar{b}\mathrm{/}r$. Thus $L(a,b)(a,b{)}^T=(\gamma ,0{)}^T$ with $\mathrm{\mid }\gamma \mathrm{\mid }=r$. Set $J=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ and define the right factor $R(a,b)=JL(\bar{b},\bar{a}{)}^{\ast }J\mathrm{.}$ Then $(a,b)R(a,b)=(0,\eta )$ with $\mathrm{\mid }\eta \mathrm{\mid }=r$; the zero pair again uses identity. These factors are real orthogonal over $\mathbb{R}$ or unitary over $\mathbb{C}$, as direct multiplication shows in Householder reflectors and Givens transformations are unitary and can annihilate prescribed entries; the right identity follows by taking adjoints of the left annihilation of $(\bar{b},\bar{a}{)}^T$ and reversing the coordinates. Use their identity embeddings on the two rows or columns specified by each step below.

1. Triangularise $B$ by left rotations. For $j=0,\dots ,n-1$ and, in descending order, $i=n-1,n-2,\dots ,j+1$, set $L=L(B_{i-1,j},B_{i,j}),A\leftarrow LA,B\leftarrow LB,Q\leftarrow Q{L}^{\ast }\mathrm{.}$

2. Reduce $A$ to upper Hessenberg form while restoring triangularity of $B$. For $j=0,\dots ,n-3$ and, in descending order, $i=n-1,n-2,\dots ,j+2$, set $L=L(A_{i-1,j},A_{i,j}),A\leftarrow LA,B\leftarrow LB,Q\leftarrow Q{L}^{\ast },$ then set $R=R(B_{i,i-1},B_{i,i}),A\leftarrow AR,B\leftarrow BR,Z\leftarrow ZR\mathrm{.}$

Return $Q,Z,H=A,T=B$, where $H$ is upper Hessenberg and $T$ is upper triangular in the senses of Upper Hessenberg matrices and real symmetric tridiagonal matrices and Upper triangular, lower triangular and diagonal square matrices over a commutative ring. The outputs are represented by the exact products of the recorded Givens factors; no dense rounded factor is asserted unitary.

Let $(A,B)$ be a regular pencil of order $n$. A complex generalized Schur form is a factorisation $Q^{\ast }AZ=S,Q^{\ast }BZ=T,$ where $Q,Z\in {\mathbb{C}}^{n\times n}$ are unitary in the sense of Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces, and $S,T$ are upper triangular as in Upper triangular, lower triangular and diagonal square matrices over a commutative ring. For its $i$th one-by-one diagonal block, $[s_{ii}:t_{ii}]$ is the diagonal homogeneous pair.

For real $A,B$, a real generalized Schur form has $Q^{T}AZ=S,Q^{T}BZ=T,$ where $Q,Z$ are orthogonal, $S$ is block upper triangular with diagonal blocks of size one or two, and $T$ is upper triangular. Each one-by-one diagonal block has a nonzero real homogeneous pair. For a two-by-two diagonal block $(S_{kk},T_{kk})$, the diagonal homogeneous roots are the zeros of $\det (\beta S_{kk}-\alpha T_{kk})$ in $[\alpha :\beta ]$; such a block has a nonreal conjugate pair of finite roots. A singular pencil is outside this definition.

For $A,B\in {\mathbb{F}}^{n\times n}$, $n\ge 1$, let $p(\alpha ,\beta )=\det (\beta A-\alpha B)$. For every $c\in \mathbb{C}$, $p(c\alpha ,c\beta )=c^{n}p(\alpha ,\beta )\mathrm{.}$ Consequently the zero condition is independent of the nonzero representative of a homogeneous pair. If $\beta \mathrm{\ne }0$, then $p(\alpha ,\beta )={\beta }^n\det (A-(\alpha \mathrm{/}\beta )B)\mathrm{.}$

If $(A,B)$ is a regular pencil and $x\in {\mathbb{C}}^n$ satisfies $Ax=0$ and $Bx=0$, then $x=0$.

Let $n\ge 1$, $m\ge 0$, $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, and $A,B\in {\mathbb{F}}^{n\times n}$. Put $A_0=A$, $B_0=B$. For $j=1,\dots ,m$, suppose exact unitary/orthogonal factors $Q_j,Z_j$ and local arithmetic/deflation perturbations satisfy $A_j=Q_j^{\ast }(A_{j-1}+E_j^A+D_j^A)Z_j,$ $B_j=Q_j^{\ast }(B_{j-1}+E_j^B+D_j^B)Z_j\mathrm{.}$ Then with $Q=Q_1\cdots Q_m$ and $Z=Z_1\cdots Z_m$ (empty products are $I_n$) there are perturbations ${\mathrm{\Delta }}_A,{\mathrm{\Delta }}_B$ such that $A_m=Q^{\ast }(A+{\mathrm{\Delta }}_A)Z,B_m=Q^{\ast }(B+{\mathrm{\Delta }}_B)Z,$ and $\sqrt{\mathrm{\parallel }{\mathrm{\Delta }}_A{\mathrm{\parallel }}_F^2+\mathrm{\parallel }{\mathrm{\Delta }}_B{\mathrm{\parallel }}_F^2}\le {\sum }_{j=1}^m(\sqrt{\mathrm{\parallel }{E}_j^A{\mathrm{\parallel }}_F^2+\mathrm{\parallel }{E}_j^B{\mathrm{\parallel }}_F^2}+\sqrt{\mathrm{\parallel }{D}_j^A{\mathrm{\parallel }}_F^2+\mathrm{\parallel }{D}_j^B{\mathrm{\parallel }}_F^2})\mathrm{.}$

Let $A=A^{\ast }$ and let $B=B^{\ast }$ be positive definite in ${\mathbb{F}}^{n\times n}$, where $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. If $B=L{L}^{\ast }$ is its Cholesky factorisation, then $C=L^{-1}A{L}^{-\ast }$ is self-adjoint and has an orthonormal eigenbasis with real eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$. The vectors $x_i=L^{-\ast }{y}_i(i=1,\dots ,n)$ form a basis satisfying $A{x}_i={\lambda }_{i}B{x}_i$ and $x_i^{\ast }B{x}_j={\delta }_{ij}$. The generalized eigenvalues of $(A,B)$ are exactly $[{\lambda }_i:1]$; none is infinite.

For every input of Givens reduction of a matrix pair to Hessenberg-triangular form, the algorithm terminates and returns orthogonal/unitary $Q,Z$, an upper Hessenberg matrix $H$, and an upper triangular matrix $T$ such that $H=Q^{\ast }AZ,T=Q^{\ast }BZ\mathrm{.}$

Every regular finite square pencil $(A,B)$ over $\mathbb{R}$ or $\mathbb{C}$ has at least one homogeneous generalized eigenvalue pair $[\alpha :\beta ]$ over $\mathbb{C}$.

Let $n\ge 1$, let $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, and let $A,B\in {\mathbb{F}}^{n\times n}$ be Hermitian with $B$ positive definite. For $x\in {\mathbb{F}}^n\setminus \{0\}$ and $\mu \in \mathbb{R}$, put $r=Ax-\mu Bx$. Then $\mathrm{dist}(\mu ,\sigma (A,B))\le \frac{\mathrm{\parallel }r{\mathrm{\parallel }}_{B^{-1}}}{\mathrm{\parallel }x{\mathrm{\parallel }}_B},$ where $\sigma (A,B)$ is the finite generalized spectrum and $\mathrm{dist}(\mu ,S):={\min }_{\lambda \in S}\mathrm{\mid }\mu -\lambda \mathrm{\mid }$. Equivalently, the interval with centre $\mu$ and radius $\mathrm{\parallel }r{\mathrm{\parallel }}_{B^{-1}}\mathrm{/}\mathrm{\parallel }x{\mathrm{\parallel }}_B$ contains at least one generalized eigenvalue.

Use the successful real/complex Givens arithmetic of Scaled real and complex Householder and Givens update arithmetic, with $0<u<1$. For a matrix pair write $P(C,D)=(\mathrm{\parallel }C{\mathrm{\parallel }}_F^2+\mathrm{\parallel }D{\mathrm{\parallel }}_F^2{)}^{1\mathrm{/}2}$ and put $a_2=\frac{1+u}{(1-u{)}^2}-1,q=\max \{{\left(\frac{1+u}{1-u}\right)}^3-1,\frac{(1+a_2)(1+6u)(1+u)}{(1-u{)}^3}-1\},$ $v=q+2(7u+6u^2)(1+q),h=u+2q+v,\eta =v+h\mathrm{.}$ Generate a single stored block $T_0=\left(\begin{array}{cc}c& s\\ -\bar{s}& c\end{array}\right)$ from the selected target and use its same coefficients on BOTH matrices. Retain its exact unitary representative $U=T_0\mathrm{/}\sqrt{c^2+\mathrm{\mid }s{\mathrm{\mid }}^2}$ as a factor record. Use the exact identity in the source's zero branch.

A raw common left or right action, without a target overwrite, has pair discrepancy at most $vP(C,D)$ from its exact representative. For an actual matrix target, overwrite only its intended annihilated entry with exact zero; this write has norm at most $h$ times the target pair norm. The complete action therefore satisfies $C_{+}=Q_0^{\ast }(C+E^C)Z_0,D_{+}=Q_0^{\ast }(D+E^D)Z_0,P(E^C,E^D)\le \mathrm{\ell }P(C,D),$ where $\mathrm{\ell }=\eta$ for a target action and $\mathrm{\ell }=v$ for a raw action; the unused factor is identity. Zero branches have zero discrepancy. A left action annihilates the second coordinate of a column. To annihilate the FIRST coordinate of a row $r=(a,b)$, let $J=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, generate $U$ from $(rJ{)}^{\ast }=(\bar{b},\bar{a}{)}^T$, and use the right factor $J{U}^{\ast }J$, applying its stored adjoint/permuted coefficients. For a second-coordinate right target omit $J$. An external shift-vector action has no matrix-target overwrite. Grouped left/right coefficients ${\mathrm{\ell }}_L,{\mathrm{\ell }}_R$ compose to ${\mathrm{\ell }}_L+{\mathrm{\ell }}_R+{\mathrm{\ell }}_L{\mathrm{\ell }}_R$.

Post-action zero writes are pulled back by the exact local factor adjoints before they enter a pre-action perturbation ledger. Structural writes may be included in $E$ with $\eta$, or separately recorded with raw coefficient $v$ and write allowance $h$, never both. Tolerance deflations remain separate exact perturbations, without an $O(u)$ assertion.

There is also a concrete residual certificate for represented products $Q=Q_1\cdots Q_m$, $Z=Z_1\cdots Z_m$. Apply stored raw right-factor kernels to $e_k$ in reverse order to approximate $Z{e}_k$; apply stored raw adjoint left-factor kernels in order $Q_1^{\ast },\dots ,Q_m^{\ast }$ to approximate $Q^{\ast }$ action. Omit all structural overwrites in these vector actions. For a stored current vector $y$ and discrepancy allowance $e$, propagate $e_{\mathrm{n}\mathrm{e}\mathrm{x}\mathrm{t}}=e+v\mathrm{\parallel }y{\mathrm{\parallel }}_2\mathrm{.}$ With $\widehat{z}\approx Z{e}_k$ and allowance $e_z$, compute $\widehat{a}=\mathrm{fl}(A\widehat{z})$ by sequential stored-input dot products. When $(n-1)u<1$, its allowance relative to $AZ{e}_k$ is $e_a=g_n\mathrm{\parallel }A{\mathrm{\parallel }}_F\mathrm{\parallel }\widehat{z}{\mathrm{\parallel }}_2+\mathrm{\parallel }A{\mathrm{\parallel }}_F{e}_z,g_n=\frac{1+6u}{1-(n-1)u}-1.$ Propagate through the $Q^{\ast }$ kernels, obtaining $\widehat{w},e_w$, then form ${\widehat{r}}_k=\mathrm{fl}(\widehat{w}-S_{:k})$ with allowance $e_k=e_w+u(\mathrm{\parallel }\widehat{w}{\mathrm{\parallel }}_2+\mathrm{\parallel }{S}_{:k}{\mathrm{\parallel }}_2)\mathrm{.}$ Thus $\mathrm{\parallel }{Q}^{\ast }AZ-S{\mathrm{\parallel }}_F\le {\sum }_{k=1}^n(\mathrm{\parallel }{\widehat{r}}_k{\mathrm{\parallel }}_2+e_k)$; repeat with $B,T$. All these norms may be replaced by the component sum $\sum (\mathrm{\mid }\mathrm{\Re }x\mathrm{\mid }+\mathrm{\mid }\mathrm{\Im }x\mathrm{\mid })$ over the relevant vector/matrix. These conservative certificates use only finite exact real field operations and comparisons on stored inputs, $u$, and the finite factor list, and have exact rational implementations for rational/binary inputs and rational $u$. The controller uses the displayed finite expression trees and loops, with no square root or untyped certification oracle. Their failure hypotheses make this independent residual route inconclusive; they do not invalidate a separately valid local-accumulation certificate.

Input a regular pencil $(A,B)$ with $A,B\in {\mathbb{C}}^{n\times n}$, $n\ge 1$, a nonnegative integer sweep budget $N$, and a finite stored real tolerance $\tau \ge 0$. Real input data are embedded in $\mathbb{C}$. Scalar updates of the stored matrices use the operationwise model of Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add. Use zero-based matrix indices throughout. Each active block $[a:b]$ includes both endpoints; its relative coordinate $0$ is global index $a$. Use the canonical stored Givens generator and application order of Scaled real and complex Householder and Givens update arithmetic, with the common-pair orientations and explicit coefficients $v,h,\eta$ of Common computed Givens actions certify both pencil matrices and factor residuals. Generate each rotation ONCE and apply its same stored coefficients to BOTH matrices. Retain the exact normalized unitary representatives as product records, never as purported stored dense unitary matrices. Left rotations annihilate a column's second entry; right rotations annihilating a row's first entry use the coordinate reversal/adjoint construction of that lemma. After each genuine matrix target application write only its intended target to exact zero and include that write in the local coefficient $\eta$. An external-vector application has coefficient $v$ and no matrix-target overwrite. Local roundoff certification requires $0<u<1$; otherwise retain diagnostics with certificate-inconclusive. Record each elementary rotation separately. If the source cannot produce its admissible factor, return range-failure or certificate-inconclusive with diagnostics.

1. Execute the finite index loops of Givens reduction of a matrix pair to Hessenberg-triangular form with these COMPUTED common rotations: triangularize $B$ with left targets $B_{i,j}$; then reduce $A$ with left targets $A_{i,j}$ followed by right targets $B_{i,i-1}$. Every application updates both whole arrays. The exact initializer and Givens reduction terminates with a unitary-equivalent Hessenberg-triangular pair supply the index schedule and support induction, not exact rounded reconstruction. Retain each local factor and residual defined against its exact representative. Include structural target writes in that local arithmetic residual. Record all OTHER explicit zero writes separately: their post-action perturbations are pulled back by the local factor adjoints before entering the pre-action $D_j^A,D_j^B$ ledger. A pure tolerance write is an identity-factor stage. Never count a structural write twice.

Initialize the sweep counter to zero. Process active blocks in increasing first index, splitting them at exact zero subdiagonals of $H$. In each deflation pass execute step 2, then repeat step 3 for the smallest available non-isolated zero diagonal of $T$ until none remains or a status exits. Then run step 5; if it returns a status, stop. Otherwise, if the sweep counter equals $N$, return budget-exhausted. If not, increment the counter, execute step 4 on all remaining active blocks, and repeat the deflation pass. In particular $N=0$ permits initialization/deflation but no step-4 sweep.

2. On each active block $H_{a:b,a:b},T_{a:b,a:b}$, apply the following deflation tests before a sweep. For $i=a,\dots ,b-1$, set $H_{i+1,i}$ to zero when $\mathrm{\mid }{H}_{i+1,i}\mathrm{\mid }\le \tau (\mathrm{\mid }{H}_{i,i}\mathrm{\mid }+\mathrm{\mid }{H}_{i+1,i+1}\mathrm{\mid }),$ and record the negative of its old value at that position in $D^A$, with all other entries zero. For $k=a,\dots ,b$, set $T_{k,k}$ to zero when $\mathrm{\mid }{T}_{k,k}\mathrm{\mid }\le \tau (\mathrm{\mid }{T}_{k-1,k}\mathrm{\mid }+\mathrm{\mid }{T}_{k,k+1}\mathrm{\mid }),$ using zero for a missing boundary term outside the active block, and record the negative of the old value at that position in $D^B$, with all other entries zero. Treat each write as a separate identity-factor stage, so the new matrix is the old matrix plus its recorded perturbation. Evaluate each displayed modulus by the canonical rounded scaled two-component norm; evaluate its additions and tolerance product with the declared rounded real operations, then compare the stored finite values exactly. Excluded operations return range-failure. The tests mean these rounded comparisons, not an assertion about exact moduli at the threshold. Save the actual old entries, so their deflation perturbations remain exact regardless of the test. A one-by-one diagonal pair at $k$ is isolated when $H_{k,k-1}=0$ and $H_{k+1,k}=0$, omitting a boundary entry when $k=a$ or $k=b$. If it has $T_{k,k}=0$ and $H_{k,k}\mathrm{\ne }0$, report an infinite candidate for the computed pencil and deflate it from the active block. If the isolated diagonal pair is $(0,0)$, return singular-pencil-suspected without assigning an eigenvalue.

3. To move a non-isolated zero $T_{k,k}$ to the top of its active block, for $j=k-1,k-2,\dots ,a$ generate a right factor from the row pair $(T_{j,j},T_{j,j+1})$ and apply it to columns $j,j+1$, setting $T_{j,j}$ to zero. Then, when $j+2\le b$, generate a left factor from $(H_{j+1,j},H_{j+2,j})$ and apply it to rows $j+1,j+2$, setting the resulting bulge $H_{j+2,j}$ to zero. Finally, when $a<b$, generate a left factor from $(H_{a,a},H_{a+1,a})$ and apply it to rows $a,a+1$, setting $H_{a+1,a}$ to zero. Record all rounded update residuals and target writes. If this isolates $(H_{a,a},T_{a,a})=(h,0)$ with $h\mathrm{\ne }0$, report the infinite candidate and remove the first row/column from the active block. If the isolated pair is $(0,0)$, return singular-pencil-suspected; if isolation fails, return certificate-inconclusive. Each successful isolation removes one index, so at most $n$ such removals occur.

4. For each remaining active block with more than one row in the current sweep, choose the homogeneous shift $[\alpha :\beta ]=[H_{b,b}:T_{b,b}]$ if this pair is nonzero and $T_{b,b}\mathrm{\ne }0$; if $T_{b,b}=0$, use $[0:1]$. Write $\widehat{H}=H_{a:b,a:b}$ and $\widehat{T}=T_{a:b,a:b}$, with relative indices $0,\dots ,b-a$, and form $x=(\beta \widehat{H}-\alpha \widehat{T})e_0\mathrm{.}$ Compute $x_0,x_1$ using the declared rounded complex products/subtractions and generate a left factor from $(x_0,x_1)$. Apply it to relative rows $0,1$ of both matrices without a matrix-target overwrite. Its rounding changes the selected factor, not its application certificate. Generate a right factor from the row pair $({\widehat{T}}_{1,0},{\widehat{T}}_{1,1})$ and apply it to relative columns $0,1$, setting ${\widehat{T}}_{1,0}$ to zero. For relative $j=1,\dots ,b-a-1$, generate a left factor from $({\widehat{H}}_{j,j-1},{\widehat{H}}_{j+1,j-1})$ and apply it to rows $j,j+1$, setting the current Hessenberg bulge ${\widehat{H}}_{j+1,j-1}$ to zero; then generate a right factor from $({\widehat{T}}_{j+1,j},{\widehat{T}}_{j+1,j+1})$ and apply it to columns $j,j+1$, setting ${\widehat{T}}_{j+1,j}$ to zero. Update and retain the products $Q,Z$; record every local residual including its structural target write. Apply the embedded transformations to the entire pair, retaining the transformed off-block data. All divisions by a generalized eigenvalue ratio are avoided.

5. After each infinite isolation and before every successful return, scan all isolated diagonal pairs. Any $(0,0)$ pair returns singular-pencil-suspected without an eigenvalue. Stop with qz-computed only when $H$ is upper triangular and every diagonal pair is nonzero. Otherwise stop after $N$ sweeps with budget-exhausted. Range failures return range-failure with partial factors; unavailable local certificates return certificate-inconclusive. Neither a rounded diagnostic nor a tolerance-induced infinite candidate asserts an exact infinite eigenvalue of the original pencil.