Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 21 results · all verified · 12 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 9 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Numerical algebraic Riccati equations and stabilizing branches

1 · Prerequisites

2 · Summary

Objective

This page fixes the real and complex CARE/DARE conventions, proves the closed-region PBH equivalences and stabilizing value solutions, and relates those solutions to Hamiltonian and symplectic-pencil stable graphs. It records finite-budget Schur/QZ candidate extraction with an exact finite stable-block reordering routine, local residual-and-margin certificates, exact and safeguarded Newton-Kleinman iteration, and discrete structure-preserving doubling. All numerical branches require actual Riccati residuals, symmetry checks, DARE positive-definiteness checks, and separate closed-loop stability evidence.

The underlying algebra permits singular $A$ and uses homogeneous pencil coordinates, so infinite generalized eigenvalues are retained without forming $A^{- 1}$ . A small residual alone does not identify the stabilizing branch. Unstructured Schur/QZ backward error is not interpreted as a nearby structured Hamiltonian or symplectic pencil.

Conventions and proof map

The state, input, and output matrices have sizes $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , $C \in F^{p \times n}$ over $F \in {R, C}$ ; $Q = C^{*} C ⪰ 0$ , $R = R^{*} ≻ 0$ , and $G = B R^{- 1} B^{*}$ . The CARE is $A^{*} X + X A - X G X + Q = 0$ . The DARE is $X = Q + A^{*} X A - A^{*} X B (R + B^{*} X B)^{- 1} B^{*} X A .$ The feedback and closed-loop conventions are fixed in Standard CARE and DARE data, equations, and conventions.

The CARE proof constructs finite-horizon value matrices, passes to a positive-semidefinite limit, proves transversality using detectability, and establishes uniqueness. The DARE proof uses finite-horizon dynamic programming and a detectability convolution estimate; it never requires $A^{- 1}$ . The Hamiltonian and homogeneous-pencil graph identities follow by block multiplication after the value theorems. Candidate extraction runs the finite stable-block reordering procedure after the Schur/QZ reduction; boundary, separation, swap-budget, work-budget, and graph-conditioning failures remain explicit statuses.

Numerical scope and limits

CARE and DARE local residual balls use their own derivative operators, inverse bounds, and separate stability margins. DARE stable-deflating-subspace sensitivity uses generalized Sylvester separation, paired-graph contraction, leading and reciprocal-trailing Stein margins, and a normalized graph-chart estimate. Exact Newton-Kleinman convergence is conditional on a supplied stabilizing initial feedback and exact Lyapunov solves. Inexact updates are accepted only after distinct residual, descent, and stability checks. SDA is an exact-arithmetic structure theorem; finite precision reports symmetry defects and recomputes the DARE residual and positivity evidence after any symmetrization.

Stable-block reordering acts exactly on the returned computed Schur/QZ arrays and preserves any existing unstructured reduction residual. An ordered return certifies the selected subspace of that represented form; Riccati acceptance still requires equation-level residual, symmetry, positivity where applicable, and closed-loop stability certificates. QZ backward error alone does not imply structured pencil or DARE subspace accuracy.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Stabilizability and detectability for continuous and discrete linear systems

Definition

Let $F \in {R, C}$ , $n, m, p \geq 1$ , $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , and $C \in F^{p \times n}$ . A matrix is Hurwitz when every complex eigenvalue has strictly negative real part, as in Hurwitz matrices and the continuous Lyapunov equation. It is Schur stable when every complex eigenvalue has modulus strictly less than one.

The pair $(A, B)$ is continuously stabilizable if some $K \in F^{m \times n}$ makes $A - B K$ Hurwitz. The pair $(A, C)$ is continuously detectable if some $L \in F^{n \times p}$ makes $A - L C$ Hurwitz.

The pair $(A, B)$ is discretely stabilizable if some $K \in F^{m \times n}$ makes $A - B K$ Schur stable. The pair $(A, C)$ is discretely detectable if some $L \in F^{n \times p}$ makes $A - L C$ Schur stable. These are exact existential properties of the given finite matrices. A residual size or an approximate spectral estimate does not itself establish any of them.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Reachable block decomposition and same-field state-feedback pole placement

Statement

Let $F \in {R, C}$ , let $n, m \geq 0$ , and let $A \in F^{n \times n}$ and $B \in F^{n \times m}$ . The real case is viewed over $C$ when a complex spectral parameter or rank is used. Define $R = {span}_{F} {A^{j} B e_{ℓ} : 0 \leq j < n, 1 \leq ℓ \leq m}, r = \dim_{F} R,$ where a span of an empty family is ${0}$ . Then there is an invertible $P \in F^{n \times n}$ such that $P^{- 1} A P = [\begin{array}{cc} A_{r} & D \\ 0 & A_{u} \end{array}], P^{- 1} B = [\begin{array}{c} B_{r} \\ 0 \end{array}] .$ The pair $(A_{r}, B_{r})$ is reachable on $F^{r}$ in the displayed algebraic sense, and empty blocks are permitted. For every $λ \in C$ , ${rank}_{C} [λ I - A B] = n ⟺ λ \notin σ_{C} (A_{u}^{C}),$ where $A_{u}^{C}$ is the complexification of $A_{u}$ when $F = R$ and is $A_{u}$ itself when $F = C$ .

If $r = n$ , then for every prescribed list $μ_{1}, \dots, μ_{n} \in F$ there is a gain $K \in F^{m \times n}$ satisfying $\det (z I - A + B K) = \prod_{j = 1}^{n} (z - μ_{j}) .$ Thus a real reachable pair can be assigned any real pole list, including repetitions, and a complex reachable pair any complex list. The pole-placement claim does not assert arbitrary nonreal conjugate-pair placement for a real pair.

Facts & Assumptions

Given: Finite matrices $A, B$ over $F$ , with the reachable space and rank convention stated above.

[F1]

Linear combination of a finite list, and the span $span (S)$ as the smallest linear subspace containing $S$ and $span (S)$ is exactly the set of linear combinations of finite lists of elements of $S$ , and $span (\emptyset) = {0_{V}}$ : the span is precisely the set of finite linear combinations and is the smallest subspace containing the listed vectors.

[F2]

Rank-nullity: $\dim_{F} V = nullity T + rank T$ : for a map with finite-dimensional domain, dimension equals rank plus nullity.

[F3]

Row rank equals column rank, and both equal the number of pivots: every finite matrix over a field has equal row rank and column rank.

[F4]

The characteristic polynomial of a block upper- or lower-triangular matrix is the product of the characteristic polynomials of its diagonal blocks: the characteristic polynomial of a block-triangular matrix is the product of those of its diagonal blocks.

[F5]

For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ and Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism: for a complex finite-dimensional endomorphism, its spectrum is the set of roots of $\det (λ I - M)$ in $C$ .

Proof

1.1givenF1algebra

For each integer $k \geq 0$ , put $R_{k} = span {A^{j} B e_{ℓ} : 0 \leq j < k, 1 \leq ℓ \leq m}$ . Then $R_{k + 1} = R_{k} + A R_{k} + im B$ . If $R_{k + 1} = R_{k}$ , then $im B \subseteq R_{k}$ and $A R_{k} \subseteq R_{k}$ , so every later space equals $R_{k}$ . Otherwise each inclusion is strict; if no equality occurs before $R_{n}$ , its dimension has increased at least $n$ times from zero, hence $R_{n} = F^{n}$ . Therefore $R = R_{n}$ is the smallest $A$ -invariant subspace containing $im B$ .

1.2F2F3algebra

Let $(E, H)$ be reachable on $F^{d}$ . If $[λ I - E H]$ had rank less than $d$ over $C$ , row-rank equality and rank-nullity applied to its adjoint would give a nonzero $y \in C^{d}$ with $y^{*} (λ I - E) = 0$ and $y^{*} H = 0$ . Induction then gives $y^{*} E^{j} H = λ^{j} y^{*} H = 0$ for every $j < d$ , contradicting reachability; for real data the real reachable columns complexify to span $C^{d}$ . Thus the horizontal rank is $d$ for every complex $λ$ .

2.1givenF1step 1.1constructalgebra

Scan the finite columns of $B, A B, \dots, A^{n - 1} B$ , retaining a column exactly when it is outside the span of those retained; then scan the standard coordinate vectors until the retained list is a basis of $F^{n}$ . This gives a basis matrix $P$ whose first $r$ columns span $R$ . Invariance and $im B \subseteq R$ give $P^{- 1} A P = [\begin{array}{cc} A_{r} & D \\ 0 & A_{u} \end{array}]$ and $P^{- 1} B = [\begin{array}{c} B_{r} \\ 0 \end{array}]$ ; the first $r$ coordinates of the columns $A^{j} B$ are $A_{r}^{j} B_{r}$ and span $F^{r}$ . Applying the stabilization argument of step 1.1 in dimension $r$ shows that the first $r$ powers already span $F^{r}$ , so $(A_{r}, B_{r})$ is reachable, including $r = 0$ . For real data, complexifying the real span gives the complex span because each complex coefficient splits into real and imaginary parts. No arbitrary basis choice is used.

2.2givenstep 1.1algebra

For any gain $J$ , a subspace $W$ contains $im H$ and is $E$ -invariant exactly when it contains $im H$ and is $(E - H J)$ -invariant: $H J W \subseteq im H \subseteq W$ , and the converse follows from $E = (E - H J) + H J$ . By step 1.1 the smallest invariant subspace containing $im H$ , hence reachability, is feedback-invariant.

3.1F5step 2.1step 1.2algebra

In the block coordinates of step 2.1, $[λ I - A B]$ has block form $[\begin{array}{ccc} λ I - A_{r} & - D & B_{r} \\ 0 & λ I - A_{u} & 0 \end{array}]$ . A left annihilator $(a, b)$ must satisfy $a [λ I - A_{r} B_{r}] = 0$ , so step 1.2 forces $a = 0$ ; a nonzero remaining annihilator exists exactly when $\det (λ I - A_{u}^{C}) = 0$ , which by [F5] is exactly $λ \in σ_{C} (A_{u}^{C})$ . Invertible coordinate changes preserve rank, proving the claimed equivalence in the original coordinates.

3.2F2step 1.2step 2.2choosealgebra

Prove pole placement by induction on $d$ . For $d = 0$ the empty gain gives determinant $1$ . For $d > 0$ , reachability implies $rank H > 0$ . Fix $μ_{1} \in F$ . By step 1.2, $[E - μ_{1} I - H]$ has full row rank over $C$ ; for real data a nonzero full-size minor has real nonzero determinant, so it also has full row rank over $F$ . Its kernel has dimension $m$ by [F2], whereas kernel vectors with first component zero have dimension $m - rank H < m$ . Choose a kernel vector $(v, u)$ with $v \neq 0$ ; it satisfies $(E - μ_{1} I) v = H u$ . Choose $v_{i} \neq 0$ and define $J_{0} x = u x_{i} / v_{i}$ , so $(E - H J_{0}) v = μ_{1} v$ .

4.1F4step 1.1step 2.2step 3.2inductionalgebra∎

Let $π : F^{d} \to F^{d} / F v$ be the quotient map, ${\overset{ˉ}{E}}_{0} π = π (E - H J_{0})$ , and $\overset{ˉ}{H} = π H$ . The quotient pair is reachable because the spanning columns of $(E - H J_{0}, H)$ project onto the quotient by step 2.2; the stabilization argument of step 1.1 in dimension $d - 1$ shows that its first $d - 1$ powers suffice. To obtain quotient coordinates over $F$ , begin with $v$ and append standard coordinate vectors whenever they increase its span; the resulting finite basis has $d - 1$ remaining vectors whose cosets form a basis of $F^{d} / F v$ . Thus the induction applies over the original field, also when $d = 1$ and the quotient is zero. By induction a quotient gain $\overset{ˉ}{J}$ places $μ_{2}, \dots, μ_{d}$ ; lift it as $J_{1} = \overset{ˉ}{J} π$ and set $J = J_{0} + J_{1}$ . Since $J_{1} v = 0$ , the closed loop retains eigenvalue $μ_{1}$ on $F v$ and induces the assigned quotient characteristic polynomial. The block-triangular characteristic identity [F4] gives $\det (z I - E + H J) = \prod_{j = 1}^{d} (z - μ_{j})$ , including repeated poles and poles already in $σ (E)$ ; no inverse of $E$ or $E - μ I$ is used.

AlgorithmAlgorithm: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Finite-budget stable block reordering for Schur and QZ forms

Definition

Inputs are an order $d \geq 0$ real or complex Schur matrix $T$ , or a regular real or complex generalized Schur pair $(S, T)$ , with the declared diagonal block partition. Complex Schur and QZ forms have scalar blocks; real Schur forms have scalar blocks or real $2 \times 2$ blocks; real generalized Schur forms have real $1 \times 1$ or $2 \times 2$ blocks. Each generalized diagonal block pair must be regular. Optional accumulated factors are exact unitary/orthogonal products; if omitted they are identity. Other inputs are a CARE selector (strict left half-plane) or DARE selector (strict unit disk), a required integer selected dimension $0 \leq r \leq d$ , nonnegative integer budgets $K$ and $W$ , a positive local separation threshold $η$ , and either an exact arithmetic controller or a bounded outward evaluator.

Use the CARE selector with an ordinary Schur form and the DARE selector with a generalized Schur form; an unmatched form-selector combination returns invalid-form.

Before any charged operation, initialize attempts, accepted swaps and primitive/evaluator counts to zero, diagnostic lists to empty, and every uncomputed diagnostic to unavailable. In particular, the actual selected dimension, block labels, boundary and separation predicates, and initial inversion count remain unavailable until their respective scans or tests finish; the requested dimension $r$ is always retained separately. Report only completed tests and certificates, together with the last committed arrays and factors, on an early exit. Unavailable predicates assert neither truth nor falsity.

The entries of the input arrays are treated as their exact represented real or complex values. All local transformed arrays and accumulated factors are retained exactly as finite products; a rounded dense copy is only a separately evaluated diagnostic. Before each scalar primitive or outward evaluation, return work-budget-exhausted if no units of $W$ remain; otherwise consume one unit before requesting the operation. Charge validation, label and inversion-count scans, local construction, and the final ordering scan to this same budget. For rational or dyadic arrays, the exact core uses rational arithmetic and positive square roots, with exact real-algebraic sign comparisons where needed. Exact decisions on arbitrary real inputs are an exact-real arithmetic model, not a bit-computability claim. The bounded-evaluator branch returns arithmetic-inconclusive whenever a needed zero, sign, division, or normalization remains unresolved.

Validate dimensions, the declared block pattern, and regularity of each generalized diagonal pair in one finite scan. For ordinary scalar blocks over either field classify $t_{i i}$ by $Re t_{i i} < 0$ or $> 0$ for CARE; for real $2 \times 2$ blocks first verify negative discriminant and then classify by trace less than or greater than zero. For generalized scalar blocks over either field $[s_{i i} : t_{i i}]$ , verify the pair is nonzero and classify by $∣ s_{i i} ∣ < ∣ t_{i i} ∣$ or $∣ s_{i i} ∣ > ∣ t_{i i} ∣$ for DARE; thus $t_{i i} = 0$ , $s_{i i} \neq 0$ is complementary and represents infinity without division. For a real generalized $2 \times 2$ block, verify $\det (T_{b}) \neq 0$ and that $\det (S_{b} - λ T_{b})$ has negative discriminant; its conjugate roots have common squared modulus $\det (S_{b}) / \det (T_{b})$ , so classify by strict comparison of this ratio with one, cross-multiplying with the certified sign of $\det (T_{b})$ . Exact equality with the selected boundary returns boundary-spectrum. A bounded enclosure touching the boundary returns separation-inconclusive. Require that the selected block sizes sum to $r$ , or return dimension-mismatch. Invalid patterns or singular local homogeneous pairs return invalid-form. Compute the initial inversion count once by scanning all ordered block pairs after classification.
Give every whole block its selected or complementary label. Locate the leftmost adjacent complementary-selected inversion. If none exists, return ordered with the current exact arrays and accumulated factors. If an inversion exists but $K$ swap attempts have already been made, return swap-budget-exhausted. Otherwise consume one attempt before starting its local construction. Never split a real conjugate pair.
Let $p, q \in {1, 2}$ be the two adjacent block sizes (over $C$ , $p = q = 1$ ), with local blocks $T_{J J} = [\begin{array}{cc} A & C \\ 0 & B \end{array}]$ for ordinary Schur form, or $S_{J J} = [\begin{array}{cc} A & C \\ 0 & B \end{array}], T_{J J} = [\begin{array}{cc} D & F \\ 0 & E \end{array}]$ for QZ form. With column-vectorization, form the local coefficient system $H = I_{q} \otimes A - B^{T} \otimes I_{p}, h = - vec (C)$ for ordinary Schur, with unknown $vec (R)$ , and $H = [\begin{array}{cc} I_{q} \otimes A & - B^{T} \otimes I_{p} \\ I_{q} \otimes D & - E^{T} \otimes I_{p} \end{array}], h = - [\begin{array}{c} vec (C) \\ vec (F) \end{array}]$ for QZ, with unknown $[vec (R); vec (L)]$ . The transpose in $B^{T}$ and $E^{T}$ is intentional, also over $C$ . Solve $H x = h$ and $H Y = I$ by finite Gaussian elimination with complete pivoting: at each stage scan the finite remaining submatrix, choose an entry of largest certified modulus with lexicographic ties, swap rows and columns, eliminate, and back-substitute while undoing column permutations. An exact all-zero remaining submatrix returns swap-singular. An unresolved pivot or range failure returns separation-inconclusive or range-failure. Verify $H x = h$ and $H Y = I$ exactly, or verify a usable approximate-inverse certificate $∥ I - Y H ∥_{2} \leq θ < 1$ and still solve $H x = h$ exactly. In the latter case it gives $∥ H^{- 1} ∥_{2} \leq ∥ Y ∥_{2} / (1 - θ)$ . In the exact-inverse branch take $β = ∥ Y ∥_{F}$ in exact arithmetic, or an outward upper bound for that norm; in the approximate-inverse branch take an outward bound for $∥ Y ∥_{2} / (1 - θ)$ . Require $η β \leq 1$ ; otherwise return swap-separation-inconclusive. Record the threshold, solves, pivot decisions and certificate.
For ordinary Schur form set $V = [R; I_{q}]$ . For QZ set $V = [R; I_{q}]$ and $W_{L} = [L; I_{q}]$ . Complete the columns of $V$ , and separately $W_{L}$ , to exact orthonormal bases by Gram–Schmidt: process the graph columns first, then $e_{1}, \dots, e_{p + q}$ , skipping exactly zero residuals and normalizing each nonzero residual by the positive square root of its squared norm. The graph columns are independent because their last $q$ rows form $I_{q}$ ; the coordinate scan completes a basis. An unresolved zero or normalization decision in bounded mode returns arithmetic-inconclusive.
Let $Z_{l o c}$ be the ordinary orthogonal/unitary completion; for QZ let $Z_{l o c}$ be the right completion and $Q_{l o c}$ the left completion. Propose the local transform $Z_{l o c}^{*} T Z_{l o c}$ in the ordinary case, or $Q_{l o c}^{*} S Z_{l o c}$ and $Q_{l o c}^{*} T Z_{l o c}$ in the QZ case. Apply it to the entire affected row and column panels, including upper off-diagonal blocks. The lower-left block is set to exact zero only by the local equations solved in step 3. For a real QZ form, factor each newly formed real $2 \times 2$ diagonal block as $T_{b} = L_{b} R_{b}$ by Gram–Schmidt on its two columns, apply the embedded $L_{b}^{*}$ to the corresponding rows of both arrays, and update $Q_{l o c} \leftarrow Q_{l o c} L_{b}$ with the same embedded factor; such a block is nonsingular because its roots are finite and nonreal. A size-one infinite pair requires no division by its zero second coordinate. Commit the provisional panels and factor updates only after every required local operation succeeds, incrementing accepted swaps by one as part of that same commit; otherwise return the previous committed arrays with a failed-attempt diagnostic and leave accepted swaps unchanged.
After a committed exchange, swap the two labels and sizes and return to step 2. Ordinary accumulated factors are updated by right multiplication with $Z_{l o c}$ ; generalized accumulated factors are updated as $Q \leftarrow Q Q_{l o c}$ and $Z \leftarrow Z Z_{l o c}$ . The first $r$ columns of the updated factor are reported as the selected basis candidate; in QZ the right factor $Z$ , not the left factor $Q$ , supplies the right deflating basis.

On every exit return the current partial form, exact product factors, status, selected dimension, boundary and separation predicates, initial inversion count, attempts, accepted swaps, primitive/evaluator counts, original residual certificates, local inverse-norm certificates, and any residual transport data. Other statuses are work-budget-exhausted, arithmetic-inconclusive, range-failure, invalid-form, dimension-mismatch, boundary-spectrum, separation-inconclusive, swap-singular, swap-separation-inconclusive, and swap-budget-exhausted. ordered is distinct from any Riccati acceptance status. Reordering a computed form does not assert a structured Hamiltonian or symplectic backward-error theorem.

Facts & Assumptions

Given: The exact represented Schur or generalized Schur input, its block partition, selector, required dimension, two finite budgets and the declared exact controller or bounded evaluator.

[F1]

Real and complex Schur forms: a complex Schur form is upper triangular; a real Schur form is block upper triangular with $1 \times 1$ blocks and real $2 \times 2$ blocks of negative discriminant.

[F2]

Complex and real generalized Schur forms: complex generalized Schur factors are unitary with upper-triangular arrays and nonzero diagonal homogeneous pairs; the real form retains whole $1 \times 1$ and $2 \times 2$ diagonal blocks.

[F3]

Verified point and uniform linear residual certificate data: a uniform approximate-inverse/residual certificate is usable only under its stated strict norm bound.

[F4]

A uniform approximate inverse and residual enclose every linear solution: usable certificate data bound every exact solution; unavailable or unusable data do not assert a finite enclosure.

[F5]

Outward-rounded operations are inclusion-isotone and enclose DAG evaluations: a finite outward evaluator enclosure contains the exact value, while non-finite statuses make no finite claim.

[F6]

Gram–Schmidt turns every finite independent list into an orthonormal list with the same successive spans: finite independent vectors yield an orthonormal list with the same successive spans.

[F7]

A Neumann defect bounds the inverse norm: if $∥ E ∥_{2} \leq θ < 1$ , then $I - E$ is invertible and its inverse norm is at most $(1 - θ)^{- 1}$ .

[F8]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: compatible operator norms are submultiplicative.

[F9]

Rank-nullity: $\dim_{F} V = nullity T + rank T$ : an injective or surjective endomorphism of a finite-dimensional space is bijective.

Proof

1.1givenF1F2F5algebra

The validation scan and each selector test examine finitely many matrix entries or declared blocks. The listed Schur forms and homogeneous block conventions are exactly [F1] and [F2]; every sign decision either has an exact result or a finite outward enclosure by [F5]. Invalid structure, boundary equality, an unresolved enclosure, or a dimension mismatch takes its declared return branch before a swap is committed.

1.2F3F4F5F7F8F9givenalgebra

At each local attempt $p, q \leq 2$ , so the coefficient matrix has order at most eight and the pivot search is finite. Complete pivoting uses invertible row and column permutations; each elimination subtracts a pivot-row multiple and is reversed by adding it back. Exact back-substitution therefore solves the recorded system or detects an exact zero remaining block. If $∥ I - Y H ∥_{2} \leq θ < 1$ , [F7] makes $Y H$ invertible; $(Y H)^{- 1} Y$ is a left inverse of square $H$ , so [F9] makes $H$ invertible and [F8] gives $∥ H^{- 1} ∥_{2} \leq ∥ Y ∥_{2} / (1 - θ)$ . The routine still verifies $H x = h$ exactly. An unavailable solve, comparison, or bound takes its explicit failure status.

