Polynomial eigenproblems and linearization

For $m\ge 2$, partition the columns of $L$ as $u=(z_1,\dots ,z_{m-1})$ and $x=z_m$, and the rows as the top block row and the lower $m-1$ block rows; write the resulting blocks as $L=\left[\begin{array}{cc}C& E\\ D& G\end{array}\right]$. The lower-left block $D(\lambda )$ is upper block-bidiagonal with $-I_n$ on its diagonal and $\lambda I_n$ on its superdiagonal. Thus $D=-(I-\lambda S)$ for the nilpotent upper block shift $S$, so $D^{-1}=-(I+\lambda S+\cdots +{\lambda }^{m-2}{S}^{m-2})$ is polynomial and $\det D=(-1{)}^{n(m-1)}$. The lower equations with zero right-hand side are $Du+Gx=0$; solving them gives $z_j={\lambda }^{m-j}x$. Substitution into the top row shows that the Schur complement is $E-C{D}^{-1}G=P(\lambda )$. To compute the determinant, swap the top and lower row groups, with sign $(-1{)}^{n^2(m-1)}$, obtaining $\left[\begin{array}{cc}D& G\\ C& E\end{array}\right]$. Left multiplication by $\left[\begin{array}{cc}I& 0\\ -C{D}^{-1}& I\end{array}\right]$ has determinant one and gives $\left[\begin{array}{cc}D& G\\ 0& P\end{array}\right]$, whose determinant is $\det D\det P$. Since $\det D=(-1{)}^{n(m-1)}$, the total sign is $(-1{)}^{n^2(m-1)+n(m-1)}=(-1{)}^{n(n+1)(m-1)}=1$, so $\det L=\det P$. For $m=1$, $L=P$ directly.

For the partition in step 1.1, left multiplication by $\left[\begin{array}{cc}I& -C{D}^{-1}\\ 0& I\end{array}\right]$ clears the top-left block and leaves $P$ in the top-right block, since $E-C{D}^{-1}G=P$. Left multiplication of the lower rows by $D^{-1}$ makes the lower-left block $I$ and the lower-right block $H:=D^{-1}G$. Right multiplication by $\left[\begin{array}{cc}I& -H\\ 0& I\end{array}\right]$ clears that lower-right block; a block-column permutation then gives $\mathrm{diag}(P,I_{(m-1)n})$. Each operation and its inverse has polynomial entries and determinant a nonzero constant, so their products are unimodular.

Put $L_h(\alpha ,\beta ):=\beta A_c-\alpha B_c$. If $\beta \mathrm{\ne }0$, then $L_h=\beta L(\alpha \mathrm{/}\beta )$, so step 1.1 gives $\det L_h={\beta }^{mn}\det P(\alpha \mathrm{/}\beta )=\det P_h(\alpha ,\beta )$. Both sides are polynomials in $(\alpha ,\beta )$. Fix any $\beta \mathrm{\ne }0$; the identity holds for every $\alpha$, so their coefficients in powers of $\alpha$ agree. Each such coefficient is a polynomial in $\beta$ and agrees for every $\beta \mathrm{\ne }0$; as univariate polynomials with infinitely many common values they are identical, so the identity holds also at $\beta =0$. For finite $\lambda$, the lower rows of $L(\lambda )z=0$ force $z_j={\lambda }^{m-j}{z}_m$; if $z\mathrm{\ne }0$ then $z_m\mathrm{\ne }0$, and the top row is $P(\lambda )z_m=0$. Conversely, for each nonzero $x$ with $P(\lambda )x=0$, the lift in [F2] is nonzero and the lower rows vanish while the top row is $P(\lambda )x$. At infinity, $L_h(1,0)=-B_c=\mathrm{diag}(A_m,I_n,\dots ,I_n)$, so its kernel consists exactly of $(x,0,\dots ,0{)}^T$ with $A_{m}x=0$.

For the reversal pencil $\mu A_c-B_c$, reorder the block columns as $(z_2,\dots ,z_m,z_1)$. Its lower equations are $z_i-\mu z_{i-1}=0$; on the first $m-1$ reordered block columns their coefficient matrix is lower block-bidiagonal with $I_n$ on its diagonal and $-\mu I_n$ on its subdiagonal, so its determinant is $1$ and its inverse is polynomial by the finite nilpotent-shift expansion. Solving these equations gives $z_i={\mu }^{i-1}{z}_1$; substitution into the top row gives ${\sum }_{j=0}^m{A}_{m-j}{\mu }^j=P_m^{\mathrm{r}\mathrm{e}\mathrm{v}}(\mu )$. The same row elimination, normalization by this polynomial inverse, column clearing, and block permutation used in step 2.1 therefore give $\mathrm{diag}(P_m^{\mathrm{r}\mathrm{e}\mathrm{v}},I_{(m-1)n})$ by unimodular polynomial matrices. For $m=1$ the reversal pencil equals $P_1^{\mathrm{r}\mathrm{e}\mathrm{v}}$ directly.

The reversal determinant identity is $\det P_m^{\mathrm{r}\mathrm{e}\mathrm{v}}(\mu )={\mu }^{mn}\det P(1\mathrm{/}\mu )$. If $d=\mathrm{deg}\det P$, write $\det P(\lambda )=c_d{\lambda }^d+\cdots +c_0$ with $c_d\mathrm{\ne }0$; then $\det P_m^{\mathrm{r}\mathrm{e}\mathrm{v}}(\mu )=c_d{\mu }^{mn-d}+\cdots +c_0{\mu }^{mn}$, whose zero order at $0$ is exactly $mn-d$. Step 3.1 shows the reversal pencil has the same zero order, and step 2.2 identifies the homogeneous companion spectrum and eigenspaces. In the permutation expansion of $\det P(\lambda )$, every product has $n$ factors of degree at most $m$; degree $mn$ can occur only by taking the ${\lambda }^m$ coefficient from each factor, so its coefficient is $\det A_m$. Thus invertibility of $A_m$ is equivalent to $d=mn$ and no infinity eigenvalue; singularity gives $d<mn$ and positive multiplicity at infinity. The geometric multiplicity is $\dim \ker A_m$ by step 2.2 and is not used to infer the zero order.

From the lower residual equations in [F2], $z_{k-1}=\lambda z_k-e_k$. Back-substitution from $x=z_m$ gives $z_j={\lambda }^{m-j}x-{\sum }_{k=j+1}^m{\lambda }^{k-j-1}{e}_k$ for $1\le j<m$; when $j=m$ the same formula has an empty sum.

Substitute these expressions into the top row from [F2]. The terms containing $x$ sum to ${\sum }_{j=0}^m{A}_j{\lambda }^{j}x=P(\lambda )x$. For fixed $e_k$, its coefficient is the negative of ${\sum }_{j=m-k+1}^m{A}_j{\lambda }^{j-m+k-1}$: the $z_1$ term contributes $-(\lambda A_m+A_{m-1}){\lambda }^{k-2}{e}_k$, and each $z_j$ term for $2\le j<k$ contributes $-A_{m-j}{\lambda }^{k-j-1}{e}_k$. Thus $e_1=P(\lambda )x-{\sum }_{k=2}^m{Q}_k(\lambda )e_k$, which is the claimed identity.

We first derive the finite-dimensional Euclidean estimates used here. For $u,v\in {\mathbb{C}}^d$ with $v\mathrm{\ne }0$, set $c:=⟨u,v⟩\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$. Direct expansion gives $\mathrm{\parallel }u-cv{\mathrm{\parallel }}_2^2=\mathrm{\parallel }u{\mathrm{\parallel }}_2^2-\mathrm{\mid }⟨u,v⟩{\mathrm{\mid }}^2\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2\ge 0$, hence $\mathrm{\mid }⟨u,v⟩\mathrm{\mid }\le \mathrm{\parallel }u{\mathrm{\parallel }}_2\mathrm{\parallel }v{\mathrm{\parallel }}_2$; if $v=0$ the inequality is immediate. Since $\mathrm{\parallel }u+v{\mathrm{\parallel }}_2^2=\mathrm{\parallel }u{\mathrm{\parallel }}_2^2+\mathrm{\parallel }v{\mathrm{\parallel }}_2^2+2\mathrm{Re}⟨u,v⟩\le (\mathrm{\parallel }u{\mathrm{\parallel }}_2+\mathrm{\parallel }v{\mathrm{\parallel }}_2{)}^2$, taking nonnegative square roots gives $\mathrm{\parallel }u+v{\mathrm{\parallel }}_2\le \mathrm{\parallel }u{\mathrm{\parallel }}_2+\mathrm{\parallel }v{\mathrm{\parallel }}_2$. For any matrix $M$ and vector $v$, apply the derived inner-product bound to each row of $M$ and $\bar{v}$ to obtain $\mathrm{\mid }(Mv{)}_r{\mathrm{\mid }}^2\le ({\sum }_s\mathrm{\mid }{M}_{rs}{\mathrm{\mid }}^2)\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$; summing over rows gives $\mathrm{\parallel }Mv{\mathrm{\parallel }}_2\le \mathrm{\parallel }M{\mathrm{\parallel }}_F\mathrm{\parallel }v{\mathrm{\parallel }}_2$. Now put $y=e_1+{\sum }_{k=2}^m{Q}_k{e}_k=P(\lambda )x$. Repeated use of the derived triangle inequality gives $\mathrm{\parallel }y{\mathrm{\parallel }}_2\le \mathrm{\parallel }{e}_1{\mathrm{\parallel }}_2+{\sum }_{k=2}^m\mathrm{\parallel }{Q}_k{e}_k{\mathrm{\parallel }}_2$. Applying the rowwise matrix estimate to each $Q_k$ gives the claimed bound. For the companion lift, each lower row vanishes by construction and the top row is $P(\lambda )x$.

