2026-09-20T00:30:27Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/98401 2023-07-11 col_2142_10761 col_2142_5131 com_2142_10755 com_2142_234 com_2142_5130

Kolla, Alexandra Carlson, Charles A 2017-09-29T17:56:57Z 2017-09-29T17:56:57Z 2017-07-17 2017-08 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. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms The student, Charles Carlson, accepted the attached license on 2017-07-14 at 15:07. The student, Charles Carlson, submitted this Thesis for approval on 2017-07-14 at 15:14. This Thesis was approved for publication on 2017-07-17 at 08:50. DSpace SAF Submission Ingestion Package generated from Vireo submission #11474 on 2017-09-29 at 11:30:54 Made available in DSpace on 2017-09-29T17:56:57Z (GMT). No. of bitstreams: 2 CARLSON-THESIS-2017.pdf: 261724 bytes, checksum: 73e742c3412743ba3088d657c33a68f5 (MD5) LICENSE.txt: 4212 bytes, checksum: 49a5937d9204afd49a345dde3f2cd9ab (MD5) Previous issue date: 2017-07-17 application/pdf http://hdl.handle.net/2142/98401 en Copyright 2017 Charles A. Carlson Matrix signings Spectral graph theory Eigenvalues Matchings Determinant Some results on symmetric signings text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.