{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/98401"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/98401","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Some results on symmetric signings","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Carlson, Charles A"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kolla, Alexandra"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-09-29T17:56:57Z","date_published":"2017-09-29T17:56:57Z","updated_at":"2026-07-22T22:24:35Z","subjects":["Matrix signings","Spectral graph theory","Eigenvalues","Matchings","Determinant"],"languages":["en"],"rights":["Copyright 2017 Charles A. Carlson"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/98401","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kolla, Alexandra"]},{"key":"dc:creator","label":"Author","values":["Carlson, Charles A"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-09-29T17:56:57Z","2017-07-17","2017-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Matrix signings","Spectral graph theory","Eigenvalues","Matchings","Determinant"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Charles A. Carlson"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/98401"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Some results on symmetric signings"]}]}],"canonical_facts":{"dc:contributor":["Kolla, Alexandra"],"dc:creator":["Carlson, Charles A"],"dc:date":["2017-09-29T17:56:57Z","2017-07-17","2017-08"],"dc:description":["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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/98401"],"dc:language":["en"],"dc:rights":["Copyright 2017 Charles A. Carlson"],"dc:subject":["Matrix signings","Spectral graph theory","Eigenvalues","Matchings","Determinant"],"dc:title":["Some results on symmetric signings"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:35Z"}