CS Paper Radar

A kernel proof of the De Cock-De Moor Lyapunov identity

Jonas Gillberg, Johan Löfberg

eess.SY math.OC ·submitted 2026-08-25 11:07 UTC · v1
theoryunusual

Abstract

We prove the rank-one Lyapunov spectral identity recorded as Problem 9.1 in the 2004 collection of unsolved problems in mathematical systems and control theory. Let $P,Q,R$ solve the coupled discrete Lyapunov and Sylvester equations associated with $A$ and its rank-one update $A_2=A+vw^\top$. When the displayed inverses exist, we show that $P^{-1}RQ^{-1}R^\top$ and $(I+PQ)^{-1}$ have the same characteristic polynomial. A rank-one determinant factorization of the equation for $Q$ produces a scalar bilinear kernel. Evaluating it at the eigenvalues of $A$ and at their reciprocals gives $RQ^{-1}R^\top=BQ^{-1}B=P-BPB$, after which the two target matrices are the same two factors in opposite order. Polynomial continuation extends the identity from a nonempty open set of admissible systems to the full admissible domain and yields a determinant corollary without stability assumptions; when the spectra of $A$ and $A_2$ are disjoint, $Z=b(A)^{-1}P$ gives an explicit similarity. In the Schur-stable realization setting, the result recovers the associated principal-angle and past/future canonical-correlation spectra.

Comment
13 pages, 3 figures. Submitted to Automatica

Closest papers

Nearest neighbours by meaning across the whole index.

The De Cock--De Moor Conjecture: Proof, Normal Form, and Indefinite Angles

eess.SY math.OC ·2026-08-30 ·Jeffrey Humpherys
theory similarity 0.68
Abstract

De Cock and De Moor conjectured that two matrices built from the solutions of three coupled Lyapunov equations always share their eigenvalues, an identity linking principal angles between model subspaces with the canonical correlations between the past and future of a stochastic process. The conjecture was recorded as Problem 9.1 of \emph{Unsolved Problems in Mathematical Systems and Control Theory}. We prove it under the natural nonresonance condition, without stability or diagonalizability, and show that the two matrices are similar. The proof exposes a Cauchy-matrix structure created by the rank-one perturbation and reduces the problem to rational interpolation, and the main theorem has also been verified in the Lean~4 proof assistant. The same structure gives a normal form that depends only on the poles and zeros of the model. Off the stable set the eigenvalues become squared cosines of angles in an indefinite metric. We prove an inertia theorem for them and show that reflecting a pole or a zero across the unit circle acts on the angles by a principal pivot transform. For several inputs and outputs, where the conjecture fails, we identify the subspaces whose angles do give the canonical correlations. We also relate our approach to the independent proof of Gillberg and Löfberg.

0.21

Elementwise Positivity of the Solution to Lyapunov Equation for Hurwitz Companion Matrices

eess.SY ·2026-09-10 ·Miaomiao Wang, Patrizio Colaneri, Jie Chen
theory similarity 0.64
Abstract · 7 pages

We prove, with the aid of AI, that for every real symmetric forcing matrix $Q\succeq0$, the unique solution of a continuous-time Lyapunov equation is entrywise nonnegative whenever the state matrix is a real Hurwitz companion matrix. This proves an earlier conjecture. The proof makes no assumption on the spectrum of the state matrix, and is made possible by means of using Horner polynomial matrices. We also show that discrete-time counterpart of the conjecture is false: Counterexamples can be readily constructed to show that Schur companion matrices, including one generated by a polynomial with all positive coefficients, yield solutions with negative off-diagonal entries even with identity forcing.

0.22

A Duality Reformulation of the Companion-Matrix Lyapunov Problem

eess.SY math.OC ·2026-09-11 ·Augusto Ferrante
theory similarity 0.62
Abstract

We study the relation between positive semidefiniteness and entrywise nonnegativity for solutions of continuous-time Lyapunov equations. For a real Hurwitz matrix $A$, we show that the solution of $AP+PA^\top=-Q$ is positive semidefinite for every symmetric entrywise nonnegative $Q$ if and only if the solution of $A^\top X+XA=-R$ is entrywise nonnegative for every positive semidefinite $R$. This equivalence follows from the adjointness of the two solution operators and extends to all real unmixed matrices. We then prove that both properties hold for every real Hurwitz companion matrix, settling a conjecture previously established under the additional assumption of a real spectrum. The proof combines a controllability-Gramian normalization with a pairwise positivity theorem for the coefficients of the adjugate polynomial of a real accretive matrix. The latter is obtained from a coefficient-sign property of bivariate polynomials, an auxiliary determinant that does not vanish on the product of two open right half-planes, and a rank-one perturbation argument. Covariance and energy interpretations connect these results with dissipative realizations, damped second-order systems, and comparisons between input Gramians.

0.32

Riccati Stability Without Auxiliary Matrices

eess.SY math.OCmath.FAmath.SP ·2026-09-05 ·Jeffrey Humpherys
similarity 0.57
Abstract

In the 2004 collection \emph{Unsolved Problems in Mathematical Systems and Control Theory}, Erik Verriest posed the problem of characterizing Riccati stability ``without invoking additional matrices.'' We give such a characterization through a scalar invariant of the resolvent family. The invariant is defined by covariance balances using at most $n^2+1$ frequency--direction pairs. A finite-dimensional separation argument shows that this covariance radius equals the optimal common ellipsoidal norm of the resolvent family. Combined with the strict bounded real lemma, this yields a necessary and sufficient condition for Riccati stability involving only the Hurwitz property of the first matrix and a single scalar inequality. The invariant reduces to the ordinary spectral radius for one matrix, lies between the pointwise spectral-radius and unscaled small-gain levels of the resolvent family, and coincides with the operator-space spectral radius of Shalit and Shamovich for the natural resolvent function space. The main results have been formally verified in the Lean proof assistant.

