Finite-budget stable block reordering has exact adjacent-swap correctness and status

For an ordinary complex scalar block the diagonal entry itself classifies the root, while a real $2\times 2$ block with negative discriminant has conjugate roots with real part $\mathrm{tr}(T_b)\mathrm{/}2$. For a generalized scalar pair $[s:t]$, a finite root is $s\mathrm{/}t$, so $\mathrm{\mid }s\mathrm{\mid }<\mathrm{\mid }t\mathrm{\mid }$ is exactly the disk predicate and $t=0$, $s\mathrm{\ne }0$ is infinity and complementary. For a real generalized $2\times 2$ pair with finite nonreal roots, the root product is $\det (S_b)\mathrm{/}\det (T_b)=\mathrm{\mid }\lambda {\mathrm{\mid }}^2$. Thus the procedure labels whole blocks exactly and detects equality at the selector boundary.

For ordinary adjacent diagonal blocks $A,B$, column-wise expansion gives $\mathrm{vec}(AR-RB)=(I_q\otimes A-B^T\otimes I_p)\mathrm{vec}R$. The selected and complementary spectra are disjoint, so [F2] applied to $X\mapsto AX+X(-B)$ makes this square coefficient operator invertible, giving a unique local solve.

For generalized adjacent pairs $(A,D)$ and $(B,E)$, their homogeneous root sets are disjoint and both pairs are regular. The polynomials $\det (A-\zeta D)$ and $\det (B-\zeta E)$ are nonzero of degrees at most $p,q$; among $p+q+1$ distinct real integers, [F3] gives a $\zeta$ for which $A_0=A-\zeta D$ and $B_0=B-\zeta E$ have nonzero determinants, hence are invertible by [F4]. Each homogeneous root $[\alpha :\beta ]$ maps injectively to $\mu =\beta \mathrm{/}(\alpha -\zeta \beta )$, an eigenvalue of $D{A}_0^{-1}$ because $D-\mu A_0=-(\beta A-\alpha D)\mathrm{/}(\alpha -\zeta \beta )$; this also maps infinity to zero, and maps the second pair to $E{B}_0^{-1}$, so the ordinary spectra remain disjoint. If $AR-LB=0$ and $DR-LE=0$, then $A_{0}R=L{B}_0$, hence $R=A_0^{-1}L{B}_0$ and $D{A}_0^{-1}L=LE{B}_0^{-1}$; [F2] forces $L=0$, then $R=0$. The square generalized Sylvester system has zero kernel, so [F5] makes it invertible; for real blocks its real coefficient matrix has the same nonzero determinant as its complexification.

For ordinary input, $Q_0^{\ast }A{Q}_0=T_0+R_0$ and $Q_{\mathrm{n}\mathrm{e}\mathrm{w}}=Q_{0}V$ imply $Q_{\mathrm{n}\mathrm{e}\mathrm{w}}^{\ast }A{Q}_{\mathrm{n}\mathrm{e}\mathrm{w}}=V^{\ast }{T}_{0}V+V^{\ast }{R}_{0}V$. For QZ, substituting $Q_{\mathrm{n}\mathrm{e}\mathrm{w}}=Q_{0}U$ and $Z_{\mathrm{n}\mathrm{e}\mathrm{w}}=Z_{0}V$ into the two input relations gives residuals $U^{\ast }{R}_{A}V$ and $U^{\ast }{R}_{B}V$; [F9] preserves their Frobenius norms. These unstructured residual relations assert no structured pencil perturbation.

Each exact Gaussian-elimination pivot is nonzero; row and column permutations and row eliminations preserve the solution set. A zero remaining block before all pivots would contradict the invertibility in steps 1.2–1.3. Back-substitution gives the unique exact solution and applying the same operations to the coordinate vectors gives the inverse. In the approximate branch, $\mathrm{\parallel }I-YH{\mathrm{\parallel }}_2\le \theta <1$ and [F10] make $YH$ invertible; finite-dimensional square rank and [F11] give $\mathrm{\parallel }{H}^{-1}{\mathrm{\parallel }}_2=\mathrm{\parallel }(YH{)}^{-1}Y{\mathrm{\parallel }}_2\le \mathrm{\parallel }Y{\mathrm{\parallel }}_2\mathrm{/}(1-\theta )$. Thus each committed swap has an exact solve and valid recorded inverse bound.