2.1F6step 1.1algebra

The last $q$ rows of each graph matrix $[R; I_{q}]$ and $[L; I_{q}]$ form $I_{q}$ , so both have independent columns. By [F6], Gram–Schmidt gives orthonormal graph columns with the same span. If the current span is proper, some standard coordinate vector lies outside it because those vectors span $F^{p + q}$ ; the finite scan therefore completes a basis.

3.1givenstep 1.1step 1.2step 2.1algebra∎

All remaining loops are finite scans of blocks, rows, columns, pivots, or the bounded standard basis. Every arithmetic or evaluation request consumes one unit of $W$ before execution, and every local attempt consumes one unit of $K$ before construction. Each failure returns without committing provisional data. Thus the procedure returns a declared status after finitely many operations or reaches ordered after finitely many committed exchanges; no unresolved comparison is retried indefinitely.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Standard CARE and DARE data, equations, and conventions

Definition

Let $F \in {R, C}$ , $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , $C \in F^{p \times n}$ , and $R = R^{*} \in F^{m \times m}$ be positive definite. Write $Q = C^{*} C$ and $G = B R^{- 1} B^{*}$ . The inverse $R^{- 1}$ is well-defined: A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique supplies an invertible factor $R = L L^{*}$ , so $R^{- 1} = L^{- *} L^{- 1}$ . Thus $v^{*} G v = ∥ L^{- 1} B^{*} v ∥_{2}^{2} \geq 0$ and $v^{*} Q v = ∥ C v ∥_{2}^{2} \geq 0$ . The symbol $^{*}$ is transpose over $R$ and conjugate transpose over $C$ .

The continuous algebraic Riccati equation (CARE) is $A^{*} X + X A - X G X + Q = 0.$ Its residual is $F_{c} (X) = A^{*} X + X A - X G X + Q$ , its feedback is $K_{c} (X) = R^{- 1} B^{*} X$ , and its closed-loop matrix is $A_{c} (X) = A - B K_{c} (X) = A - G X$ .

For $X = X^{*} ⪰ 0$ , $S_{X} : = R + B^{*} X B$ is positive definite because $v^{*} S_{X} v = v^{*} R v + (B v)^{*} X (B v) > 0$ for every nonzero $v$ . The discrete algebraic Riccati equation (DARE) is $X = Q + A^{*} X A - A^{*} X B (R + B^{*} X B)^{- 1} B^{*} X A .$ Its residual is $F_{d} (X) = Q + A^{*} X A - A^{*} X B (R + B^{*} X B)^{- 1} B^{*} X A - X$ . Whenever $X = X^{*}$ , the matrix $R + B^{*} X B$ is positive definite if $X ⪰ 0$ . Its feedback and closed-loop matrix are $K_{d} (X) = (R + B^{*} X B)^{- 1} B^{*} X A, A_{c} (X) = A - B K_{d} (X) .$ A CARE solution is stabilizing when it is Hermitian and $A_{c} (X)$ is Hurwitz. A DARE solution is stabilizing when it is Hermitian, $R + B^{*} X B ≻ 0$ , and $A_{c} (X)$ is Schur stable. No inverse of $A$ is part of either definition.

For Hermitian $X$ with $S_{X}$ invertible, multiplication gives $(I + G X)^{- 1} = I - B S_{X}^{- 1} B^{*} X, X (I + G X)^{- 1} = X - X B S_{X}^{- 1} B^{*} X .$ In either product, the additional coefficient of $B$ is $R^{- 1} - S_{X}^{- 1} - S_{X}^{- 1} (B^{*} X B) R^{- 1} = 0$ , because $S_{X} = R + B^{*} X B$ . Thus the DARE is equivalently $X = Q + A^{*} X (I + G X)^{- 1} A$ , and its closed-loop matrix is $A_{c} (X) = (I + G X)^{- 1} A$ .

The associated homogeneous symplectic pencil is $N = [\begin{array}{cc} A & 0 \\ - Q & I \end{array}], M = [\begin{array}{cc} I & G \\ 0 & A^{*} \end{array}], P (α, β) = β N - α M .$ The homogeneous-coordinate convention is that a finite eigenvalue $λ$ is $[α : β] = [λ : 1]$ and $[1 : 0]$ denotes infinity.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Powers of a Schur-stable matrix decay geometrically up to a polynomial factor

Statement

Let $M \in C^{n \times n}$ be Schur stable and let $r$ satisfy $ρ (M) < r < 1$ . For the Euclidean induced operator norm there is a finite $C_{r}$ such that $∥ M^{k} ∥_{2} \leq C_{r} r^{k} (k \geq 0) .$ For a real matrix, interpret the same statement on its complexification.

Facts & Assumptions

Given: A finite Schur-stable matrix $M$ and $r$ with $ρ (M) < r < 1$ .

[A1]

For $n \geq 1$ , the notation $ρ (M)$ means $\max {∣ λ ∣ : λ \in σ_{C} (M)}$ ; for the unique $0 \times 0$ matrix set $ρ (M) = 0$ .

[F1]

Stabilizability and detectability for continuous and discrete linear systems: Schur stable means every eigenvalue has modulus strictly less than one.

[F2]

If the characteristic polynomial of an endomorphism splits, some orthonormal basis makes its matrix upper triangular: a complex finite-dimensional endomorphism has an orthonormal basis in which its matrix is upper triangular.

[F3]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: $∥ S T ∥_{2} \leq ∥ S ∥_{2} ∥ T ∥_{2}$ for compatible finite-dimensional maps.

[F4]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: $∥ T ∥_{2} = \max_{∥ v ∥_{2} = 1} ∥ T v ∥_{2}$ .

[F5]

Every nonconstant polynomial in $C [x]$ splits into linear factors: every nonconstant characteristic polynomial over $C$ splits over $C$ , so the hypothesis of [F2] holds.

[F6]

Linear isometries, and orthogonal or unitary operators on finite-dimensional inner product spaces: a unitary operator and its adjoint preserve the Euclidean norm.

[F7]

For $A \in M_{n} (F)$ , the characteristic polynomial is $χ_{A} (x) = \det (x I_{n} - A)$ when $n \geq 1$ , with $χ_{A} (x) = 1$ for the unique $0 \times 0$ matrix and The determinant of a triangular matrix is the product of its diagonal entries: for upper-triangular $T$ , $χ_{T} (z) = \det (z I - T) = \prod_{i} (z - T_{i i})$ .

[F8]

Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism and For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ : the complex spectrum is the root set of the characteristic polynomial.

Proof

1.1A1F1F2F5F7F8construct

If $n = 0$ , the unique endomorphism and every power of it is the zero map on the zero domain; its operator norm is zero, so the assertion holds with $C_{r} = 0$ . Assume now $n \geq 1$ and regard a real matrix, if present, as a complex matrix. Its characteristic polynomial is a nonconstant complex polynomial, so [F5] and [F2] give $M = U T U^{*}$ with $U$ unitary and $T = D + N$ , where $D$ is diagonal and $N$ is strictly upper triangular. Similar matrices have the same eigenvalues: $M v = λ v$ is equivalent to $T (U^{*} v) = λ (U^{*} v)$ . By [F7] and [F8], the eigenvalues are the diagonal entries of $T$ ; hence $ρ (M) = \max_{i} ∣ T_{i i} ∣ = ∥ D ∥_{2}$ , where the last equality follows directly from the Euclidean induced norm. Set $ρ = ρ (M) < r$ . Each occurrence of $N$ in a product raises the row-to-column index, while $D$ preserves it, so every word containing at least $n$ copies of $N$ is zero.

2.1F3F4F6step 1.1algebra

Expand $(D + N)^{k}$ as the sum of noncommuting words. The terms with exactly $j$ copies of $N$ number $(\binom{k}{j})$ , vanish for $j \geq n$ , and for $j < n$ have norm at most $ρ^{k - j} ∥ N ∥_{2}^{j}$ by [F3] and $∥ D ∥_{2} = ρ$ . Thus $∥ T^{k} ∥_{2} \leq \sum_{j = 0}^{\min (k, n - 1)} (\binom{k}{j}) ρ^{k - j} ∥ N ∥_{2}^{j} .$ Because $U$ and $U^{*}$ preserve vector norms by [F6] and $U^{*}$ maps the unit sphere onto itself, the induced norm [F4] gives $∥ M^{k} ∥_{2} = ∥ U T^{k} U^{*} ∥_{2} = ∥ T^{k} ∥_{2}$ .

3.1step 2.1algebracases∎

If $ρ = 0$ , then $D = 0$ and $T = N$ , so $T^{k} = 0$ for $k \geq n$ ; taking $C_{r} = \max_{0 \leq k < n} ∥ T^{k} ∥_{2} r^{- k}$ proves the claim. If $0 < ρ < r$ , each fixed $j < n$ satisfies $(\binom{k}{j}) ρ^{k - j} ∥ N ∥_{2}^{j} / r^{k} \leq c_{j} k^{j} (ρ / r)^{k}$ for a finite $c_{j}$ . The ratio of consecutive terms $k^{j} (ρ / r)^{k}$ tends to $ρ / r < 1$ , so this sequence is bounded. Summing its finitely many bounds over $0 \leq j < n$ gives a finite $C_{r}$ in step 2.1.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Stabilizability and detectability imply the closed-region PBH rank tests

Statement

For $F \in {R, C}$ , $n, m, p \geq 1$ , $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , and $C \in F^{p \times n}$ , the following necessary conditions hold.

If $(A, B)$ is continuously stabilizable, then $rank [λ I - A B] = n$ for every $λ \in C$ with $Re λ \geq 0$ . If it is discretely stabilizable, the same rank is $n$ for every $∣ λ ∣ \geq 1$ .

If $(A, C)$ is continuously detectable, then $rank [\begin{array}{c} λ I - A \\ C \end{array}] = n$ for every $Re λ \geq 0$ . If it is discretely detectable, the same rank is $n$ for every $∣ λ ∣ \geq 1$ .

This proves the necessary half of the PBH tests. The converse pole-placement implication is not asserted here.

Facts & Assumptions

Given: The matrices and continuous/discrete stabilizability and detectability definitions of Stabilizability and detectability for continuous and discrete linear systems. Every rank test and eigenvector argument is over $C$ ; when $F = R$ , the real matrices and their real feedback or injection witnesses act complex-linearly on their complexifications.

[F1]

Stabilizability and detectability for continuous and discrete linear systems: continuous stabilizability means $A - B K$ is Hurwitz for some $K$ ; discrete stabilizability means $A - B K$ is Schur stable; detectability is the dual condition with $A - L C$ .

[F2]

Row rank equals column rank, and both equal the number of pivots: for a finite matrix, row rank and column rank agree.

[F3]

Rank-nullity: $\dim_{F} V = nullity T + rank T$ : for a linear map with finite-dimensional domain, dimension of domain equals rank plus nullity.

[A1]

For $F = R$ , real matrices and feedback/injection witnesses are extended complex-linearly when tested against a complex $λ$ .

Proof

1.1A1F1F2F3contradiction

Suppose $(A, B)$ is continuously stabilizable and fix its same-field feedback $K$ from [F1]. If for some $λ$ with $Re λ \geq 0$ the horizontal matrix $H_{λ} = [λ I - A B]$ has rank less than $n$ , [F2] and [F3] applied over $C$ to $H_{λ}^{*}$ give a nonzero $y \in C^{n}$ with $y^{*} (λ I - A) = 0$ and $y^{*} B = 0$ . By [A1], the same real or complex $K$ acts on this vector, so $y^{*} (A - B K) = λ y^{*}$ . Thus $\det (λ I - (A - B K)) = 0$ , contradicting that $A - B K$ is Hurwitz.

1.2A1F1F3contradiction

Suppose $(A, C)$ is continuously detectable and fix its same-field injection $L$ from [F1]. If $V_{λ} = [\begin{array}{c} λ I - A \\ C \end{array}]$ has rank less than $n$ , rank-nullity over $C$ gives a nonzero $x \in C^{n}$ with $(λ I - A) x = 0$ and $C x = 0$ . Hence $(A - L C) x = λ x$ , which contradicts that $A - L C$ is Hurwitz because $Re λ \geq 0$ .

2.1A1F1F2F3step 1.1contradiction

Suppose $(A, B)$ is discretely stabilizable and fix its same-field Schur feedback $K$ from [F1]. If $[λ I - A B]$ has rank less than $n$ for some $∣ λ ∣ \geq 1$ , the same complex left-kernel argument as in step 1.1 gives a nonzero $y$ with $y^{*} (A - B K) = λ y^{*}$ . Thus $\det (λ I - (A - B K)) = 0$ , contradicting Schur stability.

3.1A1F1F3step 1.2contradiction∎

Suppose $(A, C)$ is discretely detectable and fix its same-field Schur injection $L$ from [F1]. If the vertical matrix has rank less than $n$ for some $∣ λ ∣ \geq 1$ , its complex kernel contains a nonzero $x$ and $C x = 0$ , so $(A - L C) x = λ x$ . This contradicts Schur stability.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

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

Statement

For an order- $d$ real or complex Schur form, or a regular generalized Schur form, run Finite-budget stable block reordering for Schur and QZ forms with its declared selector, selected dimension $r$ , swap budget $K$ , primitive/evaluator budget $W$ , and positive local threshold $η$ . Every execution returns after its finite scans or an explicit budget, boundary, form, separation, arithmetic, or range status. Every committed exact swap uses orthogonal/unitary transformations, preserves the appropriate Schur form over the original field, and exchanges exactly the two adjacent block spectra; for generalized Schur form it exchanges the homogeneous roots with multiplicity, including infinity.

Let $b$ be the initial number of diagonal blocks and $I$ the number of complementary-before-selected block pairs. If the initial selected block sizes sum to $r$ , all selector comparisons are strict, every local construction and certificate succeeds, every inverse-norm threshold passes, $K \geq I$ , and $W$ suffices for the entire execution, including validation, label and inversion scans, all $I$ swaps, and the final ordering scan, the procedure returns ordered. The first $r$ columns of the updated ordinary Schur factor then span the selected invariant subspace of the current computed form; the first $r$ columns of the updated right QZ factor span the selected right deflating subspace of the current computed pencil. When an original reduction residual is present, this is the exact subspace of its represented nearby matrix or pencil, not automatically the original data's subspace. Each accepted swap decreases the inversion count by one and $I \leq b (b - 1) / 2$ . Boundary, small-gap, arithmetic, or budget exits do not prove that a stabilizing Riccati solution does not exist.

If the ordinary input relation is $Q_{0}^{*} A Q_{0} = T_{0} + R_{0}$ and the cumulative exact reordering factor is $V$ , then $Q_{n e w} = Q_{0} V$ , $T_{n e w} = V^{*} T_{0} V$ , and the new residual is $V^{*} R_{0} V$ , with unchanged Frobenius norm. If the generalized input relations are $Q_{0}^{*} A Z_{0} = S_{0} + R_{A}$ and $Q_{0}^{*} B Z_{0} = T_{0} + R_{B}$ , then for cumulative left and right factors $U, V$ the new residuals are $U^{*} R_{A} V$ and $U^{*} R_{B} V$ , again with unchanged Frobenius norms. Thus exact reordering preserves the original unstructured reduction certificate but creates no structured Hamiltonian or symplectic error theorem.

For $k$ local swap attempts, the scalar-core work is $O (d^{2} + k d)$ in the declared exact scalar/evaluator unit model: the initial structure scan costs $O (d^{2})$ and each local system has order at most eight while whole-panel updates touch $O (d)$ entries. On success $k = I$ , so the worst-case swap core is $O (d^{3})$ . Exact algebraic bit cost, evaluator implementation cost beyond the declared units, and dense evaluation of product factors are separate. From $L_{0}$ bounded-support input factors, directly evaluating the first $r$ columns costs $O (L_{0} d r + I d r)$ ; a dense residual multiplication, if used, has its own actual $O (d^{3})$ cost.

Facts & Assumptions

Given: The algorithm's admitted exact Schur or generalized Schur input, block partition, strict selector, selected dimension, finite budgets and local exact or bounded-evaluator certificates.

[F1]

Finite-budget stable block reordering for Schur and QZ forms: it forms the stated ordinary or generalized Sylvester systems, completes exact orthonormal bases, applies whole-panel transformations transactionally, and returns explicit finite statuses.

[F2]

A Sylvester equation is uniquely solvable exactly when the spectra are disjoint: $X \mapsto A X + X B$ is invertible exactly when $σ (A) \cap (- σ (B)) = \emptyset$ .

[F3]

A nonzero polynomial of degree $n$ over an integral domain has at most $n$ distinct roots: a nonzero polynomial of degree $q$ over an integral domain has at most $q$ distinct roots.

[F4]

A finite-dimensional linear operator over a field is invertible if and only if its determinant is nonzero: a finite-dimensional square operator is invertible exactly when its determinant is nonzero.

[F5]

Rank-nullity: $\dim_{F} V = nullity T + rank T$ : an injective square map on a finite-dimensional space is invertible.

[F6]

Gram–Schmidt turns every finite independent list into an orthonormal list with the same successive spans: Gram–Schmidt gives an orthonormal list with the same successive spans as a finite independent input list.

[F7]

For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ : determinants multiply under finite square matrix products.

[F8]

The homogeneous determinant factors across a block upper triangular pencil: the homogeneous determinant of a block upper-triangular pencil is the product of the diagonal-block homogeneous determinants.

[F9]

Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: unitary changes preserve the Frobenius norm and $∥ M ∥_{2} \leq ∥ M ∥_{F}$ .

[F10]

A Neumann defect bounds the inverse norm: if $∥ E ∥_{2} \leq θ < 1$ , then $∥ (I - E)^{- 1} ∥_{2} \leq (1 - θ)^{- 1}$ .

[F11]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: compatible operator norms are submultiplicative.

Proof

1.1F1givenalgebra

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 $tr (T_{b}) / 2$ . For a generalized scalar pair $[s : t]$ , a finite root is $s / t$ , so $∣ s ∣ < ∣ t ∣$ is exactly the disk predicate and $t = 0$ , $s \neq 0$ is infinity and complementary. For a real generalized $2 \times 2$ pair with finite nonreal roots, the root product is $\det (S_{b}) / \det (T_{b}) = ∣ λ ∣^{2}$ . Thus the procedure labels whole blocks exactly and detects equality at the selector boundary.

1.2F1F2givenalgebra

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

1.3F1F2F3F4F5givenconstructalgebra

For generalized adjacent pairs $(A, D)$ and $(B, E)$ , their homogeneous root sets are disjoint and both pairs are regular. The polynomials $\det (A - ζ D)$ and $\det (B - ζ E)$ are nonzero of degrees at most $p, q$ ; among $p + q + 1$ distinct real integers, [F3] gives a $ζ$ for which $A_{0} = A - ζ D$ and $B_{0} = B - ζ E$ have nonzero determinants, hence are invertible by [F4]. Each homogeneous root $[α : β]$ maps injectively to $μ = β / (α - ζ β)$ , an eigenvalue of $D A_{0}^{- 1}$ because $D - μ A_{0} = - (β A - α D) / (α - ζ β)$ ; this also maps infinity to zero, and maps the second pair to $E B_{0}^{- 1}$ , so the ordinary spectra remain disjoint. If $A R - L B = 0$ and $D R - L E = 0$ , then $A_{0} R = L B_{0}$ , hence $R = A_{0}^{- 1} L B_{0}$ and $D A_{0}^{- 1} L = L E 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.

1.4F1F9givenalgebra

For ordinary input, $Q_{0}^{*} A Q_{0} = T_{0} + R_{0}$ and $Q_{n e w} = Q_{0} V$ imply $Q_{n e w}^{*} A Q_{n e w} = V^{*} T_{0} V + V^{*} R_{0} V$ . For QZ, substituting $Q_{n e w} = Q_{0} U$ and $Z_{n e w} = Z_{0} V$ into the two input relations gives residuals $U^{*} R_{A} V$ and $U^{*} R_{B} V$ ; [F9] preserves their Frobenius norms. These unstructured residual relations assert no structured pencil perturbation.

2.1F1F5F9F10F11step 1.2step 1.3algebra

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, $∥ I - Y H ∥_{2} \leq θ < 1$ and [F10] make $Y H$ invertible; finite-dimensional square rank and [F11] give $∥ H^{- 1} ∥_{2} = ∥ (Y H)^{- 1} Y ∥_{2} \leq ∥ Y ∥_{2} / (1 - θ)$ . Thus each committed swap has an exact solve and valid recorded inverse bound.

2.2F1step 1.1algebra

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 \leq b (b - 1) / 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.

3.1F1F6step 2.1algebra

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.

4.1F1F7step 3.1algebra

In the ordinary case $A R - R B = - C$ gives $[\begin{array}{cc} A & C \\ 0 & B \end{array}] [\begin{array}{c} R \\ I_{q} \end{array}] = [\begin{array}{c} R \\ I_{q} \end{array}] 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 $π (x, y) = x - R y$ has kernel this graph and satisfies $π T_{J J} = A π$ , 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.

4.2F1F7F8step 3.1algebra

In the generalized case the two local equations give $S_{J J} [R; I_{q}] = [L; I_{q}] B$ and $T_{J J} [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$ .

4.3F1step 2.2step 3.1givenalgebra

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} + k d)$ . On success $k = I \leq b (b - 1) / 2 \leq d (d - 1) / 2$ , giving $O (d^{3})$ worst-case swap work. Evaluating $L_{0}$ bounded-support input factors on $r$ columns costs $O (L_{0} d r + I d r)$ ; dense residual multiplication costs its separate $O (d^{3})$ . These counts do not bound algebraic bit cost or evaluator implementation cost.

5.1F1step 1.4step 2.2step 4.1step 4.2step 4.3algebra∎

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.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration

Definition

Inputs are CARE data with $Q = C^{*} C ⪰ 0$ , $R ≻ 0$ , a supplied stabilizing gain $K_{0}$ , a nonnegative integer outer budget $N$ , and either exact or safeguarded-inexact solve mode. Each exact-mode pass takes an admissible control packet for Finite-budget Bartels-Stewart solve for a Sylvester equation: pivot threshold $τ_{B S} \geq 0$ , a fixed $c_{0} > 0$ , nonnegative integer Schur sweep budgets $N_{A}, N_{B} \leq c_{0} n$ , and Schur controls for each coefficient matrix (deflation tolerance, positive integer stagnation period, finite exceptional-shift tables, arithmetic/range controls, and any supplied encoding or evaluator). Use its bounded-controller mode with a supplied nonnegative integer instruction budget $K_{B S}$ and its built-in discriminant-sign controller. In inexact mode, also supply a nonnegative integer line-search limit $L$ ; each pass takes a Hermitian proposal ${\tilde{P}}_{j}$ , a stored candidate ${\hat{X}}_{j}$ and approximate inverses for the finite Lyapunov systems below, and finite factorization witnesses for each trial. Stored inputs and point-solve proposals in this mode are exact dyadics; derived gains and coefficients are retained as exact rational expressions. Every point call uses the operationwise controller of Finite precision point linear solve certificate with explicit status; every scalar enclosure uses a finite outward evaluator with a declared work budget. Write $S (K) = Q + K^{*} R K$ and $L_{A} (P) = A^{*} P + P A$ .