0.19

Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

cs.CC quant-pheess.SYmath.OC ·2026-11-09 ·Mohamed Serry, Jun Liu
theory similarity 0.55
Abstract

Fundamental tasks in linear systems analysis and control require evaluating infinite-horizon output energies for autonomous systems and optimal value functions for controlled systems. These quantities are characterized by Lyapunov and algebraic Riccati equations, respectively. In this work, we study promise problems for their evaluation when the system matrices are sparse and represented succinctly by Boolean circuits specifying their nonzero entries, with input length polynomial in the logarithm of the system dimension. For dissipative autonomous systems with coordinate-vector initial states, we define the succinct Lyapunov value problem (SLV). Its extension to linear-quadratic optimal control is the succinct LQR value problem (SLQRV). We prove that SLV is $\BQP$-hard: every problem in bounded-error quantum polynomial time ($\BQP$) reduces to it in polynomial time. We then establish that the more general SLQRV problem admits a quantum algorithm running in time polynomial in the succinct input length. Since SLV is a special case of SLQRV, both problems are $\BQP$-complete. Consequently, unless bounded-error probabilistic polynomial time coincides with $\BQP$, no classical randomized algorithm can solve either problem on all promised instances in time polynomial in the succinct input length.

0.28

Optimizing Lyapunov Certificates via Stability-Preserving Quadratization for Polynomial Systems

cs.SC math.OCeess.SY ·2026-09-16 ·Yubo Cai, Gioele Zardini
benchmark similarity 0.53
Abstract · 43 pages, 4 figures, 7 tables; includes appendices

Region-of-attraction (ROA) certificates for polynomial systems become expensive as state dimension and degree grow: direct sum-of-squares (SOS) formulations require combinatorially growing monomial bases. Quadratization represents a polynomial vector field exactly on an invariant manifold of a quadratic system, allowing a quadratic Lyapunov function to certify the ROA. For a fixed lift, stabilizer gains shape the off-manifold extension and transverse dynamics, while representation gauges change the matrix representation but not the vector field. Both affect the spectral-norm certificate, yet prior work fixes the gain by a feasibility heuristic before optimizing the gauge. We formulate optimal dissipative quadratization (ODQ), jointly designing gains and gauges for a fixed monomial lift, reference extension, stabilizer factorization, and Lyapunov weight $Q=I$. Gains lie in a prescribed compact Hurwitz box. At each gain, an exact semidefinite program globally minimizes the spectral-norm bound over the gauge. Residual-aware bounds yield a certified closed Lyapunov sublevel set, accounting for the floating-point Lyapunov residual. Under our stated assumptions, every accumulation point of the idealized outer search is box-Clarke stationary. A finite run returns the best independently verified candidate; global optimality of the gain search is not claimed. On a planar quintic, optimizing the gain increases the certified area by a factor of $2.238$ over a matched zero-gain gauge. Across 16 heterogeneous polynomial systems with stabilizer freedom, ODQ improves on both fixed-gain lifted baselines. All 36 ODQ runs on the relay benchmark complete, and all 27 repeat-level comparisons across nine fully paired cases favor ODQ over an SOS baseline with a fixed quadratic Lyapunov function in both the fixed-direction proxy and construction time. Broader comparisons with direct SOS methods remain mixed.

0.28

On the positive semidefinteness of a class of Hermitian Cauchy-like matrices

eess.SY math.RA ·2026-09-18 ·Augusto Ferrante
theory similarity 0.53
Abstract

We establish the positive semidefiniteness of a class of Hermitian Cauchy-like matrices associated with real Hurwitz polynomials having distinct zeros. Writing the zeros as $-λ_1,\ldots,-λ_n$, the matrix entries are defined through ratios of elementary symmetric polynomials in the variables $λ_i$. The result extends an earlier positivity theorem obtained under the assumption that all zeros are real. We first show that the coefficients appearing in the denominators are nonzero, so that the matrices are well defined. We then construct an explicit congruence between each matrix and the solution of a Lyapunov equation whose state matrix is in companion form. Positive semidefiniteness follows from a recent result on such equations with entrywise nonnegative right-hand-side data. This approach establishes the extension to complex zeros through the connection between structured matrices and Lyapunov equations.

0.09

Controllability of polynomial systems is undecidable and not recursively enumerable

cs.CC math.OCeess.SY ·2026-10-19 ·Jun Liu, Ivan O. Shevchenko
theory similarity 0.51
Abstract

Sontag conjectured in 1988 that global controllability of polynomial control systems with rational coefficients is undecidable, but that the controllable systems form a recursively enumerable set. We prove the first part of the conjecture and disprove the second. For every homogeneous polynomial vector field $F$ of odd degree with rational coefficients, we construct an explicit polynomial control system $Σ_F$, with one more state than $F$, that is globally controllable if and only if the origin is \emph{not} globally asymptotically stable for $\dot x=F(x)$. By a recent result, the homogeneous polynomial vector fields with a globally asymptotically stable origin form a set that is recursively enumerable but not decidable. Consequently, global controllability of polynomial systems is undecidable, and the controllable polynomial systems are not recursively enumerable. The same conclusions hold for systems of the form $\dotξ=f(ξ)+Bu$ with a polynomial drift and a constant input matrix.

0.27