Givens reduction of a matrix pair to Hessenberg-triangular form

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.