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

We study stability criteria for discrete time switching systems and provide a meta- theorem 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 encapsulates all the possible conditions, thus putting a conclusion to this research effort. As a corollary, we show that it is PSPACE-complete to recognize whether a particular set of LMIs implies the stability of a switching system.