Some results on symmetric signings

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Carlson, Charles A

Contributors dc:contributor

• Kolla, Alexandra

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

Statement dc:rights

• Copyright 2017 Charles A. Carlson

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/98401

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/98401