The GUPTRI Form of a Regularized Problem.

The deflations made in the staircase algorithm result in an exact GUPTRI form of a nearby matrix pencil $A + \delta A - \lambda (B + \delta B)$:

$$P^{\ast}(A + \delta A - \lambda (B + \delta B)) Q = \bmat{cc... ...g} - \lambda B_{reg} & * \\ 0 & 0 & A_l - \lambda B_l \emat .$$

If all range/null space separations in the GUPTRI algorithm are well defined with respect to the deflation tolerance parameters $\epsilon$ and gap, then $\Vert(\delta A, \delta B)\Vert _F$ $=O(\epsilon \Vert(A,B)\Vert _F)$. The nearby problem represents a regularized problem that has a stable Kronecker structure with respect to the deflation criteria of the algorithm.