Carlson, Charles ;
Chandrasekaran, Karthekeyan ;
Chang, HsienChih ;
Kakimura, Naonori ;
Kolla, Alexandra
Spectral Aspects of Symmetric Matrix Signings
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. 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 2matching. Further, we present an efficient algorithm to search for an invertible symmetric signing.
2) We use the abovementioned 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 NPcompleteness 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.
BibTeX  Entry
@InProceedings{carlson_et_al:LIPIcs:2019:11025,
author = {Charles Carlson and Karthekeyan Chandrasekaran and HsienChih Chang and Naonori Kakimura and Alexandra Kolla},
title = {{Spectral Aspects of Symmetric Matrix Signings}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {81:181:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11025},
URN = {urn:nbn:de:0030drops110258},
doi = {10.4230/LIPIcs.MFCS.2019.81},
annote = {Keywords: Spectral Graph Theory, Matrix Signing, Matchings}
}
20.08.2019
Keywords: 

Spectral Graph Theory, Matrix Signing, Matchings 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 