Abstract
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. In this talk, I will present two main results:
1. A characterization of matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Furthermore, there is an efficient algorithm to search for an invertible symmetric signing. I will discuss connections between this result and constructive proofs for Alon’s Combinatorial Nullstellensatz.
2. NP-completeness of the following three problems: verifying whether a given matrix has a symmetric signing that is positive semi-definite/singular/has bounded eigenvalues. I will discuss connections between those problems and constructing Ramanujan expanders via graph lifts.
Joint with Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura.