2012/06/10 by Nikos Vlassis, Vlassis, Nikos
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #graph theory and CDMA systems #information engineering
paper · pdf · doi:10.48550/arxiv.1206.2059
openalex publication_date 2012/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note we prove NP-hardness of the following problem: Given a set of matrices, is there a convex combination of those that is a nonsingular M-matrix? Via known characterizations of M-matrices, our result establishes NP-hardness of several fundamental problems in systems analysis and control, such as testing the instability of an uncertain dynamical system, and minimizing the spectral radius of an affine matrix function.