TY - JOUR

T1 - Spectral aspects of symmetric matrix signings

AU - Carlson, Charles

AU - Chandrasekaran, Karthekeyan

AU - Chang, Hsien Chih

AU - Kakimura, Naonori

AU - Kolla, Alexandra

N1 - Funding Information:
Supported by National Science Foundation, USACCF 18-14613.Partly supported by JSPS KAKENHI Grant Numbers JP17K00028 and JP18H05291.Supported by National Science Foundation, USACCF 18-55919.
Publisher Copyright:
© 2020 Elsevier B.V.

PY - 2020/8

Y1 - 2020/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 off-diagonal signing that is singular/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 off-diagonal signing that is singular/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=85083886768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083886768&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2020.100582

DO - 10.1016/j.disopt.2020.100582

M3 - Article

AN - SCOPUS:85083886768

SN - 1572-5286

VL - 37

JO - Discrete Optimization

JF - Discrete Optimization

M1 - 100582

ER -