Split Certificates for Switched Systems: Polynomial Lyapunov Functions on a Few Critical Modes, Integral Bounds on the Rest

A switched system jumps among several linear dynamics, for example a recurrent layer whose transition matrix changes with every input token. Such a system can diverge even when every mode is stable on its own. The standard proof that it never diverges is a common Lyapunov function: one energy-like function that decreases under every mode. The cheapest version is a single quadratic, and it is often far too conservative. A recent control-theoretic analysis of Mamba with input-dependent transition matrices reports quadratic worst-case bounds that are looser than observed behaviour by roughly two orders of magnitude (A Control-Theoretic View of Mamba on Stability and Robustness). Polynomial sum-of-squares certificates remove this conservatism in principle. A polynomial is sum-of-squares (SOS) if it is a sum of squared polynomials, a property that can be checked with a semidefinite program. Converse theorems guarantee that any switched linear system stable under arbitrary switching has a common SOS Lyapunov function of some finite degree (Converse results on existence of sum of squares Lyapunov functions; Sum of Squares Certificates for Stability of Planar, Homogeneous, and Switched Systems). The catch is size: the semidefinite program grows like $\binom{n+d}{d}$, and the research file places the practical limit around state dimension 8 to 10.

This note proposes a way to spend high polynomial degree only where it is needed. In many switched families most directions contract quickly under every mode, and only a few near-marginal directions decide whether the system is stable. We split the state, in coordinates chosen to be the same for all modes, into a small critical block and a strongly contracting complement. The complement gets a cheap common quadratic certificate. Its effect on the critical block is written as a summed (discrete Volterra) memory term with a provable gain. The high-degree SOS search then runs only on the small critical block, perturbed by that bounded memory term. The splitting borrows its logic from Lyapunov-Schmidt reduction, a classical technique that solves the well-behaved part of a problem in terms of the few critical modes and keeps an exact equation for those modes. The difference is that we carry the remainder as an integral operator with an explicit bound instead of discarding it. The result is a certificate for the full system that scales with the number of critical modes rather than the full state dimension.

Core Claim

The joint spectral radius is the worst-case asymptotic growth rate over all switching sequences, and a system is stable under arbitrary switching exactly when it is below one. For discrete-time switched linear systems $x_{k+1} = A_{\sigma_k} x_k$ with $\sigma_k \in \{1,\dots,M\}$, the claim is as follows. When a common invariant-like splitting into an $m$-dimensional critical block and a uniformly contracting complement exists, a split certificate brings the joint-spectral-radius upper bound close to what full-dimensional SOS achieves. It does so at a semidefinite-program size governed by $m$ rather than $n$, and it continues to produce valid certificates at dimensions where full SOS cannot run.

The certificate is invariant to the choice of basis within each block, because the joint spectral radius is unchanged by a change of coordinates and the construction depends only on the two subspaces. When no such splitting exists, the method falls back to a quadratic certificate and should report this honestly. This fallback is the known spectral-gap requirement of Lyapunov-Schmidt reduction, and we treat it as a regime to measure rather than hide.

Concretely, choose an invertible change of coordinates $T$, shared by all modes, so that each mode in the new coordinates has block form with critical state $v \in \mathbb{R}^m$ and complement state $w \in \mathbb{R}^{n-m}$:

$$v_{k+1} = F_{\sigma_k} v_k + G_{\sigma_k} w_k, \qquad w_{k+1} = S_{\sigma_k} w_k + H_{\sigma_k} v_k .$$

Suppose a single quadratic norm makes every $S_i$ contract at rate $\rho_s<1$, which is a linear matrix inequality, or LMI, in $n-m$ variables. Solving the $w$ equation by discrete Duhamel summation expresses $w_k$ as a weighted sum of past critical states. The weights are the products of the $S$ blocks, and their norm decays like $\rho_s^{k-j}$. Substituting this sum makes the critical block a switched system with a memory input whose gain is at most $\gamma = \max_i\|G_i\|\,\max_i\|H_i\|/(1-\rho_s)$, measured in the certified norms.

