License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.81
URN: urn:nbn:de:0030-drops-110258
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11025/
Go to the corresponding LIPIcs Volume Portal

Carlson, Charles ; Chandrasekaran, Karthekeyan ; Chang, Hsien-Chih ; Kakimura, Naonori ; Kolla, Alexandra

Spectral Aspects of Symmetric Matrix Signings

pdf-format:
LIPIcs-MFCS-2019-81.pdf (0.5 MB)

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 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.

BibTeX - Entry

@InProceedings{carlson_et_al:LIPIcs:2019:11025,
  author =	{Charles Carlson and Karthekeyan Chandrasekaran and Hsien-Chih 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:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11025},
  URN =		{urn:nbn:de:0030-drops-110258},
  doi =		{10.4230/LIPIcs.MFCS.2019.81},
  annote =	{Keywords: Spectral Graph Theory, Matrix Signing, Matchings}
}

Keywords: Spectral Graph Theory, Matrix Signing, Matchings
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI