Spectral aspects of symmetric matrix signings

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
EditorsJoost-Pieter Katoen, Pinar Heggernes, Peter Rossmanith
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771177
DOIs
StatePublished - Aug 2019
Event44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 - Aachen, Germany
Duration: Aug 26 2019Aug 30 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume138
ISSN (Print)1868-8969

Conference

Conference44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
CountryGermany
CityAachen
Period8/26/198/30/19

Fingerprint

Social sciences
Graph theory
Control theory

Keywords

  • Matchings
  • Matrix Signing
  • Spectral Graph Theory

ASJC Scopus subject areas

  • Software

Cite this

Carlson, C., Chandrasekaran, K., Chang, H. C., Kakimura, N., & Kolla, A. (2019). Spectral aspects of symmetric matrix signings. In J-P. Katoen, P. Heggernes, & P. Rossmanith (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 [81] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 138). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2019.81

Spectral aspects of symmetric matrix signings. / Carlson, Charles; Chandrasekaran, Karthekeyan; Chang, Hsien Chih; Kakimura, Naonori; Kolla, Alexandra.

44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. ed. / Joost-Pieter Katoen; Pinar Heggernes; Peter Rossmanith. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 81 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 138).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Carlson, C, Chandrasekaran, K, Chang, HC, Kakimura, N & Kolla, A 2019, Spectral aspects of symmetric matrix signings. in J-P Katoen, P Heggernes & P Rossmanith (eds), 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019., 81, Leibniz International Proceedings in Informatics, LIPIcs, vol. 138, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, 8/26/19. https://doi.org/10.4230/LIPIcs.MFCS.2019.81
Carlson C, Chandrasekaran K, Chang HC, Kakimura N, Kolla A. Spectral aspects of symmetric matrix signings. In Katoen J-P, Heggernes P, Rossmanith P, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 81. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.MFCS.2019.81
Carlson, Charles ; Chandrasekaran, Karthekeyan ; Chang, Hsien Chih ; Kakimura, Naonori ; Kolla, Alexandra. / Spectral aspects of symmetric matrix signings. 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019. editor / Joost-Pieter Katoen ; Pinar Heggernes ; Peter Rossmanith. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs).
@inproceedings{6a4a4cdeaae443d49b28d42641a7cc80,
title = "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 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.",
keywords = "Matchings, Matrix Signing, Spectral Graph Theory",
author = "Charles Carlson and Karthekeyan Chandrasekaran and Chang, {Hsien Chih} and Naonori Kakimura and Alexandra Kolla",
year = "2019",
month = "8",
doi = "10.4230/LIPIcs.MFCS.2019.81",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Joost-Pieter Katoen and Pinar Heggernes and Peter Rossmanith",
booktitle = "44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019",

}

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

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

ER -