The program then searches for a homogeneous SOS function $V$ on $\mathbb{R}^m$ that certifies decay rate $\rho_v$ for the critical modes together with a robustness margin $\kappa$ against that memory input. Stability of the full system follows from a small-gain condition of the form

$$\rho_v + \kappa\,\gamma < 1 .$$

The Lyapunov-Schmidt ingredient enters before this step. We do not treat $G_i w$ as pure disturbance. Instead we substitute the mode-wise quasi-static graph $w \approx (I-S_i)^{-1}H_i v$ into the critical dynamics, which gives the analogue of the reduced "bifurcation equation". Only the summed deviation from that graph is charged to $\gamma$. Under slow or correlated switching this deviation is driven only by changes between consecutive modes, which is where we expect the improvement over a naive block small-gain argument to come from.

Research Program

The first component is computing the shared splitting. For a single mode, the natural coordinates are the real Jordan form, which aligns state axes with eigenmodes. Bounded Verification with On-the-Fly Discrepancy Computation uses this form locally along simulated trajectories to stop Euclidean metrics from inflating reachable sets in oscillatory systems. We need one global splitting valid for all modes at once. We will compute it from the dominant invariant subspaces of an averaged generator (the mean of the $A_i$, or of $A_i^\top A_i$), refined by alternating minimisation of the coupling norms $\|G_i\|,\|H_i\|$ subject to the complement LMI.

This stays closer to convex optimisation than the similarity-transform search of Nonquadratic Stability Condition of Continuous Fuzzy Systems, which looks for a matrix $T$ making all fuzzy subsystems contract under a matrix measure. That search is non-convex and has no unified LMI procedure, and it applies one transformation to the full state. We use the transformation only to locate a split. The critical dimension $m$ is increased until the certificate succeeds or the SOS program becomes too large.

The second component is the integral bound. The idea of moving to an integral formulation follows Validated and Numerically Efficient Chebyshev Spectral Methods for Linear Ordinary Differential Equations, which turns differential equations into bounded integral operators so that contraction arguments become tractable. It also follows Green’s matching: an efficient approach to parameter estimation in complex dynamic systems, which uses Green's functions to avoid unstable differentiation. Here the kernel is not analytic. It is the product of switched complement blocks, and we only need a norm bound on it, which the complement LMI supplies.

The third component is the reduced SOS problem. It uses the Top Homogeneous Component (THC) reduction of Sum of Squares Certificates for Stability of Planar, Homogeneous, and Switched Systems, which imposes the SOS condition only on the highest-degree homogeneous terms. We add a dissipation-type constraint that yields $\kappa$.

The theoretical deliverables are two. The first is a soundness theorem for the composed certificate. The second is a converse-flavoured statement: if the full system has joint spectral radius below one and the coupling gain is small enough relative to the spectral gap, then a split certificate exists at some finite critical degree. This would connect to the existence results of Converse results on existence of sum of squares Lyapunov functions.

The closest structural precedent is Lyapunov Stability Analysis of a String Equation Coupled With an Ordinary Differential System. That paper augments a finite state with Legendre projections of an infinite-dimensional state and certifies stability with LMIs, but it truncates the projection, keeps a quadratic certificate, and assumes no switching. We keep the complement exactly through its integral bound and put polynomial degree on the critical part. The same paper's requirement of strictly positive damping is a constraint we share: without a spectral gap the splitting has no contracting complement. Coordinate-invariant incremental Lyapunov functions supplies the conceptual motivation, since stability notions should not depend on coordinates, but its converse theorems are non-constructive and assume convex inputs. Our construction is computational, and it handles discrete switching signals directly.

Baselines

