Sparse matrix spaces

This thesis addresses theoretical questions that arise in the design and control of decentralized multi-agent systems. These systems are characterized by their communication, or network, topology, which indicates which agents a given agent can communicate with. An important problem, which occurs for example in information transmission and distributed computations, is the design of a control system based on a given network topology. In this work, we study the following related question: for a specified network topology, can one find a set of interaction laws that yield stable dynamics for the ensemble of agents? We restrict our analysis to systems with strictly linear dynamics. In mathematical terms, we consider vector spaces of real square matrices for which every entry is either fixed at zero, or an arbitrary real number. We call them sparse matrix spaces, abbreviated SMS, and examine under what conditions they contain matrices for which all eigenvalues have strictly negative real parts. We call an SMS with this property stable. We start by reviewing the necessary background from control theory and graph theory. Then we discuss some general results related to sparse matrix spaces, and then focus on SMSs which have symmetric structure, that is, all fixed at zero entries are symmetric with respect to the main diagonal. Using graph theory techniques, we derive necessary and sufficient conditions which determine whether a given symmetric SMS is stable. Finally, we present a result by Lin (1974), in which the author considers pairs of sparse matrix spaces and studies under what conditions one can find two matrices in them, which form a controllable pair