TY - GEN
T1 - Spectral aspects of symmetric matrix signings
AU - Carlson, Charles
AU - Chandrasekaran, Karthekeyan
AU - Chang, Hsien Chih
AU - Kakimura, Naonori
AU - Kolla, Alexandra
N1 - Publisher Copyright:
© Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla.
PY - 2019/8
Y1 - 2019/8
N2 - 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. Our results are the following: 1. We characterize 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. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2. We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3. We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.
AB - 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. Our results are the following: 1. We characterize 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. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2. We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3. We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.
KW - Matchings
KW - Matrix Signing
KW - Spectral Graph Theory
UR - http://www.scopus.com/inward/record.url?scp=85071753068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85071753068&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2019.81
DO - 10.4230/LIPIcs.MFCS.2019.81
M3 - Conference contribution
AN - SCOPUS:85071753068
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
A2 - Katoen, Joost-Pieter
A2 - Heggernes, Pinar
A2 - Rossmanith, Peter
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
Y2 - 26 August 2019 through 30 August 2019
ER -