Spectral aspects of symmetric matrix signings
Spectral aspects of symmetric matrix signings
复制标题
对称矩阵签名的频谱方面
DOI：
10.1016/j.disopt.2020.100582
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Kolla, Alexandra
中科院分区：
文献类型：
--
作者：
Carlson, Charles;Chandrasekaran, Karthekeyan;Chang, Hsien-Chih;Kakimura, Naonori;Kolla, Alexandra
符号矩阵的谱在社会科学、图论和控制理论中起着重要的作用。本文研究了具有自然谱性质的矩阵的对称符号识别的计算问题。我们的研究结果如下：1.我们刻画了具有可逆符号的矩阵：对称矩阵具有可逆对称符号当且仅当矩阵的支撑图包含完美2-匹配。此外，我们还提出了一个寻找可逆对称签名的有效算法.利用上述特征给出了一个算法，求出了一个对称矩阵的支持度的最小增量，使得它具有可逆的对称符号.我们证明了以下问题的NP-完全性：验证一个给定的矩阵是否有一个奇异的对角符号/有界特征值。然而，我们也说明了，输入矩阵的邻接矩阵的graphs.We使用组合技术，除了经典的结果匹配理论的复杂性可能会有很大的不同。
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 offindingsymmetric signings of matrices with natural spectral properties. Our results are the following:1. We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signingif and only ifthe support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing.2. We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing.3. We show NP-completeness of the following problems: verifying whether a given matrix has a symmetricoff-diagonalsigning that is singular/has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs.We use combinatorial techniques in addition to classic results from matching theory.