The naive reference point is the common quadratic Lyapunov function computed by LMI on the full state (On Padé approximations, quadratic stability and discretization of switched linear systems). It is the cheapest certificate and the one used for input-dependent Mamba in A Control-Theoretic View of Mamba on Stability and Robustness. The only reported figure in the file is that paper's statement that quadratic worst-case bounds are looser than empirical behaviour by roughly two orders of magnitude, a factor of about 100. Beating this baseline means a substantially smaller ratio between the certified and the empirical error-growth constant on the same trained layers.

The strongest existing method is full-dimensional homogeneous SOS with THC reduction, following Sum of Squares Certificates for Stability of Planar, Homogeneous, and Switched Systems and Approximation of the joint spectral radius using sum of squares. The file contains no reported joint-spectral-radius numbers for these methods, so no reported result was found on Lacuna for SOS joint-spectral-radius bounds on standard instances. We will rerun it on identical systems with the same solver, the same wall-clock and memory budget, and the same maximum degree grid.

Beating full SOS means two things. Where it runs, our bound should be within a few percent of its bound at a fraction of the solve time. Above the dimension where it runs out of memory or time, ours should still produce valid bounds.

Two ablations isolate the key ingredients. The first removes the Lyapunov-Schmidt graph correction, treating $G_i w$ purely as disturbance in a plain block small-gain argument. The second replaces the computed shared splitting with an arbitrary coordinate split of the same size, which tests whether the coordinate alignment matters. A further ablation drops the polynomial degree on the critical block to quadratic, to test whether the polynomial degree on that block carries the gain.

Why not just…?

Why not just run full SOS at higher degree? On small systems this is the real threat. The converse theorems say it will eventually succeed, and our method can at best tie it. The file's own limitation is scaling: semidefinite-program size grows as $\binom{n+d}{d}$ and becomes impractical past dimensions of about 8 to 10. The dimension sweep in the experiments will show where full SOS fails and whether the split certificate stays tight beyond that point. If our bound is noticeably worse than full SOS wherever both run, the claim fails.

Why not just reduce the model first, for example by balanced truncation, and certify the reduced system? Theoretical analysis of balanced truncation for linear switched systems studies such reductions, but certifying a truncated model does not certify the original. The discarded states can destabilise the full system under switching. Our remainder term is exactly what makes the reduction a proof. We will include "truncate then SOS" as a diagnostic and count how often it declares stable a system whose lower bound from long switching products shows instability.

Why not just use mode-dependent or piecewise quadratic functions? Stability of switched linear systems under dwell time switching with piece wise quadratic functions shows these work when switching respects a minimum dwell time. Token-driven layers and our arbitrary-switching question do not grant a dwell time, so these functions answer a different question. We will report them only in a dwell-time side experiment.

Proposed Experiments

The first testbed is synthetic switched linear families with controlled structure. Each family has $M$ modes, total dimension $n$ from 4 to 64, a planted critical block of dimension $m$ from 1 to 4, a tunable spectral gap, and a tunable coupling strength. Ground truth comes from lower bounds on the joint spectral radius computed from long switching products. The primary metric is the ratio of the certified upper bound to this lower bound. Secondary metrics are solve time, memory, and the largest dimension certified.

The second testbed is input-dependent transition layers of the kind analysed in A Control-Theoretic View of Mamba on Stability and Robustness. We will train small selective state-space layers whose transition matrix depends on the input, then extract a finite family of discretised modes from sampled tokens. On these we compare certified against empirical error-growth constants. Success means closing a substantial part of the reported factor-of-100 gap without simply invoking diagonal structure.

The decisive checks are three. The split certificate must match full SOS within a small tolerance wherever full SOS completes. It must keep its advantage when the spectral gap is large and degrade toward the quadratic baseline as the gap closes, which is the predicted failure regime. And the graph-corrected version must beat plain block small-gain mainly under correlated or slow switching, where consecutive modes differ little. If the advantage instead appears equally under adversarial fast switching, our explanation of where the gain comes from is wrong, and we will say so.