Input matrix construction and approximation using a graphic approach

Given a state transition matrix (STM), we reinvestigate the problem of constructing the sparsest input matrix with a fixed number of inputs to guarantee controllability of the associated system. A new and simple graph-theoretic characterisation is obtained for the sparsity pattern of input matrices to guarantee controllability for a general STM admitting multiple eigenvalues, and a deterministic procedure with polynomial time complexity is suggested for constructing real valued input matrices satisfying the controllability requirement with an arbitrarily prescribed sparsity pattern. Based on this criterion, some novel results on sparsely controlling a system are obtained. It is proven that the minimal number of inputs to guarantee controllability equals the maximum geometric multiplicity of the STM under the constraint that some states can not be directly actuated by inputs (provided such problem is feasible), extending the existing results. Moreover, the minimal sparsity of an input matrix to ensure system controllability can be affected by the number of independent inputs. Furthermore, a graphic submodular function is built, leading to a greedy algorithm which efficiently approximates the minimal states needed to be directly actuated by inputs to ensure controllability for general STMs. To approximate the sparsest input matrices with a fixed number of inputs, we propose a simple greedy algorithm (non-submodular) and a two-stage algorithm, and demonstrate that the latter algorithm, inspired from graph colouring, has a provable approximation guarantee. Finally, we present some numerical results to show the efficiency and effectiveness of our approaches.