Some results on symmetric signings

Matrix signings;Spectral graph theory;Eigenvalues;Matchings;Determinant

Carlson, Charles A ; Kolla ; Alexandra

关键词: Matrix signings;    Spectral graph theory;    Eigenvalues;    Matchings;    Determinant;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/98401/CARLSON-THESIS-2017.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In this work, we investigate several natural computational problems related to identifying symmetric signings of symmetric matrices with specific spectral properties. We show NP-completeness for verifying whether an arbitrary matrix has a symmetric signing that is positive semi-definite, is singular, or has bounded eigenvalues. We exhibit a stark contrast between invertibility and the above-mentioned spectral properties by presenting a combinatorial characterization of matrices with invertible symmetric signings and an efficient algorithm using this characterization to verify whether a given matrix has an invertible symmetric signing. Finally, we give efficient algorithms to verify and find invertible and singular symmetric signing for matrices whose support graph is bipartite.