To see why no uniform unscaled transfer factor follows, take the fixed scalar polynomial $P(\lambda )={\lambda }^2+1$. For any $t>0$, set $x=t\mathrm{/}(t^2+1)$, $z_2=x$, and $z_1=tx-1$. Direct substitution into its first companion pencil gives $e_1=t{z}_1+z_2=0$ and $e_2=-z_1+t{z}_2=1$, while $P(t)x=t$. Hence the block-pencil residual norm is $1$ and the polynomial residual is $t$, which is unbounded as $t\to \mathrm{\infty }$. Any error or conditioning comparison must retain the displayed coefficient and parameter scaling.

Since $[\alpha :\beta ]$ is nonzero, either $\alpha \mathrm{\ne }0$ or $\beta \mathrm{\ne }0$. If $\beta \mathrm{\ne }0$, the $j=0$ term in $S$ is ${\omega }_0^2\mathrm{\mid }\beta {\mathrm{\mid }}^{2m}>0$; if $\beta =0$, then $\alpha \mathrm{\ne }0$ and the $j=m$ term is ${\omega }_m^2\mathrm{\mid }\alpha {\mathrm{\mid }}^{2m}>0$. Thus $S>0$ and the displayed denominator is defined because also $x\mathrm{\ne }0$.

We use only finite-dimensional estimates, derived as follows. For $u,v\in {\mathbb{C}}^d$ with $v\mathrm{\ne }0$, put $c:=⟨u,v⟩\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$. Direct expansion gives $\mathrm{\parallel }u-cv{\mathrm{\parallel }}_2^2=\mathrm{\parallel }u{\mathrm{\parallel }}_2^2-\mathrm{\mid }⟨u,v⟩{\mathrm{\mid }}^2\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2\ge 0$, so $\mathrm{\mid }⟨u,v⟩{\mathrm{\mid }}^2\le \mathrm{\parallel }u{\mathrm{\parallel }}_2^2\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$; if $v=0$ the inequality is immediate. Since $\mathrm{\parallel }u+v{\mathrm{\parallel }}_2^2=\mathrm{\parallel }u{\mathrm{\parallel }}_2^2+\mathrm{\parallel }v{\mathrm{\parallel }}_2^2+2\mathrm{Re}⟨u,v⟩\le (\mathrm{\parallel }u{\mathrm{\parallel }}_2+\mathrm{\parallel }v{\mathrm{\parallel }}_2{)}^2$, taking nonnegative square roots gives $\mathrm{\parallel }u+v{\mathrm{\parallel }}_2\le \mathrm{\parallel }u{\mathrm{\parallel }}_2+\mathrm{\parallel }v{\mathrm{\parallel }}_2$. Applying the inner-product bound to each row of any matrix $M$ and $\bar{v}$ and summing gives $\mathrm{\parallel }Mv{\mathrm{\parallel }}_2\le \mathrm{\parallel }M{\mathrm{\parallel }}_F\mathrm{\parallel }v{\mathrm{\parallel }}_2$. For real lists $a,b\in {\mathbb{R}}^d$ with $b\mathrm{\ne }0$, set $t=({\sum }_j{a}_j{b}_j)\mathrm{/}({\sum }_j{b}_j^2)$; direct expansion gives ${\sum }_j(a_j-t{b}_j{)}^2={\sum }_j{a}_j^2-({\sum }_j{a}_j{b}_j{)}^2\mathrm{/}({\sum }_j{b}_j^2)\ge 0$, hence $({\sum }_j{a}_j{b}_j{)}^2\le ({\sum }_j{a}_j^2)({\sum }_j{b}_j^2)$, and the same inequality is immediate if $b=0$. For any feasible perturbations, $r=-{\sum }_j\mathrm{\Delta }{A}_j{c}_{j}x$, where $c_j={\alpha }^j{\beta }^{m-j}$. The derived matrix estimate, $\mathrm{\parallel }{c}_{j}w{\mathrm{\parallel }}_2=\mathrm{\mid }{c}_j\mathrm{\mid }\mathrm{\parallel }w{\mathrm{\parallel }}_2$, and repeated triangle inequality give $\mathrm{\parallel }r{\mathrm{\parallel }}_2\le \mathrm{\parallel }x{\mathrm{\parallel }}_2{\sum }_j\mathrm{\mid }{c}_j\mathrm{\mid }\mathrm{\parallel }\mathrm{\Delta }{A}_j{\mathrm{\parallel }}_F$. Apply the derived real-list inequality to $a_j={\omega }_j\mathrm{\mid }{c}_j\mathrm{\mid }$ and $b_j=\mathrm{\parallel }\mathrm{\Delta }{A}_j{\mathrm{\parallel }}_F\mathrm{/}{\omega }_j$ to obtain $\mathrm{\parallel }r{\mathrm{\parallel }}_2\le \mathrm{\parallel }x{\mathrm{\parallel }}_2\sqrt{{\sum }_j{\omega }_j^2\mathrm{\mid }{c}_j{\mathrm{\mid }}^2}{\left({\sum }_j\frac{\mathrm{\parallel }\mathrm{\Delta }{A}_j{\mathrm{\parallel }}_F^2}{{\omega }_j^2}\right)}^{1\mathrm{/}2}=\mathrm{\parallel }x{\mathrm{\parallel }}_2\sqrt{S}{\left({\sum }_j\frac{\mathrm{\parallel }\mathrm{\Delta }{A}_j{\mathrm{\parallel }}_F^2}{{\omega }_j^2}\right)}^{1\mathrm{/}2}$. Hence every feasible cost is at least $\mathrm{\parallel }r{\mathrm{\parallel }}_2\mathrm{/}(\mathrm{\parallel }x{\mathrm{\parallel }}_2\sqrt{S})$.

