  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 $\leq d$, or (ii) a polytopic Lyapunov function with $\leq
d$ facets, or (iii) a piecewise quadratic Lyapunov function with $\leq 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 an extremal piecewise
algebraic Lyapunov function implies the finiteness property of the optimal
product, generalizing a result of Lagarias and Wang. As a corollary, we prove
that the finiteness property holds for sets of matrices with an extremal
Lyapunov function belonging to some of the most popular function classes in
controls.