For $j = 0, \dots, N - 1$ , put $A_{j} = A - B K_{j}$ . In exact mode, call Finite-budget Bartels-Stewart solve for a Sylvester equation with coefficient matrices $A_{j}^{*}, A_{j}$ , right-hand side $- S (K_{j})$ , and that pass's complete control packet to solve $L_{A_{j}} (X_{j}) = - S (K_{j}) .$ If it does not return success, stop with its status. Otherwise set $K_{j + 1} = R^{- 1} B^{*} X_{j}$ , append the gain and residual, and continue.

In safeguarded-inexact mode, $X_{j}$ denotes the unique exact solution of $L_{A_{j}} (X_{j}) = - S (K_{j})$ ; it exists because $K_{0}$ is stabilizing and every previously accepted trial has a Hurwitz witness. Under column vectorization, use the point matrix $I_{n} \otimes A_{j}^{*} + A_{j}^{T} \otimes I_{n}$ for $L_{A_{j}}$ , as in Column vectorization is an isometry and represents the Sylvester map by a Kronecker sum. Before the current-cost point call, clear a common positive integer denominator $d_{j}$ from this exact rational coefficient matrix and from $- vec (S (K_{j}))$ . Call Finite precision point linear solve certificate with explicit status on the resulting dyadic system, with the supplied inverse proposal for the scaled coefficient and ${\hat{X}}_{j}$ as the solution proposal. Scaling both sides by $d_{j}$ preserves the exact solution $X_{j}$ ; if the scaled entries cannot be stored exactly in the declared point format, return range-failure. A range-failure returns that status; an inconclusive result returns safeguard-inconclusive. Let its solution ball have center ${\hat{X}}_{j}$ and radius $s_{j}$ , replacing the center by its Hermitian part if needed. Set $D_{j} = {\tilde{P}}_{j} - {\hat{X}}_{j}$ and compute the outward Gershgorin upper bound $η_{j} = s_{j} + \max_{i} ((D_{j})_{i i} + \sum_{k \neq i} ∣ (D_{j})_{i k} ∣) .$ For Hermitian $D_{j}$ , the maximum row bound above is at least $λ_{\max} (D_{j})$ , by applying the eigenvector equation at a coordinate of maximal modulus. Define ${\tilde{K}}_{j} = R^{- 1} B^{*} {\tilde{P}}_{j}$ and inspect the finite line-search list $θ_{ℓ} = 2^{- ℓ}$ , $0 \leq ℓ \leq L$ . For each trial $K_{ℓ} = K_{j} + θ_{ℓ} ({\tilde{K}}_{j} - K_{j})$ , let $A_{ℓ} = A - B K_{ℓ}$ and use its supplied exact factor witnesses $W_{ℓ} = L_{ℓ}^{*} L_{ℓ}$ with nonsingular $L_{ℓ}$ , and $Z_{ℓ}$ satisfying $A_{ℓ}^{*} W_{ℓ} + W_{ℓ} A_{ℓ} ⪯ - μ_{ℓ} I,$ where $μ_{ℓ} > 0$ and $- A_{ℓ}^{*} W_{ℓ} - W_{ℓ} A_{ℓ} - μ_{ℓ} I = Z_{ℓ}^{*} Z_{ℓ}$ . Verify these exact factor identities; otherwise reject the trial and continue. Vectorize $L_{A_{ℓ}}$ using the same coefficient matrix as for $A_{j}$ . Outward-evaluate $I - R_{ℓ} L_{A_{ℓ}}$ and let $q_{ℓ}$ be a Frobenius upper bound. If no finite enclosure is available or $q_{ℓ} \geq 1$ , reject the trial and continue. Set $κ_{ℓ} = ∥ R_{ℓ} ∥_{F} / (1 - q_{ℓ})$ ; the Neumann estimate and $∥ T ∥_{2} \leq ∥ T ∥_{F}$ give $κ_{ℓ} \geq ∥ L_{A_{ℓ}}^{- 1} ∥_{F \to F}$ . Separately outward-evaluate the raw residual and set $r_{ℓ}$ to an upper bound for $L_{A_{ℓ}} ({\tilde{P}}_{j}) + Q + K_{ℓ}^{*} R K_{ℓ},$ with Frobenius norm. Accept the first trial satisfying $η_{j} + κ_{ℓ} r_{ℓ} \leq 0$ ; then set $K_{j + 1} = K_{ℓ}$ , append the accepted gain and its certificates, and proceed to pass $j + 1$ . If no trial passes, return safeguard-inconclusive without changing $K_{j}$ . Any unavailable outward bound is inconclusive. The inverse bound above follows from the Neumann estimate, and $r_{ℓ}$ bounds the raw residual separately; the preconditioned residual in Verified point and uniform linear residual certificate data is a different quantity. All certificate witnesses and bounds use the finite outward evaluator; a non-finite operation returns its range status. After at most $N$ accepted updates return the gain sequence, solve residuals, cost-matrix data and terminal status. An arbitrary approximate Lyapunov solve is never accepted without the separate stability and descent checks above.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Finite-budget structure-preserving doubling iteration for the DARE

Definition

Input $F \in {R, C}$ , dimensions $n, m, p \geq 1$ , standard DARE data $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , $C \in F^{p \times n}$ , and $R \in F^{m \times m}$ with $R = R^{*} ≻ 0$ , a nonnegative integer iteration budget $N$ , and the operationwise arithmetic/range controller. In finite mode the stored input entries are exact dyadics; also supply stored dyadic inverse and solution proposals for every recurrence and residual solve. In exact mode set $G_{0} = B R^{- 1} B^{*}$ , $H_{0} = Q = C^{*} C$ , and $A_{0} = A$ , the standard DARE coefficients of Standard CARE and DARE data, equations, and conventions.

For finite-mode initialization, first solve $R V = B^{*}$ by the exact complete-pivoting elimination rule below, using order $m$ and the $n$ right-hand sides of $B^{*}$ in place of $M_{j}$ and $I$ . Perform this preprocessing in exact rational arithmetic on the dyadic inputs. Form $B V$ and $C^{*} C$ exactly, then round each real and imaginary component once to the declared stored format (nearest, with ties to even), obtaining stored $G_{0}$ and $H_{0}$ ; set stored $A_{0} = A$ . A zero pivot returns inverse-inconclusive; a component outside the controller's admitted range returns range-failure. On an initialization failure return the inputs, zero completed updates, any formed initial matrices and solve data, and unavailable for every unformed matrix or diagnostic. The finite-mode notation $G_{0}, H_{0}$ denotes these rounded matrices, not an assertion that $B R^{- 1} B^{*}$ is dyadic. Record $V$ and the initialization rounding differences separately. This exact rational preprocessing has no asserted bit-cost bound and adds no point-certifier calls.

In exact mode, for each $j = 0, \dots, N - 1$ , form $M_{j} = I + G_{j} H_{j}$ and solve $M_{j} W_{j} = I$ by Gaussian elimination with complete pivoting: at stage $k$ , scan the remaining submatrix, choose a nonzero entry of largest exact modulus with lexicographic tie-breaking, swap its row and column into pivot position, eliminate below it, and back-substitute for all columns of $I$ , undoing the accumulated column permutation in the solution. If the remaining submatrix is exactly zero before all pivots, return inverse-inconclusive. This is a finite exact-arithmetic procedure; no bit-complexity bound is asserted.

In finite arithmetic, form the stored dyadic matrix ${\hat{M}}_{j} = fl (I + G_{j} H_{j})$ . For each standard basis vector $e_{k}$ , call Finite precision point linear solve certificate with explicit status with $({\hat{M}}_{j}, e_{k}, R_{j}, {\hat{w}}_{j, k})$ , using the supplied stored dyadic inverse and solution proposals. Assemble the returned solution centers as ${\hat{W}}_{j}$ . If any call returns range-failure, return range-failure; if any call is inconclusive, return inverse-inconclusive; otherwise apply the recurrence updates below using ${\hat{W}}_{j}$ and the declared operationwise arithmetic. The point certifier's solution balls are diagnostics for the stored solve and do not make the rounded recurrence an exact PSD-preserving recurrence.

In exact mode let $W_{j}$ be the exact solve result; in finite mode let $W_{j} = {\hat{W}}_{j}$ . The recurrence formulas are

A_{j + 1} = A_{j} W_{j} A_{j}, G_{j + 1} = G_{j} + A_{j} W_{j} G_{j} A_{j}^{*}, H_{j + 1} = H_{j} + A_{j}^{*} H_{j} W_{j} A_{j} .

These formulas use no inverse of $A_{j}$ . Any range failure while forming a stored matrix or applying an update returns range-failure with the current raw matrices.

After successful initialization, if all $N$ updates finish without a recurrence failure, return budget-exhausted with $N$ completed updates, including when $N = 0$ . This status records only completion of the prescribed budget; the diagnostics below remain required.

At initialization and after each update, preserve the raw matrices and report $∥ G_{j} - G_{j}^{*} ∥_{F}$ and $∥ H_{j} - H_{j}^{*} ∥_{F}$ . To report the standard DARE residual, form $S_{j} = R + B^{*} H_{j} B$ exactly from the current $H_{j}$ and original input entries. In exact mode, $S_{j}$ need not be dyadic: independently solve $S_{j} V_{j} = I$ by the same exact elimination rule, using order $m$ , and evaluate the residual from Standard CARE and DARE data, equations, and conventions exactly using $V_{j}$ . In finite mode, $S_{j}$ is dyadic because the original inputs and current stored $H_{j}$ are dyadic; apply the point-certified solve rule to its $m$ columns with the separate residual proposal packet, and outward-evaluate the residual over the certified solution balls. If the residual solve or evaluation is unavailable or inconclusive, mark the residual unavailable without changing the recurrence status. Symmetrization may be used only to form a candidate and must be followed by fresh residual and positivity checks. On every exit return the current raw matrices, status, completed updates, symmetry defects, and available residual and solve certificates. No exact positive-semidefinite or structure-preserving backward-error claim is made from a rounded recurrence alone.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Closed-region PBH rank tests characterize continuous and discrete stabilizability and detectability

Statement

Let $F \in {R, C}$ and let $A \in F^{n \times n}$ , $B \in F^{n \times m}$ and $C \in F^{p \times n}$ have the domains in Stabilizability and detectability for continuous and discrete linear systems. All rank tests below are over $C$ , including for real matrices.

$(A, B)$ is continuously stabilizable if and only if ${rank}_{C} [λ I - A B] = n$ for every $λ$ with $Re λ \geq 0$ .
$(A, B)$ is discretely stabilizable if and only if that horizontal rank is $n$ for every $λ$ with $∣ λ ∣ \geq 1$ .
$(A, C)$ is continuously detectable if and only if ${rank}_{C} [\begin{array}{c} λ I - A \\ C \end{array}] = n$ for every $λ$ with $Re λ \geq 0$ .
$(A, C)$ is discretely detectable if and only if that vertical rank is $n$ for every $λ$ with $∣ λ ∣ \geq 1$ .

Whenever the converse direction constructs a feedback or injection, its entries lie in the original field $F$ . The boundary $Re λ = 0$ or $∣ λ ∣ = 1$ is included in each forbidden region. These are exact finite-dimensional tests; a small equation residual or approximate eigenvalue does not imply them.

Facts & Assumptions

Given: The finite matrices and the existential continuous/discrete stabilizability and detectability definitions of Stabilizability and detectability for continuous and discrete linear systems.

[F1]

Stabilizability and detectability for continuous and discrete linear systems: stabilizability means existence of a same-field $K$ with $A - B K$ Hurwitz or Schur stable; detectability means existence of a same-field $L$ with $A - L C$ Hurwitz or Schur stable.

[F2]

Stabilizability and detectability imply the closed-region PBH rank tests: each of the four existential stability hypotheses implies its horizontal or vertical rank test on the corresponding closed region.

[F3]

Reachable block decomposition and same-field state-feedback pole placement: the horizontal rank test for all complex $λ$ is equivalent to the uncontrollable block having no eigenvalue there, and a reachable block admits arbitrary same-field pole assignment.

[F4]

[F5]

Row rank equals column rank, and both equal the number of pivots: the rank of a finite complex matrix equals the rank of its adjoint, so vanishing of the left nullspace is equivalent to full row rank.

Proof

1.1F2

Necessity in all four assertions is exactly [F2]. This proves the forward implications from stabilizability or detectability to the stated rank tests, including every point on each closed boundary.

1.2F1F3F4givenalgebra

Fix either forbidden closed region $Ω = {λ : Re λ \geq 0}$ or $Ω = {λ : ∣ λ ∣ \geq 1}$ . Suppose the horizontal rank test holds for all $λ \in Ω$ , and apply [F3] to $(A, B)$ over the original field $F$ . The uncontrollable block $A_{u}$ has no eigenvalue in $Ω$ , so its eigenvalues lie in the open left half-plane or open unit disk, respectively. Assign the reachable block repeated pole $- 1$ or $0$ by [F3], obtaining $K_{r}$ . With its decomposition matrix $P$ , set $K = [K_{r} 0] P^{- 1}$ ; if $r = 0$ take $K = 0$ , and if $r = n$ omit the empty trailing block. Then $P^{- 1} (A - B K) P = [\begin{array}{cc} A_{r} - B_{r} K_{r} & D \\ 0 & A_{u} \end{array}]$ . By [F4] its eigenvalues are the assigned stable poles and those of $A_{u}$ , with multiplicity; hence $A - B K$ is Hurwitz or Schur stable, and $K \in F^{m \times n}$ .

2.1F1F5step 1.2algebra∎

For every $λ \in C$ , ${rank}_{C} [\overset{ˉ}{λ} I - A^{*} C^{*}] = {rank}_{C} [\begin{array}{c} λ I - A \\ C \end{array}]$ because these matrices are adjoints and [F5] applies. Each forbidden region is invariant under conjugation, so its vertical test for $(A, C)$ is the horizontal test for $(A^{*}, C^{*})$ . Step 1.2 supplies $J \in F^{p \times n}$ with $A^{*} - C^{*} J$ Hurwitz or Schur stable. Its adjoint $A - J^{*} C$ has conjugate eigenvalues with the same real parts and moduli, so $L = J^{*} \in F^{n \times p}$ is the required injection. This proves both detectability converses, including their boundary cases.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution

Statement

Let $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , $C \in F^{p \times n}$ , $R = R^{*} ≻ 0$ , $Q = C^{*} C$ , and $G = B R^{- 1} B^{*}$ . Assume $(A, B)$ is continuously stabilizable and $(A, C)$ is continuously detectable, using Stabilizability and detectability for continuous and discrete linear systems. Then the CARE of Standard CARE and DARE data, equations, and conventions has exactly one Hermitian positive-semidefinite solution $X$ . Its closed-loop matrix $A_{c} = A - G X$ is Hurwitz, and for every initial state $x_{0}$ the infinite-horizon value $\inf_{u} \int_{0}^{\infty} (x (t)^{*} Q x (t) + u (t)^{*} R u (t)) d t = x_{0}^{*} X x_{0}$ is attained by $u (t) = - R^{- 1} B^{*} X x (t)$ . Controls are locally square-integrable and states are locally absolutely continuous solutions of $\dot{x} = A x + B u$ . A finite value also forces the terminal term $x (T)^{*} X x (T)$ to tend to zero; this transversality is proved below.

Facts & Assumptions

Given: The finite matrices in the statement, continuous stabilizability/detectability, $R ≻ 0$ , $Q = C^{*} C$ , and locally square-integrable controls.

[F1]

Stabilizability and detectability for continuous and discrete linear systems: stabilizability/detectability mean existence of a Hurwitz state-feedback or output-injection matrix.

[F2]

Standard CARE and DARE data, equations, and conventions: $G = B R^{- 1} B^{*}$ and the CARE residual is $A^{*} X + X A - X G X + Q$ .

[F3]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: $R ≻ 0$ yields an invertible factor $R = L L^{*}$ .

[F4]

Picard-Lindelöf local existence and uniqueness for first-order systems: a locally Lipschitz finite-dimensional ODE vector field has a unique local IVP solution.

[F5]

Every Picard–Lindelöf initial value problem has one maximal solution on an open interval: the local solution has a unique maximal interval; any solution through the same data is its restriction.

[F6]

A Hurwitz matrix exponential has a polynomial-exponential decay bound: if $M$ is Hurwitz then $e^{t M}$ has a bound by a polynomial times $e^{- α t}$ for some $α > 0$ .

[F7]

Linear matrix ODEs have unique global solutions on a fixed interval: for a continuous real matrix coefficient on a compact interval, every homogeneous linear matrix IVP has a unique solution throughout that interval.

Proof

1.1F2F3F4F5algebra