Define ${\widehat{\mathrm{\Delta }A}}_j:=-\frac{{\omega }_j^2\overline{{\alpha }^j{\beta }^{m-j}}}{\mathrm{\parallel }x{\mathrm{\parallel }}_2^{2}S}r{x}^{\ast }$. Then ${\widehat{\mathrm{\Delta }A}}_j{c}_{j}x=-{\omega }_j^2\mathrm{\mid }{c}_j{\mathrm{\mid }}^{2}r\mathrm{/}S$, because $x^{\ast }x=\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$. Summing over $j$ yields ${\sum }_j{\widehat{\mathrm{\Delta }A}}_j{c}_{j}x=-r$, so these perturbations are feasible.

Directly from the entries of the rank-one matrix, $\mathrm{\parallel }r{x}^{\ast }{\mathrm{\parallel }}_F^2={\sum }_{a,b}\mathrm{\mid }{r}_a\overline{x_b}{\mathrm{\mid }}^2=\mathrm{\parallel }r{\mathrm{\parallel }}_2^2\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$. Therefore the cost of the feasible perturbations in step 2.2 is ${\sum }_j\mathrm{\parallel }{\widehat{\mathrm{\Delta }A}}_j{\mathrm{\parallel }}_F^2\mathrm{/}{\omega }_j^2=\mathrm{\parallel }r{\mathrm{\parallel }}_2^2\mathrm{/}(\mathrm{\parallel }x{\mathrm{\parallel }}_2^{2}S)$. Taking square roots and combining with the lower bound in step 2.1 proves attainment and the formula. Substituting $[\lambda :1]$ leaves the terms ${\omega }_j^2\mathrm{\mid }\lambda {\mathrm{\mid }}^{2j}$; substituting $[1:0]$ leaves only ${\omega }_m^2$ and $P_h(1,0)=A_m$. When $\alpha \mathrm{\ne }0$, set $\mu =\beta \mathrm{/}\alpha$ and reindex with $k=m-j$; then $S=\mathrm{\mid }\alpha {\mathrm{\mid }}^{2m}{\sum }_{k=0}^m{\omega }_{m-k}^2\mathrm{\mid }\mu {\mathrm{\mid }}^{2k}$ and $P_h(\alpha ,\beta )={\alpha }^m{P}_m^{\mathrm{r}\mathrm{e}\mathrm{v}}(\mu )$, so the homogeneous formula is precisely the reversed-polynomial formula with weights ${\tilde{\omega }}_k={\omega }_{m-k}$. The zero-residual case is included, with minimizer $\mathrm{\Delta }{A}_j=0$.

If $\lambda \in \mathrm{\Omega }$, then $q(\lambda )\mathrm{\ne }0$ by [F1]. Multiplying $R(\lambda )x=0$ by the nonzero scalar $q(\lambda )$ gives $N(\lambda )x=0$. Conversely, if $N(\lambda )x=0$, division by the same nonzero scalar gives $R(\lambda )x=0$. This proves the stated equivalence exactly on $\mathrm{\Omega }$.

If $\lambda \in \mathcal{P}$, then at least one entry of $R$ has a pole by the reduced common-denominator definition in [F1], so $R(\lambda )$ is undefined and $(\lambda ,x)$ is outside the rational eigenproblem's domain. A singular value of $N(\lambda )$ cannot change that domain condition; hence every cleared root at such a point must be rejected.