Generic pole assignability, structurally constrained controllers and unimodular completion

In this paper we assume dynamical systems are represented by linear differential-algebraic equations (DAEs) of order possibly higher than one. We consider a structured system of DAEs for both the to-be-controlled plant and the controller. We model the structure of the plant and the controller as an undirected and bipartite graph and formulate necessary and sufficient conditions on this graph for the structured controller to generically achieve arbitrary pole placement. A special case of this problem also gives new equivalent conditions for structural controllability of a plant. Use of results in matching theory, and in particular, ‘admissibility’ of edges and ‘elementary bipartite graphs’, make the problem and the solution very intuitive. Further, our approach requires standard graph algorithms to check the required conditions for generic arbitrary pole placement, thus helping in easily obtaining running time estimates for checking this. When applied to the state space case, for which the literature has running time estimates, our algorithm is faster for sparse state space systems and comparable for general state space systems.The solution to the above problem also provides a necessary and sufficient condition for the following matrix completion problem. Given a structured rectangular polynomial matrix, when can it be completed to a unimodular matrix such that the additional rows that are added during the completion process are constrained to have zeros at certain locations.