English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The spectra of signed matrices have played a fundamental role in socialsciences, graph theory, and control theory. In this work, we investigate thecomputational problems of identifying symmetric signings of matrices withnatural spectral properties. Our results are twofold:  1. We show NP-completeness for the following three problems: verifyingwhether a given matrix has a symmetric signing that is positivesemi-definite/singular/has bounded eigenvalues. However, we also illustratethat the complexity could substantially differ for input matrices that areadjacency matrices of graphs.  2. We exhibit a stark contrast between invertibility and the above-mentionedspectral properties: we show a combinatorial characterization of matrices withinvertible symmetric signings and design an efficient algorithm using thischaracterization to verify whether a given matrix has an invertible symmetricsigning. Next, we give an efficient algorithm to solve the search problem offinding an invertible symmetric signing for matrices whose support graph isbipartite. We also provide a lower bound on the number of invertible symmetricsigned adjacency matrices. Finally, we give an efficient algorithm to find aminimum increase in support of a given symmetric matrix so that it has aninvertible symmetric signing.  We use combinatorial and spectral techniques in addition to classic resultsfrom matching theory. Our combinatorial characterization of matrices withinvertible symmetric signings might be of independent interest.

Invertibility and Largest Eigenvalue of Symmetric Matrix Signings