  The spectra of signed matrices have played a fundamental role in social
sciences, graph theory, and control theory. In this work, we investigate the
computational problems of identifying symmetric signings of matrices with
natural spectral properties. Our results are twofold:
  1. We show NP-completeness for the following three problems: verifying
whether a given matrix has a symmetric signing that is positive
semi-definite/singular/has bounded eigenvalues. However, we also illustrate
that the complexity could substantially differ for input matrices that are
adjacency matrices of graphs.
  2. We exhibit a stark contrast between invertibility and the above-mentioned
spectral properties: we show a combinatorial characterization of matrices with
invertible symmetric signings and design an efficient algorithm using this
characterization to verify whether a given matrix has an invertible symmetric
signing. Next, we give an efficient algorithm to solve the search problem of
finding an invertible symmetric signing for matrices whose support graph is
bipartite. We also provide a lower bound on the number of invertible symmetric
signed adjacency matrices. Finally, we give an efficient algorithm to find a
minimum increase in support of a given symmetric matrix so that it has an
invertible symmetric signing.
  We use combinatorial and spectral techniques in addition to classic results
from matching theory. Our combinatorial characterization of matrices with
invertible symmetric signings might be of independent interest.
