When is a set of LMIs a sufficient condition for stability?

We study stability criteria for discrete time switching systems and provide a metatheorem that characterizes all the LMI-based Lyapunov theorems.For this purpose, we investigate the structure of sets of LMIs that are a sufficient condition for stability (i.e., such that any switching system which satisfies these LMIs is stable). Different such LMI conditions have been proposed in the last fifteen years, and we prove in this paper that a family of conditions recently provided by us actually encapsulates all the possible valid conditions.As a byproduct, we show that it is PSPACE-complete to recognize whether a particular set of LMIs implies the stability of a switching system.