Files in this item

FilesDescriptionFormat

application/pdf

application/pdfCARLSON-THESIS-2017.pdf (262kB)
(no description provided)PDF

Description

Title:Some results on symmetric signings
Author(s):Carlson, Charles A
Advisor(s):Kolla, Alexandra
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):matrix signings, spectral graph theory, eigenvalues, matchings, determinant
Abstract: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.
Issue Date:2017-07-17
Type:Thesis
URI:http://hdl.handle.net/2142/98401
Rights Information:Copyright 2017 Charles A. Carlson
Date Available in IDEALS:2017-09-29
Date Deposited:2017-08


This item appears in the following Collection(s)

Item Statistics