On complexity of Lyapunov functions for switched linear systems

We show that for any positive integer d, there are families of switched linear systems-in fixed dimension and defined by two matrices only-that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree ≥ d, or (ii) a polytopic Lyapunov function with ≥ d facets, or (iii) a piecewise quadratic Lyapunov function with ≥ d pieces. This implies that there cannot be an upper bound on the size of the linear and semidefinite programs that search for such stability certificates. Several constructive and non-constructive arguments are presented which connect our problem to known (and rather classical) results in the literature regarding the finiteness conjecture, undecidability, and non-algebraicity of the joint spectral radius. In particular, we show that existence of a sum of squares Lyapunov function implies the finiteness property of the optimal product.