By [F3], $R^{- 1}$ exists and $G = G^{*} ⪰ 0$ , since $v^{*} G v = (B^{*} v)^{*} R^{- 1} (B^{*} v) \geq 0$ . Regard the Hermitian matrices as a finite-dimensional real vector space and solve the initial-value problem $P^{'} (s) = A^{*} P (s) + P (s) A - P (s) G P (s) + Q, P (0) = 0.$ Its polynomial vector field is locally Lipschitz: on each bounded matrix ball, expanding the quadratic difference gives $P G P - H G H = (P - H) G P + H G (P - H)$ , which is bounded linearly in $∥ P - H ∥_{F}$ . Thus [F4] and [F5] give a unique maximal solution. The adjoint $P (s)^{*}$ satisfies the same IVP, so uniqueness makes $P (s) = P (s)^{*}$ on its interval.

2.1F2F7step 1.1algebra

Fix $T$ in this interval and let $x$ follow any admissible control on $[0, T]$ . Put $S (t) = P (T - t)$ . Differentiating $x (t)^{*} S (t) x (t)$ and substituting the ODE gives $x^{*} Q x + u^{*} R u + \frac{d}{d t} (x^{*} S x) = (u + R^{- 1} B^{*} S x)^{*} R (u + R^{- 1} B^{*} S x) .$ Integrating, using $P (0) = 0$ , yields $J_{T} (u) = x_{0}^{*} P (T) x_{0} + \int_{0}^{T} (u + R^{- 1} B^{*} S x)^{*} R (u + R^{- 1} B^{*} S x) d t .$ The candidate feedback makes $\dot{x} = (A - G S (t)) x$ , whose coefficient is continuous on $[0, T]$ . If $F = R$ , [F7] gives its unique solution on the interval. If $F = C$ , write $x$ in real and imaginary parts and replace the coefficient $M$ by $[\begin{array}{cc} Re M & - Im M \\ Im M & Re M \end{array}]$ ; [F7] applies to this continuous real system, and its solution is exactly the complex feedback trajectory. Thus $u = - R^{- 1} B^{*} S x$ is admissible and makes the last integral zero, so $x_{0}^{*} P (T) x_{0}$ is the finite-horizon value and $P (T) ⪰ 0$ .

3.1F1F4F5F6step 2.1

By stabilizability [F1], choose $K_{0}$ with $A_{0} = A - B K_{0}$ Hurwitz. Under $u = - K_{0} x$ , [F6] bounds $x (t) = e^{t A_{0}} x_{0}$ by a square-integrable polynomial-exponential multiple of $∥ x_{0} ∥$ . The control $K_{0} x (t)$ has the same property, so its cost on $[0, T]$ is at most $c ∥ x_{0} ∥^{2}$ for one finite $c$ independent of $T$ . Step 2.1 therefore gives $0 ⪯ P (T) ⪯ c I$ . If the maximal interval ended at finite $T_{*}$ , the polynomial ODE field would be bounded on this bounded range, so $P^{'} (s)$ would be bounded and every entry of $P (s)$ would have a finite limit as $s ↑ T_{*}$ . Applying [F4] at that limiting matrix extends the solution past $T_{*}$ , contradicting maximality [F5]. Hence $P$ exists for every $s \geq 0$ .

4.1step 2.1step 3.1algebra

For $T_{2} > T_{1}$ , every control on $[0, T_{2}]$ has nonnegative cost after $T_{1}$ ; its restriction to $[0, T_{1}]$ costs at least $x_{0}^{*} P (T_{1}) x_{0}$ by step 2.1. Taking infima gives $P (T_{2}) ⪰ P (T_{1})$ . Together with the bound in step 3.1, each quadratic form $v^{*} P (T) v$ increases to a finite limit. Applying this to the coordinate vectors and their pairwise sums shows every matrix entry converges to a Hermitian limit $X ⪰ 0$ .

5.1F2step 4.1algebracontradiction

Let $Φ (P) = A^{*} P + P A - P G P + Q$ . By step 4.1 and continuity, $P^{'} (T) = Φ (P (T)) \to Φ (X)$ . If $Φ (X) \neq 0$ , polarization gives a vector $v$ with $v^{*} Φ (X) v \neq 0$ . Then the derivative of the convergent scalar function $v^{*} P (T) v$ tends to a nonzero real number, so it is eventually bounded away from zero with constant sign; integration contradicts its convergence. Thus $Φ (X) = 0$ , so $X$ solves the CARE.

6.1F2F3step 5.1algebra

Set $K = R^{- 1} B^{*} X$ and $A_{c} = A - B K = A - G X$ . The CARE gives $A_{c}^{*} X + X A_{c} = - Q - K^{*} R K$ . Along $\dot{x} = A_{c} x$ , integration over $[0, T]$ gives $\int_{0}^{T} (∥ C x (t) ∥_{2}^{2} + u (t)^{*} R u (t)) d t = x_{0}^{*} X x_{0} - x (T)^{*} X x (T) \leq x_{0}^{*} X x_{0} .$ The Cholesky factor $R = L L^{*}$ is invertible by [F3], so $u^{*} R u = ∥ L^{*} u ∥_{2}^{2}$ controls $∥ u ∥_{2}^{2}$ by the finite operator norm of $L^{- *}$ . Hence $C x, u \in L^{2} (0, \infty)$ .

7.1F1F6step 6.1algebracontradiction

By detectability [F1], choose $L$ with $A_{o} = A - L C$ Hurwitz. Then $\dot{x} = A_{o} x + w$ , where $w = B u + L C x \in L^{2}$ . Since $x$ is locally absolutely continuous, $w$ is locally integrable and the product rule gives $\frac{d}{d t} (e^{- t A_{o}} x (t)) = e^{- t A_{o}} w (t)$ almost everywhere. Integrating this identity from $0$ to $t$ and multiplying by $e^{t A_{o}}$ proves $x (t) = e^{t A_{o}} x_{0} + \int_{0}^{t} e^{(t - s) A_{o}} w (s) d s$ . From [F6], there are $M, α > 0$ with $∥ e^{t A_{o}} ∥_{2} \leq M e^{- α t}$ after absorbing the finite polynomial factor into a smaller exponential rate. The initial term tends to zero. For the integral, split at a fixed $S$ : the portion $0 \leq s \leq S$ tends to zero as $t \to \infty$ ; by Cauchy–Schwarz the tail is at most $M (2 α)^{- 1 / 2} ∥ w ∥_{L^{2} (S, \infty)}$ , which tends to zero as $S \to \infty$ . Thus $x (t) \to 0$ . Since this holds for every initial state, no eigenvalue of $A_{c}$ can have nonnegative real part: an eigenvector for such an eigenvalue would not decay. Therefore $A_{c}$ is Hurwitz.

8.1F1F2F3step 2.1step 6.1step 7.1algebra

For any admissible control of finite infinite-horizon cost, $u, C x \in L^{2}$ . Repeating the stable-convolution argument in step 7.1 gives $x (T) \to 0$ . The same square-completion identity as step 2.1, now with constant $S = X$ , yields $J_{T} (u) = x_{0}^{*} X x_{0} - x (T)^{*} X x (T) + \int_{0}^{T} (u + K x)^{*} R (u + K x) d t .$ Taking $T \to \infty$ gives $J_{\infty} (u) \geq x_{0}^{*} X x_{0}$ . The feedback in step 6.1 has $u + K x = 0$ and $x (T) \to 0$ , hence attains equality.

9.1F2F6step 6.1step 7.1algebra∎

Let $Y ⪰ 0$ be any other CARE solution. Repeating steps 6.1–7.1 with $Y$ proves $A_{Y} = A - G Y$ is Hurwitz. Subtracting the CAREs and using $X G X - Y G Y = P G (X - Y) + (X - Y) G Y with P = X$ gives $A_{c}^{*} (X - Y) + (X - Y) A_{Y} = 0$ . Hence the derivative of $e^{t A_{c}^{*}} (X - Y) e^{t A_{Y}}$ is zero, so this matrix equals $X - Y$ for every $t \geq 0$ . Both exponential factors tend to zero by [F6], forcing $X - Y = 0$ . Thus $X$ is the unique positive-semidefinite solution, and in particular the unique stabilizing one.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution

Statement

Let $A \in F^{n \times n}$ , $B \in F^{n \times m}$ , $C \in F^{p \times n}$ , $R = R^{*} ≻ 0$ , and $Q = C^{*} C$ . Assume $(A, B)$ is discretely stabilizable and $(A, C)$ discretely detectable, using Stabilizability and detectability for continuous and discrete linear systems. Then the DARE of Standard CARE and DARE data, equations, and conventions has exactly one Hermitian positive-semidefinite solution $X$ . For the equivalent Riccati map $f (P) = Q + A^{*} P (I + G P)^{- 1} A$ , its finite-horizon iterates $P_{0} = 0$ , $P_{k + 1} = f (P_{k})$ satisfy $0 ⪯ P_{k} ↑ X$ . For all Hermitian positive-semidefinite $Y, Z$ , $f (Y) - f (Z) = A_{c} (Y)^{*} (Y - Z) A_{c} (Z), A_{c} (Y) = (I + G Y)^{- 1} A .$ The solution satisfies $R + B^{*} X B ≻ 0$ , and its closed loop $A_{c} = A - B (R + B^{*} X B)^{- 1} B^{*} X A$ is Schur stable. For each $x_{0}$ , the infinite-horizon discrete cost $\inf_{(u_{k})} \sum_{k = 0}^{\infty} (x_{k}^{*} Q x_{k} + u_{k}^{*} R u_{k}), x_{k + 1} = A x_{k} + B u_{k},$ over sequences with finite cost equals $x_{0}^{*} X x_{0}$ and is attained by $u_{k} = - K_{d} x_{k}$ . Singular $A$ is allowed throughout; no inverse of $A$ is used.

Facts & Assumptions

Given: The finite matrices in the statement, discrete stabilizability/detectability, $R ≻ 0$ , $Q = C^{*} C$ , and the discrete-time dynamics.

[F1]

Stabilizability and detectability for continuous and discrete linear systems: discrete stabilizability/detectability mean there exist a feedback/injection making the corresponding matrix Schur stable.

[F2]

Standard CARE and DARE data, equations, and conventions: $G = B R^{- 1} B^{*}$ and the DARE residual and feedback are defined there.

[F3]

Powers of a Schur-stable matrix decay geometrically up to a polynomial factor: if $M$ is Schur stable, then for any $r$ with $ρ (M) < r < 1$ , $∥ M^{k} ∥_{2} \leq C_{r} r^{k}$ .

[F4]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: $R ≻ 0$ gives an invertible factor $R = L L^{*}$ .

[F5]

A non-negative operator has a unique non-negative square root: if $P ⪰ 0$ and $v^{*} P v = 0$ , then $P v = 0$ .

[F6]

Rank-nullity: $\dim_{F} V = nullity T + rank T$ : an injective endomorphism of a finite-dimensional space is invertible.

Proof

1.1F2F4algebrainduction

Define $P_{0} = 0$ and recursively $S_{j} = R + B^{*} P_{j} B, K_{j} = S_{j}^{- 1} B^{*} P_{j} A, P_{j + 1} = Q + A^{*} P_{j} A - A^{*} P_{j} B S_{j}^{- 1} B^{*} P_{j} A .$ If $P_{j} ⪰ 0$ , then for nonzero $v$ , $v^{*} S_{j} v = v^{*} R v + (B v)^{*} P_{j} (B v) > 0$ , so $S_{j}^{- 1}$ exists. For each $x, u$ , expansion and completion of the positive square gives $x^{*} Q x + u^{*} R u + (A x + B u)^{*} P_{j} (A x + B u) = x^{*} P_{j + 1} x + (u + K_{j} x)^{*} S_{j} (u + K_{j} x) .$ Thus $x^{*} P_{j + 1} x$ is the finite-horizon value for $j + 1$ stages, attained by the minimizing first control; induction gives $P_{j} ⪰ 0$ .

1.2F2F5F6algebra

For positive-semidefinite $P, Q$ , if $(I + P Q) v = 0$ , multiplication by $v^{*} Q$ gives $v^{*} Q v + (Q v)^{*} P (Q v) = 0$ . Both terms are nonnegative, so [F5] gives $Q v = 0$ and then $v = 0$ . Interchanging $P, Q$ proves the same for $I + Q P$ . Thus $I + Y G$ , $I + G Y$ , $I + G Z$ , and $I + Z G$ are injective and hence invertible by [F6]. Since $(I + Y G) Y = Y (I + G Y)$ , multiplication by the established inverses gives $(I + Y G)^{- 1} Y = Y (I + G Y)^{- 1}$ . Further, multiplying both sides of $Y (I + G Y)^{- 1} - Z (I + G Z)^{- 1} = (I + Y G)^{- 1} (Y - Z) (I + G Z)^{- 1}$ by $I + Y G$ on the left and $I + G Z$ on the right reduces both sides to $Y - Z$ . Substitution into $f (Y) - f (Z)$ proves the difference identity in the Statement.

2.1F1F3step 1.1algebra

Longer horizons add nonnegative stage costs, so their value matrices increase in the Loewner order: $0 ⪯ P_{j} ⪯ P_{j + 1}$ . By stabilizability [F1], choose $K_{0}$ so $A_{0} = A - B K_{0}$ is Schur stable. Under that fixed feedback the cost is bounded by $\sum_{k \geq 0} (∥ C ∥_{2}^{2} + ∥ K_{0}^{*} R K_{0} ∥_{2}) ∥ A_{0}^{k} x_{0} ∥_{2}^{2} \leq c ∥ x_{0} ∥_{2}^{2},$ because [F3] gives a summable geometric-square bound. Therefore $P_{j} ⪯ c I$ . The forms on $e_{i}$ , $e_{i} + e_{j}$ , and $e_{i} + i e_{j}$ are bounded and monotone; they determine the diagonal entries and the real and imaginary parts of each Hermitian off-diagonal entry. Thus all entries converge to a Hermitian $X ⪰ 0$ .

3.1F2F4step 1.1step 2.1algebra

The update map is continuous on $P ⪰ 0$ : $R + B^{*} P B ⪰ R ≻ 0$ , so its inverse varies continuously there. Passing to the limit in step 1.1 gives the DARE for $X$ , and the same inequality gives $R + B^{*} X B ≻ 0$ .

4.1F1F2step 1.1step 3.1algebra

Put $S = R + B^{*} X B$ , $K = S^{- 1} B^{*} X A$ , and $A_{c} = A - B K$ . The square identity in step 1.1 with $P_{j} = X$ yields $x^{*} Q x + u^{*} R u + (A x + B u)^{*} X (A x + B u) - x^{*} X x = (u + K x)^{*} S (u + K x) .$ For $u = - K x$ , summing from $k = 0$ to $N - 1$ gives total stage cost $x_{0}^{*} X x_{0} - x_{N}^{*} X x_{N} \leq x_{0}^{*} X x_{0}$ . Thus $u, C x \in ℓ^{2}$ .

5.1F1F3step 4.1algebracontradiction

By detectability [F1], choose $L$ such that $A_{o} = A - L C$ is Schur stable. Along the feedback trajectory, $x_{k + 1} = A_{o} x_{k} + w_{k}, w_{k} = B u_{k} + L C x_{k} \in ℓ^{2} .$ Variation of constants gives $x_{k} = A_{o}^{k} x_{0} + \sum_{j = 0}^{k - 1} A_{o}^{k - 1 - j} w_{j}$ . The first term tends to zero by [F3]. For any fixed $J$ , the finite sum over $j < J$ also tends to zero. The remaining sum is bounded by $(\sum_{ℓ \geq 0} ∥ A_{o}^{ℓ} ∥_{2}^{2})^{1 / 2} (\sum_{j \geq J} ∥ w_{j} ∥_{2}^{2})^{1 / 2} .$ The first factor is finite by [F3], and the second tends to zero as $J \to \infty$ . Hence $x_{k} \to 0$ . This holds for every initial state, so no eigenvalue of $A_{c}$ can satisfy $∣ λ ∣ \geq 1$ ; therefore $A_{c}$ is Schur stable.

6.1F1F2step 4.1step 5.1algebra

For any finite-cost control, $u, C x \in ℓ^{2}$ ; the same detectability argument in step 5.1, now with its state equation, gives $x_{k} \to 0$ . Summing the square identity in step 4.1 and taking $N \to \infty$ gives cost at least $x_{0}^{*} X x_{0}$ . The stabilizing feedback makes the square term zero and has $x_{N} \to 0$ , so it attains equality.

7.1F2F3step 5.1step 1.2algebra∎

Let $Y ⪰ 0$ be another DARE solution. Step 5.1 applied to $Y$ shows its closed loop $A_{Y} = (I + G Y)^{- 1} A$ is Schur stable. Since both $X$ and $Y$ are fixed points, step 1.2 gives $X - Y = A_{c} (X)^{*} (X - Y) A_{Y}$ . Iteration yields $X - Y = (A_{c} (X)^{*})^{k} (X - Y) A_{Y}^{k}$ . By [F3], both powers tend to zero, so the right side tends to zero and $X = Y$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

The DARE doubling recurrence composes two Riccati steps and preserves positive semidefiniteness

Statement

For Hermitian $G, H ⪰ 0$ , define $Φ_{G} (X) = X (I + G X)^{- 1}$ and $f (X) = H + A^{*} Φ_{G} (X) A$ on $X ⪰ 0$ . One step of the exact inverse recurrence in Finite-budget structure-preserving doubling iteration for the DARE is well-defined, preserves $G_{j}, H_{j} ⪰ 0$ , and its updated triple satisfies $f \circ f (X) = H_{1} + A_{1}^{*} X (I + G_{1} X)^{- 1} A_{1},$ where $A_{1} = A (I + G H)^{- 1} A, G_{1} = G + A (I + G H)^{- 1} G A^{*}, H_{1} = H + A^{*} H (I + G H)^{- 1} A .$ Consequently, starting from $(A, G, H)$ , the exact recurrence satisfies $H_{j} = f^{2^{j}} (0)$ after $j$ updates. These claims concern exact arithmetic; the rounded branch has only its separately reported diagnostics.

Facts & Assumptions

Given: Finite matrices $A$ and Hermitian positive-semidefinite $G, H$ over $F \in {R, C}$ .

[F1]

Finite-budget structure-preserving doubling iteration for the DARE: the exact-mode update formulas are $A_{1} = A (I + G H)^{- 1} A$ , $G_{1} = G + A (I + G H)^{- 1} G A^{*}$ , and $H_{1} = H + A^{*} H (I + G H)^{- 1} A$ .

[F2]

Standard CARE and DARE data, equations, and conventions: for $G = B R^{- 1} B^{*}$ , the DARE map is $X \mapsto Q + A^{*} X (I + G X)^{- 1} A$ .

[F3]

A non-negative operator has a unique non-negative square root: a positive-semidefinite matrix has a positive-semidefinite square root.

Proof

1.1F1F3algebra

If $(I + G H) v = 0$ , then multiplication by $v^{*} H$ gives $v^{*} H v + (H v)^{*} G (H v) = 0.$ Both terms are nonnegative, so $H v = 0$ and then $v = 0$ . Thus $I + G H$ is invertible; the same argument applies to $I + H G$ . The identities $(I + G H)^{- 1} G = G (I + H G)^{- 1} = G^{1 / 2} (I + G^{1 / 2} H G^{1 / 2})^{- 1} G^{1 / 2},$ $H (I + G H)^{- 1} = (I + H G)^{- 1} H = H^{1 / 2} (I + H^{1 / 2} G H^{1 / 2})^{- 1} H^{1 / 2}$ follow by multiplication and the push-through identity. Their middle matrices are positive definite, so both displayed products are Hermitian positive semidefinite. Therefore the updates in [F1] give $G_{1}, H_{1} ⪰ 0$ and use only an inverse already proved to exist.

1.2F1F2algebra

For any invertible displayed factors, direct multiplication gives the resolvent identity $Φ_{G} (X) - Φ_{G} (Y) = (I + X G)^{- 1} (X - Y) (I + G Y)^{- 1},$ and the push-through identity $(I + U V)^{- 1} U = U (I + V U)^{- 1}$ . For $X ≻ 0$ , $Φ_{G} (X)^{- 1} = X^{- 1} + G$ . Put $U = Φ_{G} (X)$ and $Y = A^{*} U A$ . Applying the resolvent identity at $H + Y$ and $H$ gives $Φ_{G} (H + Y) - Φ_{G} (H) = (I + (H + Y) G)^{- 1} Y (I + G H)^{- 1} .$ Since $I + (H + Y) G = (I + H G) + Y G$ , multiplication verifies $(I + (H + Y) G)^{- 1} Y = (I + H G)^{- 1} Y (I + G (I + H G)^{- 1} Y)^{- 1} .$ Substituting $Y = A^{*} U A$ and applying push-through twice rewrites this difference as $(I + H G)^{- 1} A^{*} (U^{- 1} + A G (I + H G)^{- 1} A^{*})^{- 1} A (I + G H)^{- 1} .$ Using $U^{- 1} = X^{- 1} + G$ and [F1], the middle inverse is $X (I + G_{1} X)^{- 1}$ . Now $f (f (X)) - H_{1} = A^{*} (Φ_{G} (H + Y) - Φ_{G} (H)) A$ . Its left factor is $A^{*} (I + H G)^{- 1} A^{*} = A_{1}^{*}$ and its right factor is $A (I + G H)^{- 1} A = A_{1}$ . Adding $H_{1} = H + A^{*} Φ_{G} (H) A$ proves the composition formula for $X ≻ 0$ .

2.1F1step 1.1step 1.2inductionalgebra∎

For singular $X ⪰ 0$ , replace it by $X + ε I$ in step 1.2 and let $ε ↓ 0$ . Step 1.1 guarantees every $I + G (X + ε I)$ and $I + G_{1} (X + ε I)$ is invertible; matrix inversion is continuous at these invertible limits. Hence the composition identity extends to every $X ⪰ 0$ , including singular $A$ and singular $X$ . By induction on $j$ , the updated Riccati map is $f^{2^{j}}$ and its value at zero is $H_{j}$ .

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The stabilizing CARE solution is the Hamiltonian stable invariant graph

Statement

Let $X ⪰ 0$ be the stabilizing CARE solution from Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution, let $G = B R^{- 1} B^{*}$ , and define $H = [\begin{array}{cc} A & - G \\ - Q & - A^{*} \end{array}], A_{c} = A - G X .$ Then $H [\begin{array}{c} I \\ X \end{array}] = [\begin{array}{c} I \\ X \end{array}] A_{c} .$ Moreover, $H$ has exactly $n$ eigenvalues in the open left half-plane and $n$ in the open right half-plane, none on the imaginary axis, and $Ran [\begin{array}{c} I \\ X \end{array}]$ is its stable invariant subspace.

Facts & Assumptions

Given: The standard CARE data and the Hermitian positive-semidefinite stabilizing solution $X$ .

[F1]

Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution: $A_{c} = A - G X$ is Hurwitz and $A^{*} X + X A - X G X + Q = 0$ .

[F2]

Standard CARE and DARE data, equations, and conventions: $G = B R^{- 1} B^{*}$ is Hermitian positive semidefinite and $^{*}$ is the adjoint.

[F3]

[F4]

For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ : over $C$ , eigenvalues are precisely the roots of the characteristic polynomial.

[F5]

Every nonconstant polynomial in $C [x]$ splits into linear factors: each degree- $n$ complex characteristic polynomial has $n$ roots counted with algebraic multiplicity.

[F6]

Every finite-dimensional endomorphism over an algebraically closed field has Jordan form: generalized eigenspaces span the complex space and their dimensions equal the corresponding algebraic multiplicities.

Proof

1.1F1F2algebra

Block multiplication gives $H [\begin{array}{c} I \\ X \end{array}] = [\begin{array}{c} A - G X \\ - Q - A^{*} X \end{array}] .$ By [F1], $- Q - A^{*} X = X A - X G X = X (A - G X)$ , proving the graph identity.

2.1F1F3F4F5F6step 1.1algebra∎

Set $T_{X} = [\begin{array}{cc} I & 0 \\ X & I \end{array}]$ , whose inverse is $[\begin{array}{cc} I & 0 \\ - X & I \end{array}]$ . Using [F1], $T_{X}^{- 1} H T_{X} = [\begin{array}{cc} A - G X & - G \\ 0 & - (A - G X)^{*} \end{array}] .$ The eigenvalues of the first diagonal block lie in the open left half-plane by [F1]. If $λ$ is a root of its characteristic polynomial, then $- \overline{λ}$ is a root of the characteristic polynomial of $- (A - G X)^{*}$ , since $\det (- \overline{λ} I + (A - G X)^{*}) = \overline{\det (- λ I + (A - G X))} = 0$ ; these reflected roots lie in the open right half-plane. By [F5] each diagonal characteristic polynomial has degree $n$ and splits into $n$ roots counted with algebraic multiplicity. The characteristic polynomial factorization [F3] and root/eigenvalue connection [F4] therefore give exactly $n$ eigenvalues of $H$ in each open half-plane and none on the imaginary axis. The first coordinate subspace is invariant and its restriction has the stable spectrum of $A - G X$ . Any generalized eigenvector of the displayed triangular matrix for a stable eigenvalue has trailing component in the kernel of a power of $(- (A - G X)^{*} - λ I)$ ; that matrix is invertible because the trailing spectrum is in the open right half-plane, so the trailing component is zero. By [F6] these generalized eigenspaces have total dimension equal to the stable algebraic multiplicity $n$ from [F5], so they fill the first coordinate subspace, which is therefore the stable invariant subspace. Applying $T_{X}$ maps it to $Ran [\begin{array}{c} I \\ X \end{array}]$ .

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The stabilizing DARE solution is the stable deflating graph of a regular symplectic pencil

Statement

Let $X ⪰ 0$ be the stabilizing DARE solution, $G = B R^{- 1} B^{*}$ , and $N = [\begin{array}{cc} A & 0 \\ - Q & I \end{array}], M = [\begin{array}{cc} I & G \\ 0 & A^{*} \end{array}], A_{c} = A - B (R + B^{*} X B)^{- 1} B^{*} X A .$ Then $N [\begin{array}{c} I \\ X \end{array}] = M [\begin{array}{c} I \\ X \end{array}] A_{c} .$ The pencil $(N, M)$ is regular. Its homogeneous determinant has n roots strictly inside the unit disk and n roots strictly outside the closed unit disk, with infinite roots counted in the latter group. Thus it has no unit-circle roots, even if $A$ is singular, and $Ran [\begin{array}{c} I \\ X \end{array}]$ is its stable deflating graph.

Facts & Assumptions

Given: The DARE data and stabilizing solution from Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution.

[F1]

Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution: $X = X^{*} ⪰ 0$ , $S = R + B^{*} X B ≻ 0$ , and $A_{c} = A - B S^{- 1} B^{*} X A$ is Schur stable.

[F2]

Standard CARE and DARE data, equations, and conventions: $G = B R^{- 1} B^{*}$ and the DARE residual is $Q + A^{*} X A - A^{*} X B S^{- 1} B^{*} X A - X$ .

[F3]

A non-negative operator has a unique non-negative square root: each finite-dimensional non-negative self-adjoint matrix has a non-negative square root.

[F4]

Regular matrix pencils and homogeneous generalized eigenvalues: a square pencil is regular when its homogeneous determinant is not the zero polynomial.

[F5]

For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ : determinants multiply under finite square matrix products, so the determinant is unchanged by the determinant-one shears used below.

[F6]

The determinant of a triangular matrix is the product of its diagonal entries: the determinant of a triangular matrix is the product of its diagonal entries; in particular, the two unit-triangular shears below have determinant one.

[F7]

The homogeneous determinant factors across a block upper triangular pencil: the homogeneous determinant of a block upper-triangular pencil factors across its diagonal blocks.

[F8]

For every finite-dimensional space, $σ_{F} (T)$ is exactly the set of roots in $F$ of $χ_{T}$ : finite eigenvalues of a matrix are exactly the roots of its characteristic polynomial.

[F9]

Every nonconstant polynomial in $C [x]$ splits into linear factors: each complex characteristic polynomial of degree $n$ has $n$ roots counted with algebraic multiplicity.

[F10]

Every finite-dimensional endomorphism over an algebraically closed field has Jordan form: generalized eigenvectors span a complex finite-dimensional space, with total dimension counted by algebraic multiplicity.

Proof

1.1F1F2F3algebra

The matrix $I + G X$ is invertible. Indeed, if $(I + G X) v = 0$ , multiplication by $v^{*} X$ gives $v^{*} X v + (X v)^{*} G (X v) = 0.$ Both summands are nonnegative. By [F3], $v^{*} X v = 0$ implies $X v = 0$ , and the original equation then gives $v = 0$ . Also $S = R + B^{*} X B ≻ 0$ by [F1]. The identity $(I + G X)^{- 1} = I - B S^{- 1} B^{*} X$ is verified by multiplying the right side by $I + G X$ : the extra term is $B [R^{- 1} - S^{- 1} - S^{- 1} (B^{*} X B) R^{- 1}] B^{*} X = 0$ , since $S = R + B^{*} X B$ . Therefore $A_{c} = (I + G X)^{- 1} A$ .

2.1F1F2step 1.1algebra

The DARE and the identity in step 1.1 imply $X - Q = A^{*} X (I + G X)^{- 1} A = A^{*} X A_{c}$ . Consequently, $N [\begin{array}{c} I \\ X \end{array}] = [\begin{array}{c} A \\ X - Q \end{array}] = [\begin{array}{c} I + G X \\ A^{*} X \end{array}] A_{c} = M [\begin{array}{c} I \\ X \end{array}] A_{c} .$ This proves the deflating graph identity.

3.1F1F4F5F6F7F8F9F10step 1.1step 2.1algebra∎

Put $T_{X} = [\begin{array}{cc} I & 0 \\ X & I \end{array}]$ and $L_{X} = [\begin{array}{cc} I & 0 \\ - A^{*} X (I + G X)^{- 1} & I \end{array}]$ . By [F6] both are block triangular with identity diagonal and determinant one. For arbitrary homogeneous coordinates $[α : β]$ , $L_{X} (β N - α M) T_{X} = [\begin{array}{cc} (I + G X) (β A_{c} - α I) & - α G \\ 0 & β I - α A_{c}^{*} \end{array}] .$ The lower-left block vanishes by $X - Q = A^{*} X A_{c}$ ; the lower-right block uses $(I + G X)^{- 1} G = G (I + X G)^{- 1}$ and $I - X (I + G X)^{- 1} G = (I + X G)^{- 1}$ . Taking determinants and using [F5] and [F7] gives $\det (β N - α M) = \det (I + G X) \det (β A_{c} - α I) \det (β I - α A_{c}^{*}) .$ The first homogeneous factor has $n$ roots, counted with multiplicity; all are finite and equal to eigenvalues of $A_{c}$ , hence strictly inside the disk by [F1] and [F8]. The roots of $A_{c}^{*}$ are the conjugates of those of $A_{c}$ , since $\det (μ I - A_{c}^{*}) = \overline{\det (\overline{μ} I - A_{c})}$ ; hence each nonzero eigenvalue of $A_{c}^{*}$ has modulus less than one. The second factor has $n$ roots, counted with multiplicity: each finite root is the reciprocal of a nonzero eigenvalue of $A_{c}^{*}$ and therefore has modulus greater than one, while every zero eigenvalue of $A_{c}^{*}$ contributes a root at $β = 0$ , which is infinite. The root counts follow from [F9], with finite eigenvalues identified by [F8]. Neither factor vanishes on $∣ α ∣ = ∣ β ∣$ , so the pencil is regular with the stated root split. The homogeneous determinant is invariant under these transforms because [F5] gives multiplicativity and both shear determinants equal one by [F6]. Finally, $(I + G X)$ is invertible by step 1.1, so $M [I; X]$ has full column rank. A Jordan basis of $A_{c}$ from [F10], together with $N [I; X] = M [I; X] A_{c}$ from step 2.1, shows that the graph carries all $n$ stable finite root chains; the determinant factorization shows there are exactly $n$ stable roots in total, so this is the stable deflating graph. This uses no inverse of $A$ .

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Verified Lyapunov residual, descent, and stability checks make an inexact Newton-Kleinman step safe

Statement

Consider a trial gain $K_{t}$ in the safeguarded-inexact branch of Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration, with $A_{t} = A - B K_{t}$ . Suppose outward certificates give $W ≻ 0$ , $μ > 0$ , $A_{t}^{*} W + W A_{t} ⪯ - μ I$ , an inverse bound $κ \geq ∥ L_{A_{t}}^{- 1} ∥_{F \to F}$ , a residual bound $r$ for a Hermitian approximation $\tilde{P}$ to $A_{t}^{*} P + P A_{t} + Q + K_{t}^{*} R K_{t} = 0,$ and an upper bound $η \geq λ_{\max} (\tilde{P} - X_{j})$ with $η + κ r \leq 0$ . Then $A_{t}$ is Hurwitz, its exact cost matrix $P_{t}$ exists and is positive semidefinite, and $P_{t} ⪯ X_{j}$ . Thus every accepted line-search step preserves stability and does not increase the exact closed-loop cost matrix.

Facts & Assumptions

Given: The current exact cost matrix $X_{j}$ , trial gain, residual data, and verified bounds in the statement.

[F1]

Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration: a trial is accepted only if its Lyapunov margin, inverse bound, residual bound, and descent upper bound satisfy the stated tests.

[F2]

Standard CARE and DARE data, equations, and conventions: $Q = C^{*} C ⪰ 0$ and $R ≻ 0$ .

[F3]

The Hurwitz Lyapunov integral is the unique solution and has the stated positivity: for Hurwitz $A_{t}$ , the solution of $A_{t}^{*} P + P A_{t} + S = 0$ is the unique integral $\int_{0}^{\infty} e^{t A_{t}^{*}} S e^{t A_{t}} d t$ , and is positive semidefinite for $S ⪰ 0$ .

[F4]

A Sylvester equation is uniquely solvable exactly when the spectra are disjoint: when $A_{t}$ is Hurwitz, the Lyapunov operator $E \mapsto A_{t}^{*} E + E A_{t}$ is invertible.

[F5]

Verified point and uniform linear residual certificate data specifies bounds for an approximate-inverse defect and a preconditioned linear residual, with a usable certificate requiring $q < 1$ . The raw Lyapunov residual bound $r$ and inverse-norm bound $κ$ in this proposition are separate hypotheses of the Statement.

Proof

1.1F1givenalgebra

If $A_{t} v = λ v$ with $v \neq 0$ , the certificate gives $2 Re (λ) v^{*} W v = v^{*} (A_{t}^{*} W + W A_{t}) v \leq - μ ∥ v ∥_{2}^{2} < 0.$ Because $W ≻ 0$ , every eigenvalue has negative real part, so $A_{t}$ is Hurwitz.

2.1givenF1F2F3F4F5step 1.1algebra∎

Let $P_{t}$ be the exact solution of the Lyapunov equation; it exists uniquely by [F3] and [F4], and $P_{t} ⪰ 0$ by [F2]–[F3]. If $R_{t}$ denotes the exact residual of $\tilde{P}$ , then $L_{A_{t}} (\tilde{P} - P_{t}) = R_{t}$ . The Statement's certified inverse and raw residual bounds give $∥ \tilde{P} - P_{t} ∥_{F} \leq κ r$ ; these are distinct from the certificate quantities described in [F5]. For each unit vector $v$ , $v^{*} (P_{t} - X_{j}) v \leq v^{*} (\tilde{P} - X_{j}) v + ∥ P_{t} - \tilde{P} ∥_{2} \leq η + κ r \leq 0.$ Thus $P_{t} ⪯ X_{j}$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

A CARE residual and Lyapunov margin certify a unique stabilizing root in a matrix ball

Statement

Let $\hat{X} = {\hat{X}}^{*}$ be a CARE candidate, ${\hat{A}}_{c} = A - G \hat{X}$ , and $L (E) = {\hat{A}}_{c}^{*} E + E {\hat{A}}_{c}, F_{c} (X) = A^{*} X + X A - X G X + Q .$ Assume ${\hat{A}}_{c}$ is certified Hurwitz, $L$ is invertible on Hermitian matrices, and outward-verified bounds satisfy $κ \geq ∥ L^{- 1} ∥_{F \to F}, r \geq ∥ F_{c} (\hat{X}) ∥_{F}, g \geq ∥ G ∥_{2},$ with $ρ > 0$ such that $κ (r + g ρ^{2}) \leq ρ, 2 κ g ρ < 1.$ Then there is exactly one Hermitian CARE root in the closed Frobenius ball $∥ X - \hat{X} ∥_{F} \leq ρ$ .

If also a verified Hermitian $W ≻ 0$ and $γ > 0$ satisfy $- ({\hat{A}}_{c}^{*} W + W {\hat{A}}_{c}) ⪰ γ I, 2 ∥ W ∥_{2} g ρ < γ,$ then that root is Hurwitz-stabilizing. Under the standard CARE hypotheses of Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution, it is the unique stabilizing positive-semidefinite solution.

Facts & Assumptions

Given: The CARE data and matrix norms of Standard CARE and DARE data, equations, and conventions, a Hermitian candidate, and the outward-verified constants in the Statement.

[F1]

Standard CARE and DARE data, equations, and conventions: $F_{c} (X) = A^{*} X + X A - X G X + Q$ and $A_{c} (X) = A - G X$ .

[F2]

A Sylvester equation is uniquely solvable exactly when the spectra are disjoint: $E \mapsto {\hat{A}}_{c}^{*} E + E {\hat{A}}_{c}$ is invertible when $σ ({\hat{A}}_{c}^{*}) \cap (- σ ({\hat{A}}_{c})) = \emptyset$ ; this holds for Hurwitz ${\hat{A}}_{c}$ .

[F3]

Verified point and uniform linear residual certificate data: verified certificate data are mathematical upper bounds; the definition does not claim how a computation establishes them.

[F4]

Outward-rounded operations are inclusion-isotone and enclose DAG evaluations: a finite outward-rounded expression DAG encloses every exact node value.

[F5]

Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: the operator norm is bounded by the Frobenius norm and $∥ A X B ∥_{F} \leq ∥ A ∥_{2} ∥ X ∥_{F} ∥ B ∥_{2}$ .

[F6]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: operator norms are submultiplicative.

[F7]

Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution: under continuous stabilizability and detectability the stabilizing Hermitian positive-semidefinite CARE solution is unique.

[F8]

The Hurwitz Lyapunov integral is the unique solution and has the stated positivity: for Hurwitz $A_{c}$ , the solution of $A_{c}^{*} Y + Y A_{c} = - S$ is the convergent integral $Y = \int_{0}^{\infty} e^{t A_{c}^{*}} S e^{t A_{c}} d t$ , and is positive semidefinite when $S ⪰ 0$ .

[F9]

Every finite-dimensional normed space is Banach: every finite-dimensional normed space is complete, so a Cauchy sequence in the Hermitian matrix ball converges there.

[A1]

The numerical constants $κ, r, g, γ$ and $∥ W ∥_{2}$ are supplied as rigorous upper or lower bounds by the verifier; without valid enclosures this theorem gives no certificate.

Proof

1.1F1F2givenalgebra

For Hermitian $E$ , direct expansion gives $F_{c} (\hat{X} + E) = F_{c} (\hat{X}) + L (E) - E G E .$ Thus the root equation is equivalent to $E = T (E) : = - L^{- 1} F_{c} (\hat{X}) + L^{- 1} (E G E) .$

2.1A1F3F4F5F9step 1.1algebra

By [F5], $∥ E G E ∥_{F} \leq g ∥ E ∥_{F}^{2}$ . The assumptions give $∥ T (E) ∥_{F} \leq κ (r + g ρ^{2}) \leq ρ$ on the closed ball. Also $E G E - F G F = (E - F) G E + F G (E - F),$ so [F5] gives $∥ T (E) - T (F) ∥_{F} \leq 2 κ g ρ ∥ E - F ∥_{F}$ there. The Hermitian matrices form a closed finite-dimensional normed space, complete by [F9]. Iterating $T$ from zero gives successive differences bounded by a geometric sequence of ratio $2 κ g ρ < 1$ , hence a Cauchy sequence. Its limit lies in the closed ball and is a fixed point by continuity. Any two fixed points have distance at most that ratio times their distance, so they coincide.

3.1A1F1F2F6F7F8step 2.1algebra∎

Let $X = \hat{X} + E$ be this root. Its closed loop is $A_{c} (X) = {\hat{A}}_{c} - G E$ . Expanding, $A_{c} (X)^{*} W + W A_{c} (X) = {\hat{A}}_{c}^{*} W + W {\hat{A}}_{c} - E G W - W G E .$ By [F6] and [A1], $∥ E G W + W G E ∥_{2} \leq 2 ∥ W ∥_{2} g ρ < γ$ . Hence the left side is negative definite. For any eigenpair $A_{c} (X) v = λ v$ , $v \neq 0$ , this gives $2 Re (λ) v^{*} W v < 0$ ; since $W ≻ 0$ , $Re λ < 0$ . Thus the root is stabilizing. Its CARE identity also gives $A_{c} (X)^{*} X + X A_{c} (X) = - (Q + X G X) .$ Here $Q + X G X ⪰ 0$ because $Q, G ⪰ 0$ . Since $A_{c} (X)$ is Hurwitz, [F8] says the unique Lyapunov solution is its positive-semidefinite integral; uniqueness from [F2] identifies that solution with $X$ . Thus $X ⪰ 0$ , and [F7] identifies it with the unique stabilizing positive-semidefinite solution.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

A DARE residual, Stein inverse bound, and Lyapunov margin certify a stabilizing root

Statement

Let $\hat{X} = {\hat{X}}^{*}$ be a DARE candidate, $S (X) = R + B^{*} X B$ , $K (X) = S (X)^{- 1} B^{*} X A$ , $A_{c} (X) = A - B K (X)$ , and let $F_{d} (X) = Q + A^{*} X A - A^{*} X B S (X)^{- 1} B^{*} X A - X .$ Suppose $S (\hat{X}) ⪰ δ_{0} I$ is outward-certified. For a proposed radius $ρ > 0$ put $a = ∥ A ∥_{2}, b = ∥ B ∥_{2}, m = ∥ \hat{X} ∥_{F} + ρ, δ = δ_{0} - b^{2} ρ .$ Require $δ > 0$ and define $L_{K} = \frac{a b}{δ} + \frac{a b^{3} m}{δ^{2}}, M_{c} = a + \frac{a b^{2} m}{δ}, L_{c} = b L_{K}, L_{D} = 2 M_{c} L_{c} .$ Let $D (E) = A_{c} (\hat{X})^{*} E A_{c} (\hat{X}) - E$ be invertible on Hermitian matrices, with outward-certified $κ \geq ∥ D^{- 1} ∥_{F \to F}$ and $r \geq ∥ F_{d} (\hat{X}) ∥_{F}$ . If $κ (r + L_{D} ρ^{2} / 2) \leq ρ, κ L_{D} ρ < 1,$ there is exactly one Hermitian DARE root in the closed Frobenius $ρ$ -ball, and $R + B^{*} X B ⪰ δ I$ throughout that ball.

For the stabilizing branch, additionally suppose ${\hat{A}}_{c} = A_{c} (\hat{X})$ is Schur stable and an outward-certified $W ≻ 0$ satisfies $W - {\hat{A}}_{c}^{*} W {\hat{A}}_{c} ⪰ γ I .$ If, with $η = L_{c} ρ$ , $∥ W ∥_{2} (2 M_{c} η + η^{2}) < γ,$ then the root is Schur-stabilizing. Under the standard DARE hypotheses of Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution, it is the unique stabilizing positive-semidefinite solution.

Facts & Assumptions

Given: The DARE data and residual map of Standard CARE and DARE data, equations, and conventions, a Hermitian candidate, and the verified constants in the Statement.

[F1]

Standard CARE and DARE data, equations, and conventions: $S (X) = R + B^{*} X B$ , $A_{c} (X) = A - B S (X)^{- 1} B^{*} X A$ , and $F_{d} (X) = Q + A^{*} X A - A^{*} X B S (X)^{- 1} B^{*} X A - X$ .

[F2]

Verified point and uniform linear residual certificate data specifies mathematical bounds for a linear approximate-inverse defect and preconditioned residual, and does not prescribe how to establish them. The DARE bounds used here are the separate hypotheses in [A1].

[F3]

Outward-rounded operations are inclusion-isotone and enclose DAG evaluations: a finite outward-rounded expression DAG encloses every exact node value.

[F4]

Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: $∥ A X B ∥_{F} \leq ∥ A ∥_{2} ∥ X ∥_{F} ∥ B ∥_{2}$ and $∥ X ∥_{2} \leq ∥ X ∥_{F}$ .

[F5]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: operator norms are submultiplicative.

[F6]

Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution: under the standard discrete hypotheses there is a unique stabilizing positive-semidefinite DARE solution.

[F7]

Powers of a Schur-stable matrix decay geometrically up to a polynomial factor: if $A_{c}$ is Schur stable, then $∣ A_{c}^{k} ∣_{2} \to 0$ geometrically.

[F8]

Every finite-dimensional normed space is Banach: every finite-dimensional normed space is complete, so a Cauchy sequence in the Hermitian matrix ball converges there.

[A1]

The lower eigenvalue bound $δ_{0}$ , norm bounds, residual bound, inverse bound $κ$ , and Lyapunov margin are outward-verified inputs. If any bound is unavailable, this item supplies no certificate.

Proof

1.1F1A1F3F4F5algebra

For any Hermitian $E$ with $∥ E ∥_{F} \leq ρ$ , [F3] and [F4] give $S (\hat{X} + E) = S (\hat{X}) + B^{*} E B ⪰ (δ_{0} - b^{2} ρ) I = δ I .$ Thus $S (X)$ is invertible on the ball and $∥ S (X)^{- 1} ∥_{2} \leq δ^{- 1}$ . The resolvent identity gives $∥ S (X)^{- 1} - S (Y)^{- 1} ∥_{2} \leq b^{2} δ^{- 2} ∥ X - Y ∥_{F} .$ Using $K (X) = S (X)^{- 1} B^{*} X A$ and splitting the difference into the change in $X$ and the change in $S^{- 1}$ yields $∥ K (X) - K (Y) ∥_{F} \leq L_{K} ∥ X - Y ∥_{F}, ∥ A_{c} (X) ∥_{2} \leq M_{c}, ∥ A_{c} (X) - A_{c} (Y) ∥_{2} \leq L_{c} ∥ X - Y ∥_{F} .$

2.1F1A1F4F5step 1.1algebra

Differentiating $S^{- 1} S = I$ gives $d (S^{- 1}) [E] = - S^{- 1} (B^{*} E B) S^{- 1}$ . Substituting this in the derivative of $F_{d}$ and using $K = S^{- 1} B^{*} X A$ gives $F_{d}^{'} (X) [E] = A_{c} (X)^{*} E A_{c} (X) - E .$ Consequently, for $D_{X} = F_{d}^{'} (X)$ and $D_{Y} = F_{d}^{'} (Y)$ , [F4]–[F5] give $∥ D_{X} - D_{Y} ∥_{F \to F} \leq (∥ A_{c} (X) ∥_{2} + ∥ A_{c} (Y) ∥_{2}) ∥ A_{c} (X) - A_{c} (Y) ∥_{2} \leq L_{D} ∥ X - Y ∥_{F} .$ Integrating the derivative along the segment from $\hat{X}$ to $\hat{X} + E$ gives a Taylor remainder $R (E)$ with $F_{d} (\hat{X} + E) = F_{d} (\hat{X}) + D (E) + R (E), ∥ R (E) ∥_{F} \leq L_{D} ∥ E ∥_{F}^{2} / 2.$

3.1A1F2F8step 2.1algebra

The root equation is the fixed-point equation $E = T (E) : = - D^{- 1} F_{d} (\hat{X}) - D^{- 1} R (E) .$ The bounds in [A1], separate from the linear certificate data in [F2], make $T$ a self-map of the closed ball. For $E, F$ in that ball, integrating $D_{X} - D$ along the segment between them gives $∥ R (E) - R (F) ∥_{F} \leq L_{D} ρ ∥ E - F ∥_{F},$ so $T$ has contraction factor at most $κ L_{D} ρ < 1$ . Iteration from zero has successive differences bounded by a geometric sequence, hence is Cauchy. The closed Hermitian ball is complete by [F8], so the sequence converges in the ball; continuity makes its limit a fixed point. The same contraction inequality makes it unique.

4.1A1F1F6F7step 3.1algebra∎

Let $X = \hat{X} + E$ be the root. Then $∥ A_{c} (X) - {\hat{A}}_{c} ∥_{2} \leq L_{c} ρ = η$ . Expanding the Stein form, $A_{c} (X)^{*} W A_{c} (X) - {\hat{A}}_{c}^{*} W {\hat{A}}_{c} = {\hat{A}}_{c}^{*} W Δ + Δ^{*} W {\hat{A}}_{c} + Δ^{*} W Δ,$ where $Δ = A_{c} (X) - {\hat{A}}_{c}$ . Its norm is at most $∥ W ∥_{2} (2 M_{c} η + η^{2}) < γ$ . Hence $W - A_{c} (X)^{*} W A_{c} (X) ≻ 0$ . For an eigenvector $A_{c} (X) v = λ v$ , this gives $(1 - ∣ λ ∣^{2}) v^{*} W v > 0$ , so $∣ λ ∣ < 1$ . Let $K = K (X)$ , $S = R + B^{*} X B$ , and $x_{k + 1} = A_{c} (X) x_{k}$ , $u_{k} = - K x_{k}$ . Since $S K = B^{*} X A$ , we have $K^{*} S K = A^{*} X B S^{- 1} B^{*} X A$ . Expanding $A_{c}^{*} X A_{c} = (A - B K)^{*} X (A - B K)$ gives $A_{c}^{*} X A_{c} = A^{*} X A - K^{*} S K - K^{*} S K + K^{*} B^{*} X B K = A^{*} X A - K^{*} S K - K^{*} R K .$ The DARE root equation therefore gives $X = Q + K^{*} R K + A_{c}^{*} X A_{c}$ , which along $x_{k + 1} = A_{c} x_{k}$ and $u_{k} = - K x_{k}$ is the exact square identity $x_{k}^{*} Q x_{k} + u_{k}^{*} R u_{k} + x_{k + 1}^{*} X x_{k + 1} = x_{k}^{*} X x_{k} .$ Summing to $N - 1$ yields $x_{0}^{*} X x_{0} = \sum_{k < N} (x_{k}^{*} Q x_{k} + u_{k}^{*} R u_{k}) + x_{N}^{*} X x_{N}$ . By [F7], $x_{N} \to 0$ , so $x_{0}^{*} X x_{0}$ is a sum of nonnegative terms; hence $X ⪰ 0$ . Now [F6] identifies it as the unique stabilizing positive-semidefinite solution.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

Exact Newton-Kleinman iteration preserves stability, decreases cost matrices, and converges quadratically locally

Statement

Assume the continuous stabilizability and detectability hypotheses of Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution. From a supplied stabilizing $K_{0}$ , define the infinite exact recurrence, for every $j \geq 0$ , by $A_{j} = A - B K_{j}, A_{j}^{*} X_{j} + X_{j} A_{j} = - (Q + K_{j}^{*} R K_{j}), K_{j + 1} = R^{- 1} B^{*} X_{j} .$ These exact Lyapunov solutions exist uniquely. Every closed loop $A_{j} = A - B K_{j}$ is Hurwitz, every exact Lyapunov matrix $X_{j}$ is positive semidefinite, and $X_{j + 1} ⪯ X_{j}$ . The sequence converges to the unique stabilizing CARE solution $X_{*}$ . Once $j$ is sufficiently large, there is a finite constant $C$ such that $∥ X_{j + 1} - X_{*} ∥_{F} \leq C ∥ X_{j} - X_{*} ∥_{F}^{2} .$ Every successful exact update of Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration agrees with this recurrence, so a finite call returns only a prefix, possibly shortened by a solver failure. Convergence and the eventual quadratic estimate concern the infinite recurrence; no such guarantee is asserted for arbitrary inexact solves.

Facts & Assumptions

Given: Continuous CARE data, continuous stabilizability/detectability, a stabilizing $K_{0}$ , and the infinite exact Lyapunov recurrence in the Statement.

[F1]

Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration: $A_{j} = A - B K_{j}$ , $A_{j}^{*} X_{j} + X_{j} A_{j} = - (Q + K_{j}^{*} R K_{j})$ , and $K_{j + 1} = R^{- 1} B^{*} X_{j}$ .

[F2]

Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution: there is a unique Hermitian positive-semidefinite stabilizing solution $X_{*}$ .

[F3]

The Hurwitz Lyapunov integral is the unique solution and has the stated positivity: a Hurwitz Lyapunov equation with positive-semidefinite forcing has its unique positive-semidefinite integral solution.

[F4]

A Hurwitz matrix exponential has a polynomial-exponential decay bound: a Hurwitz matrix exponential is bounded by a polynomial times a decaying exponential.

[F5]

Standard CARE and DARE data, equations, and conventions: $G = B R^{- 1} B^{*}$ and the CARE residual is $A^{*} X + X A - X G X + Q$ .

Proof

1.1F1F3F5giveninductioncontradiction

Suppose $A_{j}$ is Hurwitz. By [F3], the exact solution $X_{j}$ of the policy Lyapunov equation is $X_{j} = \int_{0}^{\infty} e^{t A_{j}^{*}} (Q + K_{j}^{*} R K_{j}) e^{t A_{j}} d t ⪰ 0.$ For $Δ_{j} = K_{j + 1} - K_{j}$ , expansion using $B^{*} X_{j} = R K_{j + 1}$ gives $A_{j + 1}^{*} X_{j} + X_{j} A_{j + 1} + Q + K_{j + 1}^{*} R K_{j + 1} = - Δ_{j}^{*} R Δ_{j} .$ If $A_{j + 1} v = λ v$ with $Re λ \geq 0$ , the quadratic form of the left side is $2 Re (λ) v^{*} X_{j} v + v^{*} Q v + (K_{j + 1} v)^{*} R (K_{j + 1} v) \geq 0,$ while the right side is nonpositive. Equality forces $K_{j + 1} v = 0$ and $Δ_{j} v = 0$ , hence $K_{j} v = 0$ and $A_{j} v = A v = λ v$ , contradicting that $A_{j}$ is Hurwitz. Starting from $K_{0}$ , induction proves every $A_{j}$ Hurwitz and every $X_{j} ⪰ 0$ .

2.1F1F2F3step 1.1algebra

Subtracting the Lyapunov equations for $X_{j}$ and $X_{j + 1}$ after expressing both under $A_{j + 1}$ gives $A_{j + 1}^{*} (X_{j} - X_{j + 1}) + (X_{j} - X_{j + 1}) A_{j + 1} = - Δ_{j}^{*} R Δ_{j} .$ The Lyapunov integral [F3] therefore yields $X_{j} - X_{j + 1} ⪰ 0$ . The decreasing sequence is bounded below by zero, so each quadratic form converges. Evaluating at $e_{i}$ , $e_{i} + e_{j}$ , and $e_{i} + i e_{j}$ shows convergence of every matrix entry to a Hermitian limit $X_{\infty} ⪰ 0$ . Since $K_{j + 1} = R^{- 1} B^{*} X_{j}$ , the gains also converge. Passing to the limit in the policy Lyapunov equation gives the CARE for $X_{\infty}$ ; [F2] identifies this positive-semidefinite root as $X_{*}$ .

3.1F1F2F3F4step 2.1algebra∎

Let $E_{j} = X_{j} - X_{*}$ and $A_{*} = A - B R^{- 1} B^{*} X_{*}$ . Put $D_{j} = K_{j + 1} - K_{*} = R^{- 1} B^{*} E_{j}$ . Subtract the CARE identity at $X_{*}$ from the policy Lyapunov equation under $A_{j + 1}$ to obtain $A_{j + 1}^{*} E_{j + 1} + E_{j + 1} A_{j + 1} = - D_{j}^{*} R D_{j} .$ By [F2], $A_{*}$ is Hurwitz. Choose $W = \int_{0}^{\infty} e^{t A_{*}^{*}} I e^{t A_{*}} d t ≻ 0$ using [F3], so $A_{*}^{*} W + W A_{*} = - I$ . Since $A_{j + 1} \to A_{*}$ , for all large $j$ one has $A_{j + 1}^{*} W + W A_{j + 1} ⪯ - \frac{1}{2} I$ . Along $\dot{x} = A_{j + 1} x$ , differentiation gives $\frac{d}{d t} (x^{*} W x) \leq - \frac{1}{2} ∥ x ∥_{2}^{2} \leq - \frac{1}{2 ∥ W ∥_{2}} x^{*} W x .$ Consequently $∥ e^{t A_{j + 1}} ∥_{2} \leq M e^{- α t}$ with $M = (∥ W ∥_{2} / λ_{\min} (W))^{1 / 2}$ and $α = 1 / (4 ∥ W ∥_{2})$ , uniformly for all sufficiently large $j$ . Applying the Lyapunov integral to the error equation yields $∥ E_{j + 1} ∥_{F} \leq (\int_{0}^{\infty} M^{2} e^{- 2 α t} d t) ∥ R ∥_{2} ∥ R^{- 1} B^{*} ∥_{2}^{2} ∥ E_{j} ∥_{F}^{2} .$ The integral is finite and supplies the stated local quadratic constant.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms

Definition

Inputs are finite CARE or DARE data from Standard CARE and DARE data, equations, and conventions, finite Schur or QZ sweep budgets, an adjacent-swap budget $K$ , a scalar/evaluator work budget $W$ , a positive local separation threshold $η$ , and the exact arithmetic controller or bounded outward evaluator for Finite-budget stable block reordering for Schur and QZ forms. The budget $W$ also charges every graph-product enclosure and local acceptance comparison. The graph stage also takes finite dyadic proposals $R_{g}, \hat{Y}$ for a point inverse and solution matrix, together with outward enclosures of the exact product-factor entries and the certificate data required by the applicable local residual-ball theorem. If a proposal, enclosure, or certificate is unavailable, the corresponding graph or acceptance result is inconclusive. For CARE form $H = [\begin{array}{cc} A & - G \\ - Q & - A^{*} \end{array}]$ ; for DARE form $N = [\begin{array}{cc} A & 0 \\ - Q & I \end{array}]$ and $M = [\begin{array}{cc} I & G \\ 0 & A^{*} \end{array}]$ . The procedure never forms $A^{- 1}$ and does not require a separately supplied ordered basis.

Each local residual-ball packet contains its proposed radius, residual and inverse-norm bounds, norm bounds, and the required Lyapunov or Stein witness matrices with exact factorization witnesses for positive-definite and positive-semidefinite inequalities. Check all supplied matrix equalities exactly and all scalar bounds with the finite outward evaluator. A missing witness or unresolved comparison returns inconclusive; failure of a sufficient residual-ball test alone does not reject a candidate.

For CARE, run Finite-budget computed Francis Schur reduction with explicit statuses on $H$ . For DARE, run Finite-budget QZ iteration with homogeneous status and residual output on $(N, M)$ . Propagate any budget, range, invariant-pattern, or pencil-regularity failure as an explicit inconclusive status. The returned residuals and factor backward-error certificates are those specified by the corresponding supplier items; they are not interpreted as structure-preserving perturbations.
On a successful reduction, invoke Finite-budget stable block reordering for Schur and QZ forms with the CARE strict-left-half-plane selector or DARE strict-unit-disk selector and required selected dimension $n$ . Propagate every non-ordered result as its explicit status, including boundary-spectrum, separation-inconclusive, swap-separation-inconclusive, arithmetic-inconclusive, range-failure, swap-budget-exhausted, and work-budget-exhausted. The returned exact product factors, together with Finite-budget stable block reordering has exact adjacent-swap correctness and status, certify ordering of the represented computed form and transport the original unstructured reduction residual. For CARE take the first $n$ columns of the updated Schur factor; for DARE take the first $n$ columns of the updated right QZ factor, never the left factor. If the relevant exact factor or residual certificate is unavailable, keep the corresponding diagnostic inconclusive.
Write the ordered exact product basis as $U = [\begin{array}{c} U_{1} \\ U_{2} \end{array}]$ and view the supplied $n \times n$ matrix $\hat{Y}$ by columns ${\hat{y}}_{j}$ . Enclose the entries of $A_{g} = U_{1}^{*}$ and $B_{g} = U_{2}^{*}$ by finite outward rectangles. Using the supplied dyadic proposals, outward-evaluate $I - R_{g} A_{g}$ once and let $q$ be an upper bound for its Frobenius norm; the same enclosure applies to every matrix in the product of entry rectangles. If $q \geq 1$ or the enclosure is unavailable, return graph-block-inconclusive. For each column $b_{j}$ of $B_{g}$ , outward-evaluate the full uniform residual enclosure $R_{g} (b_{j} - A_{g} {\hat{y}}_{j})$ over the rectangles and choose a common finite upper bound $r$ for its Euclidean norm. If any enclosure fails, return graph-block-inconclusive. Apply A uniform approximate inverse and residual enclose every linear solution to each column: the exact system $A_{g} Y = B_{g}$ has a unique solution and each column is within $r / (1 - q)$ of the corresponding column of $\hat{Y}$ . Moreover $A_{g}$ and hence $U_{1}$ are invertible, and $∥ U_{1}^{- 1} ∥_{2} \leq ∥ R_{g} ∥_{F} / (1 - q)$ by the Neumann bound and submultiplicativity. Return this bound as the graph-block certificate; no explicit inverse is formed.
Set $X_{0} = {\hat{Y}}^{*}$ and $\hat{X} = (X_{0} + X_{0}^{*}) / 2$ . Compute outward enclosures for the CARE or DARE residual, the Hermitian symmetry defect, and, for DARE, $R + B^{*} \hat{X} B$ . Validate the supplied certificate packet against the hypotheses of A CARE residual and Lyapunov margin certify a unique stabilizing root in a matrix ball or A DARE residual, Stein inverse bound, and Lyapunov margin certify a stabilizing root, respectively. If the theorem certifies a unique stabilizing root in the stated ball, return the candidate, residual data, graph-block bound, stability witness and certified root ball. A direct exact witness that the candidate fails a required positivity or stability condition returns candidate-rejected; failure of a sufficient theorem test or unavailable data returns inconclusive. No residual by itself certifies the stabilizing branch or a nearby positive $Q, R$ .

This is the finite candidate-extraction stage for the ordered Schur/QZ solvers. Its ordering prerequisite is the finite adjacent-block routine and correctness theorem cited above; a successful order applies to the represented computed form, with the separately stated diagnostics still required for Riccati acceptance.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

An invertible graph block converts an exact stable Schur or QZ basis into a Riccati solution

Statement

For the CARE case, suppose the exact Hamiltonian stable invariant subspace has a basis $U = [\begin{array}{c} U_{1} \\ U_{2} \end{array}]$ with $U_{1}$ invertible, and set $X = U_{2} U_{1}^{- 1}$ . If $X = X^{*}$ , then $X$ solves the CARE and the restriction matrix on the graph is $A - G X$ .

For the DARE case, suppose an exact stable deflating basis for the pencil $(N, M)$ is $U = [\begin{array}{c} U_{1} \\ U_{2} \end{array}]$ with $U_{1}$ invertible, and set $X = U_{2} U_{1}^{- 1}$ . If $X = X^{*}$ and $R + B^{*} X B ≻ 0$ , then $X$ solves the DARE and the restriction matrix is $A_{c} = (I + G X)^{- 1} A = A - B (R + B^{*} X B)^{- 1} B^{*} X A$ .

Facts & Assumptions

Given: The CARE or DARE definitions and exact invariant or deflating subspace equations.

[F1]

The stabilizing CARE solution is the Hamiltonian stable invariant graph: the CARE graph equation is $H [I; X] = [I; X] (A - G X)$ and its lower block is equivalent to the CARE.

[F2]

The stabilizing DARE solution is the stable deflating graph of a regular symplectic pencil: the DARE graph equation is $N [I; X] = M [I; X] A_{c}$ for $A_{c} = (I + G X)^{- 1} A$ .

[F3]

Standard CARE and DARE data, equations, and conventions: the DARE is equivalently $X = Q + A^{*} X (I + G X)^{- 1} A$ whenever $R + B^{*} X B$ is invertible.

Proof

1.1F1givenalgebra

In either case, $U_{2} = X U_{1}$ , so $U = [I; X] U_{1}$ . If $H U = U T$ in the CARE case, right multiplication by $U_{1}^{- 1}$ gives $H [I; X] = [I; X] (U_{1} T U_{1}^{- 1})$ . The top block fixes the restriction matrix as $A - G X$ ; the bottom block reads $- Q - A^{*} X = X (A - G X)$ , which is exactly $A^{*} X + X A - X G X + Q = 0$ .

2.1F2F3algebra∎

If $N U = M U T$ in the DARE case, the same normalization gives $N [I; X] = M [I; X] (U_{1} T U_{1}^{- 1})$ . The top block is $A = (I + G X) (U_{1} T U_{1}^{- 1})$ , so invertibility of $I + G X$ gives restriction matrix $(I + G X)^{- 1} A$ . The lower block is $X - Q = A^{*} X (I + G X)^{- 1} A$ , which is the DARE by [F3]. No claim survives an unverified leading-block inverse or a subsequent nonzero symmetry residual.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

DARE structure-preserving doubling converges with a quantified quadratic error envelope

Statement

Under the discrete stabilizability and detectability hypotheses of Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution, start the exact recurrence of Finite-budget structure-preserving doubling iteration for the DARE from $A_{0} = A$ , $G_{0} = B R^{- 1} B^{*}$ , and $H_{0} = Q$ . Then all inverses exist, $G_{j}, H_{j} ⪰ 0$ , and $H_{j}$ converges to the stabilizing DARE solution $X_{*}$ . More quantitatively, there are $q \in (0, 1)$ , an index $j_{0}$ , and $C > 0$ such that $∥ H_{j} - X_{*} ∥_{F, W^{- 1}} \leq C q^{2^{j + 1}} (j \geq j_{0}),$ where $W ≻ 0$ is a Stein witness constructed from the closed-loop matrix. The envelope $ϵ_{j} = C q^{2^{j + 1}}$ obeys $ϵ_{j + 1} = ϵ_{j}^{2} / C$ . The constants are conditional on the closed-loop spectral separation and its norm conditioning; no uniform constant depending only on dimension is asserted.

Facts & Assumptions

Given: The standard DARE data and the exact discrete stabilizability/detectability hypotheses.

[F1]

Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution: the finite-horizon iterates $P_{0} = 0$ , $P_{k + 1} = f (P_{k})$ increase to $X_{*}$ , and $A_{c} (X_{*})$ is Schur stable.

[F2]

The DARE doubling recurrence composes two Riccati steps and preserves positive semidefiniteness: the recurrence is well-defined, preserves $G_{j}, H_{j} ⪰ 0$ , and $H_{j} = f^{2^{j}} (0)$ .

[F3]

Powers of a Schur-stable matrix decay geometrically up to a polynomial factor: powers of every Schur-stable matrix have a geometric bound with any rate above its spectral radius.

[F4]

A non-negative operator has a unique non-negative square root: a positive-semidefinite matrix has a positive-semidefinite square root; for $W ≻ 0$ this square root is positive definite.

[F5]

Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: compatible matrix products satisfy the induced Frobenius/operator norm bounds.

Proof

1.1F1F2algebra

By [F2], $H_{j} = P_{2^{j}}$ and $G_{j}, H_{j}$ remain positive semidefinite. Since [F1] gives $P_{k} \to X_{*}$ , the subsequence $H_{j} = P_{2^{j}}$ also converges to $X_{*}$ . No inverse of $A$ is used.

1.2F1F3F4algebra

Put $M = A_{c} (X_{*})$ . By [F1], $M$ is Schur stable; [F3] therefore makes $W = \sum_{k = 0}^{\infty} (M^{*})^{k} M^{k}$ converge in norm. It is positive definite, $W ⪰ I$ , and $M^{*} W M = W - I$ . If $w = ∥ W ∥_{2}$ , then $v^{*} M^{*} W M v \leq (1 - w^{- 1}) v^{*} W v$ , so the induced $W$ -norm $∥ M ∥_{W} : = ∥ W^{1 / 2} M W^{- 1 / 2} ∥_{2}$ is at most $q_{0} = \sqrt{1 - w^{- 1}} < 1$ . Choose $q$ with $q_{0} < q < 1$ . Since $P_{k} \to X_{*}$ and $A_{c} (P_{k})$ is continuous on $P_{k} ⪰ 0$ , choose $k_{0}$ so $∥ A_{c} (P_{k}) ∥_{W} \leq q$ for all $k \geq k_{0}$ .

2.1F1F5step 1.2algebrainduction∎

Let $E_{k} = X_{*} - P_{k} ⪰ 0$ . The Riccati-map difference identity in [F1] gives $E_{k + 1} = M^{*} E_{k} A_{c} (P_{k}) .$ Define $∥ E ∥_{F, W^{- 1}} = ∥ W^{- 1 / 2} E W^{- 1 / 2} ∥_{F}$ . By [F5], for $k \geq k_{0}$ , $∥ E_{k + 1} ∥_{F, W^{- 1}} \leq ∥ M ∥_{W} ∥ A_{c} (P_{k}) ∥_{W} ∥ E_{k} ∥_{F, W^{- 1}} \leq q^{2} ∥ E_{k} ∥_{F, W^{- 1}} .$ Iteration gives $∥ E_{k} ∥_{F, W^{- 1}} \leq ∥ E_{k_{0}} ∥_{F, W^{- 1}} q^{2 (k - k_{0})}$ . Taking $k = 2^{j}$ and setting $C = \max {1, ∥ E_{k_{0}} ∥_{F, W^{- 1}} q^{- 2 k_{0}}}$ proves the displayed envelope for all $2^{j} \geq k_{0}$ . Since $C > 0$ , direct calculation gives $ϵ_{j + 1} = C q^{2^{j + 2}} = ϵ_{j}^{2} / C$ .

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Separated DARE pencils have quantitatively stable deflating graphs

Statement

Let $(N, M)$ be the order- $2 n$ DARE pencil in The stabilizing DARE solution is the stable deflating graph of a regular symplectic pencil, with $n \geq 1$ . Work over $C$ , also for real input. Suppose exact unitary matrices $Q, V$ give an ordered complex generalized Schur pair $Q^{*} N V = S = [\begin{array}{cc} S_{11} & S_{12} \\ 0 & S_{22} \end{array}], Q^{*} M V = T = [\begin{array}{cc} T_{11} & T_{12} \\ 0 & T_{22} \end{array}],$ where each diagonal block has order $n$ , all four diagonal blocks are upper triangular, the leading homogeneous roots are strictly inside the unit disk, and the trailing roots are strictly outside its closure, including infinity. This ordered representation is an explicit input; existence of an unordered generalized Schur form is not an ordering certificate.

Give pairs of $n \times n$ matrices the product Frobenius norm $∥ (Y, Z) ∥_{P} = (∥ Y ∥_{F}^{2} + ∥ Z ∥_{F}^{2})^{1 / 2},$ and define the lower-oriented generalized Sylvester separation $γ = \min_{∥ (Y, Z) ∥_{P} = 1} ∥ (S_{22} Y - Z S_{11}, T_{22} Y - Z T_{11}) ∥_{P} .$ Then $γ > 0$ . Write $κ = γ^{- 1}$ , $h = (∥ S_{12} ∥_{2}^{2} + ∥ T_{12} ∥_{2}^{2})^{1 / 2}$ . For arbitrary pencil perturbations $Δ_{N}, Δ_{M}$ , put $E = Q^{*} Δ_{N} V$ , $F = Q^{*} Δ_{M} V$ , and $δ = (∥ E ∥_{F}^{2} + ∥ F ∥_{F}^{2})^{1 / 2} = (∥ Δ_{N} ∥_{F}^{2} + ∥ Δ_{M} ∥_{F}^{2})^{1 / 2}$ . If $r > 0$ satisfies $κ [δ + 2 δ r + (h + δ) r^{2}] \leq r, κ [2 δ + 2 (h + δ) r] < 1,$ there is a unique pair $(Y, Z)$ in the product radius- $r$ ball for which the right and left graphs $V [I; Y]$ and $Q [I; Z]$ form matching deflating spaces of the perturbed pair. In particular $∥ Y ∥_{F}, ∥ Z ∥_{F} \leq r$ . For $δ > 0$ , a sufficient choice is $r = 2 κ δ$ whenever, with $θ = κ δ$ , $4 θ + 4 κ h θ + 4 θ^{2} < 1.$ For $δ = 0$ , take $Y = Z = 0$ .

Here are separate sufficient margins identifying these graphs as the stable spaces. Set $a = δ + (∥ S_{12} ∥_{2} + δ) r, b = δ + (∥ T_{12} ∥_{2} + δ) r,$ $K_{s} = T_{11}^{- 1} S_{11}, K_{u} = S_{22}^{- 1} T_{22} .$ The inverses exist and $K_{s}, K_{u}$ are Schur stable. For $j = s, u$ , choose $W_{j} ≻ 0$ with $W_{j} - K_{j}^{*} W_{j} K_{j} = I$ ; the convergent Stein series supplies such a matrix. Require $∥ T_{11}^{- 1} ∥_{2} b < 1, ∥ S_{22}^{- 1} ∥_{2} a < 1,$ and define $ϵ_{s} = \frac{∥ T_{11}^{- 1} ∥_{2} (a + b ∥ K_{s} ∥_{2})}{1 - ∥ T_{11}^{- 1} ∥_{2} b}, ϵ_{u} = \frac{∥ S_{22}^{- 1} ∥_{2} (b + a ∥ K_{u} ∥_{2})}{1 - ∥ S_{22}^{- 1} ∥_{2} a} .$ If $∥ W_{j} ∥_{2} (2 ∥ K_{j} ∥_{2} ϵ_{j} + ϵ_{j}^{2}) < 1 (j = s, u),$ then the perturbed pencil is regular, has precisely $n$ stable roots and $n$ outside roots, and the constructed right graph is its stable deflating space. For fixed ordered input these margins hold for all sufficiently small $δ$ with $r = 2 κ δ$ .

For normalized right bases, write $V = [U V_{2}]$ and $\hat{U} = (U + V_{2} Y) (I + Y^{*} Y)^{- 1 / 2}, y = ∥ Y ∥_{2}, β (y) = \sqrt{2 (1 - \frac{1}{\sqrt{1 + y^{2}}})} .$ Then ${\hat{U}}^{*} \hat{U} = I$ , $∥ \hat{U} - U ∥_{2} = β (y) \leq y \leq r$ , and $∥ (I - U U^{*}) \hat{U} ∥_{2} = \frac{y}{\sqrt{1 + y^{2}}} .$ If the physical top block $U_{1}$ of $U = [U_{1}; U_{2}]$ is invertible, $X = U_{2} U_{1}^{- 1}$ , and $∥ U_{1}^{- 1} ∥_{2} β (y) < 1$ , then ${\hat{U}}_{1}$ is invertible and $∥ {\hat{U}}_{2} {\hat{U}}_{1}^{- 1} - X ∥_{2} \leq \frac{(1 + ∥ X ∥_{2}) β (y)}{∥ U_{1}^{- 1} ∥_{2}^{- 1} - β (y)} .$ For the directly computable bound with $β (r)$ , impose the stronger margin $∥ U_{1}^{- 1} ∥_{2} β (r) < 1$ ; replacing $β (y)$ by $β (r)$ then gives a valid weaker estimate. An independently rotated orthonormal basis of the same perturbed space produces the identical chart, so it need not be close to $U$ before alignment. The conclusion concerns an unstructured perturbed pencil; it does not certify Hermitian symmetry, Riccati residual, positive data, or the stabilizing Riccati branch after symmetrization.

Facts & Assumptions

Given: The regular DARE pencil and stable graph, an exact ordered complex unitary generalized Schur representation with the stated strict stable split, perturbations of both pencil matrices, the stated contraction radius, and the indicated separate stability and chart margins.

[F1]

The stabilizing DARE solution is the stable deflating graph of a regular symplectic pencil: the DARE pencil is regular, has $n$ stable finite roots and $n$ outside roots including infinity, and its stable right deflating space is a graph.

[F2]

Complex and real generalized Schur forms: a complex generalized Schur representation has exact unitary left/right factors and upper-triangular arrays with homogeneous scalar diagonal pairs.

[F3]

Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition: a finite-dimensional linear map has a smallest singular value; it is positive exactly when the map is injective.

[F4]

The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices: the Frobenius norm is the Euclidean norm of the matrix entry list, including for zero-sized blocks.

[F5]

Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison: unitary factors preserve Frobenius and operator norms, and $∥ M ∥_{2} \leq ∥ M ∥_{F}$ .

[F6]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: compatible operator norms are submultiplicative.

[F7]

Powers of a Schur-stable matrix decay geometrically up to a polynomial factor: powers of a Schur-stable matrix decay geometrically up to a finite constant.

[F8]

Every finite-dimensional normed space is Banach: every finite-dimensional normed real or complex space is complete.

[F9]

A non-negative operator has a unique non-negative square root and [F3]: $I + Y^{*} Y$ has a positive inverse square root with the singular-value formulas used below.

[F10]

The homogeneous determinant factors across a block upper triangular pencil: the homogeneous determinant factors across the diagonal blocks of a block upper-triangular pencil.

[F11]

Every finite-dimensional endomorphism over an algebraically closed field has Jordan form: each finite-dimensional complex endomorphism has a basis of generalized eigenvectors.

[F12]

A Neumann defect bounds the inverse norm: if $∥ E ∥_{2} \leq q < 1$ , then $I - E$ is invertible and $∥ (I - E)^{- 1} ∥_{2} \leq (1 - q)^{- 1}$ .

[F13]

For same-sized finite square matrices over a commutative ring, $\det (A B) = \det (A) \det (B)$ : determinants multiply under finite square matrix products.

[F14]

A nonzero polynomial of degree $n$ over an integral domain has at most $n$ distinct roots: a nonzero polynomial has only finitely many roots.

[F15]

Regular matrix pencils and homogeneous generalized eigenvalues: the homogeneous roots of $(N, M)$ are zeros of $\det (β N - α M)$ ; $β = 0$ represents infinity.

Proof

1.1F1F2F3F4givenconstructalgebra

By [F1], the regular base DARE pencil has an $n + n$ stable/outside split, and the ordered representation [F2] puts the stable roots in the leading blocks and the outside roots in the trailing blocks. Write trailing diagonal pairs as $(s_{i}, t_{i})$ and leading ones as $(p_{j}, q_{j})$ . Disjoint homogeneous roots give $p_{j} t_{i} - s_{i} q_{j} \neq 0$ for every $i, j$ , including $t_{i} = 0$ . In the system $S_{22} Y - Z S_{11} = C$ , $T_{22} Y - Z T_{11} = D$ , process rows $i = n, n - 1, \dots, 1$ and within each row columns $j = 1, \dots, n$ ; upper triangularity makes all other terms involve already determined $Y_{k j}$ with $k > i$ or $Z_{i ℓ}$ with $ℓ < j$ . The two unknowns $(Y_{i j}, Z_{i j})$ have coefficient matrix $[\begin{array}{cc} s_{i} & - p_{j} \\ t_{i} & - q_{j} \end{array}]$ with determinant $p_{j} t_{i} - s_{i} q_{j} \neq 0$ , so the lower-oriented generalized Sylvester map is bijective. Its minimum singular value [F3] is therefore $γ > 0$ , and its inverse norm is $κ = γ^{- 1}$ .

2.1F1F4F5F6F8step 1.1algebra

Define $C_{Y} = S_{11} + E_{11} + (S_{12} + E_{12}) Y$ and $D_{Y} = T_{11} + F_{11} + (T_{12} + F_{12}) Y$ . Block multiplication gives $(S + E) [I; Y] = [I; Z] C_{Y}$ and $(T + F) [I; Y] = [I; Z] D_{Y}$ exactly when $L (Y, Z) = (S_{22} Y - Z S_{11}, T_{22} Y - Z T_{11})$ equals $(- E_{21} - E_{22} Y + Z E_{11} + Z (S_{12} + E_{12}) Y, - F_{21} - F_{22} Y + Z F_{11} + Z (T_{12} + F_{12}) Y)$ . On the product radius- $r$ ball, the right side has norm at most $δ + 2 δ r + (h + δ) r^{2}$ : the constant pair is bounded by $δ$ , the two linear pairs by $δ ∥ Y ∥_{F}$ and $δ ∥ Z ∥_{F}$ , and the quadratic pair by $(h + δ) ∥ Z ∥_{F} ∥ Y ∥_{F}$ . Splitting the quadratic difference into its $Y$ and $Z$ changes bounds the Lipschitz constant by $2 δ + 2 (h + δ) r$ . Applying $L^{- 1}$ gives a self-map and contraction under the stated inequalities; iteration from zero has geometrically summable increments, so completeness [F8] gives a limit in the closed ball, continuity gives a fixed point, and contraction gives uniqueness. For $r = 2 κ δ$ and $θ = κ δ$ , substitution gives self-map ratio $κ [δ + 2 δ r + (h + δ) r^{2}] / r = 1 / 2 + 2 θ + 2 κ h θ + 2 θ^{2}$ and contraction constant $2 θ + 4 κ h θ + 4 θ^{2}$ ; the displayed strict condition implies both. For $δ = 0$ , the exact pair $Y = Z = 0$ solves the graph equations.

3.1F2F5F6F7F12step 2.1algebra

Set $R_{Y} = [\begin{array}{cc} I & 0 \\ Y & I \end{array}]$ and $L_{Z} = [\begin{array}{cc} I & 0 \\ - Z & I \end{array}]$ . They are invertible shears of determinant one, and the graph equations from step 2.1 give $L_{Z} (S + E) R_{Y} = [\begin{array}{cc} C_{Y} & S_{12} + E_{12} \\ 0 & A^{'} \end{array}]$ and $L_{Z} (T + F) R_{Y} = [\begin{array}{cc} D_{Y} & T_{12} + F_{12} \\ 0 & B^{'} \end{array}]$ , where $A^{'} = S_{22} + E_{22} - Z (S_{12} + E_{12})$ and $B^{'} = T_{22} + F_{22} - Z (T_{12} + F_{12})$ . Unitary invariance, $∥ M ∥_{2} \leq ∥ M ∥_{F}$ [F5], and submultiplicativity [F6] give $∥ C_{Y} - S_{11} ∥_{2}, ∥ A^{'} - S_{22} ∥_{2} \leq a$ and $∥ D_{Y} - T_{11} ∥_{2}, ∥ B^{'} - T_{22} ∥_{2} \leq b$ . Every leading stable root is finite, so $T_{11}$ is invertible and $K_{s} = T_{11}^{- 1} S_{11}$ is upper triangular with diagonal moduli below one. Every trailing outside root has nonzero first homogeneous coordinate, so $S_{22}$ is invertible and $K_{u} = S_{22}^{- 1} T_{22}$ is upper triangular with diagonal moduli below one, including zero for infinity; thus both are Schur stable. By [F7], $W_{j} = \sum_{k \geq 0} (K_{j}^{*})^{k} K_{j}^{k}$ converges for $j = s, u$ , is positive definite, and satisfies $W_{j} - K_{j}^{*} W_{j} K_{j} = I$ . The two Neumann margins and [F12] make $D_{Y}, A^{'}$ invertible with inverse norms at most $∥ T_{11}^{- 1} ∥_{2} / (1 - ∥ T_{11}^{- 1} ∥_{2} b)$ and $∥ S_{22}^{- 1} ∥_{2} / (1 - ∥ S_{22}^{- 1} ∥_{2} a)$ . The identities $D_{Y}^{- 1} C_{Y} - K_{s} = D_{Y}^{- 1} [(C_{Y} - S_{11}) - (D_{Y} - T_{11}) K_{s}]$ and $A^{' - 1} B^{'} - K_{u} = A^{' - 1} [(B^{'} - T_{22}) - (A^{'} - S_{22}) K_{u}]$ give exactly the stated $ϵ_{s}, ϵ_{u}$ bounds.

3.2F3F5F9givenstep 2.1algebra

Put $P_{Y} = (I + Y^{*} Y)^{- 1 / 2}$ . Since $V = [U V_{2}]$ is unitary, $(U + V_{2} Y)^{*} (U + V_{2} Y) = I + Y^{*} Y$ , so ${\hat{U}}^{*} \hat{U} = I$ and $U^{*} \hat{U} = P_{Y}$ . Therefore $(\hat{U} - U)^{*} (\hat{U} - U) = 2 (I - P_{Y})$ . The largest eigenvalue of $Y^{*} Y$ is $y^{2}$ , so [F3], [F5], and [F9] give the exact norm $∥ \hat{U} - U ∥_{2} = β (y)$ . The scalar function $g (t) = t - 2 (1 - (1 + t)^{- 1 / 2})$ has $g (0) = 0$ and $g^{'} (t) = 1 - (1 + t)^{- 3 / 2} \geq 0$ for $t \geq 0$ , proving $β (y) \leq y \leq r$ . Also $(I - U U^{*}) \hat{U} = V_{2} Y P_{Y}$ , whose largest singular value is $y / \sqrt{1 + y^{2}}$ by [F3] and [F5].

4.1F6F10F11F13F14F15givenstep 3.1algebra

If $K$ is either quotient in step 3.1 and $∥ H ∥_{2} \leq ϵ$ , then $W - (K + H)^{*} W (K + H) = I - (K^{*} W H + H^{*} W K + H^{*} W H)$ . The subtracted Hermitian term has norm at most $∥ W ∥_{2} (2 ∥ K ∥_{2} ϵ + ϵ^{2}) < 1$ , so the left side is positive definite; an eigenvector of $K + H$ with eigenvalue $λ$ gives $(1 - ∣ λ ∣^{2}) v^{*} W v > 0$ , hence $∣ λ ∣ < 1$ . Applied to $D_{Y}^{- 1} C_{Y}$ and $A^{' - 1} B^{'}$ , this makes the leading perturbed roots finite and stable, and the trailing roots outside, with zero eigenvalues of $A^{' - 1} B^{'}$ representing infinity. The shears have determinant one, so [F13] preserves the homogeneous determinant under their left/right transformations; [F10] factors it across the diagonal blocks. Since $D_{Y}$ and $A^{'}$ are invertible, both diagonal pencils are regular and their product is a regular pencil with the claimed $n + n$ root split. The regular base and perturbed determinant polynomials have finite root sets by [F14]; choose $λ_{0} \in C$ outside their union. Put $R = (N^{'} - λ_{0} M^{'})^{- 1} M^{'}$ for $N^{'} = L_{Z} (S + E) R_{Y}$ and $M^{'} = L_{Z} (T + F) R_{Y}$ . Then $N^{'} - λ M^{'} = (N^{'} - λ_{0} M^{'}) [I - (λ - λ_{0}) R]$ , so [F13] expresses the pencil determinant as a nonzero constant times $\det (I - (λ - λ_{0}) R)$ . Jordan form [F11] factors the latter into $\prod_{j} (1 - (λ - λ_{0}) μ_{j})$ over the eigenvalues $μ_{j}$ of $R$ , with algebraic multiplicity. Thus each finite root maps injectively to $μ = 1 / (λ - λ_{0})$ , and the polynomial degree is the number of nonzero $μ_{j}$ , counted with algebraic multiplicity. Its homogeneous form is $\det (β N^{'} - α M^{'}) = β^{2 n} \det (N^{'} - (α / β) M^{'})$ ; by [F15], its multiplicity at $[1 : 0]$ is $2 n$ minus that degree, exactly the multiplicity of the zero eigenvalue of $R$ . The matrix $R$ is block upper triangular with diagonal blocks $(C_{Y} - λ_{0} D_{Y})^{- 1} D_{Y}$ and $(A^{'} - λ_{0} B^{'})^{- 1} B^{'}$ , whose spectra are disjoint because their pencil-root groups are disjoint and the projective map is injective. For a generalized eigenvector $[x; y]$ belonging to a leading-block eigenvalue $μ$ , its trailing equation is $(R_{22} - μ I)^{k} y = 0$ ; disjoint spectra force $y = 0$ . Conversely, Jordan form [F11] supplies a basis of generalized eigenvectors of the leading $n \times n$ block, which embed as $[x; 0]$ and span exactly the full leading-root generalized eigenspace. Undoing the graph shears and unitary factors identifies this right subspace with $V [I; Y]$ and its matching left deflating graph with $Q [I; Z]$ .

4.2F5F6F12step 3.2algebra

Write $Δ U = \hat{U} - U$ . Under the strict chart margin, ${\hat{U}}_{1} = U_{1} (I + U_{1}^{- 1} Δ U_{1})$ and $∥ U_{1}^{- 1} Δ U_{1} ∥_{2} \leq ∥ U_{1}^{- 1} ∥_{2} β (y) < 1$ . By [F12], ${\hat{U}}_{1}$ is invertible and $∥ {\hat{U}}_{1}^{- 1} ∥_{2} \leq (∥ U_{1}^{- 1} ∥_{2}^{- 1} - β (y))^{- 1}$ . Using $U_{2} = X U_{1}$ gives ${\hat{U}}_{2} {\hat{U}}_{1}^{- 1} - X = (Δ U_{2} - X Δ U_{1}) {\hat{U}}_{1}^{- 1}$ ; [F6] yields the stated chart estimate. Since $β$ is increasing and $β (y) \leq β (r)$ , the stronger margin $∥ U_{1}^{- 1} ∥_{2} β (r) < 1$ gives the computable weaker bound. An independently rotated orthonormal basis of the same space is $\hat{U} R_{0}$ for unitary $R_{0}$ and has the same chart because $({\hat{U}}_{1} R_{0})^{- 1} = R_{0}^{- 1} {\hat{U}}_{1}^{- 1}$ . The proof assumes no structure on $E, F$ , so it gives no Riccati residual, symmetry, positivity, or post-symmetrization stability certificate.

5.1givenstep 2.1step 3.1step 4.1algebra∎

As $δ \to 0$ with $r = 2 κ δ$ , $θ \to 0$ , $a, b \to 0$ , and $ϵ_{s}, ϵ_{u} \to 0$ ; hence the contraction, Neumann, and both Stein margins in the Statement hold for all sufficiently small $δ$ . If $U_{1}$ is invertible, also $∥ U_{1}^{- 1} ∥_{2} β (r) < 1$ for all sufficiently small $δ$ , so the computable chart margin holds.

No arbitrary Axiom of Choice is used: all constructions are finite-dimensional scans, norm-convergent series, or selections from complements of finite subsets of $C$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Finite Riccati candidate, Newton-Kleinman, and doubling wrappers return a status

Statement

Use admitted inputs and the finite solver/arithmetic/evaluator controllers stipulated by each of Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms, Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration, and Finite-budget structure-preserving doubling iteration for the DARE. Then each procedure terminates with its declared output or status, retaining its specified failure diagnostics.

Candidate extraction makes one matching Schur or QZ reduction, at most one stable-block reordering call, and at most $n$ graph-column certificate passes followed by finite acceptance checks. Exact Newton–Kleinman makes at most $N$ policy evaluations; its safeguarded mode inspects at most $N (L + 1)$ trial gains and makes at most $N$ point-certificate calls for the current cost matrices. SDA makes at most $N$ solve/update passes, at most $n N$ point-certificate calls for recurrence solves, and at most $m (N + 1)$ calls for residual solves ( $R \in F^{m \times m}$ ), followed by finite symmetry/residual reporting. Early failures may shorten these counts. These conclusions are conditional on the declared finite controller contracts; they do not derive termination of an unspecified certificate-producing routine from an enclosure theorem.

Successful ordering concerns the represented computed form. The original Riccati residual, symmetry, positivity and closed-loop checks remain separate. This finite-status result asserts no convergence for arbitrary inexact proposals and no rounded PSD or structured-backward-error guarantee.

Facts & Assumptions

Given: The three procedures' admitted finite matrix data, their finite Schur/QZ, reordering, outer-iteration and line-search budgets, and exactly the finite solver/verifier interfaces supplied in their Definitions.

[A1]

For candidate extraction, every supplied arithmetic/evaluator controller has the finite execution and explicit failure behavior declared in its Definition. For Newton–Kleinman the finite line-search controller and each point-certificate call return their result or status; for SDA each point certificate, exact factorization, and arithmetic operation returns its result or failure in finite work. These are the existing operational hypotheses, not inferred root-finding or precision-success guarantees.

[F1]

Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms calls its matching reduction, then stable-block reordering, then its finite verified graph solve and outward acceptance diagnostics.

[F2]

Finite Francis procedure terminates with explicit statuses and verifies its Schur pattern on success and Every finite-budget QZ run returns a status and records unitary transforms and explicit deflations prove finite status return of the admitted reduction calls.

[F3]

Finite-budget stable block reordering has exact adjacent-swap correctness and status proves finite status return, selected invariant/right-deflating subspace on an ordered return, and transport of the original unstructured reduction residual.

[F4]

A uniform approximate inverse and residual enclose every linear solution and Verified point and uniform linear residual certificate data supply the interpretation of usable verified linear-solve and inverse/residual data. Outward-rounded operations are inclusion-isotone and enclose DAG evaluations gives enclosure soundness for finite DAG evaluations.

[F5]

Certified QZ residuals give a backward error bound for both pencil matrices concerns the specified nearby unstructured pencil, not a structured Riccati perturbation.

[F6]

Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration has at most $N$ outer updates, at most $L + 1$ safeguarded trials per pass, and at most one current-cost point-certificate call per pass. Finite precision point linear solve certificate with explicit status has a finite status, and The point linear solve certifier returns a sound solution ball on success gives the solution ball on a certified return. Finite Bartels–Stewart statuses and successful-pivot uniqueness proves finite policy-solve status return and uniqueness on successful exact solves.

[F7]

Finite-budget structure-preserving doubling iteration for the DARE uses exact elimination for recurrence and residual solves in exact mode. Finite mode uses at most $n$ point-certificate calls per recurrence solve and at most $m$ calls for each residual diagnostic at initialization and after each update, since $R + B^{*} H_{j} B$ has order $m$ . An unavailable residual does not change recurrence status. The point solver has finite status by [F6]. The residual/feedback conventions are Standard CARE and DARE data, equations, and conventions.

Proof

1.1givenA1F1F2algebra

Each candidate-extraction branch calls only its matching finite Schur or QZ routine. The finite controls and declared status behavior are covered by [F1]–[F2]. Any reduction, regularity, range or budget failure immediately propagates its inconclusive status; no convergence-until-success loop is present.

1.2givenA1F6algebra

Exact Newton–Kleinman performs at most $N$ policy evaluations. Each admitted Bartels–Stewart call has the complete per-pass control packet and returns a finite success or failure status by [F6]; failure stops immediately and success is followed by one finite gain update. Hence exact mode returns within its declared outer budget.

1.3A1F4F6algebra

Each safeguarded outer pass clears finitely many positive integer denominators from the rational current-cost system, preserving its solution while making the stored point-call data dyadic, or returns range-failure. It inspects the finite list of $L + 1$ gains and makes one current-cost point-certificate call. Each trial then uses finitely many outward operations to verify its inverse, residual and stability bounds. By [A1] each call and outward check returns its enclosure or status in finite work, with certified balls interpreted by [F4] and [F6]. A trial passes the certified acceptance inequality or is rejected; if no trial passes, the routine returns safeguard-inconclusive without changing the current gain. At most $N$ outer passes therefore make at most $N (L + 1)$ trial inspections and $N$ point-certificate calls. No assertion of convergence for arbitrary inexact proposals follows from this finite search.

1.4givenA1F6F7algebra

Each SDA pass $j < N$ requests one solve with $I + G_{j} H_{j}$ and, in finite mode, at most $n$ point-certificate calls for its columns. The finite-mode initialization solves the order- $m$ system $R V = B^{*}$ on finite dyadic encodings by finite exact rational elimination, forms $B V, C^{*} C$ , and rounds finitely many components or returns its declared failure; it makes no point-certificate call. At initialization and after each update, form $S_{j} = R + B^{*} H_{j} B$ exactly. In exact mode its possibly non-dyadic entries are handled by the finite exact elimination rule, as are the recurrence solves; the residual is then evaluated exactly. In finite mode $S_{j}$ is dyadic, so its order- $m$ residual solve uses at most $m$ point-certificate calls followed by outward residual evaluation. By [A1] and [F6] all these operations return a result or failure in finite work. An unavailable residual is reported without changing recurrence status. Failure of the recurrence solve immediately returns its declared range/inverse status; success is followed by the fixed finite matrix updates. Thus every pass and final report terminate.

2.1A1F1F3F4F5step 1.1algebra

On successful reduction, reordering inspects finitely many blocks and returns ordered or an explicit status by [F3]. On an ordered return its first required factor columns are the selected subspace of the represented computed form, with only the original unstructured residual certificate transported. Under [A1] the graph-block bound and verified solve [F4] terminate; missing invertibility or a failed solve takes the stated inconclusive branch. Residual, symmetry, positivity and closed-loop diagnostics use finitely many matrix/enclosure operations, and failure or unavailable evidence takes its explicit return. The enclosure interpretation in [F4] does not itself produce a terminating verifier; that is the supplied contract [A1]. The QZ diagnostic retains precisely the limitation in [F5]. Thus the wrapper returns in finite work with ordering and equation-level acceptance kept separate.

3.1A1F7step 2.1step 1.2step 1.3step 1.4algebra∎

There are at most $N$ such passes. The final symmetry defects and, when its solve is available, the standard DARE residual use finite-dimensional arithmetic under [A1] and the conventions [F7]. Therefore the exact and finite-arithmetic paths return their declared output/status by the cap. The recorded raw matrices and defects supply no rounded PSD or structured-backward-error claim without separate checks, just as the candidate and safeguarded branches retain their original acceptance restrictions.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Dense Riccati work counts and numerical acceptance require equation-level diagnostics

Statement

In the dense arithmetic model, a single-matrix Schur reduction or regular-pair QZ reduction of order $n$ with at most $s$ Francis/QZ sweeps has core work $O (n^{3} + s n^{2})$ : the initial Hessenberg or Hessenberg-triangular reduction costs $O (n^{3})$ and each full bulge-chasing sweep costs $O (n^{2})$ . Forming a graph candidate by solving $X U_{1} = U_{2}$ with dense $n \times n$ factorization, $n$ right-hand sides, and residual multiplication costs $O (n^{3})$ .

After an order- $d$ reduction, finite stable-block reordering with $k$ actual attempts costs $O (d^{2} + k d)$ scalar operations. If the form has $b$ diagonal blocks and $I$ complementary-before-selected inversions, then $I \leq b (b - 1) / 2$ ; successful ordering requires $K \geq I$ and enough scalar/evaluator budget $W$ for the entire execution, including validation, label and inversion scans, all $I$ swaps, and the final ordering scan. For a Riccati pencil or Hamiltonian with $d = 2 n$ , successful reordering, graph solve and equation-level residual multiplication preserve the $O (n^{3} + s n^{2})$ scalar-core bound. This exact postprocessing count excludes algebraic bit cost, evaluator implementation cost beyond its declared unit budget, dense product-factor evaluation, local residual-ball certificate production or validation beyond the charged dense operations, and any additional dense residual multiplication. It is not a fixed-precision floating-point flop or structured backward-stability bound.

One dense Bartels–Stewart Lyapunov solve in its specified cubic branch costs $O (n^{3})$ ; $J$ exact Newton-Kleinman policy evaluations therefore cost $O (m^{3} + J n^{3} + J (n^{2} m + n m^{2}))$ for state dimension $n$ and input dimension $m$ , charging one factorization of $R$ of order $m$ once. One exact-arithmetic SDA recurrence step costs $O (n^{3})$ , so $N$ exact steps cost $O (N n^{3})$ ; finite point-certificate and residual-enclosure work is separate.

Every computed candidate still requires its actual CARE/DARE residual and Hermitian symmetry defect. A DARE candidate also requires a positive lower bound for $R + B^{*} X B$ ; both equations require an independently certified closed-loop Hurwitz/Schur condition before the stabilizing branch is accepted. A computed QZ backward error for an unstructured nearby pencil does not certify nearby Hamiltonian/symplectic structure or positive $Q, R$ .

Facts & Assumptions

Given: Dense scalar arithmetic, finite Schur/QZ sweep budgets, dense direct factors and solves, and exact matrix dimensions.

[F1]

Finite-budget CARE and DARE candidate extraction from ordered Schur and QZ forms: candidate extraction calls finite Schur/QZ reductions and exact stable-block reordering, solves $X U_{1} = U_{2}$ , and reports actual Riccati residual, symmetry defect, positivity, and closed-loop stability data.

[F2]

Finite-budget computed Francis Schur reduction with explicit statuses: Francis reduction first reduces to Hessenberg form and then performs bounded QR bulge-chasing sweeps.

[F3]

Finite-budget QZ iteration with homogeneous status and residual output: QZ iteration first reduces a regular pair to Hessenberg-triangular form and then performs bounded QZ sweeps.

[F4]

Finite-budget Bartels-Stewart solve for a Sylvester equation: its cubic branch sets $N_{A} \leq c_{0} m$ and $N_{B} \leq c_{0} n$ for the two Schur reductions, then solves the resulting triangular Sylvester equation.

[F5]

Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration: each exact Newton-Kleinman update performs one Lyapunov solve and one gain update.

[F6]

Finite-budget structure-preserving doubling iteration for the DARE: each SDA update solves with $I + G_{j} H_{j}$ and forms three dense matrix updates.

[F7]

Certified QZ residuals give a backward error bound for both pencil matrices: the QZ backward-error statement certifies the computed pair against an unstructured nearby pencil.

[F8]

Standard CARE and DARE data, equations, and conventions: the acceptance quantities are the CARE/DARE residuals, symmetry, DARE matrix $R + B^{*} X B$ , and the corresponding closed-loop matrices.

[F9]

Finite-budget stable block reordering for Schur and QZ forms: the exact reordering has initial form-validation work, bounded-size local solves, whole-panel updates, and separate finite $K, W$ budgets.

[F10]

Finite-budget stable block reordering has exact adjacent-swap correctness and status: each accepted adjacent inversion swap reduces the count by one and the exact factors transport existing unstructured residual norms.

[F11]

Finite Bartels–Stewart statuses and successful-pivot uniqueness: the admitted finite solve terminates with a declared status and every successful local pivot is unique.

[A1]

Dense reductions and exact equation solves use classical dense multiplication, factorization, and triangular solve costs. Reordering counts exact scalar primitives and declared evaluator units; algebraic bit cost, evaluator implementation cost, factor evaluation, local residual-ball verifier work, and any uncounted enclosure work remain separate.

Proof

1.1A1F2F3givenalgebra

In a Householder Hessenberg reduction, there are at most $n$ reflectors. At each stage a reflector updates a trailing block with at most $n^{2}$ entries using matrix-vector and rank-one operations, so the initialization costs $O (n^{3})$ . In a Francis or QZ bulge-chasing sweep, there are $O (n)$ rotations/reflections; each is applied to $O (n)$ entries in the active matrix and accumulated factor, hence a sweep costs $O (n^{2})$ . The finite budgets in [F2]–[F3] therefore give $O (n^{3} + s n^{2})$ core work.

2.1A1F1F4F11step 1.1algebra

Dense LU factorization of $U_{1}$ costs $O (n^{3})$ ; applying its factors to $n$ right-hand sides costs $O (n^{3})$ . The residual product $(X U_{1} - U_{2})$ is also $O (n^{3})$ , yielding the candidate solve count in [F1]. In the Lyapunov branch, [F4] imposes $N_{A}, N_{B} \leq c_{0} n$ . By step 1.1, each of its two dense Schur reductions therefore costs $O (n^{3})$ ; exact certificate checks and factor transformations are also $O (n^{3})$ . Triangular substitution for $n^{2}$ unknown entries with $O (n)$ work per entry costs $O (n^{3})$ , so one solve in this cubic branch costs $O (n^{3})$ . The fixed controller is bounded there; arbitrary-terminating-controller work is separate.

3.1A1F1F9F10step 1.1step 2.1algebra

Let $d$ be the reduction order, $b$ its diagonal block count and $I$ its initial inversion count. The reordering validation scan costs $O (d^{2})$ . Each local system has order at most eight, and each exact factor update touches $O (d)$ panel entries, so $k$ attempts cost $O (d^{2} + k d)$ by [F9]. On success, [F10] gives $k = I \leq b (b - 1) / 2 \leq d (d - 1) / 2$ , so the worst-case reordering core is $O (d^{3})$ ; this success path also requires $K \geq I$ and sufficient $W$ for the entire execution through its final ordering scan. For a Riccati matrix of order $2 n$ , combining reduction, reordering, graph solve and dense equation residual multiplication preserves $O (n^{3} + s n^{2})$ scalar-core work. Exact algebraic bit cost, evaluator implementation, dense factor-product evaluation and any additional dense residual multiplication are separate costs.

3.2A1F5F6step 2.1algebra

Each exact Newton-Kleinman pass has one Bartels–Stewart solve by [F5], costing $O (n^{3})$ by step 2.1. Factorizing $R$ once costs $O (m^{3})$ . With $m$ controls, forming $B^{*} X$ and the gain uses $O (n^{2} m + m^{2} n)$ arithmetic including triangular solves with this pre-factored $R$ ; forming $K^{*} R K$ and $A - B K$ is bounded by the same $O (n^{2} m + n m^{2})$ term. Summing over $J$ passes gives $O (m^{3} + J n^{3} + J (n^{2} m + n m^{2}))$ . Each exact-arithmetic SDA recurrence step uses one dense $n \times n$ solve and a fixed number of dense products, each $O (n^{3})$ ; [F6] therefore gives $O (N n^{3})$ over $N$ exact steps. Finite point-certificate and residual-enclosure work is separate under [A1].

4.1F1F7F8givenalgebra∎

A small backward error for a computed QZ pair, as supplied by [F7], is a statement about an unstructured nearby pencil. It contains no premise that the perturbation preserves Hamiltonian or symplectic block relations, nor that it preserves positive definiteness of $Q$ or $R$ . Consequently acceptance must separately compute the equation residual and symmetry defect, check $R + B^{*} X B ≻ 0$ for DARE, and certify the closed-loop stability property in [F8]; [F1] explicitly reports these quantities. Neither ordering a computed form nor its unstructured backward error establishes a structured pencil perturbation or an equation-level stabilizing certificate.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Riccati residual sensitivity and invariant graph conditioning retain spectral separation

Statement

Let $X_{c}$ and $X_{d}$ be the stabilizing CARE and DARE solutions under the hypotheses of Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution and Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution. Their residual derivatives on Hermitian matrices are $L_{c} (E) = A_{c} (X_{c})^{*} E + E A_{c} (X_{c}), L_{d} (E) = A_{c} (X_{d})^{*} E A_{c} (X_{d}) - E .$ When invertible, the local residual condition numbers are $κ_{c} = ∥ L_{c}^{- 1} ∥_{F \to F}$ and $κ_{d} = ∥ L_{d}^{- 1} ∥_{F \to F}$ . If additive Hermitian residual perturbations admit radii satisfying the contraction and separate stability-margin hypotheses of A CARE residual and Lyapunov margin certify a unique stabilizing root in a matrix ball or A DARE residual, Stein inverse bound, and Lyapunov margin certify a stabilizing root, the perturbed equations have stabilizing roots within those radii; the linear leading sensitivity is $- L_{c}^{- 1} Δ$ or $- L_{d}^{- 1} Δ$ .

For CARE, write $T_{X} = [\begin{array}{cc} I & 0 \\ X_{c} & I \end{array}]$ and let $σ = sep (- A_{c} (X_{c})^{*}, A_{c} (X_{c})) > 0$ , with $κ_{s} = 1 / σ$ . For a Hamiltonian perturbation $Δ H$ , put $Z = T_{X}^{- 1} Δ H T_{X}$ , $ζ = ∥ Z ∥_{F}$ , $θ = κ_{s} ζ$ , and $μ = κ_{s} ∥ G ∥_{2}$ . If $6 θ + 4 μ θ + 4 θ^{2} < 1$ , the perturbed Hamiltonian has an invariant graph $Ran [I; X_{c} + Y]$ with $∥ Y ∥_{F} \leq 2 θ$ . If its restriction is certified Hurwitz and the perturbed Hamiltonian is certified to have exactly $n$ left-half-plane eigenvalues, this graph is its stable subspace.

Finally, for either an exact CARE invariant graph basis or DARE deflating graph basis $U = [U_{1}; U_{2}]$ with invertible $U_{1}$ , let $X = U_{2} U_{1}^{- 1}$ and let $\tilde{U} = U + Δ U$ . If $∥ U_{1}^{- 1} ∥_{2} ∥ Δ U_{1} ∥_{2} < 1$ , then ${\tilde{U}}_{1}$ remains invertible and $∥ {\tilde{U}}_{2} {\tilde{U}}_{1}^{- 1} - X ∥_{2} \leq \frac{∥ Δ U_{2} ∥_{2} + ∥ X ∥_{2} ∥ Δ U_{1} ∥_{2}}{∥ U_{1}^{- 1} ∥_{2}^{- 1} - ∥ Δ U_{1} ∥_{2}} .$ This basis-chart estimate does not by itself certify a perturbed QZ deflating subspace.

For the DARE pencil, Separated DARE pencils have quantitatively stable deflating graphs gives a separate perturbation-to-stable-deflating-space estimate from a generalized Sylvester separation, explicit contraction inequalities, and distinct leading/trailing Stein margins. Under those conditions its aligned orthonormal stable basis changes by at most $β (r) \leq r$ . The computable physical chart estimate additionally requires $∥ U_{1}^{- 1} ∥_{2} β (r) < 1$ ; without that margin the chart remains inconclusive. A QZ pencil backward-error bound alone supplies none of these conditions.

Facts & Assumptions

Given: Standard CARE/DARE data, their stabilizing solutions and graph representations, and the indicated residual or basis perturbation bounds.

[F1]

Stabilizability and detectability give the unique stabilizing positive-semidefinite CARE solution: the CARE has a unique Hermitian positive-semidefinite solution whose closed loop is Hurwitz.

[F2]

Stabilizability and detectability give the unique stabilizing positive-semidefinite DARE solution: the DARE has a unique Hermitian positive-semidefinite solution whose closed loop is Schur stable.

[F3]

Standard CARE and DARE data, equations, and conventions: $F_{c} (X) = A^{*} X + X A - X G X + Q$ and $F_{d} (X) = Q + A^{*} X (I + G X)^{- 1} A - X$ on their stated domains.

[F4]

The stabilizing CARE solution is the Hamiltonian stable invariant graph: $H [I; X_{c}] = [I; X_{c}] A_{c} (X_{c})$ .

[F5]

The stabilizing DARE solution is the stable deflating graph of a regular symplectic pencil: $N [I; X_{d}] = M [I; X_{d}] A_{c} (X_{d})$ for the stated homogeneous DARE pencil.

[F6]

Sylvester operator and Frobenius separation number: $sep (P, - Q)$ is the smallest singular value of $Y \mapsto P Y + Y Q$ in Frobenius norm.

[F7]

A CARE residual and Lyapunov margin certify a unique stabilizing root in a matrix ball: CARE residual radius conditions are $κ (r + g ρ^{2}) \leq ρ$ and $2 κ g ρ < 1$ , with a separate Lyapunov stability margin.

[F8]

A DARE residual, Stein inverse bound, and Lyapunov margin certify a stabilizing root: DARE residual radius conditions use $κ (r + L_{D} ρ^{2} / 2) \leq ρ$ and $κ L_{D} ρ < 1$ , with a separate Stein stability margin.

[F9]

A Sylvester equation is uniquely solvable exactly when the spectra are disjoint: $Y \mapsto P Y + Y Q$ is invertible when $σ (P) \cap [- σ (Q)] = \emptyset$ .

[F10]

Every finite-dimensional normed space is Banach: finite-dimensional Frobenius matrix spaces are complete.

[F11]

Powers of a Schur-stable matrix decay geometrically up to a polynomial factor: powers of a Schur-stable matrix decay geometrically, so the Stein series in the proof converges.

[F12]

The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2: compatible operator norms are submultiplicative.

[F13]

The Hurwitz Lyapunov integral is the unique solution and has the stated positivity: for a Hurwitz matrix, the Lyapunov integral with positive-definite forcing is positive definite and solves the associated Lyapunov equation.

[F14]

Separated DARE pencils have quantitatively stable deflating graphs: generalized Sylvester separation, paired-graph contraction, separate leading and reciprocal-trailing Stein margins, and normalized basis/chart estimates bound the perturbed DARE stable deflating graph, including infinite roots.

[A1]

Residual perturbations are Hermitian and the verified norm and stability bounds in the applicable radius certificate enclose their exact values.

[A2]

For the CARE subspace part, the perturbed stable eigenvalue count and the Hurwitz property of the restriction are supplied as verified inputs when stable-subspace identity is asserted.

Proof

1.1F3givenalgebra

By [F3], expanding the CARE polynomial at a Hermitian $X$ gives $F_{c} (X + E) - F_{c} (X) = L_{c}^{X} (E) - E G E,$ where $L_{c}^{X} (E) = (A - G X)^{*} E + E (A - G X)$ . For the DARE, set $f (X) = Q + A^{*} X (I + G X)^{- 1} A$ . Direct multiplication gives $Φ_{G} (X + E) - Φ_{G} (X) = (I + (X + E) G)^{- 1} E (I + G X)^{- 1}, Φ_{G} (X) = X (I + G X)^{- 1} .$ Taking the derivative at $E = 0$ and multiplying by $A^{*}, A$ gives $D f (X) [E] = A_{c} (X)^{*} E A_{c} (X)$ ; since $F_{d} = f - X$ , this gives $D F_{d} (X) [E] = A_{c} (X)^{*} E A_{c} (X) - E$ .

1.2F14given

Apply [F14] to the exact ordered unitary DARE pencil representation and the supplied perturbations of both pencil matrices. Its paired generalized Sylvester operator and contraction inequalities give the radius- $r$ right and left deflating graphs; its separate Neumann and Stein margins establish the perturbed stable split. Its normalized basis construction gives distance at most $β (r) \leq r$ , and its computable physical chart estimate retains the inverse graph-block norm and the strict margin $∥ U_{1}^{- 1} ∥_{2} β (r) < 1$ . No part of this conclusion follows from QZ backward error alone.

2.1A1F1F2F7F8F10F11F12F13step 1.1algebra

For a CARE additive residual perturbation $Δ$ , write $X = X_{c} + E$ and let $δ = ∥ Δ ∥_{F}$ . Then $F_{c} (X_{c}) = 0$ and step 1.1 makes the perturbed root equation equivalent to $E = - L_{c}^{- 1} Δ + L_{c}^{- 1} (E G E) .$ If $ρ$ satisfies $κ_{c} (δ + ∥ G ∥_{2} ρ^{2}) \leq ρ$ and $2 κ_{c} ∥ G ∥_{2} ρ < 1$ , the map sends the closed radius- $ρ$ Hermitian ball to itself and has Lipschitz constant at most the second displayed quantity. Iteration from zero gives geometric successive differences; [F10] gives a limit in the ball, continuity gives a fixed point, and contraction gives uniqueness. Let $W_{c} = \int_{0}^{\infty} e^{t A_{c}^{*}} e^{t A_{c}} d t ≻ 0$ ; then $A_{c}^{*} W_{c} + W_{c} A_{c} = - I$ . If also $2 ∥ W_{c} ∥_{2} ∥ G ∥_{2} ρ < 1$ , then $∥ E G W_{c} + W_{c} G E ∥_{2} \leq 2 ∥ W_{c} ∥_{2} ∥ G ∥_{2} ρ < 1$ . Hence $(A_{c} - G E)^{*} W_{c} + W_{c} (A_{c} - G E) ≺ 0$ ; an eigenvector $v$ with eigenvalue $λ$ gives $2 Re (λ) v^{*} W_{c} v < 0$ , so the perturbed loop is Hurwitz. For DARE, [F2] gives Schur stability and [F11] gives the Stein inverse $L_{d}^{- 1} (Y) = - \sum_{k \geq 0} (A_{c}^{*})^{k} Y A_{c}^{k}$ . On a sufficiently small ball, $S (X) = R + B^{*} X B ⪰ δ_{S} I$ , where $δ_{S} = λ_{\min} S (X_{d}) - b^{2} ρ > 0$ . Put $a = ∥ A ∥_{2}$ , $b = ∥ B ∥_{2}$ , and $m = ∥ X_{d} ∥_{F} + ρ$ . The resolvent identity gives $∥ S (X)^{- 1} ∥_{2} \leq δ_{S}^{- 1}$ and $∥ S (X)^{- 1} - S (Y)^{- 1} ∥_{2} \leq b^{2} δ_{S}^{- 2} ∥ X - Y ∥_{F}$ . Splitting $K (X) - K (Y)$ into its $X$ and inverse-factor changes yields $∥ K (X) - K (Y) ∥_{F} \leq L_{K} ∥ X - Y ∥_{F}$ , where $L_{K} = a b / δ_{S} + a b^{3} m / δ_{S}^{2}$ ; hence $∥ A_{c} (X) ∥_{2} \leq M_{c} = a + a b^{2} m / δ_{S}$ and $∥ A_{c} (X) - A_{c} (Y) ∥_{2} \leq L_{c} ∥ X - Y ∥_{F}$ , $L_{c} = b L_{K}$ . Since $D F_{d} (X) [E] = A_{c} (X)^{*} E A_{c} (X) - E$ , subtraction gives $∥ D F_{d} (X) - D F_{d} (Y) ∥_{F \to F} \leq 2 M_{c} L_{c} ∥ X - Y ∥_{F} = : L_{D} ∥ X - Y ∥_{F}$ . Integrating this derivative along line segments gives $R (E) = F_{d} (X_{d} + E) - F_{d} (X_{d}) - L_{d} (E)$ with $∥ R (E) ∥_{F} \leq L_{D} ∥ E ∥_{F}^{2} / 2$ and $∥ R (E) - R (F) ∥_{F} \leq L_{D} ρ ∥ E - F ∥_{F}$ on the ball. Thus $E = - L_{d}^{- 1} (Δ + R (E))$ is a self-map when $κ_{d} (δ + L_{D} ρ^{2} / 2) \leq ρ$ and a contraction when $κ_{d} L_{D} ρ < 1$ . The same completeness argument gives its unique local root. For a separate stability margin, take $W_{d} = \sum_{k \geq 0} (A_{c}^{*})^{k} A_{c}^{k} ≻ 0$ , so $W_{d} - A_{c}^{*} W_{d} A_{c} = I$ by [F11]. Put $η = L_{c} ρ$ . Expanding the Stein form bounds its change by $∥ W_{d} ∥_{2} (2 M_{c} η + η^{2})$ ; choose $ρ$ so this is below $1$ . Then $W_{d} - A_{c} (X)^{*} W_{d} A_{c} (X) ≻ 0$ , and an eigenvector gives $(1 - ∣ λ ∣^{2}) v^{*} W_{d} v > 0$ , so the perturbed loop is Schur stable. For sufficiently small $δ > 0$ , take $ρ = 2 κ_{c} δ$ in CARE when $∥ G ∥_{2} > 0$ ; the contraction and stability inequalities hold for small enough $δ$ , giving $∥ E ∥_{F} = O (δ)$ . If $G = 0$ , the equation is linear and this order bound is exact. In DARE, take $ρ = 2 κ_{d} δ$ when $L_{D} > 0$ ; for sufficiently small $δ$ this satisfies the self-map, contraction, $S (X) ≻ 0$ , and Stein-margin bounds, again giving $∥ E ∥_{F} = O (δ)$ . If $L_{D} = 0$ , the local equation is linear. The remainders are therefore $O (δ^{2})$ , proving the first-order terms $- L_{c}^{- 1} Δ$ and $- L_{d}^{- 1} Δ$ .

2.2A2F3F4F6F9F10F12step 1.1algebra

Put $T_{X} = [I 0; X_{c} I]$ . Multiplying the Hamiltonian in [F4] on the right by $T_{X}$ and then on the left by $T_{X}^{- 1} = [I 0; - X_{c} I]$ , and using the CARE identity in [F3], gives $T_{X}^{- 1} H T_{X} = [\begin{array}{cc} A_{c} & - G \\ 0 & - A_{c}^{*} \end{array}] .$ The Sylvester map $S (Y) = - A_{c}^{*} Y - Y A_{c}$ has smallest singular value $σ = sep (- A_{c}^{*}, A_{c}) > 0$ : [F9] applies because $σ (- A_{c}^{*})$ lies in the right half-plane while $- σ (- A_{c}) = σ (A_{c})$ lies in the left half-plane; [F6] gives inverse norm $κ_{s} = 1 / σ$ . In the perturbed coordinates, write $Z = [Z_{i j}]$ and seek an invariant graph $[I; Y]$ . Its lower-block graph equation is $- A_{c}^{*} Y - Y A_{c} + Z_{21} + Z_{22} Y - Y Z_{11} + Y G Y - Y Z_{12} Y = 0.$ Hence $Y$ is a fixed point of $T (Y) = - S^{- 1} (Z_{21} + Z_{22} Y - Y Z_{11} + Y G Y - Y Z_{12} Y) .$ On the Frobenius ball $∥ Y ∥_{F} \leq 2 θ$ , each block norm of $Z$ is at most $ζ$ . The map norm is at most $κ_{s} [ζ + 2 ζ ∥ Y ∥_{F} + (∥ G ∥_{2} + ζ) ∥ Y ∥_{F}^{2}]$ , hence at most $θ + 4 θ^{2} + 4 μ θ^{2} + 4 θ^{3} \leq 2 θ$ under the displayed smallness condition. Its Lipschitz constant is at most $2 θ + 4 μ θ + 4 θ^{2} < 1$ . Completeness [F10] and iteration therefore give a unique fixed point in the ball. Returning through $T_{X}$ turns $[I; Y]$ into $[I; X_{c} + Y]$ , proving the graph bound. Under [A2], the restriction has $n$ stable eigenvalues and the perturbed matrix has exactly $n$ stable eigenvalues in total. In a basis beginning with this invariant graph, the perturbed matrix is block upper triangular with this stable restriction as its first diagonal block; the quotient block therefore has no stable eigenvalues. A stable generalized eigenvector must project to a stable generalized eigenvector of the quotient, which is impossible, so every stable generalized eigenspace lies in the graph. Both spaces have dimension $n$ , hence the graph is the stable spectral subspace.

3.1F4F5F12givenalgebra∎

Since ${\tilde{U}}_{1} = U_{1} + Δ U_{1} = U_{1} (I + U_{1}^{- 1} Δ U_{1})$ and $∥ U_{1}^{- 1} Δ U_{1} ∥_{2} < 1$ , the Neumann geometric series makes the second factor invertible and gives $∥ {\tilde{U}}_{1}^{- 1} ∥_{2} \leq (∥ U_{1}^{- 1} ∥_{2}^{- 1} - ∥ Δ U_{1} ∥_{2})^{- 1}$ . Using $U_{2} = X U_{1}$ , ${\tilde{U}}_{2} {\tilde{U}}_{1}^{- 1} - X = (Δ U_{2} - X Δ U_{1}) {\tilde{U}}_{1}^{- 1} .$ Submultiplicativity [F12] proves the displayed basis-chart bound. This derivation uses only the graph equation, so it applies to both the CARE invariant graph and the DARE deflating graph; it does not convert a pencil backward error into a deflating-subspace error.

5 · Examples, counterexamples and false statements

None yet.