Every regular real or complex pencil has a generalized Schur form

We prove the statement by induction on $n$, with the empty trailing pencil allowed after a final block is removed. For $n=1$, regularity says the scalar pair $(A,B)$ is not $(0,0)$, and $Q=Z=[1]$ gives the required form. Now let $n>1$ and assume the result for smaller regular pencils.

Choose a homogeneous eigenvalue pair $[\alpha :\beta ]$ by [F1]. Its homogeneous determinant is zero, so [F10] gives a nonzero vector $v$ in the kernel over $\mathbb{C}$. For real input and a real projective root, rescale $[\alpha :\beta ]$ to real coordinates and apply [F10] over $\mathbb{R}$. If $\beta \mathrm{\ne }0$, put $\lambda =\alpha \mathrm{/}\beta$; then $Av=\lambda Bv$. If $Bv=0$, this also gives $Av=0$, contrary to [F2], so $Bv\mathrm{\ne }0$. If $\beta =0$, then $Bv=0$ and [F2] gives $Av\mathrm{\ne }0$.

If the input field is complex, or if the selected root for real input is real, use a one-dimensional block. Set $q=Bv$ in the finite case and $q=Av$ in the infinite case. Both vectors are nonzero by step 1.2. By [F4], choose unitary/orthogonal alignments $Lq=\gamma e_1$ and $Rv=\eta e_1$ and set $Q=L^{\ast }$, $Z=R^{\ast }$. Then $Q^{\ast }q=\gamma e_1$ and $Z^{\ast }v=\eta e_1$, so $Q^{\ast }AZ$ and $Q^{\ast }BZ$ have zeros below their first entries in the first column. The leading diagonal pair is nonzero: in the finite case its $B$ entry is nonzero, and in the infinite case its $A$ entry is nonzero.

If the input is real and the selected root is nonreal, then $\beta \mathrm{\ne }0$; write $\lambda =\alpha \mathrm{/}\beta =a+ib$ with $b\mathrm{\ne }0$ and write the vector from step 1.2 as $v=x+iy$ in $\ker (A-\lambda B)$. The real vectors $x,y$ are linearly independent. If they were dependent, $v$ would be a nonzero complex multiple of a nonzero real vector $w$, so $(A-\lambda B)w=0$. If $Bw=0$, then $Aw=0$, contradicting [F2]. If $Bw\mathrm{\ne }0$, a coordinate with $(Bw{)}_i\mathrm{\ne }0$ gives $\lambda =(Aw{)}_i\mathrm{/}(Bw{)}_i\in \mathbb{R}$, contradicting $b\mathrm{\ne }0$. Put $X={\mathrm{span}}_{\mathbb{R}}\{x,y\}$ and $Y={\mathrm{span}}_{\mathbb{R}}\{Bx,By\}$. Separating real and imaginary parts gives $Ax=aBx-bBy$ and $Ay=bBx+aBy$, so $A(X)\subseteq Y$. If $\dim Y<2$, then for each $\mu \in \mathbb{C}$ the map $(A-\mu B):X_{\mathbb{C}}\to Y_{\mathbb{C}}$ has a nonzero kernel because its domain has dimension two and its range has dimension at most one. Hence $A-\mu B$ is not invertible, so [F7] gives $\det (A-\mu B)=0$ for every $\mu$, contradicting regularity and [F8]. Thus $\dim Y=2$.

Apply [F5] to obtain orthonormal bases $z_1,z_2$ of $X$ and $q_1,q_2$ of $Y$, choosing $q_1,q_2$ by Gram–Schmidt on $B{z}_1,B{z}_2$. The restriction $B{\mathrm{\mid }}_X:X\to Y$ sends a basis to the independent pair $B{z}_1,B{z}_2$ and is therefore an isomorphism. Its matrix in these bases is $B_{11}=Q_1^{T}B{Z}_1$, so $B_{11}$ is invertible and [F7] gives $\det (B_{11})\mathrm{\ne }0$; the Gram–Schmidt choice makes this matrix upper triangular. Extend these bases by orthonormal bases of $Y^{\perp }$ and $X^{\perp }$ using [F6]. In these full bases, the first two columns of both transformed matrices are supported in the first two rows. Let $P$ be the invertible change-of-basis matrix from $(x,y)$ to $(z_1,z_2)$. The equations in step 2.2 give $A[z_1{z}_2]=B[z_1{z}_2]C$, where $C=P^{-1}\left(\begin{array}{cc}a& b\\ -b& a\end{array}\right)P$. Thus the leading blocks satisfy $A_{11}=B_{11}C$, and $C$ is similar to $\left(\begin{array}{cc}a& b\\ -b& a\end{array}\right)$. Consequently $\det (A_{11}-\mu B_{11})=\det (B_{11})\det (C-\mu I)=\det (B_{11})((a-\mu {)}^2+b^2)$ is a nonzero polynomial with roots $a\pm ib$.

In either the one-dimensional case of step 2.1 or the two-dimensional case of step 3.1, the transformed pair has a nonzero leading block determinant polynomial $g$. The transformed full pencil is regular: by [F8] choose $\mu$ with $\det (A-\mu B)\mathrm{\ne }0$; the unitary or orthogonal changes of basis preserve invertibility. By [F7], the transformed determinant at this $\mu$ is also nonzero, so the transformed full determinant polynomial is nonzero. If there is no trailing block, the transformed pencil is just its leading block and this already proves regularity. If the trailing block is nonempty, both block sizes are positive, so [F3] factors the full determinant polynomial as $g$ times the trailing determinant. A product of two nonzero complex polynomials is nonzero because their leading nonzero coefficients have nonzero product. Since $g$ and the full determinant are nonzero, the trailing determinant is nonzero, so the trailing pencil is regular.

If the trailing block is nonempty, apply the induction hypothesis to it and extend its left and right transformations by identity matrices on the leading block. If it is empty, no further transformation is needed. This produces the stated upper triangular complex form or real block upper triangular form with upper triangular second factor.

The left and right basis changes are invertible, so [F7] shows that they preserve singularity of every homogeneous pencil matrix. If there is one diagonal block, its determinant is the full determinant. With at least two blocks, split off the first diagonal block and apply [F3] repeatedly; every split has positive block sizes. The resulting product is the nonzero determinant polynomial of the regular transformed pencil, so each factor is nonzero by the leading-coefficient argument in step 4.1. Thus a homogeneous pair is a root of the full determinant exactly when it is a root of at least one diagonal block determinant. The basis changes preserve this root set, which proves the claim.