Every complementary-selected inversion can be removed by swapping an adjacent complementary-selected pair, which decreases the inversion count by one and leaves all other relative block orders unchanged. Thus $I\le b(b-1)\mathrm{/}2$ and, after $I$ successful swaps, no inversion remains. The finite scans, local systems, and exact return branches in [F1] give a finite declared status; exhausted $K$ or $W$ returns its budget status.

The columns of $[R;I_q]$ and $[L;I_q]$ are independent because their last $q$ rows form $I_q$. Applying [F6] gives orthonormal graph columns; if their span is proper, some standard coordinate vector lies outside it, so the finite scan completes each required local basis.

In the ordinary case $AR-RB=-C$ gives $\left[\begin{array}{cc}A& C\\ 0& B\end{array}\right]\left[\begin{array}{c}R\\ I_q\end{array}\right]=\left[\begin{array}{c}R\\ I_q\end{array}\right]B$. Writing $[R;I_q]=Z_1{R}_v$ with $R_v$ invertible shows the leading transformed block is similar to $B$. The quotient map $\pi (x,y)=x-Ry$ has kernel this graph and satisfies $\pi T_{JJ}=A\pi$, so its restriction to the orthogonal complement is an isomorphism onto the quotient and the trailing block is similar to $A$. Embedded local unitary updates preserve the surrounding block triangular zeros because rows below the pair vanish in its columns and columns before the pair vanish in its rows; the solved equations make the new lower-left block zero. Similarity preserves the characteristic polynomial and negative discriminant of a real $2\times 2$ block, so whole conjugate pairs remain intact.

In the generalized case the two local equations give $S_{JJ}[R;I_q]=[L;I_q]B$ and $T_{JJ}[R;I_q]=[L;I_q]E$. Writing the graph matrices as $Z_1{R}_v$ and $Q_1{R}_w$ gives a zero lower-left block and a leading pair strictly equivalent to $(B,E)$. The full homogeneous determinant changes only by nonzero factors under exact left/right transforms [F7] and factors across diagonal pairs [F8]; cancelling the nonzero leading polynomial shows that the trailing pair has exactly the old first pair's homogeneous roots with multiplicity, including infinity and regularity. A real $2\times 2$ pair with a finite nonreal conjugate root pair has nonsingular $T$ block, since otherwise its determinant polynomial has degree at most one. The prescribed QR restores triangularity of this block; applying the same left factor to both QZ arrays and to $Q$ changes the homogeneous determinant only by a nonzero factor and preserves the lower-left zero. An infinite scalar pair keeps its zero second coordinate and is never divided by it. The left update changes $Q$, while the right update changes $Z$, so the selected right deflating basis comes from $Z$.

The initial structure scan costs $O(d^2)$ scalar/evaluator units. Each local solve has order at most eight, each basis completion has bounded local dimension, and each panel update touches $O(d)$ entries; therefore $k$ attempts cost $O(d^2+kd)$. On success $k=I\le b(b-1)\mathrm{/}2\le d(d-1)\mathrm{/}2$, giving $O(d^3)$ worst-case swap work. Evaluating $L_0$ bounded-support input factors on $r$ columns costs $O(L_{0}dr+Idr)$; dense residual multiplication costs its separate $O(d^3)$. These counts do not bound algebraic bit cost or evaluator implementation cost.

Under the stated sufficient conditions, including enough $W$ for every scan through the final ordered return, steps 2.2 and 4.1–4.3 show that all selected blocks move before every complementary block without splitting real pairs; the first $r$ factor columns therefore span the selected invariant subspace or right deflating subspace of the represented computed form. Step 1.4 transports only the original unstructured residual certificate. Algorithm [F1] returns explicitly on boundary, separation, arithmetic, range, form, and budget failures; none of those statuses proves nonexistence of a stabilizing Riccati solution or supplies structured backward error.